Time Based Key-Value Store
On this page
Problem statement
Design a key-value store that remembers every version of a value.
set(key, value, timestamp)storesvalueforkeyat timetimestamp.get(key, timestamp)returns the value whose timestamp is the largest one at or beforetimestamp, or an empty string if the key had no value yet. For each key,setis called with increasing timestamps.
This is the classic "versioned config" or "price history" question: you keep every write and answer "what was the value back then?". It is often the first part of a longer, multi-level round. Original problem: LeetCode 981.
Example

set("alice:plan", "free", 5)
set("alice:plan", "pro", 12)
set("alice:plan", "team", 20)
get("alice:plan", 1) -> "" # nothing set yet
get("alice:plan", 5) -> "free" # exact timestamp counts
get("alice:plan", 15) -> "pro"
get("alice:plan", 25) -> "team"
get("bob:plan", 25) -> "" # unknown key
Constraints (assumed)
- Up to 2 × 10⁵ calls to
setandgetin total. - 1 ≤ timestamp ≤ 10⁷; timestamps for one key arrive in increasing order.
What this question tests
- Choosing a per-key sorted list instead of storing one value per key.
- Writing a "last element ≤ t" binary search without off-by-one errors.
- Saying what changes when the easy assumption (timestamps only grow) is removed.
Questions to ask first
- Do timestamps for one key always increase? (Here: yes. If not, the structure changes; see the follow-ups.)
- What should
getreturn before the firstset? (Here: an empty string.) - Can the same key be set twice at the same timestamp? (Here: no. If yes, does the later write win?)
- Is it read-heavy or write-heavy? That decides which side should be O(1).
Try it yourself first
You have the full problem. Sketch your answer, then sign up free to read the complete walkthrough.
- The complete design, flow by flow, with pictures
- Deep dives into the hard parts
- What mid, senior and staff candidates are expected to say
- Full company question lists
Free forever. No card needed.