Time-Based Key-Value Store

Hash Mapsmedium

Course · Section 9: Data Structures, Modern Operators and Strings · Lecture 124: Maps: Fundamentals

Design a store that keeps multiple values per key at different timestamps (set calls use increasing timestamps). Implement `TimeMap`: - `set(key, value, timestamp)` stores the value. - `get(key, timestamp)` returns the value with the largest stored timestamp `<= timestamp`, or `''` if none.

Examples

Input: set('foo','bar',1), get('foo',1), get('foo',3), set('foo','bar2',4), get('foo',4), get('foo',5)

Output: ['bar', 'bar', 'bar2', 'bar2']

Each get returns the value with the latest timestamp not exceeding the query.

Sample tests

Input: set/get across timestamps

Output: ["bar","bar","bar2","bar2"]

Input: query before any set

Output: ""

+ 1 hidden test run on Submit.

Hints

Common pitfalls

Returning the newest value regardless of the query timestamp.
Missing the empty-string result for an unknown key or too-early timestamp.

Learning resources

MDN: Map

Approach & explanation (try first)

Each key keeps a chronological list; get scans (or binary-searches) for the latest timestamp at or before the query. O(n) per get here; binary search would be O(log n).

⌘/Ctrl + Enter

Run your code to see results.

← Back to problems