Solve path normalization and nested iterator
Company: Bridge
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
1) Normalize Unix-style absolute paths: Given a string representing an absolute Unix file path, return its canonical form. Rules: '.' refers to the current directory, '..' moves one directory up (ignore if already at root), multiple consecutive slashes are treated as a single slash, and no trailing slash should appear in the result except for the root '/'. Implement normalizePath(path: string) and explain your algorithm, time complexity, and space complexity.
2) Implement a nested-list iterator: Given a nested collection containing integers and lists (which themselves may contain integers or lists arbitrarily), design an iterator that outputs the integers from left to right. Implement hasNext() and next() with a lazy approach that uses a stack to avoid flattening everything up front; optionally discuss an eager alternative. Analyze time and space complexity and compare the trade-offs between the two designs.
Quick Answer: This question evaluates proficiency in string/path normalization, manipulation of hierarchical data structures, stack-based iterator design, lazy versus eager flattening strategies, and algorithmic time/space complexity analysis in the Coding & Algorithms domain.
Normalize Unix-Style Absolute Path
Given a string `path` representing an absolute Unix-style file path, return its simplified canonical form.
Rules:
- A single period `.` refers to the current directory and is ignored.
- A double period `..` moves up one directory; if already at the root, it is ignored.
- Multiple consecutive slashes `//` are treated as a single slash `/`.
- The canonical path must start with a single `/` and must not have a trailing `/`, except the root which is just `/`.
The input always starts with `/` (it is an absolute path).
Examples:
- `/home/` -> `/home`
- `/../` -> `/`
- `/home//foo/` -> `/home/foo`
- `/a/./b/../../c/` -> `/c`
Constraints
- 1 <= path.length
- path consists of English letters, digits, '.', '/' and '_'
- path is an absolute Unix path that begins with '/'
Examples
Input: ('/home/',)
Expected Output: '/home'
Explanation: Trailing slash is removed.
Input: ('/../',)
Expected Output: '/'
Explanation: '..' at the root is ignored, leaving the root '/'.
Hints
- Split the string on '/'. Empty strings (from '//' or leading/trailing slashes) and '.' can be skipped entirely.
- Use a stack of directory names. On '..', pop one entry if the stack is non-empty (this naturally handles '..' at root by doing nothing).
- Rebuild the answer as '/' + '/'.join(stack); an empty stack yields the root '/'.
Flatten a Nested List Iterator
You are given a nested list of integers `nestedList`. Each element is either an integer or a list whose elements may themselves be integers or lists, nested arbitrarily deep.
Implement an iterator that returns the integers in left-to-right order via `hasNext()` and `next()`, using a lazy stack-based design that does not flatten the entire structure up front. For this challenge, write a function that drains such an iterator and returns the full sequence of integers as a flat list (the grader compares this flattened output).
Example:
- `[[1,1],2,[1,1]]` -> `[1, 1, 2, 1, 1]`
- `[1,[4,[6]]]` -> `[1, 4, 6]`
Discuss the lazy (stack) approach versus an eager pre-flattening approach: the lazy design defers work and keeps O(depth + width-at-top) extra space, while the eager design pays O(total integers) space and full traversal cost in the constructor.
Constraints
- 0 <= total number of integers
- Each leaf value fits in a 32-bit signed integer
- Nesting may be arbitrarily deep but is finite
Examples
Input: ([[1, 1], 2, [1, 1]],)
Expected Output: [1, 1, 2, 1, 1]
Explanation: Left-to-right flattening of two sublists around a bare integer.
Input: ([1, [4, [6]]],)
Expected Output: [1, 4, 6]
Explanation: Deeper nesting: 6 lives two levels down but still emits in order.
Hints
- Push the top-level elements onto a stack in reverse order so the leftmost element ends up on top.
- Before answering hasNext(), repeatedly pop any list on top of the stack and push its children in reverse order until an integer surfaces (this is the lazy part).
- next() simply pops the now-guaranteed integer. Compared to eager flattening, this avoids touching elements you never iterate to and uses space proportional to depth, not to the total count.