Latest-Timestamp Key-Value Store
Updated
Problem statement
Build a key-value store that picks values by the timestamp each set carries, not by the order the sets arrive. The input is four arrays of the same length. Together they list the operations in order, and each index is one operation:
operations[i] = 0: callset(timestamps[i], keys[i], values[i]).operations[i] = 1: callget(keys[i]). For this operation, ignoretimestamps[i]andvalues[i].
A get looks at the sets for its key that came before it. It returns the value whose timestamp is largest. If several of those sets share the largest timestamp, use the one that came last. If the key was never set, return the empty string.
Return only the results of the gets, in the order the gets appear. Sets add nothing to the output. Each call starts with an empty store. Values never expire and are never evicted, and the store has no size limit. A get never asks for the value at a past timestamp.
Timestamps may arrive out of order. A later set with a smaller timestamp must not replace the value with the largest timestamp. Each get sees only the sets that came before it in the list.
Function
latestTimestampValues(operations: int[], keys: String[], values: String[], timestamps: int[]) → String[]Examples
Example 1
operations = [0,0,1,0,1,0,1]keys = ["a","a","a","a","a","a","a"]values = ["newer","older","","tie","","newest",""]timestamps = [10,3,0,10,99,12,1]return = ["newer","tie","newest"]The set of older comes later, but its timestamp 3 is smaller than 10, so the first get still returns newer. Next, tie is set at timestamp 10 too. It ties and came later, so the second get returns tie. Then newest is set at timestamp 12, the largest so far, so the last get returns newest. The timestamps on the get rows are ignored. The output is newer, tie, newest.
Example 2
operations = [1,0,0,1,1]keys = ["x","x","y","x","y"]values = ["ignored","red","blue","",""]timestamps = [8,0,5,999,0]return = ["","red","blue"]The first get asks for x before any set, so it returns the empty string. Then red is set for x at timestamp zero, which is a valid timestamp, and blue is set for y. Each key keeps its own value, so the remaining gets return red for x and blue for y.
Constraints
- All four arrays have the same length
q, where0 <= q <= 200. - Each operation code is
0or1. - Keys contain
1through20lowercase English letters. - Values contain
0through20lowercase English letters. 0 <= timestamps[i] <= 1000000000. This holds for gets too, even though their timestamps are ignored.
More Amazon Phone Screen questions
- LRU Cache for Query ResultsPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Course SchedulePHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Course Schedule IIPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Minimum Time to Spread Through a GridPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Consistent-Hash Packet RouterPHONE SCREEN · Seen Nov 2026
- Count Connected ComponentsPHONE SCREEN · Seen Nov 2026
- Second Largest Distinct ElementPHONE SCREEN · Seen Nov 2026
- Task SchedulerOA · PHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Top K Frequent ElementsOA · PHONE SCREEN · Seen Nov 2026
- Number of IslandsPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
Similar questions at other companies
- In-Memory Filesystem CommandsPerplexity AI · PHONE SCREEN · ONSITE INTERVIEWPerplexity AI interview questions
- LRU CacheServiceNow · PHONE SCREEN · ONSITE INTERVIEWServiceNow interview questions
- Mutable Points in a Hash Set and a ListMillennium · PHONE SCREENMillennium interview questions
- Snapshot Map with Sparse Version HistorySnorkel AI · PHONE SCREEN
- Insert Delete GetRandom O(1)Charta Health · PHONE SCREENCharta Health interview questions
- N-ary Index-Path Encoder and DecoderBloomberg LP · PHONE SCREEN · ONSITE INTERVIEWBloomberg LP interview questions
- Per-Client API Rate LimiterDocker · PHONE SCREEN
- LRU CacheGimlet Labs · PHONE SCREEN
- Tree Selection and VisibilityJane Street · PHONE SCREENJane Street interview questions
- Rectangle Point Coverage CountsOpenAI · PHONE SCREEN · ONSITE INTERVIEWOpenAI interview questions