Implement a simple **in-memory key-value store** that processes a sequence of operations and returns the result of every read. ## Function ``` solution(operations) ``` `operations` is a list of operations. Apply them **in the given order** and return a list containing one entry for each `get` operation, in the order those reads occur. ## Input format Each operation is itself a list whose first element is the command name: - **Put** — `['put', key, value, t]` Store the string `value` under the string `key`. If `key` already has a value, overwrite it so the key always holds its most recent write. - **Get** — `['get', key, t]` Read the value currently stored for `key`. Here `key` and `value` are short strings, and `t` is an integer timestamp. ## Output Return a list with **one element per `get` operation**, in read order: - the latest value stored for that `key`, or - `None` if the key has never been written. `put` operations produce no output. ## Timestamps Every operation carries a timestamp `t`, and timestamps are **nondecreasing** across the input. In this part, `t` does **not** affect behavior — a `get` always returns the most recent write to its key. (It is included for consistency with later parts.) ## Constraints - `0 <= len(operations) <= 10^5` - Keys and values are short strings. - Timestamps are integers and are nondecreasing across operations. - Only the latest write for a key matters. ## Examples - `[['put', 'a', 'x', 1], ['get', 'a', 2], ['put', 'a', 'y', 3], ['get', 'a', 4], ['get', 'b', 5]]` → `['x', 'y', None]` (`a` reads `x`, then is overwritten to `y`; `b` was never written, so it reads `None`.) - `[['get', 'missing', 1]]` → `[None]` - `[]` → `[]`

Implement an **in-memory key/value database** that supports lookups and **prefix scans**, extending the basic store with a `scan` operation. ### Function ``` solution(operations) ``` You are given a list `operations`, where each element is an array describing one operation. Process the operations **in order** and return a list containing the results of the operations that produce output (described below). ### Operations Each operation is an array whose first element is the command name: - **`['put', key, value, t]`** — Store `value` under `key`. If `key` already exists, **overwrite** its value with `value`. This operation produces **no output**. - **`['get', key, t]`** — Append the **current value** stored under `key` to the result. If `key` is not present, append `None` (null). - **`['scan', prefix, t]`** — Append a list of all currently stored entries whose **key starts with `prefix`**. Each matching entry is represented as the pair `[key, value]`, and the list is **sorted lexicographically by key**. If no key matches, append an **empty list** `[]`. Here `key`, `value`, and `prefix` are short strings, and `t` is an integer timestamp. ### Output Return a list whose entries are, in order, the results of every `get` and `scan` operation (a `put` contributes nothing): - A `get` contributes a single value (the stored string, or `None` if the key is absent). - A `scan` contributes a list of `[key, value]` pairs, sorted lexicographically by key. ### Rules & notes - Only the **most recent** `put` to a key is in effect; later puts overwrite earlier ones. - For `scan`, a key matches when it **starts with** `prefix`. An **empty prefix `''` matches every stored key**, so the scan returns all entries sorted by key. - **Timestamps** `t` are integers and are **nondecreasing** across the input, but they **do not affect behavior** in this part — you can treat each `put` as simply setting the current value. ### Constraints - `0 <= len(operations) <= 10^5` - Keys, values, and prefixes are short strings. - Timestamps are integers and are nondecreasing across operations. - Scan results must be sorted lexicographically by key. ### Example For the operations: ``` [['put', 'car', 'red', 1], ['put', 'cat', 'blue', 2], ['put', 'car', 'green', 3], ['get', 'car', 4], ['scan', 'ca', 5]] ``` the result is: ``` ['green', [['car', 'green'], ['cat', 'blue']]] ``` The two puts to `car` leave it set to `green`, so `get('car')` returns `'green'`, and `scan('ca')` returns both keys sorted lexicographically.

Implement an in-memory key/value store that supports **time-to-live (TTL) expiration**, then replay a chronological log of operations against it. You are given a list `operations`. Each element is itself a list whose first element is the command name (`'put'`, `'get'`, or `'scan'`), followed by that command's arguments. Process the operations **in the given order** (timestamps are nondecreasing). Return a list containing one result for **each `get` and `scan` operation**, in the order those operations appear. `put` operations produce no output. ## Operations - **`['put', key, value, t]`** — Store `value` under `key` at time `t` with **no expiration** (the value is valid for all times `>= t` until overwritten). - **`['put', key, value, t, ttlSeconds]`** — Store `value` under `key` at time `t` with a TTL. The value is valid only during the **half-open interval `[t, t + ttlSeconds)`** — that is, for every time `T` with `t <= T < t + ttlSeconds`. - **`['get', key, t]`** — Append the current value of `key` at time `t` to the output. If `key` was never written, or its latest entry has expired by time `t`, append `None`. - **`['scan', prefix, t]`** — Append a list of `[key, value]` pairs to the output: one pair for every key that **starts with `prefix`** and whose latest entry is still valid at time `t`. The pairs must be **sorted lexicographically by key**. ## Rules - **Overwrite semantics:** Writing to an existing `key` replaces its previous value *and* its previous TTL. Only the most recently written entry for a key is ever considered. - **Expiration:** An entry written at time `t` with `ttlSeconds` is expired at any query time `T >= t + ttlSeconds`. Expired entries must never be returned by `get` or `scan`. - In particular, a TTL of `0` means the entry is **already expired** at the instant it is written (since `t < t + 0` is never true). - `get` returns the scalar value (or `None`); `scan` returns a list of `[key, value]` pairs. ## Function signature ```python def solution(operations): pass ``` ## Constraints - `0 <= len(operations) <= 10^5` - Keys, values, and prefixes are short strings. - Timestamps are integers and are nondecreasing across operations. - `0 <= ttlSeconds <= 10^9` - An entry with TTL is valid exactly for times `t` such that `start_time <= t < start_time + ttlSeconds`. ## Examples **Example 1** ``` operations = [['put', 'a', 'x', 1, 5], ['get', 'a', 1], ['get', 'a', 5], ['get', 'a', 6]] output = ['x', 'x', None] ``` `'a'` is valid on `[1, 6)`: it is present at times 1 and 5, but expired at time 6. **Example 2** ``` operations = [['put', 'k', 'v1', 1, 2], ['get', 'k', 2], ['put', 'k', 'v2', 4], ['get', 'k', 5]] output = ['v1', 'v2'] ``` At time 2, `'k'` still holds `'v1'` (valid on `[1, 3)`). The second `put` overwrites it with `'v2'` (no TTL), so the later `get` returns `'v2'`. **Example 3** ``` operations = [['put', 'app', '1', 1, 3], ['put', 'apple', '2', 2], ['put', 'ape', '3', 3, 1], ['scan', 'ap', 3], ['scan', 'ap', 4]] output = [[['ape', '3'], ['app', '1'], ['apple', '2']], [['apple', '2']]] ``` At time 3, all three keys are valid, returned sorted by key. At time 4, `'app'` (valid on `[1, 4)`) and `'ape'` (valid on `[3, 4)`) have expired, leaving only `'apple'`. **Example 4** ``` operations = [['put', 'z', 'gone', 10, 0], ['get', 'z', 10], ['scan', 'z', 10]] output = [None, []] ``` A TTL of `0` expires immediately, so `'z'` is never visible to `get` or `scan`.

Implement an in-memory key-value database that supports time-based expiry (TTL), plus point-in-time **backup** and **restore** where a restored entry keeps its *remaining* TTL rather than getting a fresh one. ## Function ```python def solution(operations): ... ``` `operations` is a list of operations to process **in the given order**. Each operation is itself a list whose first element is the operation name. Every timestamp `t` is an integer, and timestamps are **nondecreasing** across operations. Return a list containing the result of each operation **that produces output**, in the order those operations occur. ## Operations Each operation has one of the following shapes: - **`['put', key, value, t]`** — Store `value` under `key` with **no expiry** (it never expires). If `key` already exists, overwrite it. **Produces no output.** - **`['put', key, value, t, ttlSeconds]`** — Store `value` under `key` with a time-to-live of `ttlSeconds`. The entry is considered alive for any time strictly **before** `t + ttlSeconds`, and is expired at or after that time. Overwrites an existing key. **Produces no output.** - **`['get', key, t]`** — Return the stored value for `key` if it exists and is **not expired** at time `t`; otherwise return `None`. **Appends the value (or `None`) to the output.** - **`['scan', prefix, t]`** — Return a list of `[key, value]` pairs for every key that starts with `prefix` and is **not expired** at time `t`, sorted **lexicographically by key**. An empty `prefix` matches all keys. **Appends this list (possibly empty) to the output.** - **`['backup', t]`** — Snapshot the database **as of time `t`**, capturing only entries that are **not expired** at `t`. For each captured entry that has a TTL, store its **remaining** time (`expire_time - t`) rather than an absolute expiry. Assign and return a new integer backup id; ids start at **1** and increase by 1 with each backup. **Appends the backup id to the output.** - **`['restore', backupId, t]`** — Replace the **entire** current database with the state saved in backup `backupId`. For each restored entry that had remaining TTL, it expires that many seconds **after** the restore — i.e. at `t + remaining` — so an entry with, say, 5 seconds of TTL left at backup time will expire 5 seconds after this restore, not on a fresh full TTL. Non-expiring entries stay non-expiring. **Produces no output.** `backupId` is always a valid, previously returned id. ## Expiry rule An entry created (or restored) so that it expires at time `E` is **alive while `t < E`** and **expired once `t >= E`**. Non-expiring entries (`put` without `ttlSeconds`) are always alive until overwritten or replaced by a restore. ## Output The returned list contains, in order, one element per `get` / `scan` / `backup` operation: - `get` → the value or `None` - `scan` → a list of `[key, value]` pairs sorted by key (may be empty) - `backup` → the integer backup id ## Constraints - `0 <= len(operations) <= 10^5` - Keys, values, and prefixes are short strings. - Timestamps are integers and are nondecreasing across operations. - `0 <= ttlSeconds <= 10^9` - `backupId` passed to `restore` is always valid. - Only non-expired entries at backup time are stored in that backup. ## Example ``` operations = [ ['put', 'a', '1', 1, 2], # 'a' expires at t = 3 ['put', 'b', '2', 2], # 'b' never expires ['backup', 4], # at t=4 'a' is already expired -> only 'b' captured; returns 1 ['restore', 1, 10], # restore backup 1; 'b' restored, 'a' is gone ['scan', '', 11] # scan all live keys ] # Output: [1, [['b', '2']]] ```