Query a Versioned Array
Company: Truefoundry
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
# Query a Versioned Array
A fixed-length array starts with all values equal to zero. Process update, save, and get operations. An update changes one index in the current working state. A save captures the current state and returns the next version number, starting at 1. A get returns an index's value in a previously saved version. Return the results of every save and get operation in order.
## Function Contract
Implement `process_versioned_array(length, operations) -> list[int]`. `operations` is a homogeneous list of three-integer rows. Opcode 0 is `[0, index, value]` for update, opcode 1 is `[1, 0, 0]` for save, and opcode 2 is `[2, index, version]` for get. Return the integer result of every save and get operation in input order.
## Constraints
- 1 <= length <= 200000.
- 0 <= number of operations <= 200000.
- Every index is valid, and every queried version has already been saved.
- Values are integers between -10^9 and 10^9.
- Every operation row contains exactly three integers and a valid opcode.
## Examples
```text
length = 3, operations = [[0, 1, 5], [1, 0, 0], [0, 1, 7], [2, 1, 1], [1, 0, 0]]
output = [1, 5, 2]
```
```text
length = 1, operations = [[1, 0, 0], [2, 0, 1]]
output = [1, 0]
```
```hint Check repeated saves
Two consecutive save operations receive different version numbers even when no update occurs between them.
```
```hint Preserve historical isolation
An update after a save must not change any value observed through that earlier version.
```
Quick Answer: A fixed-length array starts with all values equal to zero. Work through the function contract, boundary cases, correctness argument, and time and space complexity expected in a production-quality solution.
A fixed-length array starts with zeros. Process three-integer operation rows: `[0,index,value]` updates the current state, `[1,0,0]` saves it under the next version number starting at one, and `[2,index,version]` retrieves a value from an already saved version. Return every save version number and get value in operation order.
Constraints
- 1 <= length <= 200000 and 0 <= len(operations) <= 200000.
- Every operation is a valid three-integer row with opcode 0, 1, or 2.
- Every index is valid and every queried version has already been saved.
- Updated values are integers from -10^9 through 10^9; output follows save/get operation order exactly.
Examples
Input: (1, [])
Expected Output: []
Explanation: No operations produce no returned results.
Input: (3, [[0, 1, 5], [1, 0, 0], [0, 1, 7], [2, 1, 1], [1, 0, 0]])
Expected Output: [1, 5, 2]
Explanation: The source example returns a version, a historical value, and the next version.
Hints
- Test no operations, updates without a save, and repeated saves without an intervening update.
- Update one index before and after a save, then query both the older and newer versions.
- Include repeated updates to one index and independent updates at several indices.