Versioned Array
Updated
Problem statement
Design a versioned array. It starts with length elements, all equal to 0. Process the operations in operations in order. For each index i, args[i] holds the arguments of operations[i].
"update"withargs[i] = [index, value]: set the element atindexof the current array tovalue. This records nothing."saveVersion"withargs[i] = []: save the current state of the whole array and record its version number. Version numbers start from1and go up by1with each save."getValue"withargs[i] = [index, versionNumber]: record the value that the element atindexhad in saved versionversionNumber.
Updates after a save change only the current array. They never change a version that was already saved.
Return the recorded values of all "saveVersion" and "getValue" operations, in order.
Function
runVersionedArray(length: int, operations: String[], args: int[][]) → int[]Examples
Example 1
length = 3operations = ["update","saveVersion","update","getValue"]args = [[0,5],[],[0,6],[0,1]]return = [1,5]The array starts as [0,0,0]. The update makes it [5,0,0], and "saveVersion" saves that state as version 1, so 1 is recorded.
The next update makes the current array [6,0,0], but version 1 still holds 5 at index 0. So "getValue" records 5.
Example 2
length = 2operations = ["saveVersion","update","update","saveVersion","getValue","getValue","getValue"]args = [[],[1,4],[1,7],[],[1,1],[1,2],[0,2]]return = [1,2,0,7,0]Version 1 is saved right away, so it is [0,0]. Index 1 is then set to 4 and then to 7, and version 2 saves [0,7].
The reads give 0 (index 1 in version 1), 7 (index 1 in version 2), and 0 (index 0 in version 2). The result is the two version numbers followed by these three values.
Example 3
length = 1operations = ["update","saveVersion","saveVersion","update","saveVersion","getValue","getValue","getValue"]args = [[0,3],[],[],[0,9],[],[0,2],[0,3],[0,1]]return = [1,2,3,3,9,3]Versions 1 and 2 are both saved while the element is 3, because nothing changes between them. Version 3 is saved after the element becomes 9.
So the reads of versions 2, 3, and 1 record 3, 9, and 3.
Constraints
1 <= length <= 10^41 <= operations.length <= 10^4args.length == operations.length- Each
operations[i]is"update","saveVersion", or"getValue". - For
"update",args[i] = [index, value]with0 <= index < lengthand0 <= value <= 10^9. - For
"saveVersion",args[i]is empty. - For
"getValue",args[i] = [index, versionNumber]with0 <= index < length, andversionNumberis a version that has already been saved.
More TrueFoundry Phone Screen questions
Similar questions at other companies
- Future-Effective Employee SalaryRippling · ONSITE INTERVIEWRippling interview questions
- Insert Delete GetRandom O(1)Charta Health · PHONE SCREENCharta Health interview questions
- Portfolio Tickers with Constant-Time Random PickCitadel · PHONE SCREENCitadel interview questions
- Snapshot Map with Sparse Version HistorySnorkel AI · PHONE SCREEN
- Time-Based Key-Value StoreOracle · PHONE SCREEN · ONSITE INTERVIEWOracle interview questions
- Build a Pivot Table with TotalsSigma Computing · PHONE SCREEN
- Process On-Call Routing OperationsOpenAI · PHONE SCREENOpenAI interview questions
- Time-Based Key-Value StoreCockroach Labs · PHONE SCREEN · ONSITE INTERVIEW
- Stateful Paginated Fetch NLyft · PHONE SCREENLyft interview questions
- Time Map with Sum and AverageConfluent · PHONE SCREENConfluent interview questions