Design a Restorable (Checkpointable) Iterator

Problem: Design a Restorable (Checkpointable) Iterator Design an iterator wrapper RestorableIterator that wraps an existing iterator (or an array/list). In addition to normal iteration via next(), it must support saving the current position as a checkpoint and later restoring the iterator back to that checkpoint to continue iterating. Required operations Implement the following API (language-agnostic semantics): hasNext() -> bool: whether there is a next element. next() -> T: returns the next element and advances the position; if no element remains, throw an error/exception. checkpoint() -> int: saves the current iterator position and returns a unique checkpoint id. restore(id: int) -> void: restores the iterator to the position saved under the given checkpoint id; if the id does not exist, throw an error/exception. Notes & constraints “Current position” means the position of the element that would be returned by the next call to next(). Multiple checkpoints are allowed, and you may restore to any previously created checkpoint in any order. restore should not delete checkpoints (you can restore to the same id multiple times). You may only read elements from the underlying data source sequentially (i.e., no random access into the underlying iterator). Discuss time/space complexity, and how to control memory usage when the underlying iterator is very large. Example test scenario Given input sequence A = [1, 2, 3, 4]: Initialize: it = RestorableIterator(A) it.next() -> 1 c1 = it.checkpoint() (next next() should return 2) it.next() -> 2 it.next() -> 3 it.restore(c1) (next next() should return 2 again) it.next() -> 2 c2 = it.checkpoint() (next next() should return 3) it.next() -> 3 it.restore(c2) (next next() should return 3 again) it.next() -> 3 it.next() -> 4 it.hasNext() -> false Constraints (suggested discussion range) n (total number of elements) can be very large (e.g., up to 1e7). Total calls to checkpoint/restore/next can be up to 1e5. Note: You may choose the input as an array/list or a true streaming iterator, but must respect the “underlying source is sequential-only” constraint. Example Input [1,2,3,4] ops: next, checkpoint, next, next, restore(c1), next, checkpoint, next, restore(c2), next, next, hasNext Output 1 c1=1 2 3 (restored) 2 c2=2 3 (restored) 3 4 false