Design a nested-list iterator
Company: Adobe
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Technical Screen
You are given a nested structure that can contain integers or further lists. Design an iterator over this structure that returns integers in left-to-right order without pre-flattening the entire input. Implement a class NestedIterator with: constructor(nestedList), boolean hasNext(), and int next(). The iterator must use O(d) extra space where d is the maximum nesting depth, and hasNext()/next() should be amortized O(
1). Avoid recursion by using an explicit stack of iterators or indexes. Additionally, implement a recursive pre-flattening approach, compare both methods in time and space complexity, and discuss edge cases such as empty lists, deeply nested empty lists, and integer bounds.
Quick Answer: This question evaluates the ability to implement an efficient iterator over nested lists, testing skills in iterator state management, lazy traversal, explicit stack usage, and algorithmic complexity reasoning.
Return integers from a nested list in left-to-right order, equivalent to a lazy NestedIterator traversal.
Constraints
- Inputs are Python literals matching the function signature.
- Return a deterministic exact-match value.
Examples
Input: ([1,[2,[3]],4],)
Expected Output: [1, 2, 3, 4]
Explanation: Nested integers.
Input: ([[],[1,[]],2],)
Expected Output: [1, 2]
Explanation: Empty nested lists.
Input: ([],)
Expected Output: []
Explanation: Empty input.
Hints
- Model object-style prompts as arrays or operation streams when needed.
- Handle empty and boundary cases before the main logic.