Katkat
Back

Implement a versioned in-memory DB with CAS and history

MetaSoftware Engineer · Online Assessment
MediumSoftware EngineerOnline AssessmentCoding & Algorithms

Last updated

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.

In-Memory DB V2: TTL + Compare-And-Set/Delete + Historical Reads

Implement an in-memory database keyed by (key, field) supporting TTL, conditional updates, scans, and historical queries.

Data model / rules

  • For each (key, field) store:
  • value
  • expire_at (integer; +∞ means never expires)
  • A record is visible at time t iff t < expire_at.
  • All operations are given a timestamp. You may assume operations are provided in non-decreasing timestamp order.
  • You must also support historical queries: retrieve what value was valid at some earlier time.

API

  1. set(timestamp, key, field, value) -> void
  • Set with no TTL (expire_at = +∞).
  1. set_with_ttl(timestamp, key, field, value, ttl) -> void
  • Set with expire_at = timestamp + ttl.
  1. get(timestamp, key, field) -> value | null
  • Return current value if exists and not expired at timestamp, else null.
  1. compare_and_set(timestamp, key, field, expected_value, new_value) -> bool
  • If (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.
  • Otherwise return false.
  1. compare_and_set_with_ttl(timestamp, key, field, expected_value, new_value, ttl) -> bool
  • Same as above, but sets expire_at = timestamp + ttl.
  1. compare_and_delete(timestamp, key, field, expected_value) -> bool
  • If current visible value equals expected_value, delete it and return true, else return false.
  1. scan(timestamp, key) -> list<string>
  • Return all non-expired fields for key at timestamp.
  • Sort by field ascending.
  • Format each item as "field(value)".
  1. scan_by_prefix(timestamp, key, prefix) -> list<string>
  • Like scan, but only fields starting with prefix.
  1. get_value_at(timestamp, key, field, at_timestamp) -> value | null
  • Return the value that was valid for (key, field) at time at_timestamp.
  • Return null if it did not exist, was deleted, or was expired at at_timestamp.

Notes

  • You will likely need to keep a per-(key,field) history of changes to answer get_value_at efficiently.
  • Assume up to ~1e5 operations.