Implement a versioned in-memory DB with CAS and history
Company: Meta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Take-home Project
## 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 = +∞`).
2. `set_with_ttl(timestamp, key, field, value, ttl) -> void`
- Set with `expire_at = timestamp + ttl`.
3. `get(timestamp, key, field) -> value | null`
- Return current value if exists and not expired at `timestamp`, else `null`.
4. `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`.
5. `compare_and_set_with_ttl(timestamp, key, field, expected_value, new_value, ttl) -> bool`
- Same as above, but sets `expire_at = timestamp + ttl`.
6. `compare_and_delete(timestamp, key, field, expected_value) -> bool`
- If current visible value equals `expected_value`, delete it and return `true`, else return `false`.
7. `scan(timestamp, key) -> list<string>`
- Return all non-expired fields for `key` at `timestamp`.
- Sort by `field` ascending.
- Format each item as `"field(value)"`.
8. `scan_by_prefix(timestamp, key, prefix) -> list<string>`
- Like `scan`, but only fields starting with `prefix`.
9. `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.
Quick Answer: 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.
Simulate timestamped set/get/CAS/delete/scan/history operations for a key-field store with TTL.
Constraints
- Operation timestamps are non-decreasing
Examples
Input: ((('set', 1, 'u', 'name', 'Ann'), ('get', 2, 'u', 'name'), ('cas', 3, 'u', 'name', 'Ann', 'Ana'), ('get', 4, 'u', 'name')),)
Expected Output: ['Ann', True, 'Ana']
Explanation: Set, get, compare-and-set.
Input: ((('set_ttl', 1, 'k', 'a', 'v', 3), ('get', 3, 'k', 'a'), ('get', 4, 'k', 'a'), ('get_at', 5, 'k', 'a', 2)),)
Expected Output: ['v', None, 'v']
Explanation: TTL visibility and historical read.
Input: ((('set', 1, 'k', 'b', '2'), ('set', 2, 'k', 'a', '1'), ('scan', 3, 'k'), ('scan_prefix', 3, 'k', 'a'), ('cad', 4, 'k', 'a', '1'), ('scan', 5, 'k')),)
Expected Output: [['a(1)', 'b(2)'], ['a(1)'], True, ['b(2)']]
Explanation: Sorted scans and compare-and-delete.
Hints
- Keep current state for live reads and append history entries for historical reads.