In-Memory Key-Value Store

Q: In-Memory Key-Value Store

Build a key-value store as a single class. Layer on prefix-scan, TTL, then gzip persistence - each phase is its own surface area on top of the previous one.

PracticalmediumFree

45:00

Desktop only

Coding Challenges are optimized for Desktop

Come back on a wider screen - the live editor needs room to breathe. You can still read the problem brief above.

Problem

Every production key-value store started as a hash map. Redis, Memcached, and etcd all evolved from a put/get/delete core by layering on prefix scans, TTL expiry, and persistence. You will build that same progression. All keys and values are strings; each level builds on the previous - implement only what each test file exercises.

Level 1 - get / set / delete

class Database:
    def set(self, key: str, value: str) -> None: ...
    def get(self, key: str) -> str | None: ...
    def delete(self, key: str) -> bool: ...

set: store key→value (overwrite if it already exists)
get: return the value or None if the key isn't set
delete: remove the key. Return True if it existed, False otherwise

Example:

db = Database()
db.set("color", "blue")
db.get("color")      # "blue"
db.delete("color")   # True
db.get("color")      # None
db.delete("color")   # False  (already gone)

Level 2 - Prefix scan

Add two methods that let callers iterate keys whose names share a prefix:

def scan(self, prefix: str) -> list[str]:
    """Keys that start with `prefix`, sorted alphabetically."""

def scan_values(self, prefix: str, value_filter: str) -> list[tuple[str, str]]:
    """(key, value) pairs where the key starts with `prefix` AND the value
    contains `value_filter` as a substring. Sorted by key."""

Example:

db.set("user:alice", "admin")
db.set("user:bob",   "viewer")
db.set("config:x",  "1")
db.scan("user:")              # ["user:alice", "user:bob"]  (alphabetical)
db.scan_values("user:", "min")  # [("user:alice", "admin")]

Level 3 - TTL (time-to-live)

Extend set to take an optional TTL in milliseconds, and let every read accept a now_ms for deterministic tests:

def set(self, key: str, value: str,
        ttl_ms: int | None = None,
        now_ms: int | None = None) -> None: ...

If ttl_ms is given, the key expires ttl_ms after it is set.
get, delete, scan, scan_values all accept now_ms: int | None = None. When provided, treat it as the current time. Otherwise read the real clock.
Expired keys behave as if they don't exist - get returns None, delete returns False, scan results skip them.

Example:

db.set("session", "abc", ttl_ms=1000, now_ms=0)
db.get("session", now_ms=999)    # "abc"  (not yet expired)
db.get("session", now_ms=1000)   # None   (boundary: expired at exactly 1000)
db.delete("session", now_ms=999) # True
db.delete("session", now_ms=999) # False  (already deleted)

Level 4 - Persistence (dump / load)

def dump(self, path: str) -> None:
    """Serialize the database to a gzip-compressed JSON file."""

def load(self, path: str, now_ms: int | None = None) -> None:
    """Load from a dump file. Discard entries that have already expired."""

After load, the database state is exactly what it was when dump was called, minus any TTL that has elapsed since.
Standard library only: gzip and json.

Example:

db.set("session", "abc", ttl_ms=1000, now_ms=0)
db.dump("/tmp/snap.gz")
db2 = Database()
db2.load("/tmp/snap.gz", now_ms=500)
db2.get("session", now_ms=500)   # "abc"  (still live)
db2.get("session", now_ms=1000)  # None   (expired)
db2.get("original")              # None   (load replaces, not merges)

Patterns used

Foundations primers this challenge draws on.

Hash Maps

Loading editor...

0/4 passed

Level 1 - set / get / delete.

set(key, value) stores the key-value pair, overwriting any prior value. get(key) returns the stored value, or None if the key does not exist. delete(key) removes the key and returns True if it existed, False otherwise.

Level 2 - prefix scan.

Locked

Pass the previous level to unlock.

Level 3 - TTL (time-to-live).

Locked

Pass the previous level to unlock.

Level 4 - persistence (dump / load).

Locked

Pass the previous level to unlock.