How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Bridge.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Bridge during technical interviews.

Solve path normalization and nested iterator

Quick Overview

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.

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 '/'.

Input: ('/home//foo/',)

Expected Output: '/home/foo'

Explanation: The double slash collapses to a single separator and the trailing slash is dropped.

Input: ('/a/./b/../../c/',)

Expected Output: '/c'

Explanation: '.' is skipped, 'b' is popped by the first '..', 'a' is popped by the second '..', leaving '/c'.

Input: ('/',)

Expected Output: '/'

Explanation: The root path is already canonical.

Input: ('/a/../../b/../c//.//',)

Expected Output: '/c'

Explanation: 'a' is popped, the extra '..' at root is ignored, 'b' is popped, leaving '/c'.

Input: ('/...',)

Expected Output: '/...'

Explanation: '...' is a valid directory name (not '.' or '..'), so it is kept.

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.

Input: ([],)

Expected Output: []

Explanation: Empty input yields no integers.

Input: ([[]],)

Expected Output: []

Explanation: A single empty sublist contains no integers.

Input: ([[], [], []],)

Expected Output: []

Explanation: Several empty sublists still produce nothing.

Input: ([5],)

Expected Output: [5]

Explanation: Single integer.

Input: ([[[[7]]], 8, [[-3, 0]]],)

Expected Output: [7, 8, -3, 0]

Explanation: Mix of deep nesting, negatives and zero, preserved in order.

Input: ([1, [], 2, [[], [3]], 4],)

Expected Output: [1, 2, 3, 4]

Explanation: Empty sublists are skipped lazily while real integers emit 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.

Quick Overview