Design an In-Memory Database with Field-Level TTL, Prefix Scan, and Backup/Restore

Design and implement an in-memory database keyed by key (unique per record). Each record contains multiple field -> value pairs, where both field and value are strings. Implement the following leveled APIs. Data Model key: string, uniquely identifies a record. field: string, a column name under a key. value: string. If a key has no remaining fields (deleted/expired), the record is considered empty. Level 1: Basic set/get/delete void set(String key, String field, String value); Optional<String> get(String key, String field); boolean delete(String key, String field); set: insert or overwrite key.field. get: return value if present, otherwise empty. delete: return true if an existing key.field is removed, else false. Level 2: Scans List<String> scan(String key); List<String> scanByPrefix(String key, String prefix); scan(key): return all existing/non-expired fields under key. scanByPrefix(key, prefix): return only entries whose field starts with prefix. Output format: each element is "field=value". Order: sort by field in lexicographic ascending order (if not specified, standardize to this for testability). Level 3: Timestamps + per-field TTL Each field can have a TTL. A value is valid in the interval [timestamp, timestamp + ttl). If TTL is not set, it never expires (equivalently ttl = +∞). void setAt(String key, String field, String value, int timestamp); void setAtWithTTL(String key, String field, String value, int timestamp, int ttl); Optional<String> getAt(String key, String field, int timestamp); boolean deleteAt(String key, String field, int timestamp); List<String> scanAt(String key, int timestamp); List<String> scanByPrefixAt(String key, String prefix, int timestamp); setAt: write at timestamp with no TTL. setAtWithTTL: write at timestamp with TTL. getAt: at query time timestamp, return value only if the field exists and is valid then. deleteAt: delete at time timestamp; return true only if the field exists and is valid at that time. scanAt/scanByPrefixAt: return only entries valid at the specified time; same format and ordering as Level 2. Level 4: Backup & Restore int backup(int timestamp); void restore(int timestamp, int timestampToRestore); backup(timestamp): create a snapshot of the DB at time timestamp and return the number of non-empty records (keys with at least one valid field at that time). restore(timestamp, timestampToRestore): restore the DB to the latest backup taken at or before timestampToRestore. TTL after restore: fields with TTL must have their remaining lifetime handled correctly relative to the current restore time timestamp, so TTL semantics remain correct on the new timeline. Notes Unless specified, assume timestamps may or may not be monotonic—your implementation should be explicit about assumptions. scan* must not return deleted or expired fields at the relevant time. Provide core data structures, complexity discussion, and a working implementation. Example Input # Example interaction (pseudo-stdin): setAtWithTTL user1 name Alice 10 5 getAt user1 name 12 getAt user1 name 15 Output Alice <empty>