Implement a Removable Nested-List Iterator

Question

Implement an iterator that flattens a nested list structure, allowing for the removal of elements during iteration.

Codemia · Accepted Answer

We need to implement a nested list iterator that can traverse a list containing integers and other nested lists. The iterator should support the methods `next()` to get the next integer and `remove()` to remove the last returned integer from the iteration.

The iterator will maintain a stack to keep track of the current position in the nested list. This stack will allow us to backtrack when we encounter nested lists. We will also maintain a reference to the last returned item to facilitate the removal operation.

The main methods to implement are `__init__()`, `next()`, and `remove()`. In `__init__()`, we initialize our stack with the input nested list. In `next()`, we pop elements from the stack until we find an integer, which we return. The `remove()` method will use a reference to the last returned integer to remove it from the list.

This approach is efficient for small to medium-sized nested lists. However, for very large datasets, we may need to consider memory usage and performance optimizations. The space complexity is O(n) for the stack, where n is the number of elements in the nested structure. The time complexity for each `next()` call is O(1) on average, but can be O(n) in the worst case when traversing deeply nested structures.

Here is a basic implementation of the nested list iterator:

```python
class NestedIterator:
    def __init__(self, nestedList):
        self.stack = nestedList[::-1]  # Initialize stack with reversed list
        self.last_returned = None

def next(self):
        while self.stack:
            top = self.stack.pop()
            if isinstance(top, int):
                self.last_returned = top
                return top
            self.stack.extend(top[::-1])  # Add nested list back to stack

def remove(self):
        if self.last_returned is None:
            raise Exception('No element to remove')
        # Logic to remove last_returned from the original nested list
```
This code provides a basic structure for the iterator and handles the removal of elements.

Implement a Removable Nested-List Iterator

Airbnb

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Requirements

High-Level Design

Submit Your Answer

Airbnb Software Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string