Implement an In-Memory Database
Company: Coinbase
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Take-home Project
Design and implement an in-memory database that stores records by `key`. Each record is a map from `field` to integer `value`.
Implement the following functionality.
### Basic operations
- `set(key, field, value) -> None`
- If `key` does not exist, create it.
- Set `records[key][field] = value`.
- `get(key, field) -> Optional[int]`
- Return the value for `records[key][field]` if it exists.
- Otherwise return `None`.
- `delete(key, field) -> bool`
- Delete `field` from `records[key]` if it exists and return `true`.
- If the key or field does not exist, return `false`.
- If deleting the field makes the record empty, remove the record.
### Operation counts and top keys
For every operation that references a `key`, increment that key's operation count by `1`. This includes reads, writes, deletes, and user/lock operations that reference the key.
Implement:
- `topN(n) -> List[str]`
- Return at most `n` keys sorted by operation count in descending order.
- If two keys have the same operation count, sort them lexicographically ascending.
- Return only keys that currently have an operation count.
### User locks
Add user-aware modification operations and per-key locks.
A key can be locked by at most one user at a time.
- If a key is locked by user `u`, only user `u` may modify that key.
- Other users may still call read-only operations such as `get`, but they cannot modify the locked key.
- If a key is not locked, any user may modify it.
Implement:
- `setByUser(key, field, value, user) -> bool`
- If `key` is unlocked or locked by `user`, set the field and return `true`.
- If `key` is locked by another user, do not modify anything and return `false`.
- `deleteByUser(key, field, user) -> bool`
- If `key` is unlocked or locked by `user`, delete the field if it exists and return whether a field was deleted.
- If `key` is locked by another user, do not modify anything and return `false`.
- `lock(key, user) -> bool`
- If `key` does not exist, return `false`.
- If `key` is unlocked, lock it for `user` and return `true`.
- If `key` is already locked, return `false`.
- `unlock(key) -> bool`
- If `key` is currently locked, remove the lock and return `true`.
- If `key` is not locked, return `false`.
Your implementation should support all operations efficiently and maintain correct operation counts for `topN`.
Quick Answer: This question evaluates data-structure design, mutable in-memory storage, operation counting, and concurrency control via per-key user locks, in the domain of coding and algorithms focused on in-memory databases and hashmap-based key-value stores.
Part 1: Basic In-Memory Database
You are given a sequence of queries for an in-memory database. The database stores records by key, and each record is a map from field names to integer values.
Implement these operations:
- SET key field value: create the record if needed and set the field value.
- GET key field: return the stored integer, or None if the key or field does not exist.
- DELETE key field: remove the field if it exists and return True; otherwise return False.
If deleting a field makes a record empty, remove the entire record.
Return the result of every query in order. For SET queries, append None to the output list.
Constraints
- 0 <= len(queries) <= 2 * 10^5
- 1 <= len(key), len(field) <= 20
- -10^9 <= value <= 10^9
- All queries are valid and match one of the allowed formats
Examples
Input: ([['SET', 'user1', 'age', 30], ['GET', 'user1', 'age'], ['DELETE', 'user1', 'age'], ['GET', 'user1', 'age']],)
Expected Output: [None, 30, True, None]
Explanation: The value is inserted, read, deleted, and then no longer exists.
Input: ([['SET', 'a', 'x', 1], ['SET', 'a', 'y', 2], ['DELETE', 'a', 'x'], ['GET', 'a', 'y'], ['DELETE', 'a', 'y'], ['GET', 'a', 'y']],)
Expected Output: [None, None, True, 2, True, None]
Explanation: Deleting the last field removes the whole record for key 'a'.
Input: ([],)
Expected Output: []
Explanation: Edge case: no queries.
Input: ([['GET', 'missing', 'f'], ['DELETE', 'missing', 'f'], ['SET', 'k', 'f', 5], ['DELETE', 'k', 'g']],)
Expected Output: [None, False, None, False]
Explanation: Missing keys and missing fields should be handled safely.
Hints
- A dictionary of dictionaries works well: one dict for keys, and an inner dict for fields.
- After a successful delete, check whether the inner record became empty.
Part 2: Operation Counts and Top Keys
Implement an in-memory database with operation counting.
The database stores records by key, and each record maps field names to integer values.
Supported operations:
- SET key field value: create the record if needed and set the field.
- GET key field: return the stored integer, or None if the key or field does not exist.
- DELETE key field: remove the field if it exists and return True; otherwise return False. If the record becomes empty, remove it.
- TOP n: return at most n keys sorted by:
1. operation count descending
2. key name lexicographically ascending when counts tie
Counting rule:
- Every SET, GET, and DELETE increments the mentioned key's count by 1.
- This count increases even if the key or field does not exist.
- TOP does not change any count.
- Counts persist even if a record is completely deleted.
Return the result of every query in order. For SET queries, append None to the output list.
Constraints
- 0 <= len(queries) <= 2 * 10^5
- 1 <= len(key), len(field) <= 20
- 0 <= n <= 2 * 10^5
- -10^9 <= value <= 10^9
- All queries are valid and match one of the allowed formats
Examples
Input: ([['SET', 'a', 'x', 1], ['SET', 'b', 'x', 2], ['GET', 'a', 'x'], ['DELETE', 'b', 'x'], ['TOP', 2]],)
Expected Output: [None, None, 1, True, ['a', 'b']]
Explanation: Both 'a' and 'b' were referenced twice; the tie is broken lexicographically.
Input: ([['GET', 'ghost', 'x'], ['DELETE', 'ghost', 'x'], ['SET', 'alpha', 'y', 5], ['TOP', 3]],)
Expected Output: [None, False, None, ['ghost', 'alpha']]
Explanation: Missing-key operations still count, so 'ghost' has count 2.
Input: ([['SET', 'c', 'x', 1], ['SET', 'a', 'x', 1], ['GET', 'c', 'x'], ['GET', 'a', 'x'], ['SET', 'b', 'x', 1], ['TOP', 3]],)
Expected Output: [None, None, 1, 1, None, ['a', 'c', 'b']]
Explanation: 'a' and 'c' both have count 2, so lexicographic order puts 'a' first.
Input: ([['TOP', 5]],)
Expected Output: [[]]
Explanation: Edge case: no key has been referenced yet.
Hints
- Keep the data itself and the per-key operation counts in separate hash maps.
- For TOP, sort keys by (-count, key) to handle both ranking rules at once.
Part 3: User Locks
Implement an in-memory database with per-key user locks.
The database stores records by key, and each record maps field names to integer values.
Supported operations:
- SET_BY_USER key field value user -> bool
- If the key is unlocked, or locked by the same user, set the field and return True.
- If the key is locked by another user, do not change anything and return False.
- If the key does not exist, create it.
- GET key field -> integer or None
- Reads are always allowed, even if the key is locked by another user.
- DELETE_BY_USER key field user -> bool
- If the key is unlocked, or locked by the same user, delete the field if it exists.
- Return True only if a field was actually deleted.
- If the key is locked by another user, return False.
- If deleting the last field removes the whole record, its lock must also be removed.
- LOCK key user -> bool
- Return False if the key does not exist.
- Return True if the key exists and is currently unlocked, and lock it for the given user.
- Return False if it is already locked.
- UNLOCK key -> bool
- Return True if the key is currently locked and the lock is removed.
- Return False otherwise.
Return the result of every query in order.
Constraints
- 0 <= len(queries) <= 2 * 10^5
- 1 <= len(key), len(field), len(user) <= 20
- -10^9 <= value <= 10^9
- All queries are valid and match one of the allowed formats
Examples
Input: ([['SET_BY_USER', 'doc', 'x', 10, 'alice'], ['LOCK', 'doc', 'alice'], ['SET_BY_USER', 'doc', 'y', 20, 'bob'], ['GET', 'doc', 'x'], ['SET_BY_USER', 'doc', 'y', 20, 'alice'], ['UNLOCK', 'doc'], ['SET_BY_USER', 'doc', 'y', 30, 'bob'], ['GET', 'doc', 'y']],)
Expected Output: [True, True, False, 10, True, True, True, 30]
Explanation: Only the lock owner may modify a locked key, but reads remain allowed.
Input: ([['SET_BY_USER', 'a', 'x', 1, 'u1'], ['LOCK', 'a', 'u1'], ['DELETE_BY_USER', 'a', 'x', 'u1'], ['UNLOCK', 'a'], ['LOCK', 'a', 'u2'], ['GET', 'a', 'x']],)
Expected Output: [True, True, True, False, False, None]
Explanation: Deleting the last field removes the record and also clears its lock.
Input: ([['LOCK', 'ghost', 'u'], ['DELETE_BY_USER', 'ghost', 'x', 'u'], ['SET_BY_USER', 'k', 'f', 7, 'u1'], ['LOCK', 'k', 'u2'], ['DELETE_BY_USER', 'k', 'f', 'u1'], ['GET', 'k', 'f']],)
Expected Output: [False, False, True, True, False, 7]
Explanation: A lock cannot be created on a missing key, and another user's lock blocks modifications.
Input: ([],)
Expected Output: []
Explanation: Edge case: no queries.
Hints
- Store locks in a separate dictionary: key -> user who currently owns the lock.
- When a delete removes the final field of a record, remember to clean up both the record and any lock for that key.