Implement an in-memory database with TTL and backup

In-Memory Database (Levels 1–4: TTL and Backup/Restore)

Implement an in-memory database that stores records identified by a string key. Each record contains multiple string field → string value pairs.

You must support a set of operations that progressively add features.

Data model

• key is a string.
• Each key maps to a set of fields.
• Each field maps to a value (both strings).

If an operation refers to a missing key or field, treat it as absent.

Assumption to make outputs well-defined (typical for OAs):

• get* returns "" (empty string) when absent.
• delete* returns true if something was deleted, else false .
• scan* returns an empty list when nothing matches.

Level 1: Basic CRUD on fields

Implement:

• set(key, field, value)
• get(key, field) -> string
• delete(key, field) -> bool

set inserts or overwrites the field’s value.

Level 2: Read-only listing

Implement:

• scan(key) -> list[string]
• scan_by_prefix(key, prefix) -> list[string]

Return format:

• Each returned element is formatted as "field(value)" .
• Results are sorted lexicographically by field .
• scan_by_prefix returns only fields whose name starts with prefix .

Level 3: Timestamped operations + TTL

Add timestamped variants of the above operations. Tests will use either timestamped APIs or non-timestamped APIs, but never mix them.

All timestamped operations accept an integer timestamp.

Implement:

• set_at(key, field, value, timestamp)
• set_at_with_ttl(key, field, value, timestamp, ttl)
• get_at(key, field, timestamp) -> string
• delete_at(key, field, timestamp) -> bool
• scan_at(key, timestamp) -> list[string]
• scan_by_prefix_at(key, prefix, timestamp) -> list[string]

TTL semantics:

• set_at_with_ttl makes the field valid over the half-open interval:
  • valid in [timestamp, timestamp + ttl)
• Expired fields must not appear in get_at , scan_at , or prefix scans.
• Time always moves forward: timestamps provided to operations are non-decreasing .

Level 4: Backup and restore

Implement:

• backup(timestamp)
• restore(timestamp, timestamp_to_restore)

Backup requirements:

• backup(t) stores a snapshot of the database state at time t .
• For fields with TTL, the backup must capture remaining TTL at backup time (i.e., how much lifetime is left at t ).

Restore requirements:

• restore(now, timestamp_to_restore) restores the database from the latest backup whose backup time is ≤ timestamp_to_restore .
• After restoring at current time now , TTL expiration must be recalculated based on remaining TTL stored in the backup:
  • If a field had remaining TTL r in the backup, then after restore at time now it should expire at now + r .
• Fields that were already expired at the moment of backup should not be present in that backup.

Your implementation should correctly handle overwrites, deletions, scans, TTL expiry, and backup/restore interactions under the monotonic-time guarantee.