Design a time-travel key-field store with TTL

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).