## Problem Implement an in-memory “database” that stores **records** by `key` and **fields** within each key. Each operation is given a `timestamp` (integer, non-decreasing across calls) and should behave as if executed at that time. A record conceptually looks like: - `DB[key][field] = value` (value is an integer) However, later levels add **TTL expiration** and **historical (“time-travel”) queries**, so your implementation must maintain enough history to answer those queries. ### Common rules - If a requested `key` or `field` does not exist (or is expired at the queried time), treat it as missing. - Deleting a field removes it from the record at that time. - Unless otherwise specified, functions that read data use the provided `timestamp` as the “current time” for visibility/expiration. - Return formats must be deterministic. Unless specified by the interviewer, return scan results sorted by `field` ascending. --- ## Level 1: Basic operations Implement: 1. `set(timestamp: int, key: str, field: str, value: int) -> None` - Sets `DB[key][field] = value` at `timestamp`. 2. `get(timestamp: int, key: str, field: str) -> Optional[int]` - Returns the current value for `(key, field)` at `timestamp`, or `None` if missing. 3. `compare_and_set(timestamp: int, key: str, field: str, expected_value: int, new_value: int) -> bool` - If the current value at `timestamp` equals `expected_value`, update it to `new_value` and return `True`. - Otherwise return `False` (no change). 4. `compare_and_delete(timestamp: int, key: str, field: str, expected_value: int) -> bool` - If the current value at `timestamp` equals `expected_value`, delete the field and return `True`. - Otherwise return `False`. --- ## Level 2: Scans Implement: 1. `scan(timestamp: int, key: str) -> List[str]` - Returns all visible fields for `key` at `timestamp` formatted as: `"{field}({value})"`. - Return the list sorted by `field` ascending. 2. `scan_with_prefix(timestamp: int, key: str, prefix: str) -> List[str]` - Same as `scan`, but only include entries where the formatted string starts with `prefix`. - (Equivalently: include only fields whose names start with `prefix`.) --- ## Level 3: TTL support Add per-write TTL (time-to-live). A value written with TTL is visible only in the half-open interval: - visible for times `t` where `write_timestamp <= t < write_timestamp + ttl`. Implement: 1. `set_with_ttl(timestamp: int, key: str, field: str, value: int, ttl: int) -> None` 2. `compare_and_set_with_ttl(timestamp: int, key: str, field: str, expected_value: int, new_value: int, ttl: int) -> bool` - Same semantics as `compare_and_set`, but when the update happens it writes `new_value` with the provided `ttl`. Additionally, **all previously implemented read/write operations** must be updated so that: - reads (`get`, `scan`, `scan_with_prefix`) do not return expired values, - compare-and-* operations compare against the value visible at that `timestamp` (treat expired as missing). --- ## Level 4: Time-travel query Implement: - `get_when(timestamp: int, key: str, field: str, at_timestamp: int) -> Optional[int]` It should return the value of `(key, field)` **as it was visible at time `at_timestamp`**, considering: - historical `set` / `set_with_ttl` - successful compare-and-* updates - deletions - TTL expiration relative to each write time Assume `at_timestamp <= timestamp`. If the value was missing or expired at `at_timestamp`, return `None`. --- ## Notes / Constraints (if not provided, assume typical interview constraints) - Timestamps are non-decreasing across operations. - Up to ~1e5–2e5 operations total. - Aim for efficient per-operation runtime (e.g., logarithmic in the number of updates per field).