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 ```python 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.

Implement an **in-memory database** that stores fields per record and supports point operations plus two ordered scans. Implement the function: ```python 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 ```text 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 `SET`s 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.

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: ```python 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.

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 ```python 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.