Implement a hierarchical key-value store
Company: DoorDash
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Implement an in-memory hierarchical key-value store where keys are UNIX-like paths joined by '/'. The root node is '/' with initial value '#'. Each node stores a string value. Support:
(
1) Create(path, value): create a node; parent must exist; fail if the node already exists.
(
2) SetValue(path, value): set the value; node must exist.
(
3) GetValue(path): return the value; node must exist.
(
4) Delete(path): delete the node only if it has no children; node must exist. Define the class interface, choose appropriate data structures, and provide time/space complexities. Include unit tests and discuss how you would add concurrency safety and optional persistence to disk.
Quick Answer: Implement a hierarchical key-value store evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.
Design an in-memory hierarchical key-value store where keys are UNIX-like paths joined by '/'. The root node is '/' and starts with value '#'. Every node stores a single string value and may have child nodes.
Implement a driver `solution(operations)` that replays a list of operations and returns a list with one result per operation. Each operation is a list whose first element is the op name:
- `['create', path, value]` — Create a new node at `path` with `value`. The parent node must already exist and the node must NOT already exist. Returns `True` on success, `False` otherwise.
- `['set', path, value]` — Set the value of an existing node. The node must exist. Returns `True` if updated, `False` if the node does not exist.
- `['get', path]` — Return the node's string value, or `None` if the node does not exist.
- `['delete', path]` — Delete the node only if it exists AND has no children (and is not the root). Returns `True` if deleted, `False` otherwise.
The store is pre-populated with the root: `get('/')` returns `'#'`.
Example:
```
operations = [
['create', '/a', 'x'], # -> True
['create', '/a/b', 'c'], # -> True
['delete', '/a'], # -> False (has child '/a/b')
['get', '/a/b'], # -> 'c'
['delete', '/a/b'], # -> True
['delete', '/a'] # -> True (now a leaf)
]
solution(operations) == [True, True, False, 'c', True, True]
```
Constraints
- Paths are non-empty strings beginning with '/'.
- The root '/' always exists with initial value '#' and cannot be deleted.
- Create fails if the immediate parent does not exist or if the node already exists.
- Set/Get require the target node to already exist.
- Delete requires the node to exist and to have no children.
- Values are arbitrary strings.
Examples
Input: ([['get', '/']],)
Expected Output: ['#']
Explanation: The root node is pre-populated with value '#'.
Input: ([['create', '/a', 'x'], ['get', '/a'], ['set', '/a', 'y'], ['get', '/a']],)
Expected Output: [True, 'x', True, 'y']
Explanation: Create under existing root succeeds; Set overwrites the value, confirmed by the second Get.
Hints
- Store every node under its full path (e.g. '/a/b') in a flat hash map keyed by path, instead of nesting dicts — this makes existence checks O(1).
- Keep a separate children map (path -> set of child full-paths) so Delete can reject non-leaf nodes in O(1) and Create can validate the parent quickly.
- Derive a node's parent by trimming after the last '/'; the parent of '/a' is '/', and the parent of '/a/b' is '/a'. Handle the root '/' as a special case.
- For concurrency, guard the maps with a read-write lock (or per-subtree locks); for persistence, append each mutating op to a write-ahead log and replay it on startup.