Implement an Expiring Record Store
Company: Meta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Implement a level-based in-memory record store.
The store contains records identified by a string `key`. Each record contains fields, where each `field` is a string and each `value` is a string.
### Level 1: Basic mutations
Implement:
- `set(key, field, value)`: Create the record if it does not exist, then set `field` to `value`.
- `get(key, field)`: Return the current value for `field`, or `null` if the record or field does not exist.
- `delete(key, field)`: Remove `field` from the record. Return `true` if a field was removed, otherwise return `false`. If a record becomes empty, it may be removed from the store.
### Level 2: Scanning
Implement:
- `scan(key)`: Return all fields for `key`, sorted lexicographically by field name. Format each item as `field(value)`. Return an empty list if the record does not exist.
- `scan_by_prefix(key, prefix)`: Return only fields whose names start with `prefix`, sorted lexicographically by field name and formatted as `field(value)`.
### Level 3: Timestamps and TTL
Extend the store so fields can be written with timestamps and optional time-to-live values.
Implement:
- `set_at(key, field, value, timestamp)`: Set the field at `timestamp` with no expiration.
- `set_at_with_ttl(key, field, value, timestamp, ttl)`: Set the field at `timestamp`; it is visible for query times `t` such that `timestamp <= t < timestamp + ttl`.
- `delete_at(key, field, timestamp)`: Delete the field at `timestamp` if it exists and is not expired at that time. Return `true` if a field was deleted, otherwise return `false`.
- `get_at(key, field, timestamp)`: Return the value visible at `timestamp`, or `null` if none exists.
- `scan_at(key, timestamp)`: Return all fields visible at `timestamp`, sorted and formatted as in `scan`.
- `scan_by_prefix_at(key, prefix, timestamp)`: Return all visible fields at `timestamp` whose names start with `prefix`, sorted and formatted as in `scan_by_prefix`.
Assume timestamps passed to timestamped operations are non-decreasing. A later write to the same `(key, field)` replaces the previous value and expiration policy. Expired or deleted fields must not appear in reads or scans.
Quick Answer: This question evaluates skills in designing and implementing an in-memory, level-based key-field-value store with lexicographic scanning, time-based versioning, TTL semantics, and efficient mutation operations.
Part 1: Basic In-Memory Record Store
Implement the core mutation operations of an in-memory record store. Each record is identified by a string `key` and stores string `field -> value` pairs. Process the operations in order and return the result of each operation. Supported operations: `['set', key, field, value]` creates the record if needed and stores the value; `['get', key, field]` returns the current value or `None`; `['delete', key, field]` removes the field and returns `True` if something was removed, otherwise `False`. If a record becomes empty after deletion, remove it from the store.
Constraints
- 1 <= len(operations) <= 200000
- Each `key`, `field`, and `value` is a string of length between 1 and 100
- The total length of all strings in the input is at most 200000
- All operation names are valid and appear exactly as specified
Examples
Input: [['set', 'user', 'name', 'alice'], ['get', 'user', 'name'], ['set', 'user', 'name', 'bob'], ['get', 'user', 'name'], ['delete', 'user', 'name'], ['get', 'user', 'name']]
Expected Output: [None, 'alice', None, 'bob', True, None]
Explanation: Setting the same field again overwrites the old value.
Input: [['get', 'missing', 'field'], ['delete', 'missing', 'field'], ['set', 'a', 'x', '1'], ['delete', 'a', 'y'], ['get', 'a', 'x']]
Expected Output: [None, False, None, False, '1']
Explanation: Reading or deleting a missing field should safely return `None` or `False`.
Hints
- A dictionary from `key` to another dictionary of `field -> value` is enough for all Level 1 operations.
- After deleting a field, check whether its record became empty and remove that record too.
Part 2: Record Store with Scanning
Extend the in-memory record store to support scanning. Each record is identified by a string `key` and stores string `field -> value` pairs. Process the operations in order and return the result of each operation. In addition to `set`, `get`, and `delete`, support `['scan', key]`, which returns all fields for that key sorted lexicographically and formatted as `field(value)`, and `['scan_by_prefix', key, prefix]`, which returns only fields whose names start with `prefix`, also sorted and formatted. If a record does not exist, scans return an empty list.
Constraints
- 1 <= len(operations) <= 200000
- Each `key`, `field`, `value`, and `prefix` is a string of length between 0 and 100
- The total length of all strings in the input is at most 200000
- Fields in scans must be sorted lexicographically by field name
Examples
Input: [['set', 'user', 'name', 'alice'], ['set', 'user', 'age', '30'], ['set', 'user', 'email', 'a@example.com'], ['scan', 'user'], ['scan_by_prefix', 'user', 'e']]
Expected Output: [None, None, None, ['age(30)', 'email(a@example.com)', 'name(alice)'], ['email(a@example.com)']]
Explanation: Scan results must be sorted by field name, not by insertion order.
Input: [['set', 'k', 'apple', '1'], ['set', 'k', 'app', '2'], ['set', 'k', 'banana', '3'], ['scan_by_prefix', 'k', 'app'], ['delete', 'k', 'app'], ['scan_by_prefix', 'k', 'app']]
Expected Output: [None, None, None, ['app(2)', 'apple(1)'], True, ['apple(1)']]
Explanation: Only fields starting with the prefix are returned, still in lexicographic order.
Hints
- Keep the same nested dictionary structure from Part 1, then build scan results from the inner dictionary.
- For prefix scans, filter field names first, then sort the matching fields before formatting them.
Part 3: Expiring Record Store with Timestamps and TTL
Implement a timestamped in-memory record store with TTL support. Each record is identified by a string `key`, and each field stores a string value plus an optional expiration time. Process operations in order and return the result of each operation. Timestamps in the input are non-decreasing across the whole operation list. Supported operations: `['set_at', key, field, value, timestamp]` writes a non-expiring value; `['set_at_with_ttl', key, field, value, timestamp, ttl]` writes a value visible exactly when `timestamp <= t < timestamp + ttl`; `['delete_at', key, field, timestamp]` deletes the field only if it exists and is not expired at that time; `['get_at', key, field, timestamp]` returns the visible value or `None`; `['scan_at', key, timestamp]` returns all visible fields sorted and formatted as `field(value)`; `['scan_by_prefix_at', key, prefix, timestamp]` returns only visible fields whose names start with `prefix`, also sorted and formatted. A later write to the same `(key, field)` replaces the previous value and expiration policy.
Constraints
- 1 <= len(operations) <= 200000
- The sequence of timestamps across all operations is non-decreasing
- 1 <= ttl <= 1000000000
- Each `key`, `field`, `value`, and `prefix` is a string of length between 0 and 100
Examples
Input: [['set_at_with_ttl', 'user', 'token', 'abc', '10', '5'], ['get_at', 'user', 'token', '10'], ['get_at', 'user', 'token', '14'], ['get_at', 'user', 'token', '15'], ['scan_at', 'user', '15']]
Expected Output: [None, 'abc', 'abc', None, []]
Explanation: A TTL write at time 10 with TTL 5 is visible at times 10 through 14, but not at 15.
Input: [['set_at_with_ttl', 'k', 'a', '1', '1', '10'], ['set_at', 'k', 'a', '2', '5'], ['get_at', 'k', 'a', '6'], ['get_at', 'k', 'a', '20'], ['scan_at', 'k', '20']]
Expected Output: [None, None, '2', '2', ['a(2)']]
Explanation: A later write replaces both the old value and the old expiration policy.
Hints
- Because timestamps never go backward, you do not need full history for each field; keeping only the current value and its expiration time is enough.
- On any read, scan, or delete at time `t`, treat a field with `expire_at <= t` as missing, and you can lazily remove it from the store.