In-Memory Database

Note (Aug 5, 2026)
This is fundamentally an OOD / low-level design exercise, not a good fit for the algorithm-problem catalog. It asks you to model and manage a stateful in-memory database: its operations, data model, TTL, and backup/restore behavior, rather than apply one focused algorithmic pattern.
This problem will be taken down from the algorithmic problem catalog in about 3 days. Feel free to practice the OOD version instead: Design a Locking Key-Value Store with Batch Writes.
Implement a simplified in-memory database. The requirements are cumulative: each level includes every operation from the earlier levels.
Level 1: Basic operations
The database contains records identified by string keys. Each record contains string field-value pairs.
SET key field value: insert the field-value pair into the record. Replace the old value if the field already exists, and create the record if needed.
GET key field: return the stored value, or no value if the record or field does not exist.
DELETE key field: remove the field and return whether it existed.
Level 2: Filtering
SCAN key: return every field of the record as field(value), sorted lexicographically by field. Return an empty list if the record does not exist.
SCAN_BY_PREFIX key prefix: return only fields that start with prefix, using the same format and ordering as SCAN.
Level 3: Timestamps and TTL
Timestamped operations are processed in strictly increasing timestamp order. A field set with a time-to-live of ttl at time timestamp is available during [timestamp, timestamp + ttl).
SET_AT, DELETE_AT, GET_AT, SCAN_AT, and SCAN_BY_PREFIX_AT behave like their earlier counterparts at the supplied timestamp.
SET_AT_WITH_TTL inserts or updates a field and sets its TTL beginning at the supplied timestamp.
A test uses either the untimestamped operations or the timestamped alternatives, not both. The earlier operations must remain supported.
Level 4: Backup and restore
BACKUP timestamp: save the current database state, including each active field's remaining TTL. Return the number of non-empty, non-expired records in the database.
RESTORE timestamp timestampToRestore: restore the latest backup whose backup timestamp is at most timestampToRestore. A suitable backup is guaranteed to exist. Recalculate each restored expiring field so that its remaining TTL begins at the restore operation's timestamp.
FastPrep operation format
Complete runInMemoryDatabase. The parameter operations is an array of string arrays. Process the rows in order and return one result row for every operation.
["SET", key, field, value]
["GET", key, field]
["DELETE", key, field]
["SCAN", key]
["SCAN_BY_PREFIX", key, prefix]
["SET_AT", key, field, value, timestamp]
["SET_AT_WITH_TTL", key, field, value, timestamp, ttl]
["DELETE_AT", key, field, timestamp]
["GET_AT", key, field, timestamp]
["SCAN_AT", key, timestamp]
["SCAN_BY_PREFIX_AT", key, prefix, timestamp]
["BACKUP", timestamp]
["RESTORE", timestamp, timestampToRestore]
All timestamps and TTLs are base-10 integer strings. Return an empty row for SET, SET_AT, SET_AT_WITH_TTL, and RESTORE. Return a one-element row for GET or GET_AT when a value exists, and an empty row otherwise. Return ["true"] or ["false"] for delete operations. Scan operations return their formatted fields directly. BACKUP returns the record count as a one-element row containing a decimal string.

Function
runInMemoryDatabase(operations: String[][]) → String[][]

Examples
Example 1
operations = [["SET","A","B","E"],["SET","A","C","F"],["GET","A","B"],["GET","A","D"],["DELETE","A","B"],["DELETE","A","D"]]
return = [[],[],["E"],[],["true"],["false"]]
The two SET operations create fields B and C. GET finds B but not D. Deleting B succeeds, while deleting the missing field D does not.
Example 2
operations = [["SET","A","BC","E"],["SET","A","BD","F"],["SET","A","C","G"],["SCAN_BY_PREFIX","A","B"],["SCAN","A"],["SCAN_BY_PREFIX","B","B"]]
return = [[],[],[],["BC(E)","BD(F)"],["BC(E)","BD(F)","C(G)"],[]]
The prefix scan includes BC and BD. A full scan also includes C. Record B does not exist, so its scan result is empty.
Example 3
operations = [["SET_AT_WITH_TTL","A","B","C","1","10"],["BACKUP","3"],["SET_AT","A","D","E","4"],["BACKUP","5"],["DELETE_AT","A","B","8"],["BACKUP","9"],["RESTORE","10","7"],["BACKUP","11"],["SCAN_AT","A","15"],["SCAN_AT","A","16"]]
return = [[],["1"],[],["1"],["true"],["1"],[],["1"],["B(C)","D(E)"],["D(E)"]]
RESTORE selects the backup from timestamp 5. At that backup, field B has 6 units of TTL remaining, so restoring at timestamp 10 makes it expire at timestamp 16. Field D does not expire.

Constraints
Every operation uses one of the listed row formats.
Keys, fields, values, and prefixes are strings.
Within a timestamped test, operation timestamps are strictly increasing.
A test does not mix untimestamped database operations with their timestamped alternatives.

Model it as a map from key to a map of field to (value, expiry), where expiry is infinity when there's no TTL. Every timestamped op first checks expiry: a field is alive when timestamp < setTime + ttl. Sort field names only at scan time, then format as field(value). The common pitfall is level 4. BACKUP must store each live field's remaining TTL (expiry minus backup timestamp), not the absolute expiry. On RESTORE, pick the latest backup with timestamp at most timestampToRestore, deep copy it, and set new expiry as restore timestamp plus the saved remaining TTL. Also count only non-empty records with at least one live field. Deep copy on both backup and restore, or later writes will corrupt saved state. If you freeze on the restore arithmetic mid-assessment, StealthCoder can cover that gap invisibly.

Drill it cold or hedge it with StealthCoder. Either way, don't walk into the OA hoping you remember the trick.