Time-Based Key-Value Store

Q: Time-Based Key-Value Store

A key-value store with timestamped writes. Read at time t returns the latest value written at or before t; later phases add arbitrary-order inserts and range queries.

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

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

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)  -> []

Patterns used

Foundations primers this challenge draws on.

Binary Search

Hash Maps

Loading editor...

0/3 passed

Level 1 - Strictly increasing timestamps.

For a given key, all set() calls arrive with strictly increasing timestamps. get(key, t) returns the value of the latest set with timestamp <= t, or "" if no such write exists. get() must run in O(log N).

Level 2 - Arbitrary-order timestamps.

Locked

Pass the previous level to unlock.

Level 3 - Range queries.

Locked

Pass the previous level to unlock.