Time-Based Key-Value Store

PracticalmediumPremium

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

Audit logs and event-sourced systems need point-in-time reads: given a key, what was its value at time T? You will implement a timestamped key-value store where each write records its time and get returns the latest value at or before the queried timestamp. If no such write exists, return "".

Level 1 - Strictly increasing timestamps

Per the LeetCode 981 contract: for a given key, all set calls arrive with strictly increasing timestamp values. get must run in O(log N).

Example:

store.set("key", "value_a", 10)
store.set("key", "value_b", 20)
 
store.get("key", 5)   -> ""         # before any write
store.get("key", 10)  -> "value_a"  # exact match
store.get("key", 15)  -> "value_a"  # between writes; latest at or before 15
store.get("key", 20)  -> "value_b"  # exact match

Level 2 - Arbitrary timestamps

Drop the strictly-increasing assumption. set calls can arrive in any order: set("k","v1",10); set("k","v2",5) is legal and must be supported. get must still return the latest value at or before the queried time, and stay efficient as a key accumulates many out-of-order writes.

Re-setting the same (key, timestamp) should overwrite (later write wins).

Example:

store.set("k", "v_10", 10)
store.set("k", "v_5",   5)   # inserted before v_10 in history
 
store.get("k", 4)   -> ""
store.get("k", 5)   -> "v_5"
store.get("k", 9)   -> "v_5"
store.get("k", 10)  -> "v_10"

Level 3 - Range queries

Add a method:

def get_range(self, key: str, t1: int, t2: int) -> list[tuple[int, str]]:
    """All (timestamp, value) pairs for `key` with t1 <= ts <= t2, sorted by timestamp."""

Both ends inclusive. Empty list if nothing falls in the window or the key doesn't exist.

Example:

store.set("k", "a", 5)
store.set("k", "b", 10)
store.set("k", "c", 15)
 
store.get_range("k", 5, 10)   -> [(5, "a"), (10, "b")]
store.get_range("k", 6, 14)   -> [(10, "b")]
store.get_range("k", 20, 30)  -> []

Mastery checklist

Check	Why it matters
`bisect_right(ts, t) - 1` gives the latest entry `<=` t	Off-by-one against `bisect_left` is the classic mistake
Two parallel lists, not a list of tuples	`bisect` on tuples needs a key function (Python 3.10+) and is slower
Get of a key never set returns `""`	The empty string, not `None` - mirrors LC 981
Set with the same `(key, ts)` twice overwrites	The natural answer; document if asked
Range query is `bisect_left` for the lower bound and `bisect_right` for the upper bound	Both ends inclusive falls out of that pairing

Patterns used

Foundations primers this challenge draws on.

Loading editor…

Premium content

The live editor for this challenge unlocks with Premium.

0/0 passed