Skip to content
Onsite
18 / 20

Time Based Key-Value Store

MediumP2Coding

Design a time-versioned key-value store.

Implement the TimeMap class:

  • TimeMap() creates an empty store.
  • set(key, value, timestamp) stores value for key at timestamp.
  • get(key, timestamp) returns the value stored for key with the largest timestamp that is less than or equal to timestamp. If there is none, return the empty string "".

For each key, set is called with strictly increasing timestamps. get should use binary search.

Example 1

Input
["TimeMap","set","get","get","set","get","get"] [[],["foo","bar",1],["foo",1],["foo",3],["foo","bar2",4],["foo",4],["foo",5]]
Output
[null,null,"bar","bar",null,"bar2","bar2"]
Why
get(foo, 3) finds the entry at timestamp 1, the latest one not after 3.

Constraints

  • 1 <= key.length, value.length <= 100
  • 1 <= timestamp <= 10^7
  • Timestamps passed to set for one key are strictly increasing
  • At most 2 * 10^5 calls in total

Hints

Run checks the 2 visible tests, Submit all 5.