Time Based Key-Value Store

Free with account Updated Nov 19, 2026 · 6 min read
On this page

    Problem statement

    Design a key-value store that remembers every version of a value. set(key, value, timestamp) stores value for key at time timestamp. get(key, timestamp) returns the value whose timestamp is the largest one at or before timestamp, or an empty string if the key had no value yet. For each key, set is 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

    A user's plan was "free" from time 5, "pro" from 12 and "team" from 20; each query returns the value in force at that time.
    A user's plan was "free" from time 5, "pro" from 12 and "team" from 20; each query returns the value in force at that time.
    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 set and get in 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

    1. Do timestamps for one key always increase? (Here: yes. If not, the structure changes; see the follow-ups.)
    2. What should get return before the first set? (Here: an empty string.)
    3. Can the same key be set twice at the same timestamp? (Here: no. If yes, does the later write win?)
    4. Is it read-heavy or write-heavy? That decides which side should be O(1).