Time Based Key Value Store

Medium · Binary Search

Design a store that keeps multiple values for the same string key, each tagged with a timestamp. Support setting a value for a key at a given timestamp, and fetching the value that was current for a key at or before a given timestamp. Timestamps for a given key always arrive in strictly increasing order when set is called. When getting, return the value whose timestamp is the largest one not exceeding the query timestamp; if no such value exists, return an empty string.

Examples

Input:  ops=["TimeMap","set","get","get","set","get","get"], args=[[],["foo","bar",1],["foo",1],["foo",3],["foo","bar2",4],["foo",4],["foo",5]]
Output: [null,null,"bar","bar",null,"bar2","bar2"]
Why:    At timestamp 1 'foo' becomes 'bar'; queries at 1 and 3 both see 'bar' since no later value exists before 4. At timestamp 4 'foo' becomes 'bar2'; queries at 4 and 5 see 'bar2'.

Input:  ops=["TimeMap","get"], args=[[],["missing",5]]
Output: [null,""]
Why:    The key was never set, so the lookup returns an empty string.

Input:  ops=["TimeMap","set","get"], args=[[],["a","x",10],["a",5]]
Output: [null,null,""]
Why:    The only stored value for 'a' has timestamp 10, which is after the queried timestamp 5, so nothing qualifies.

Constraints

1 <= key.length, value.length <= 100, 1 <= timestamp <= 10^7, timestamps passed to set for the same key strictly increase, at most 2*10^5 total calls to set and get

Practise it by voice

Describe the solution out loud and the interviewer writes exactly what you say, asks when you are vague, and runs the tests in your browser.

Practise Time Based Key Value Store

This statement is written for CodeSpeek. The problem is part of the NeetCode 150 list; Watch NeetCode's explanation of Time Based Key Value Store. Reference solutions from the NeetCode repository (MIT) are used to verify our tests.