Design an in-memory database with TTL and history
Company: Meta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Take-home Project
Design and implement an in-memory key–field–value store with monotonic timestamps. Keys and fields are strings; values are integers. Provide these APIs and behaviors:
(
1) set(timestamp, key, field, value): store value at key-field.
(
2) get(timestamp, key, field): return the current value or null if key or field does not exist or the value has expired.
(
3) compareAndSet(timestamp, key, field, expectedValue, newValue): if the current value equals expectedValue, atomically set to newValue and return true; otherwise return false.
(
4) compareAndDelete(timestamp, key, field, expectedValue): if the current value equals expectedValue, delete it and return true; otherwise return false.
(
5) scan(timestamp, key): return an array of strings formatted as "field(value)" for all fields under key, sorted alphabetically by field; return an empty array if key does not exist.
(
6) scanByPrefix(timestamp, key, prefix): like scan but only include fields whose names start with prefix.
(
7) setWithTtl(timestamp, key, field, value, ttl): like set, but the value expires automatically at timestamp + ttl; expired values must not appear in get/scan/scanByPrefix results.
(
8) compareAndSetWithTtl(timestamp, key, field, expectedValue, newValue, ttl): like compareAndSet; on success, set newValue with the given ttl.
(
9) getWhen(timestamp, key, field, atTimestamp): return the value that would have been visible at atTimestamp (where atTimestamp < timestamp), or null if none; for example, if value 10 is set at time 10, expires at 12, and value 18 is set at 18, then getWhen(...,
5) = null, getWhen(...,
11) = 10, getWhen(...,
15) = null, getWhen(...,
20) = 18. Assume all provided timestamps across calls are strictly increasing. Describe your data structures, how you track expirations and history, and analyze time and space complexity.
Quick Answer: This question evaluates understanding of time-versioned in-memory key–field–value stores, covering TTL-based expiration, historical reads, atomic compare-and-set/delete semantics, efficient scan/scan-by-prefix operations, and time/space complexity analysis, and it belongs to the Coding & Algorithms domain.
Implement an in-memory key-field-value store with monotonically increasing timestamps. Keys and fields are strings; values are integers. Rather than instantiating a class, write a single function `solution(operations)` that replays a list of API calls and returns one result per call (None/null for void methods).
Each operation is a list `[methodName, ...args]`. Support the following methods, which build up across four levels (each level keeps every earlier behavior):
Level 1 - Basic store
- `set(timestamp, key, field, value)` -> void: store value at key/field.
- `get(timestamp, key, field)` -> int|null: current value, or null if the key/field is absent or the value has expired.
- `compareAndSet(timestamp, key, field, expectedValue, newValue)` -> bool: if the current value equals expectedValue, set it to newValue and return true; otherwise return false.
- `compareAndDelete(timestamp, key, field, expectedValue)` -> bool: if the current value equals expectedValue, delete it and return true; otherwise return false.
Level 2 - Scanning
- `scan(timestamp, key)` -> string[]: every live field formatted as "field(value)", sorted alphabetically by field; empty array if the key does not exist.
- `scanByPrefix(timestamp, key, prefix)` -> string[]: like scan but only fields whose name starts with prefix.
Level 3 - TTL / expiration
- `setWithTtl(timestamp, key, field, value, ttl)` -> void: like set, but the value expires at timestamp + ttl. Expired values must not appear in get/scan/scanByPrefix.
- `compareAndSetWithTtl(timestamp, key, field, expectedValue, newValue, ttl)` -> bool: like compareAndSet; on success, write newValue with the given ttl.
Level 4 - Point-in-time history
- `getWhen(timestamp, key, field, atTimestamp)` -> int|null: the value that would have been visible at atTimestamp (with atTimestamp <= timestamp), accounting for past writes and expirations; null if none.
A value written with a ttl is visible on the half-open interval [writeTime, writeTime + ttl); at exactly the expiry time it is already gone. A later write to the same key/field supersedes the earlier value from the moment of the new write. All timestamps across calls are strictly increasing.
Constraints
- Keys, fields, and prefixes are non-empty strings; values and ttl are integers with ttl > 0.
- Timestamps passed to successive calls are strictly increasing.
- For getWhen, atTimestamp <= timestamp (you only ever query the past or present).
- A value set with ttl is live on [timestamp, timestamp + ttl); it is expired at exactly timestamp + ttl.
- scan / scanByPrefix output is sorted alphabetically by field name and excludes expired or deleted fields.
- 1 <= number of operations <= 10^4.
Examples
Input: [['set', 1, 'user1', 'age', 12], ['get', 2, 'user1', 'age'], ['get', 3, 'user1', 'height'], ['get', 4, 'userX', 'age'], ['compareAndSet', 5, 'user1', 'age', 12, 13], ['get', 6, 'user1', 'age'], ['compareAndSet', 7, 'user1', 'age', 99, 100], ['compareAndDelete', 8, 'user1', 'age', 13], ['get', 9, 'user1', 'age'], ['compareAndDelete', 10, 'user1', 'age', 13]]
Expected Output: [None, 12, None, None, True, 13, False, True, None, False]
Explanation: Level 1: set stores 12; get returns it; missing field/key give null. compareAndSet succeeds when current==expected (12->13) and fails otherwise (current 13 != 99). compareAndDelete removes the field when it matches (13), so the next get is null and the second delete fails.
Input: [['set', 1, 'user2', 'age', 18], ['set', 2, 'user2', 'height', 180], ['set', 3, 'user2', 'address', 1], ['scan', 4, 'user2'], ['scanByPrefix', 5, 'user2', 'a'], ['scan', 6, 'nope']]
Expected Output: [None, None, None, ['address(1)', 'age(18)', 'height(180)'], ['address(1)', 'age(18)'], []]
Explanation: Level 2: scan lists every live field as 'field(value)' sorted alphabetically (address, age, height). scanByPrefix 'a' keeps only address and age. Scanning a missing key returns an empty array.
Hints
- Model the store as key -> field -> list of versions, where each version is (start, end, value). end is the expiry timestamp (writeTime + ttl) or infinity for a non-TTL value.
- Because timestamps strictly increase, a new write to an existing field can simply close the previous live version by setting its end to the new write time; compareAndDelete closes the current version at the delete time.
- For get / scan, the relevant version is the latest one whose interval [start, end) contains the query timestamp. For getWhen(atTimestamp), binary-search the version list for the interval covering atTimestamp.
- Treat expiry as exclusive: a value with end = E is visible for t < E and gone at t == E. This is exactly why getWhen(15) is null in the worked example (10 expired at 12, 18 not written until 18).