Design an in-memory database with TTL and backups
Company: Coinbase
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Take-home Project
You are asked to implement a small in-memory “database” that evolves across 4 parts. In each part you may reuse your previous code and only add/extend methods.
### Data model
Each record is identified by a **string key** and stores a **string value**.
Time is represented by an integer timestamp `t` (monotonically increasing in tests).
---
## Part 1 — Basic read/write
Implement a database supporting:
- `put(key, value, t)`: store `value` for `key`.
- `get(key, t) -> value | null`: return the currently stored value for `key`, or `null` if missing.
Notes:
- If `put` is called multiple times for the same key, the latest write should be returned.
---
## Part 2 — Scan
Add:
- `scan(prefix, t) -> List<(key, value)>`: return all key/value pairs whose **key starts with `prefix`**.
Requirements:
- Results must be sorted by key in lexicographic order.
---
## Part 3 — Expiration (TTL)
Extend `put` to optionally accept a TTL:
- `put(key, value, t, ttlSeconds)` means the entry is valid for timestamps in the half-open interval `[t, t + ttlSeconds)`. After that it is expired.
Update `get` and `scan` so that expired items are not returned.
Clarifications:
- If a key is overwritten with a new `put`, the new value/TTL replaces the old one.
- Keys without TTL never expire.
---
## Part 4 — Backup / Restore
Add support for backups:
- `backup(t) -> backupId`: captures the database state at time `t` (only non-expired entries at time `t`).
- `restore(backupId, t)`: restores the database to exactly the state captured in that backup.
TTL behavior on restore:
- If an entry had remaining TTL at backup time, it should still expire after the remaining time elapses following the restore (i.e., expiration is based on the original timestamps/remaining lifetime, not “reset” to a fresh TTL).
---
### What you need to deliver
Implement the required methods so that all provided test cases pass.
### Constraints (typical for this style of OA)
- Up to ~10^5 operations.
- Keys/values are short strings.
- Aim for efficient lookups and scans.
Quick Answer: This question evaluates skills in designing and implementing in-memory data structures, TTL-based expiration, lexicographic prefix scans, and backup/restore snapshot semantics within the Coding & Algorithms domain.
Part 1: Basic read/write
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]`
- `[]` → `[]`
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
Input: [['put', 'a', 'x', 1], ['get', 'a', 2], ['put', 'a', 'y', 3], ['get', 'a', 4], ['get', 'b', 5]]
Expected Output: ['x', 'y', None]
Explanation: The second put overwrites key 'a'. Key 'b' was never written.
Input: [['get', 'missing', 1]]
Expected Output: [None]
Explanation: Edge case: reading a missing key returns None.
Input: []
Expected Output: []
Explanation: Edge case: no operations means no outputs.
Input: [['put', 'k1', 'v1', 1], ['put', 'k2', 'v2', 2], ['get', 'k1', 3], ['get', 'k2', 4]]
Expected Output: ['v1', 'v2']
Explanation: Multiple keys are stored independently.
Solution
def solution(operations):
db = {}
out = []
for op in operations:
if op[0] == 'put':
_, key, value, _ = op
db[key] = value
else:
_, key, _ = op
out.append(db.get(key))
return outExplanation
## Approach
This is the simplest version of a versioned key-value store: there is no version lookup yet, so we only ever need the **latest** value written for each key.
**Data structure.** A single Python `dict` (`db`) maps each `key` to its most recently stored `value`. A second list `out` collects the results of every `get`, in order, so the function returns one answer per read.
**Processing.** We iterate through `operations` once, in input order. Each operation is a list whose first element is the command:
- `('put', key, value, t)` — destructure with `_, key, value, _ = op` and assign `db[key] = value`. Because we always overwrite, the dict naturally holds only the latest write, which is exactly what the problem says matters. The timestamp `t` is unpacked but ignored — in Part 1 it has no effect on behavior.
- `('get', key, t)` — destructure `_, key, _ = op` and append `db.get(key)`. Using `dict.get` returns `None` automatically when the key was never written, satisfying the "return `None` if the key does not exist" requirement without a separate membership check.
**Why it's correct.** Operations are applied in the given order, so when a `get` runs, `db[key]` reflects every `put` that preceded it — i.e. the latest value. Keys never written are absent from the dict, and `get` yields `None` for them. The verified tests confirm overwrite (`x` → `y`), missing-key reads, and the empty-input edge case.
Time complexity: O(q) total for q operations; each put and get is O(1) average (dict insert/lookup).. Space complexity: O(k + g), where k is the number of distinct keys stored and g is the number of get operations (the size of the output list)..
Hints
- A hash map from key to value is enough for this part.
- When the same key is written again, simply replace the old value.
Part 2: Scan by prefix
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.
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
Examples
Input: [['put', 'apple', '1', 1], ['put', 'app', '2', 2], ['put', 'banana', '3', 3], ['scan', 'app', 4]]
Expected Output: [[['app', '2'], ['apple', '1']]]
Explanation: Only keys starting with 'app' are returned, sorted lexicographically.
Input: [['put', 'car', 'red', 1], ['put', 'cat', 'blue', 2], ['put', 'car', 'green', 3], ['get', 'car', 4], ['scan', 'ca', 5]]
Expected Output: ['green', [['car', 'green'], ['cat', 'blue']]]
Explanation: Overwriting a key changes both get and scan results.
Input: [['put', 'b', '2', 1], ['put', 'a', '1', 2], ['scan', '', 3]]
Expected Output: [[['a', '1'], ['b', '2']]]
Explanation: Edge case: an empty prefix matches all keys.
Input: [['put', 'dog', '1', 1], ['scan', 'z', 2], ['get', 'cat', 3]]
Expected Output: [[], None]
Explanation: Edge case: no keys match the prefix, and a missing key returns None.
Solution
def solution(operations):
from bisect import bisect_left
db = {}
keys = []
out = []
for op in operations:
cmd = op[0]
if cmd == 'put':
_, key, value, _ = op
if key not in db:
i = bisect_left(keys, key)
keys.insert(i, key)
db[key] = value
elif cmd == 'get':
_, key, _ = op
out.append(db.get(key))
else: # scan
_, prefix, _ = op
i = bisect_left(keys, prefix)
cur = []
while i < len(keys) and keys[i].startswith(prefix):
k = keys[i]
cur.append([k, db[k]])
i += 1
out.append(cur)
return outExplanation
**Approach.** We process operations in order while keeping two structures: a dict `db` mapping each key to its current value, and a list `keys` holding the *distinct* keys in lexicographic order. Timestamps are ignored for behavior here — `put` always overwrites, so only the latest value matters.
**put(key, value, t).** Set `db[key] = value`. If the key is new, find its sorted insertion point with `bisect_left(keys, key)` and `insert` it there, so `keys` stays sorted. Repeated puts to an existing key only update `db` and never touch `keys`, keeping it a set of unique keys.
**get(key, t).** Return `db.get(key)`, which yields the stored value or `None` if absent.
**scan(prefix, t).** Every key that starts with `prefix` is lexicographically ≥ `prefix` and — crucially — these matching keys form a *contiguous block* in sorted order. So we jump to the first candidate with `bisect_left(keys, prefix)`, then walk forward collecting `[k, db[k]]` while `keys[i].startswith(prefix)` holds. We stop at the first non-matching key. An empty prefix starts at index 0 and matches everything.
**Why it's correct.** `keys` is always sorted and deduplicated, so binary search lands exactly on the start of the prefix range, and `startswith` cleanly bounds the end. Results come out sorted by construction because we iterate the sorted list. `db` always reflects the most recent `put`, so values returned by both `get` and `scan` are current.
Time complexity: put: O(n) worst case (list insertion shifts elements; the bisect is O(log n)). get: O(1) average. scan: O(log n + m·L), where m is the number of matched keys and L the key/prefix length checked by startswith. Over all operations, sorted-list maintenance dominates at O(n²) worst case for n puts of distinct keys.. Space complexity: O(n), where n is the number of distinct keys: each key is stored once in `db` and once in `keys`. Scan additionally builds an output list of size up to m for the matched pairs..
Hints
- Use one structure for fast key -> value lookup and another to keep keys ordered.
- For scan, binary search can help you jump to the first possible matching key.
Part 3: Expiration with TTL
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`.
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
Input: [['put', 'a', 'x', 1, 5], ['get', 'a', 1], ['get', 'a', 5], ['get', 'a', 6]]
Expected Output: ['x', 'x', None]
Explanation: The key is valid for times 1 through 5, and expires at time 6.
Input: [['put', 'k', 'v1', 1, 2], ['get', 'k', 2], ['put', 'k', 'v2', 4], ['get', 'k', 5]]
Expected Output: ['v1', 'v2']
Explanation: A later put replaces the old value and expiration.
Input: [['put', 'app', '1', 1, 3], ['put', 'apple', '2', 2], ['put', 'ape', '3', 3, 1], ['scan', 'ap', 3], ['scan', 'ap', 4]]
Expected Output: [[['ape', '3'], ['app', '1'], ['apple', '2']], [['apple', '2']]]
Explanation: At time 3 all three keys are visible. At time 4 only the non-expiring key remains.
Input: [['put', 'z', 'gone', 10, 0], ['get', 'z', 10], ['scan', 'z', 10]]
Expected Output: [None, []]
Explanation: Edge case: TTL 0 means the valid interval is [10, 10), so the key is never visible.
Solution
def solution(operations):
from bisect import bisect_left
db = {}
keys = []
out = []
def alive(entry, t):
if entry is None:
return False
_, expire_at = entry
return expire_at is None or t < expire_at
for op in operations:
cmd = op[0]
if cmd == 'put':
if len(op) == 5:
_, key, value, t, ttl = op
expire_at = t + ttl
else:
_, key, value, t = op
expire_at = None
if key not in db:
i = bisect_left(keys, key)
keys.insert(i, key)
db[key] = (value, expire_at)
elif cmd == 'get':
_, key, t = op
entry = db.get(key)
out.append(entry[0] if alive(entry, t) else None)
else: # scan
_, prefix, t = op
i = bisect_left(keys, prefix)
cur = []
while i < len(keys) and keys[i].startswith(prefix):
k = keys[i]
entry = db.get(k)
if alive(entry, t):
cur.append([k, entry[0]])
i += 1
out.append(cur)
return outExplanation
**Approach.** Operations arrive in chronological order, so we process them in a single pass while maintaining two structures: a dict `db` mapping `key -> (value, expire_at)`, and a *sorted* list `keys` of all distinct keys ever written.
**Expiration model.** Each entry stores `expire_at`. A TTL put (`len(op) == 5`) sets `expire_at = t + ttl`; a plain put sets `expire_at = None` (never expires). The helper `alive(entry, t)` returns `expire_at is None or t < expire_at`, which is exactly the half-open interval `[start, start + ttl)`. This makes a `ttlSeconds` of 0 expire immediately (`t < t` is false), matching the `'z'` test.
**put.** Overwriting a key just reassigns `db[key]`, so a rewrite replaces both value and TTL. Only when the key is *new* do we insert it into `keys` at the position found by `bisect_left`, keeping the list lexicographically sorted.
**get.** A single dict lookup, returning the value if `alive` else `None`.
**scan.** `bisect_left(keys, prefix)` jumps to the first key that could match, then we walk forward while `keys[i].startswith(prefix)`, collecting `[key, value]` only for alive entries. Because `keys` is already sorted, the output is sorted by key with no extra sort.
**Correctness.** Chronological processing means every `expire_at` is computed from the put's own timestamp, and `alive` is evaluated against the query time `t`, so expired entries are never returned by `get` or `scan`. Rewrites cleanly supersede prior state because the dict holds only the latest tuple per key.
Time complexity: put: O(n) worst case (inserting a new key into the sorted list shifts elements); get: O(1) average dict lookup; scan: O(log n + m) where m is the number of keys matching the prefix. Overall O(n^2) worst case if every op is a put of a new key.. Space complexity: O(n), where n is the number of distinct keys ever written (stored once in the dict and once in the sorted keys list)..
Hints
- Instead of storing TTL directly, store an absolute expiration time.
- Be careful with the half-open interval: when current time equals expire time, the item is already expired.
Part 4: Backup and restore with TTL preservation
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']]]
```
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 used in restore is always valid
- Only non-expired entries at backup time are stored in that backup
Examples
Input: [['put', 'a', 'x', 1], ['backup', 2], ['put', 'a', 'y', 3], ['get', 'a', 4], ['restore', 1, 5], ['get', 'a', 6]]
Expected Output: [1, 'y', 'x']
Explanation: After restore, the database returns to the exact state saved in backup 1.
Input: [['put', 'temp', 'v', 1, 10], ['backup', 5], ['restore', 1, 20], ['get', 'temp', 25], ['get', 'temp', 26]]
Expected Output: [1, 'v', None]
Explanation: At backup time 5, the key has 6 seconds remaining. After restore at 20, it expires at 26.
Input: [['put', 'a', '1', 1, 2], ['put', 'b', '2', 2], ['backup', 4], ['restore', 1, 10], ['scan', '', 11]]
Expected Output: [1, [['b', '2']]]
Explanation: Key 'a' is already expired at backup time, so it is not saved.
Input: [['backup', 1], ['put', 'x', '1', 2], ['restore', 1, 3], ['get', 'x', 4], ['scan', '', 4]]
Expected Output: [1, None, []]
Explanation: Edge case: restoring an empty backup clears the database.
Solution
def solution(operations):
from bisect import bisect_left
state = {}
keys = []
backups = {}
next_backup_id = 1
out = []
def alive(entry, t):
if entry is None:
return False
_, expire_at = entry
return expire_at is None or t < expire_at
for op in operations:
cmd = op[0]
if cmd == 'put':
if len(op) == 5:
_, key, value, t, ttl = op
expire_at = t + ttl
else:
_, key, value, t = op
expire_at = None
if key not in state:
i = bisect_left(keys, key)
keys.insert(i, key)
state[key] = (value, expire_at)
elif cmd == 'get':
_, key, t = op
entry = state.get(key)
out.append(entry[0] if alive(entry, t) else None)
elif cmd == 'scan':
_, prefix, t = op
i = bisect_left(keys, prefix)
cur = []
while i < len(keys) and keys[i].startswith(prefix):
k = keys[i]
entry = state.get(k)
if alive(entry, t):
cur.append([k, entry[0]])
i += 1
out.append(cur)
elif cmd == 'backup':
_, t = op
snapshot = {}
snap_keys = []
for k in keys:
entry = state.get(k)
if alive(entry, t):
value, expire_at = entry
remaining = None if expire_at is None else expire_at - t
snapshot[k] = (value, remaining)
snap_keys.append(k)
backup_id = next_backup_id
next_backup_id += 1
backups[backup_id] = (snapshot, snap_keys)
out.append(backup_id)
else: # restore
_, backup_id, t = op
snapshot, snap_keys = backups[backup_id]
state = {}
keys = snap_keys[:]
for k in keys:
value, remaining = snapshot[k]
expire_at = None if remaining is None else t + remaining
state[k] = (value, expire_at)
return outExplanation
The database stores each key in a `state` dict as `(value, expire_at)`, where `expire_at = t + ttl` is the **absolute** expiry time, or `None` for non-expiring values. A parallel sorted list `keys` holds the live key names so that `scan` can emit results in lexicographic order without re-sorting.
**Key helper.** `alive(entry, t)` returns `True` when the entry exists and either has no TTL or hasn't reached its expiry: `expire_at is None or t < expire_at`. Expiry is lazy — nothing is deleted; reads simply ignore dead entries.
**Operations.**
- `put`: compute `expire_at`; if the key is new, `bisect_left` finds its slot in `keys` and inserts it to keep the list sorted. Overwrites reuse the existing slot.
- `get`: return the value if `alive`, else `None`.
- `scan(prefix)`: `bisect_left` jumps to the first key ≥ `prefix`, then walks forward while `keys[i].startswith(prefix)`, collecting `[key, value]` for alive entries — already in sorted order.
**Backups (the crux).** `backup(t)` snapshots only currently-alive keys, but stores **remaining TTL** (`expire_at - t`) instead of the absolute expiry, plus the snapshot's sorted key list. It assigns the next integer id (starting at 1) and returns it. `restore(backupId, t)` rebuilds `state`/`keys` from the snapshot, converting remaining TTL back to absolute via `t + remaining`. This is why an item with, say, 5 s left at backup expires 5 s after restore — not on a fresh full TTL — satisfying the preservation requirement.
Time complexity: O(n) per put/backup/restore (sorted-list insert and full-key snapshot/rebuild are linear in the number of keys), O(1) average per get, O(log n + m) per scan (binary-search seek plus m matching keys); overall O(total_ops × n) worst case.. Space complexity: O(n + B), where n is the current number of live keys and B is the total size of all stored backups (each backup keeps a copy of its alive entries and their sorted key list)..
Hints
- At backup time, save only live entries. For expiring entries, save the remaining lifetime instead of the original expiration time.
- On restore at time t, rebuild each saved expiration time as t + remaining_lifetime.