Time Based Key-Value Store

MediumBinary Searchbinary search

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

Build a key-value store that keeps every historical version of each key, stamped with the time it was written, and can answer "what was this key's value as of time t?" Implement: - TimeMap() creates an empty store. - set(key, value, timestamp) records that key had value starting at timestamp. - get(key, timestamp) returns the value from the set of key with the **largest timestamp that is <= the given timestamp**. If key has no such version (never set, or all its versions are later), return the empty string "". Timestamps passed to set are strictly increasing across all calls. Timestamps passed to get can be anything in range. Target O(log n) per get.

Examples

Input: ["TimeMap","set","get","get","set","get","get","get"] [[],["color","red",1],["color",1],["color",4],["color","blue",5],["color",4],["color",5],["color",100]]
Output: [null,null,"red","red",null,"red","blue","blue"]
At times 1 and 4 the latest version is "red". After "blue" is written at 5, time 4 still sees "red" while 5 and 100 see "blue".
Input: ["TimeMap","set","get","get"] [[],["a","x",10],["a",9],["b",10]]
Output: [null,null,"",""]
Key "a" has no version at or before time 9, and key "b" was never set, so both return "".

Constraints

  • 1 <= key.length, value.length <= 100 (lowercase letters and digits)
  • 1 <= timestamp <= 10^7
  • `set` timestamps are strictly increasing.
  • At most 2 * 10^5 calls to `set` and `get` combined.

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More binary search problems