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 xAI.

What role is this question designed for?

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

Design a Recoverable Iterator | xAI Coding Question

Design a Recoverable Iterator

Company: xAI

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Implement an iterator over a sequence that supports both normal traversal and state recovery. Design a class `RecoverableIterator` initialized with an array or list of elements. It must support the following operations: - `hasNext()`: return whether there is another element to read. - `next()`: return the next element and advance the iterator. - `saveState()`: return an opaque snapshot token representing the iterator's current position. - `restoreState(token)`: restore the iterator to the position captured by a previous snapshot. Requirements: 1. After restoring a saved state, subsequent calls to `next()` and `hasNext()` must behave exactly as if no operations had happened after that snapshot was taken. 2. Multiple saved states may exist at the same time, and restoring one state must not invalidate the others. 3. The design should be efficient in both time and space. 4. Discuss edge cases, such as restoring the initial state, restoring the end state, and calling `next()` when no elements remain. As a follow-up, explain how your design would change if the iterator were reading from a stream instead of an in-memory collection.

Quick Answer: This question evaluates data-structure and state-management skills, focusing on iterator semantics, snapshotting/restore mechanics, and efficient time-space trade-offs.

Part 1: Simulate a Recoverable Iterator for an In-Memory Collection

Given a list `items` and a sequence of operations, simulate a recoverable iterator. Operations are `('hasNext',)`, `('next',)`, `('save',)`, and `('restore', token)`. The iterator starts at index 0. `next()` returns the current element and advances; if no elements remain, return `None`. `save()` returns a new snapshot token (0, 1, 2, ...) storing the current position. `restore(token)` moves the iterator back to the saved position. Restoring one snapshot must not remove or change any other snapshot. Return the result of every operation in order; use `None` as the result of `restore()`.

Constraints

0 <= len(items) <= 200000
1 <= len(operations) <= 200000
All `restore` tokens are valid and were produced by an earlier `save` operation.
Item values fit in 32-bit signed integers.

Examples

Input: ([1, 2, 3], [('save',), ('next',), ('next',), ('save',), ('restore', 0), ('next',), ('restore', 1), ('hasNext',), ('next',), ('next',)])

Expected Output: [0, 1, 2, 1, None, 1, None, True, 3, None]

Explanation: Two snapshots coexist. Restoring token 0 returns to the start, and restoring token 1 later still works.

Input: ([7, 8], [('save',), ('next',), ('hasNext',), ('restore', 0), ('next',), ('next',), ('hasNext',)])

Expected Output: [0, 7, True, None, 7, 8, False]

Explanation: Restoring the initial state lets the iterator replay the list from the beginning.

Input: ([], [('hasNext',), ('next',), ('save',), ('restore', 0), ('next',)])

Expected Output: [False, None, 0, None, None]

Explanation: Empty input should report no next element, and restoring the initial empty state changes nothing.

Input: ([5], [('next',), ('save',), ('hasNext',), ('restore', 0), ('hasNext',), ('next',)])

Expected Output: [5, 0, False, None, False, None]

Explanation: Saving after consuming the only element creates an end-state snapshot; restoring it keeps the iterator at the end.

Hints

For an array-backed iterator, a snapshot only needs to remember the current index.
Restoring a snapshot should not delete it; multiple saved states must keep working independently.

Part 2: Simulate a Recoverable Iterator on a Stream with Minimal Buffering

A forward-only stream cannot revisit old elements unless they are buffered. You are given a finite list `stream` representing the values that would arrive from such a stream, plus operations on a stream-backed recoverable iterator. Supported operations are `('hasNext',)`, `('next',)`, `('save',)`, `('restore', token)`, and `('release', token)`. `save()` returns a token for the current logical position. `restore(token)` moves the cursor back to that position. `release(token)` means that snapshot will never be used again. The iterator should keep only the minimum data needed for future restores: after each operation, it may discard every buffered element whose position is strictly before `min(current_cursor, all_unreleased_snapshot_positions)`; if there are no unreleased snapshots, use `current_cursor`. Return both the operation results and the maximum retained buffer size. Assume cleanup happens immediately after each operation, so `max_buffer_size` is measured after that cleanup.

Constraints

0 <= len(stream) <= 200000
1 <= len(operations) <= 200000
All `restore` and `release` tokens are valid and come from earlier `save` operations.
A token is never released twice, and `restore` is only called on unreleased tokens.
Stream values fit in 32-bit signed integers.

Examples

Input: ([10, 20, 30], [('save',), ('next',), ('next',), ('save',), ('restore', 0), ('next',), ('release', 0), ('next',), ('release', 1)])

Expected Output: ([0, 10, 20, 1, None, 10, None, 20, None], 2)

Explanation: Because snapshot 0 points to the beginning, the first two values must stay buffered until that snapshot is released.

Input: ([], [('hasNext',), ('next',), ('save',), ('restore', 0), ('release', 0)])

Expected Output: ([False, None, 0, None, None], 0)

Explanation: An empty stream never stores any buffered data.

Input: ([5, 6], [('next',), ('hasNext',), ('next',), ('hasNext',)])

Expected Output: ([5, True, 6, False], 0)

Explanation: With no saved states, each consumed stream element can be discarded immediately, so the retained buffer size stays 0.

Input: ([1], [('save',), ('next',), ('save',), ('restore', 0), ('next',), ('restore', 1), ('hasNext',), ('release', 0), ('release', 1)])

Expected Output: ([0, 1, 1, None, 1, None, False, None, None], 1)

Explanation: The first snapshot forces the single streamed value to stay buffered until token 0 is released; token 1 represents the end state.

Hints

Unlike an array, a stream cannot be reread from the source. Any element that might be needed after a restore must stay in a buffer.
Track the earliest unreleased snapshot position efficiently; a min-heap with lazy deletion works well.

Quick Overview

This question evaluates data-structure and state-management skills, focusing on iterator semantics, snapshotting/restore mechanics, and efficient time-space trade-offs.