This question evaluates a candidate's ability to design and implement time-versioned in-memory data structures, conditional concurrency primitives (compare-and-set and compare-and-delete), TTL expiration semantics, and efficient historical reads.
Implement an in-memory database keyed by (key, field) supporting TTL, conditional updates, scans, and historical queries.
(key, field)
store:
value
expire_at
(integer;
+∞
means never expires)
t
iff
t < expire_at
.
timestamp
. You may assume operations are provided in
non-decreasing timestamp order
.
set(timestamp, key, field, value) -> void
expire_at = +∞
).
set_with_ttl(timestamp, key, field, value, ttl) -> void
expire_at = timestamp + ttl
.
get(timestamp, key, field) -> value | null
timestamp
, else
null
.
compare_and_set(timestamp, key, field, expected_value, new_value) -> bool
(key, field)
exists and is not expired at
timestamp
and its current value equals
expected_value
, update it to
new_value
(
expire_at = +∞
) and return
true
.
false
.
compare_and_set_with_ttl(timestamp, key, field, expected_value, new_value, ttl) -> bool
expire_at = timestamp + ttl
.
compare_and_delete(timestamp, key, field, expected_value) -> bool
expected_value
, delete it and return
true
, else return
false
.
scan(timestamp, key) -> list<string>
key
at
timestamp
.
field
ascending.
"field(value)"
.
scan_by_prefix(timestamp, key, prefix) -> list<string>
scan
, but only fields starting with
prefix
.
get_value_at(timestamp, key, field, at_timestamp) -> value | null
(key, field)
at time
at_timestamp
.
null
if it did not exist, was deleted, or was expired at
at_timestamp
.
get_value_at
efficiently.