Build a Temporal In-Memory Database with Backup and Restore

Question

Process timestamped commands over records that map string keys to string field/value pairs. Timestamps are unique and strictly increasing; each command returns one string.

```python
def solution(queries: list[list[str]]) -> list[str]: ...
```

## Command contract

Every command is a list of strings. `t`, `ttl` and `target` are decimal integer strings. Command timestamps `t` are nonnegative and strictly increasing across the entire input; `ttl` is positive. Keys and field names are nonempty strings. Values may be empty strings. Inputs contain only the commands below with the stated argument counts. Return one output string for each input command, in order.

| Command | Output |
| --- | --- |
| `["SET", t, key, field, value]` | `""`; replace the field with a permanent value. |
| `["SET_WITH_TTL", t, key, field, value, ttl]` | `""`; replace the field with a value expiring at `int(t) + int(ttl)`. |
| `["GET", t, key, field]` | The live value, or `""` if absent. |
| `["DELETE", t, key, field]` | `"true"` if a live field was deleted; otherwise `"false"`. |
| `["COMPARE_AND_SET", t, key, field, expected, value]` | `"true"` only if the field is live and equals `expected`; replace it with the permanent `value`. Otherwise `"false"` without mutation. |
| `["COMPARE_AND_DELETE", t, key, field, expected]` | `"true"` only if the field is live and equals `expected`; delete it. Otherwise `"false"` without mutation. |
| `["SCAN", t, key]` | Live fields in ascending field-name order, as `field(value)` joined by `", "`; `""` if none. |
| `["SCAN_BY_PREFIX", t, key, prefix]` | The same format, including only field names starting with `prefix`; an empty prefix matches all fields. |
| `["BACKUP", t]` | `""`; save the live state and remaining TTLs at `t`. |
| `["RESTORE", t, target]` | `""`; replace state from the latest backup timestamp at or before `target`. If none exists, leave state unchanged. |

A live empty value is distinct from an absent field for conditional operations, even though `GET` returns `""` for both. Restoring does not remove existing backups. A restored TTL begins at the restore timestamp, not the original write timestamp. The base implementation processes current-state commands only; historical reads in the final follow-up are a design discussion, not another command in this interface.

For example, `SET_WITH_TTL` at `1` with TTL `4`, followed by a backup at `3` and restore at `10`, gives the restored value two remaining time units: it is present at `11` and absent at `12`.

## Requirements

- Support set, get, delete, compare-and-set, and compare-and-delete.
- Scan all live fields, or fields with a prefix, ordered by field name and formatted deterministically.
- Support values with TTL. A value written at `t` for `ttl` is live on `[t, t + ttl)`; every operation treats expired values as absent.
- A later write replaces both value and lifetime; a write without TTL is permanent.
- Backup captures all live values and their remaining lifetimes.
- Restore replaces current state with the newest backup at or before a requested historical timestamp, restarting each saved remaining lifetime from the restore time.
- A failed conditional operation must not mutate state.

## Suggested implementation approach

These milestones organize the complete task above; they are not additional commands or separate assessed stages.

1. Implement current-value operations and conditional mutation.
2. Add ordered scans and prefix scans.
3. Add precise lazy expiration.
4. Add backup and restore with paused TTL countdowns.

## Design discussion

How would you extend the interface for historical reads? Discuss efficient version lookup and compaction of old versions. No historical-read command is required by the current interface.