In-Memory Database — Levels 1–4 (TTL + Backup/Restore)

CodeSignal-style multi-level OA used for the Backend Engineering Specialist track. You implement an in-memory key/value store with field-level operations, then layer on lexicographic scan, TTL, and finally a `backup` / `restore` snapshot system. Each level is unlocked only after the prior level passes. Requirements You implement a database where each top-level key holds multiple field → value pairs (both strings). Level 1 — basic operations set(key, field, value) get(key, field) delete(key, field) Level 2 — listing scan(key) → ["field(value)", ...] returned in lexicographic field order. scan_by_prefix(key, prefix) — same shape, filtered by field prefix. Level 3 — timestamps and TTL All operations gain _at variants that take a timestamp argument. set_at_with_ttl(key, field, value, timestamp, ttl) defines a valid interval [timestamp, timestamp + ttl). Expired fields must not appear in get_at, scan_at, or any prefix scan. Test cases promise that time only moves forward, and never mix timestamped and non-timestamped APIs in the same test. Level 4 — backup and restore backup(timestamp) snapshots the database state, preserving each field's remaining TTL relative to that timestamp. restore(timestamp, timestamp_to_restore) restores the latest backup whose backup-timestamp is ≤ timestamp_to_restore; expirations are recomputed forward from timestamp. Notes The platform unlocks higher levels only when the lower levels pass — design Level 1 with Levels 3–4 in mind so you do not have to re-architect the storage when TTL arrives. A common trap is to store TTL as an absolute expiry timestamp; restore then becomes painful because you need the remaining TTL at backup time. Storing (value, set_at, ttl) and computing expiry on read is much easier to back up. Lexicographic scan is over fields within a key, not over keys. Backups should be deep copies — sharing references with the live store causes Level 4 tests to flap when later writes mutate the backed-up state. The OA platform issues no hidden test cases beyond what is shown; failures are deterministic and reproducible. Preparation Start from the canonical four-level in-memory DB pattern (a textbook CodeSignal format) and write it once end-to-end before the round. Practice the TTL → backup transition: implement Level 3 with (value, set_at, ttl) tuples so Level 4 only needs remaining = ttl - (backup_ts - set_at). Time-budget: 45 min on Level 1+2, 60 min on Level 3, 90 min on Level 4, 45 min buffer for Level-3 / Level-4 edge cases. The same family appears at other labs (Stripe / Coinbase In-Memory DB) with the same level structure — cross-train if you have done either.