Flatten a 2D array with remove
Implement a class Vector2D that walks a 2D list of integers row by row, left to right, and lets the caller delete values while walking.
Vector2D(vec: list[list[int]]) # rows may be empty; the list itself may be empty
hasNext() -> bool # is there another value to return?
next() -> int # return the next value and advance
remove() -> None # delete the value returned by the most recent next()
getVector() -> list[list[int]] # the current rows, after all removals so far
Rules:
-
next()raises an error when there are no values left. -
remove()may be called at most once pernext(). Calling it before the firstnext(), or twice without anext()in between, raises an error. -
remove()must not change which valuenext()returns afterwards: iteration continues with the value that followed the removed one. -
getVector()keeps every row in its place, including rows that became empty, and must not expose internal state that the caller could change. - The iterator must not modify the caller's input lists.
- Up to 10^4 rows and 10^5 values in total; aim for amortized O(1)
hasNext()andnext().
Example 1
it = Vector2D([[10, 20], [], [30]])
it.next() -> 10
it.next() -> 20
it.remove()
it.getVector() -> [[10], [], [30]]
it.hasNext() -> True
it.next() -> 30
it.remove()
it.hasNext() -> False
it.getVector() -> [[10], [], []]
Example 2
it = Vector2D([[5], [6, 7]])
it.next() -> 5
it.hasNext() -> True
it.remove() # removes 5, even though hasNext() already looked at row 1
it.getVector() -> [[], [6, 7]]
it.next() -> 6
Sign in to see the worked answer
The full answer, chapter by chapter, with what interviewers expect at each level. Free with an account: one full answer per company.
