Implement an In-Memory Key-Value Store

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

    Problem statement

    Build an in-memory key-value store, one level at a time. Every call receives the current time now as an integer, so the store never reads a clock.

    Level 1. set(key, value, now), get(key, now) (the value, or None if missing) and delete(key, now) (returns whether the key existed). Level 2. set takes an optional ttl: the key lives while now < set_time + ttl and then behaves as if it was never there. Level 3. begin(), commit() and rollback(), with nested transactions. Reads inside a transaction see its own writes. commit and rollback act on the innermost open transaction and return False if there is none. Level 4. snapshot(now) saves the live data and returns an id; restore(id, now) brings it back. A key that had 6 seconds left when saved has 6 seconds left after the restore.

    This is the most common "practical" coding round: a small system built in stages, where each level adds a requirement and the interviewer watches how well your earlier code absorbs it. The wording changes from company to company (a command interpreter, a store with expiry, a store with transactions or backups), but the core is the same. There's no single LeetCode original; the closest pieces are Time Based Key-Value Store and LRU Cache.

    Example

    A key with a TTL disappears at exactly set time + ttl; a nested transaction's delete is undone by rollback, and commit makes the outer change permanent.
    A key with a TTL disappears at exactly set time + ttl; a nested transaction's delete is undone by rollback, and commit makes the outer change permanent.
    set("course", "sd", now=1)
    get("course", now=2)                     -> "sd"
    set("session", "abc", now=5, ttl=10)     # alive for 5 <= now < 15
    get("session", now=14)                   -> "abc"
    get("session", now=15)                   -> None
    begin(); set("course", "coding", now=20)
    begin(); delete("course", now=21)        -> True
    get("course", now=22)                    -> None
    rollback(); get("course", now=23)        -> "coding"
    commit();   get("course", now=24)        -> "coding"
    rollback()                               -> False   # nothing open
    set("token", "t1", now=30, ttl=10)
    id = snapshot(now=34)                    # token has 6 s left
    delete("token", now=35)
    restore(id, now=100)
    get("token", now=105)                    -> "t1"
    get("token", now=106)                    -> None    # 100 + 6

    Constraints (assumed)

    • Up to 10⁵ calls; keys and values are strings.
    • now never decreases between calls.
    • snapshot and restore are only called when no transaction is open.

    What this question tests

    • Choosing a representation that later levels don't force you to rewrite.
    • Getting expiry boundaries and deletes inside transactions exactly right.
    • Clean, well-named code written quickly, with tests you run as you go.

    Questions to ask first

    1. Who supplies the time? Passing now in makes tests deterministic. (Here: it's passed in.)
    2. Is a key alive at exactly set_time + ttl? (Here: no, it expires at that instant.)
    3. Does set on an existing key reset its TTL? (Here: yes, a set replaces value and expiry together.)
    4. Does commit close one transaction or all of them? (Here: the innermost one only.)
    5. Must expired keys free memory right away, or is it enough that reads never return them?