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.

Part 1: Basic CRUD on In-Memory Database Fields

Implement a simple in-memory key-value store that supports basic CRUD operations on record fields, then return the results of all read/delete queries.

Each record is identified by a string key, and every key owns a collection of field -> value pairs, where both field and value are strings.

Function

def solution(queries):

queries is a list of operations. Each operation is itself a list whose first element is the operation name. Process the operations in order and return a list containing the output of every GET and DELETE operation, in the order they occur.

Operations

• ['SET', key, field, value] — Insert the field -> value pair under key. If the key does not yet exist, create it. If the field already exists, overwrite its value. Produces no output.

• ['GET', key, field] — Return the stored value for field under key. If the key does not exist, or the key exists but the field does not, return the empty string ''. Appends one value to the output.

• ['DELETE', key, field] — Remove field from key. Return True if the field existed and was removed; otherwise return False. Appends one boolean to the output.

Output

Return a list with one entry per GET and per DELETE, in query order. SET operations contribute nothing, so a run containing only SET operations returns an empty list [].

Examples

Example 1

queries = [
    ['SET', 'user1', 'name', 'alice'],
    ['GET', 'user1', 'name'],
    ['SET', 'user1', 'name', 'bob'],
    ['GET', 'user1', 'name'],
    ['DELETE', 'user1', 'name'],
    ['GET', 'user1', 'name'],
    ['DELETE', 'user1', 'name'],
]

Output: ['alice', 'bob', True, '', False]

• GET user1.name → 'alice'
• After the second SET, GET user1.name → 'bob' (overwritten)
• DELETE user1.name → True (field existed)
• GET user1.name → '' (field no longer exists)
• DELETE user1.name → False (already gone)

Example 2

queries = [['GET', 'missing', 'x'], ['DELETE', 'missing', 'x']]

Output: ['', False] — reading or deleting from a key that was never set returns '' and False respectively.

Example 3

queries = [
    ['SET', 'a', 'x', '1'],
    ['SET', 'a', 'y', '2'],
    ['DELETE', 'a', 'x'],
    ['GET', 'a', 'x'],
    ['GET', 'a', 'y'],
]

Output: [True, '', '2'] — deleting one field of a key leaves the key's other fields intact.

Constraints

• 0 <= len(queries) <= 100000
• Each key, field, and value is a string of length 1 to 100.
• Only the operations 'SET', 'GET', and 'DELETE' appear.
• You may assume average O(1) hash-map operations.

Hints

1. A nested dictionary works well: one map from key to another map of field to value.
2. After deleting a field, you may remove the key entirely if it has no fields left.

Approach

The store is modeled as a nested hash map: db maps each string key to an inner dict of field -> value. This two-level structure mirrors the problem exactly — a record (key) owns many field/value pairs — and gives average O(1) access at both levels.

The code processes queries one at a time, dispatching on q[0]:

• SET key field value — db.setdefault(key, {})[field] = value. setdefault returns the existing inner dict, or inserts a fresh {} and returns it if the key is new, in a single step; the field is then assigned (insert or overwrite). Produces no output.

• GET key field — db.get(key, {}).get(field, ''). The chained .get calls make both lookups safe: a missing key yields the empty default {}, and a missing field yields ''. Either way the spec's ''-on-miss rule is satisfied without explicit if checks.

• DELETE key field — first verify key in db and field in db[key]. If present, del db[key][field] removes it; then if that inner dict became empty, del db[key] prunes the now-orphan key so empty records don't accumulate. Append True. Otherwise append False.

Only GET and DELETE append to out, so the returned list contains exactly those outputs in query order (test 4 confirms a SET-only run returns []).

Why it's correct: every operation touches only the targeted key/field; the get-with-default pattern makes absence indistinguishable from an empty record for reads; and pruning empty inner dicts keeps GET behavior unchanged because db.get(key, {}) already treats a missing key as empty. Hash-map semantics give the required average-constant work per query.

• Time complexity: O(Q) average, where Q is the number of queries — each query does a constant number of average-O(1) hash-map operations.
• Space complexity: O(T), where T is the number of distinct (key, field) pairs currently stored (plus O(Q) for the output list in the worst case).

Part 2: Sorted Scan and Prefix Scan in an In-Memory Database

Implement an in-memory database that stores fields per record and supports point operations plus two ordered scans.

Implement the function:

def solution(queries):

Data model

The database holds records. Each record is identified by a string key and stores a collection of field → value pairs, where both field and value are strings. Setting an existing field overwrites its value (last write wins).

Input

• queries — a list of operations, processed in order. Each operation is itself a list of strings whose first element is the operation name, followed by its arguments:

Operation	Form	Behavior	Output
SET	['SET', key, field, value]	Create the record if needed, then set/overwrite field to value.	(none — produces no output)
GET	['GET', key, field]	Look up the value of field in key.	The stored value string, or '' if the key or field does not exist.
DELETE	['DELETE', key, field]	If both the key and field exist, remove that field (and remove the record entirely once it has no remaining fields).	True if a field was removed, otherwise False.
SCAN	['SCAN', key]	Read all fields of key.	A list of strings 'field(value)', sorted lexicographically by field name.
SCAN_BY_PREFIX	['SCAN_BY_PREFIX', key, prefix]	Same as SCAN, but only include fields whose names start with prefix.	A list of strings 'field(value)', sorted lexicographically by field name.

Output

Return a list containing the outputs of every query except SET, in the order the queries were processed. Each non-SET query contributes exactly one entry:

• GET → a value string ('' when absent)
• DELETE → a boolean (True/False)
• SCAN / SCAN_BY_PREFIX → a (possibly empty) list of 'field(value)' strings

Scan formatting and edge cases

• Each matched field is formatted as the literal field name, followed by its value wrapped in parentheses: 'field(value)'.
• Results of SCAN and SCAN_BY_PREFIX are always sorted lexicographically by field name before formatting.
• A scan on a missing key, or a SCAN_BY_PREFIX where no field matches the prefix, returns an empty list [].

Example

queries = [
  ['SET', 'user', 'b', '2'],
  ['SET', 'user', 'a', '1'],
  ['SCAN', 'user'],
  ['SCAN_BY_PREFIX', 'user', 'a'],
]

Output: [['a(1)', 'b(2)'], ['a(1)']]

The two SETs produce no output. SCAN 'user' lists both fields sorted by name. SCAN_BY_PREFIX 'user' 'a' lists only the field starting with 'a'.

Constraints

• 0 <= len(queries) <= 100000
• Each key, field, value, and prefix is a string of length 0 to 100.
• Results for scan operations must be sorted lexicographically by field name.
• Average O(1) hash-map operations may be assumed.

Hints

1. Keep the same nested dictionary structure from basic CRUD.
2. For a scan, collect matching field names first, sort them, then build the 'field(value)' strings.

Approach

Approach. Model the database as a two-level hash map: db maps each record key to an inner dict of field -> value. This gives average O(1) point operations while keeping each record's fields grouped for scanning.

Per-operation logic:

• SET key field value — db.setdefault(key, {})[field] = value lazily creates the inner dict on first write, then sets (or overwrites) the field. No output is appended (SET results are excluded).
• GET key field — db.get(key, {}).get(field, '') safely returns the stored value, or '' when the key or field is missing.
• DELETE key field — if both key and field exist, delete the field; if the inner dict becomes empty, drop the key entirely (so a later SCAN on it returns [] via the missing-key path) and append True; otherwise append False.
• SCAN / SCAN_BY_PREFIX — handled by format_scan. It reads db.get(key, {}) (empty dict for missing keys → empty result), collects fields, optionally filters to those where field.startswith(prefix), sorts them lexicographically, then formats each as 'field(value)'.

Why it's correct. Inner-dict semantics give last-write-wins for repeated SETs on the same field. The empty-record cleanup ensures missing keys and emptied keys behave identically. Sorting before formatting guarantees the required lexicographic-by-field ordering. The prefix is None branch lets one helper serve both scan variants. Only non-SET queries push to out, matching the spec.

• Time complexity: O(1) average for SET/GET/DELETE; O(F log F) per SCAN/SCAN_BY_PREFIX (F = fields under the queried key)
• Space complexity: O(T), where T is the total number of stored (key, field) pairs

Part 3: Timestamped In-Memory Database with TTL

Implement a timestamped in-memory key-value database that supports an optional time-to-live (TTL) on individual fields.

Each top-level key maps to a set of field → value pairs, where both fields and values are strings. Every operation carries an explicit timestamp, and you must answer each query as of that timestamp.

Function

Implement:

def solution(queries):
    ...

queries is a list of operations. Each operation is itself a list of strings whose first element is the operation name. Process the operations in the given order and return a single list containing the results of the operations that produce output (defined below), in the same order they occur.

Operations

All numeric arguments (timestamps and TTLs) are given as decimal strings and should be interpreted as integers.

Operation	Argument layout	Returns
SET_AT	["SET_AT", key, field, value, timestamp]	nothing
SET_AT_WITH_TTL	["SET_AT_WITH_TTL", key, field, value, timestamp, ttl]	nothing
GET_AT	["GET_AT", key, field, timestamp]	the value string, or ""
DELETE_AT	["DELETE_AT", key, field, timestamp]	True or False
SCAN_AT	["SCAN_AT", key, timestamp]	a list of strings
SCAN_BY_PREFIX_AT	["SCAN_BY_PREFIX_AT", key, prefix, timestamp]	a list of strings

Only GET_AT, DELETE_AT, SCAN_AT, and SCAN_BY_PREFIX_AT contribute to the returned list. SET_AT and SET_AT_WITH_TTL produce no output.

Semantics

• SET_AT — Set field = value under key at timestamp, with no expiry. If the field already exists (including one previously set with a TTL), it is overwritten and any prior TTL is removed.

• SET_AT_WITH_TTL — Set field = value under key at timestamp with the given ttl. The field is valid during the half-open interval [timestamp, timestamp + ttl) — i.e. it exists at and after timestamp but is treated as absent once the current time reaches timestamp + ttl. As with SET_AT, this overwrites any existing value/TTL for that field.

• GET_AT — Return the value of field under key as of timestamp. Return "" (empty string) if the key or field does not exist or the field has expired.

• DELETE_AT — Delete field under key as of timestamp. Return True if a live (non-expired) field was actually present and removed; return False if the key/field does not exist or the field has already expired.

• SCAN_AT — Return all live (non-expired) fields under key as of timestamp, formatted as "field(value)", sorted lexicographically by field name. Return an empty list if the key does not exist or has no live fields.

• SCAN_BY_PREFIX_AT — Same as SCAN_AT, but include only fields whose name starts with prefix. Results are likewise formatted as "field(value)" and sorted lexicographically by field name.

Expiry rules

• An expired field behaves exactly as if it were absent for all subsequent gets, deletes, and scans.
• The timestamps supplied across the queries are non-decreasing, so once a field has expired it never becomes valid again.

Output

Return the list of results for the output-producing operations, in query order. For example, a GET_AT that finds a live value contributes that value string; a SCAN_AT contributes its (possibly empty) sorted list; a DELETE_AT contributes True or False.

Constraints

• 0 <= len(queries) <= 100000
• All timestamps are decimal strings representing integers in [0, 10^9].
• All TTL values are positive decimal strings representing integers in [1, 10^9].
• The current timestamps in the queries are non-decreasing.

Examples

Example 1

Input: [['SET_AT_WITH_TTL', 'k', 'a', 'x', '10', '5'], ['GET_AT', 'k', 'a', '10'], ['GET_AT', 'k', 'a', '14'], ['GET_AT', 'k', 'a', '15'], ['DELETE_AT', 'k', 'a', '15']]
Output: ['x', 'x', '', False]

Explanation: The field is valid at times 10 through 14, but not at 15 because the TTL interval is [10, 15).

Example 2

Input: [['SET_AT', 'u', 'name', 'Ann', '1'], ['SET_AT_WITH_TTL', 'u', 'age', '20', '2', '3'], ['SCAN_AT', 'u', '3'], ['SET_AT', 'u', 'age', '21', '4'], ['GET_AT', 'u', 'age', '6'], ['SCAN_BY_PREFIX_AT', 'u', 'a', '6']]
Output: [['age(20)', 'name(Ann)'], '21', ['age(21)']]

Explanation: The TTL version of 'age' is alive at time 3. It is overwritten at time 4 by a non-TTL value, so it still exists at time 6.

Hints

1. Store an absolute expiration time like expire_at = timestamp + ttl instead of storing ttl directly.
2. Because time never goes backward, you can lazily remove expired fields whenever a key is touched.

Approach

Data model. The database is a nested dict db: key -> {field -> [value, expire_at]}. Each field stores its value plus an absolute expiry timestamp (None means no TTL). TTL semantics are the half-open interval [t, t+d), so SET_AT_WITH_TTL records expire_at = t + ttl, and a field is expired exactly when the current time satisfies now >= expire_at.

Lazy expiry. Rather than scheduling deletions, the code expires fields lazily. Every operation first calls purge_key(key, t), which scans that one key's fields, deletes any with expire_at is not None and t >= expire_at, and drops the key entirely if it becomes empty. Because timestamps are non-decreasing, once a field is past its expiry it stays expired, so purging on touch is sufficient — expired fields are guaranteed absent for all subsequent gets, deletes, and scans.

Operations.

• SET_AT / SET_AT_WITH_TTL: purge, then setdefault(key, {})[field] = [value, expire]. A plain SET_AT overwrites any prior TTL with None.
• GET_AT: purge, then return record[field][0] or '' if absent/expired.
• DELETE_AT: purge, then delete the field if present (returning True), else False; the key is removed if it empties.
• SCAN_AT / SCAN_BY_PREFIX_AT: purge, then scan_list collects live fields (optionally filtered by prefix via startswith), sorts them lexicographically, and formats each as field(value).

Results for the four reading ops are appended to out in query order. Correctness rests on always purging before reading and on the absolute-expiry comparison matching the [t, t+d) rule.

• Time complexity: Per point op (SET/GET/DELETE): O(F_k) for the lazy purge of the touched key's F_k fields, then O(1) work. A scan is O(F_k log F_k) due to sorting the live fields. Over n queries the total is O(sum of purge+scan costs); each scan dominated by its sort.
• Space complexity: O(T), where T is the number of currently-live stored fields across all keys (each field holds a [value, expire_at] pair). Scan output adds O(F_k) transient space for the queried key.

Part 4: Backup and Restore in a Timestamped Database with TTL

Implement a timestamped, in-memory key–value database that supports per-field TTL (time-to-live) plus backup and restore operations.

The database is a two-level store: each key maps to a set of fields, and each field holds a string value. A field may optionally have a TTL, after which it expires and is treated as if it never existed. All operations carry an explicit timestamp, so behavior is fully deterministic.

Function

def solution(queries):
    ...

• queries is a list of operations. Each operation is a list of strings: the operation name followed by its arguments.
• Return a list containing the result of every operation that produces output (GET_AT, DELETE_AT, SCAN_AT, SCAN_BY_PREFIX_AT), in the order those operations appear. SET_AT, SET_AT_WITH_TTL, BACKUP, and RESTORE produce no output.

All numeric arguments (timestamps, TTLs, restore arguments) arrive as decimal strings and should be parsed as integers.

Operations

["SET_AT", key, field, value, timestamp] Set field of key to value with no expiry. Overwrites any existing value for that field. No output.

["SET_AT_WITH_TTL", key, field, value, timestamp, ttl] Set field of key to value with a TTL of ttl, so the field expires at timestamp + ttl. Overwrites any existing value. No output.

["GET_AT", key, field, timestamp] Return the current value of field under key as a string. If the field does not exist or has expired at timestamp, return the empty string "".

["DELETE_AT", key, field, timestamp] Delete field from key. Return True if a live (non-expired) field was present and removed at timestamp; otherwise return False.

["SCAN_AT", key, timestamp] Return a list of strings for all live fields under key, sorted ascending by field name, each formatted as "field(value)". If the key has no live fields, return an empty list.

["SCAN_BY_PREFIX_AT", key, prefix, timestamp] Same as SCAN_AT, but only include fields whose name starts with prefix. Results are sorted ascending by field name and formatted as "field(value)".

["BACKUP", timestamp] Take a snapshot of the entire live database at timestamp. No output.

["RESTORE", now, timestamp_to_restore] Replace the entire database with a previously saved snapshot. No output.

Expiry rule

A field with expiry time E is live while current_time < E and expired once current_time >= E. Expired fields must never be returned by GET_AT, counted by DELETE_AT, or listed by either scan operation, and must never be included in a backup.

Backup semantics

• A BACKUP at time t snapshots only the fields that are live at t; already-expired fields are excluded.
• For each TTL field, the snapshot stores the field's remaining TTL (E - t), not its absolute expiry time. Fields without a TTL are stored as non-expiring.

Restore semantics

RESTORE is given two timestamps: the current time now, and a timestamp_to_restore (which may point to any past time).

• Choose the latest backup whose backup time is <= timestamp_to_restore.
• Restore that snapshot as the live database, treating now as the moment of restoration. Each stored field's remaining TTL r is converted back into an absolute expiry of now + r, so the field expires r units after the restore. Fields without a TTL remain non-expiring.
• If no backup has a time <= timestamp_to_restore, restore to an empty database.

Ordering guarantees

The current-time argument used by SET_AT, SET_AT_WITH_TTL, GET_AT, DELETE_AT, SCAN_AT, SCAN_BY_PREFIX_AT, BACKUP, and the now argument of RESTORE are non-decreasing across the query sequence. Only timestamp_to_restore may refer to an arbitrary past time.

Constraints

• 0 <= len(queries) <= 100000
• All timestamps, TTL values, and restore arguments are decimal strings representing integers in [0, 10^9].
• All TTL values are positive.

Examples

Example 1

Input: [['SET_AT_WITH_TTL', 'doc', 'a', '1', '10', '5'], ['BACKUP', '12'], ['GET_AT', 'doc', 'a', '13'], ['RESTORE', '20', '12'], ['SCAN_AT', 'doc', '22'], ['GET_AT', 'doc', 'a', '23']]
Output: ['1', ['a(1)'], '']

Explanation: At backup time 12, the field has 3 units of TTL left. After restoring at time 20, it is alive at 22 and expires at 23.

Example 2

Input: [['SET_AT', 'k', 'x', 'A', '1'], ['BACKUP', '2'], ['SET_AT', 'k', 'x', 'B', '3'], ['BACKUP', '4'], ['DELETE_AT', 'k', 'x', '5'], ['RESTORE', '6', '3'], ['GET_AT', 'k', 'x', '6'], ['RESTORE', '7', '100'], ['GET_AT', 'k', 'x', '7']]
Output: [True, 'A', 'B']

Explanation: Restoring to time 3 uses the backup from time 2, so the value is 'A'. Restoring to time 100 uses the later backup from time 4, so the value is 'B'.

Hints

1. At backup time t, store remaining_ttl = expire_at - t for live TTL fields.
2. Since backups are taken in time order, you can keep them in a list and use binary search to find the latest backup with time <= timestamp_to_restore.

Approach

The database is a nested dict db[key][field] = [value, expire_at], where expire_at is None for non-TTL fields or the absolute expiry time t + ttl. TTL is handled lazily: purge_key(key, t) is called before every operation on a key and drops any field whose expire_at <= t, deleting the key entirely if it becomes empty. This keeps writes O(1) while guaranteeing reads never see stale data.

Point ops (SET_AT, SET_AT_WITH_TTL, GET_AT, DELETE_AT) purge the touched key, then mutate/read the dict. Scans (SCAN_AT, SCAN_BY_PREFIX_AT) purge, filter fields by optional prefix, sort them, and format as field(value).

BACKUP calls build_snapshot(t), which walks the whole db once. For each live field (skipping any already-expired one, so expired fields never enter a backup) it stores the remaining TTL expire_at - t in the snapshot, and rebuilds live_db with absolute expiries preserved. The snapshot and its time t are appended to parallel lists backups / backup_times (times are non-decreasing, so backup_times stays sorted).

RESTORE(now, target) uses bisect_right(backup_times, target) - 1 to find the latest backup with time <= target. If none exists, the db is reset to empty. Otherwise it rehydrates each stored field, converting remaining TTL r back to an absolute expiry now + r (and leaving None as-is). This is correct because storing remaining rather than absolute TTL is exactly what lets the same field expire r units after the restore time, regardless of when the restore happens.

• Time complexity: Point ops are O(1) amortized plus lazy purge of the touched key; each scan is O(F log F) for F fields under the key; BACKUP is O(N) over all live fields; RESTORE is O(log K + L) for K backups and L fields in the chosen snapshot.
• Space complexity: O(N + S), where N is the current number of live fields and S is the total number of fields stored across all retained backups.