Implement a nested key-value store
Company: Lyft
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
Design and implement a nested key–value store that supports set(path, value), get(path), and delete(path), where path is dot-delimited (e.g., "a.b.c"). Support creating intermediate nodes, overwriting existing values, and returning clear errors for missing paths. Add:
(
1) an iterator to list immediate children under a prefix;
(
2) a method to flatten the structure into a single-level map using dot paths;
(
3) optional type checking to prevent incompatible overwrites. Provide expected time and space complexity for each operation and explain how you would serialize/deserialize the structure.
Overview: This question evaluates understanding of data structures and API design for hierarchical (nested) key-value stores, covering operations such as set/get/delete, child iteration, flattening to dot paths, optional type safety, and serialization.
Part 1: Basic Nested Key-Value Store
Implement a nested key-value store that supports three operations on dot-delimited paths: 'set(path, value)', 'get(path)', and 'delete(path)'. Missing intermediate nodes must be created automatically during 'set'. A path may store a value and still have children, so after setting 'a' you may still set 'a.b'. 'delete(path)' removes the entire subtree rooted at that path. Process a list of operations and return one result per operation.
Constraints
- 0 <= len(operations) <= 10^4
- Each path is a non-empty dot-delimited string with no empty segments
- Values are Python literals such as int, str, bool, float, or None
- delete(path) removes the whole subtree at that path
Examples
Input: [('set', 'a.b.c', 5), ('get', 'a.b.c'), ('delete', 'a.b.c'), ('get', 'a.b.c')]
Expected Output: ['OK', 5, 'OK', 'ERROR: Path not found']
Explanation: Basic create, retrieve, delete, then verify the path is gone.
Input: [('set', 'x', 1), ('set', 'x', 7), ('get', 'x')]
Expected Output: ['OK', 'OK', 7]
Explanation: Setting an existing path overwrites its old value.
Hints
- Treat each path segment as one step in a tree or trie.
- To support both 'a' and 'a.b', store a node's value separately from its children.
Part 2: List Immediate Children Under a Prefix
Extend the nested key-value store with a 'children(prefix)' operation. It should return the immediate child names directly under the given prefix, not full paths. For example, if the store contains 'a.b' and 'a.c.d', then 'children("a")' returns ['b', 'c']. The empty prefix '' refers to the root. If the prefix path does not exist, return 'ERROR: Path not found'. Return child names sorted lexicographically for deterministic output.
Constraints
- 0 <= len(operations) <= 10^4
- Paths for 'set' and 'delete' are non-empty dot-delimited strings with no empty segments
- The empty prefix '' is allowed only for 'children' and means the root
- A node may have both a direct value and child nodes
Examples
Input: [('set', 'a.b', 1), ('set', 'a.c.d', 2), ('children', 'a'), ('children', 'a.c')]
Expected Output: ['OK', 'OK', ['b', 'c'], ['d']]
Input: [('set', 'z', 1), ('set', 'a.b', 2), ('children', '')]
Expected Output: ['OK', 'OK', ['a', 'z']]
Approach
The store is modeled as a trie (prefix tree). Each Node carries a children dict (segment name -> child Node), a has_value flag, and the stored value. Dotted paths like a.c.d are split on . into segments; the empty string '' maps to the empty segment list, i.e. the root.
set(path, value) calls traverse(path, create=True), which walks segment by segment, creating any missing intermediate node, then marks the final node has_value = True. This is why a node can hold both a value and children.
children(prefix) resolves the prefix node (root for '', else traverse(prefix, create=False)). If traversal hits a missing segment it returns None → 'ERROR: Path not found'; otherwise it returns sorted(node.children.keys()) — only the immediate child names, never full paths, sorted lexicographically for deterministic output. A node with no children yields [].
delete(path) walks down recording a stack of (parent, segment) pairs; a missing segment returns False → error. It deletes the target leaf from its parent, then walks the stack bottom-up, pruning each ancestor only while it has neither a value nor remaining children, and stopping at the first node that still holds a value or other children. This keeps the trie minimal without ever removing a node another key still depends on.
Why it's correct: children reads exactly the surviving immediate keys; the value/children separation lets delete prune dead branches while preserving value-bearing or still-populated ancestors. Unknown operation kinds fall through to 'ERROR: Unknown operation'.
Time complexity: O(k) per set/delete, where k is the number of path segments (delete's prune pass is also bounded by k). children(prefix) is O(k + c log c), where c is the number of immediate children sorted/returned.
Space complexity: O(n), where n is the total number of nodes stored in the trie (one node per distinct path segment across all keys); each operation uses O(k) auxiliary space for the segment list / delete stack.
Hints
- After walking to the node for the prefix, you only need its direct children dictionary.
- Sort the child names before returning them so the result is deterministic.
Part 3: Flatten a Nested Key-Value Store
You are given set/delete operations for a nested key-value store whose keys are dot-delimited paths. Build the final store, then flatten it into a single dictionary whose keys are full dot paths. Only nodes with direct stored values should appear in the output. Intermediate nodes created only to hold children must not appear. A node may still appear in the flattened result even if it also has children.
Constraints
- 0 <= len(operations) <= 10^4
- Each set path is a non-empty dot-delimited string with no empty segments
- If delete(path) is called on a missing path, it has no effect
- Values are Python literals such as int, str, bool, float, or None
Examples
Input: [('set', 'a.b', 1), ('set', 'c', 2)]
Expected Output: {'a.b': 1, 'c': 2}
Explanation: Two stored paths become two flat entries.
Input: [('set', 'a', 1), ('set', 'a.b.c', 3)]
Expected Output: {'a': 1, 'a.b.c': 3}
Explanation: A node can keep its own value and also have descendants.
Approach
The solution models the nested store as a trie keyed by path segments. Each Node carries three fields: a children dict, a boolean has_value, and the stored value.
Why has_value is separate from value: values may legally be None, so a value is None check can't distinguish "intermediate node holding only children" from "node that explicitly stores None." The dedicated has_value flag cleanly separates structure from stored data, and lets a node appear in the output even when it also has children.
Applying operations (in order):
- set(path, v): traverse(path, create=True) walks each dot segment, lazily creating missing nodes, then marks the terminal node has_value=True, value=v. Re-setting the same path overwrites in place.
- delete(path): walk the segments, recording a stack of (parent, segment) pairs. If any segment is missing, return (no-op for missing paths). Otherwise delete the target node from its parent, then walk the stack in reverse and prune each ancestor that is now empty — i.e. has no value and no children — stopping at the first ancestor that is still needed.
Flattening: a DFS from root emits an entry only when path_parts is non-empty and node.has_value is true, joining the segments with .. Intermediate-only nodes are skipped, satisfying the requirement.
Correctness: building the trie is order-dependent and matches the operation sequence; the has_value flag guarantees only directly-stored values surface; ancestor pruning on delete keeps the tree free of dangling empty nodes so they never leak into output.
Time complexity: O(S) total, where S is the sum of segment counts across all operations. Each set/delete touches one node per path segment, and the final DFS visits every node once and pays the length of each emitted key — both bounded by S.
Space complexity: O(N), where N is the number of nodes in the trie (bounded by the total distinct segments inserted). The output dict and the recursion/traversal stacks are also O(N) in the worst case.
Hints
- Build the store as a tree, then do a DFS while carrying the current path segments.
- Do not emit intermediate nodes unless they were explicitly assigned a value.
Part 4: Optional Type Checking for Overwrites
Implement a nested key-value store with an optional strict overwrite mode. You will receive a boolean 'strictMode' and a list of operations. When 'strictMode' is True, overwriting an existing value at the same exact path is allowed only if the new value has the exact same Python type as the old value, meaning 'type(old) is type(new)'. If the types differ, reject the write with 'TYPE_ERROR' and keep the old value unchanged. When 'strictMode' is False, all overwrites are allowed. A node may store a value and still have children. 'delete(path)' removes the entire subtree rooted at that path.
Constraints
- 0 <= len(operations) <= 10^4
- Each path is a non-empty dot-delimited string with no empty segments
- Type checking applies only when overwriting an existing direct value at the same path
- Use exact Python type equality, so int and bool are considered different
Examples
Input: (True, [('set', 'a', 1), ('set', 'a', 2), ('get', 'a')])
Expected Output: ['OK', 'OK', 2]
Explanation: Strict mode still allows overwrites when the type stays the same.
Input: (True, [('set', 'a', 1), ('set', 'a', 'hello'), ('get', 'a')])
Expected Output: ['OK', 'TYPE_ERROR', 1]
Explanation: Changing the type at the same path is rejected in strict mode.
Approach
The store is modeled as a trie (prefix tree) where every dot-delimited path segment is an edge. Each Node carries a children dict plus a has_value/value pair, so a node can hold its own value and still have descendants — exactly what "a node may store a value and still have children" requires.
traverse(path, create) splits the path on . and walks segment by segment from root. With create=True it materializes missing nodes (used by set); with create=False it returns None the moment a segment is missing (used by get).
set traverses-and-creates the target node. In strict mode, if the node already has_value and type(node.value) is not type(value), it appends TYPE_ERROR and leaves the old value untouched. Using type(...) is type(...) (identity on the type object) gives exact type equality, so int and bool are correctly treated as different (type(True) is bool). Otherwise it writes the value and appends OK.
get returns the stored value, or "ERROR: Path not found" if the node is missing or has no value set.
delete records a stack of (parent, segment) pairs on the way down, deletes the entire subtree by removing the last segment from its parent's children, then walks the stack in reverse to prune any ancestor that is now valueless and childless. This keeps the trie compact and is why test 4 can re-set x.y with a different type after deleting it — the old node (and its type) are gone.
Correctness rests on the trie giving each path a unique node, value/children independence, and exact-type comparison only firing on a same-path overwrite of an existing value.
Time complexity: O(k) per operation, where k is the number of dot-separated segments in the path (set/get/delete each walk and, for delete, prune along that single path). Over all m operations the total is O(sum of path lengths). The strict type check is O(1).
Space complexity: O(n), where n is the total number of nodes stored across all inserted paths. The delete stack adds O(k) transient space for one operation.
Hints
- After reaching the target node for a 'set', compare the existing value's exact type with the new value's exact type only if the node already stores a value.
- If a write fails with 'TYPE_ERROR', do not modify the stored value.