Design an in-memory database with TTL and backups
Company: Coinbase
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Online Assessment
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.
Overview: 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.
Read the full Coinbase Software Engineer interview experience this question came from
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.
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.
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.
Approach
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.
Approach
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.