Problems
TTL Key-Value Store: Four Levels
Medium·Tagsai-coding-interview4-levelin-memory-databasettlbackup-restore
Problem Statement
This is a four-level build of an in-memory key-value store, in the progressive format that many companies use for coding rounds: you start with a small working class, and each level adds a requirement on top of the last. Work through the levels in order. Use the built-in AI assistant the way you would at work: read the code first, ask about one level at a time, and run the tests after every change.
The levels get harder in a specific way. Levels 1 and 2 are small. Level 3 adds expiry, which changes what the store has to remember about each key, so you will need to change how data is stored. Level 4 adds backup and restore, where the obvious implementation compiles, passes the simple test, and is still wrong.
Time is an argument, not the clock. Every method takes a `timestamp`. Treat it as the current time for that call and never read the system clock. Timestamps strictly increase from one call to the next.
The API
```java
class KeyValueStore {
void set(int timestamp, String key, String value);
String get(int timestamp, String key);
boolean delete(int timestamp, String key);
List<String> scan(int timestamp, String prefix);
void setWithTtl(int timestamp, String key, String value, int ttl);
int backup(int timestamp);
void restore(int timestamp, int backupTimestamp);
}
```
Level 1: Fix the bug (about 10 minutes)
`set`, `get` and `delete` are already written, and one of them has a bug.
- `set` stores the value, replacing any previous value for that key.
- `get` returns the value, or `null` if the key is not in the store.
- `delete` removes the key and returns `true` if the key was in the store, or `false` if it was not.
Level 2: Prefix scan (about 15 minutes)
`scan(timestamp, prefix)` returns every key that starts with `prefix`, formatted as `key(value)` and sorted by key in ascending string order. An empty prefix matches every key. Matching is case-sensitive. When nothing matches, return an empty list, not `null`.
Level 3: Expiry (about 20 minutes)
`setWithTtl(timestamp, key, value, ttl)` stores a key that is alive from `timestamp` up to, but not including, `timestamp + ttl`. A key set at 10 with a TTL of 5 is alive at 10 through 14 and gone at 15. `ttl` is always positive.
- `get`, `delete` and `scan` treat an expired key as if it is not in the store. `delete` on an expired key returns `false`.
- `set` without a TTL makes the key permanent again, even if it had a TTL before.
- `setWithTtl` on an existing key replaces both its value and its expiry.
Level 4: Backup and restore (about 25 minutes)
`backup(timestamp)` saves a copy of every key that is alive at `timestamp` and returns how many keys it saved. Later changes to the store must not change a saved backup.
`restore(timestamp, backupTimestamp)` replaces the whole store with the latest backup taken at or before `backupTimestamp`. If there is no such backup, throw `IllegalArgumentException` and leave the store unchanged.
A key with a TTL keeps the time it had left when the backup was taken, counted from the restore. A key with 10 time units left at backup time, restored at 100, is alive up to 110. Permanent keys stay permanent.
The tests
Each level has one visible test and one hidden test. The hidden tests check the edges of the same rules.
1. level1_delete_reports_missing: `delete` returns `false` for a key that is not in the store.
2. level1_basic_operations_intact (hidden): overwrite, re-set after delete, and empty-string values still work.
3. level2_scan_by_prefix: `scan` returns matching keys in sorted order.
4. level2_scan_edge_cases (hidden): empty prefix, no match, prefix equal to a whole key, deleted keys, case sensitivity.
5. level3_ttl_expires: a key with a TTL is readable while alive and gone after it expires.
6. level3_ttl_edge_cases (hidden): the exact expiry boundary, scan and delete on expired keys, and replacing a key's TTL.
7. level4_backup_and_restore: restore brings back the state at backup time.
8. level4_restore_edge_cases (hidden): choosing among several backups, remaining TTL after restore, restoring the same backup twice, and a restore with no backup.
Examples
Example 1
Input
set(1, "apple", "red"); delete(2, "apple"); delete(3, "apple")Output
"true, then false"Why
The second delete finds nothing to remove, so it returns false.
Example 2
Input
set(1, "user:2", "bo"); set(2, "user:10", "al"); set(3, "user:1", "cy"); scan(4, "user:")Output
"[\"user:1(cy)\", \"user:10(al)\", \"user:2(bo)\"]"Why
Keys are sorted as strings, so "user:10" comes before "user:2".
Example 3
Input
setWithTtl(10, "k", "v", 5); get(14, "k"); get(15, "k")Output
"\"v\", then null"Why
The key is alive from 10 up to, but not including, 15.
Example 4
Input
setWithTtl(10, "s", "v", 20); backup(20); restore(100, 20); get(109, "s"); get(110, "s")Output
"\"v\", then null"Why
At the backup, "s" had 10 time units left. After a restore at 100 it is alive up to 110.
Constraints
- •Every method takes a timestamp that acts as the current time. Never read the system clock.
- •Timestamps strictly increase from one call to the next.
- •get returns null for a key that is missing or expired.
- •scan returns "key(value)" strings sorted by key in ascending string order, and an empty list when nothing matches.
- •A key set with setWithTtl(t, key, value, ttl) is alive for timestamps t through t + ttl - 1.
- •backup returns the number of live keys it saved. restore uses the latest backup taken at or before backupTimestamp, or throws IllegalArgumentException if there is none.
- •After a restore, a key with a TTL has the same time left that it had when the backup was taken.
- •Keep the public method signatures. The tests call them directly.
Hints
Stuck? Reveal a nudge toward the right pattern, one step at a time.
Hint 1
Start by running the tests. Each failure message shows the exact call, the value the test expected and the value your code returned, so you can reproduce it by hand.
Hint 2
Level 1: delete checks whether the key is still there after removing it, which is always true. It should report whether the key was there before. Map.remove returns the previous value, or null if there was none.
Hint 3
Level 2: HashMap does not keep keys in any order. Collect the matching keys, sort them, then build the key(value) strings. Sorting is by string, so "user:10" comes before "user:2".
Hint 4
Level 3: a String value alone cannot tell you when a key expires. Store a small object per key that holds the value and the time it expires, and give permanent keys an expiry that is never reached.
Hint 5
Level 3: a key set at t with TTL ttl is alive while timestamp < t + ttl. Using <= keeps it alive one tick too long. Every read path (get, delete, scan) has to apply the same check.
Hint 6
Level 4: a backup has to be a copy. If you save a reference to the live map, every later set and delete also changes the backup.
Hint 7
Level 4: if you restore the saved expiry times as they are, keys that were alive at backup time can be expired the moment they come back. Work out how much time each key had left at the backup, then add that to the restore timestamp.
Hint 8
Level 4: TreeMap.floorEntry(backupTimestamp) returns the latest backup at or before that time, or null when there is none.
Hint 9
Using the assistant: it sees your code and your last run. Ask it about one level at a time and read its change before you run it. For Level 4, ask it what happens to a key with a TTL that is backed up at 20 and restored at 100, and check its answer against the rules above.