Implement a hierarchical key-value store

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.

What a Strong Answer Covers

• A clear algorithm with the right data structures and enough pseudocode or code-level detail to implement it.
• A correctness argument that explains why the algorithm covers all required cases.
• Time and space complexity, plus at least one alternative approach when relevant.
• Focused tests for normal cases, edge cases, and failure modes.

Follow-up Questions

• How would the approach change if the input were streaming or too large for memory?
• What invariants would you assert in production code?
• Which tests would catch off-by-one, duplicate, or tie-breaking bugs?

Implement a Hierarchical Key-Value Store

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.

Hints

1. 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).
2. 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.
3. 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.
4. 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.

Solution

Solution Alignment

The prompt asks for an implementation-level answer. The safest way to present it is to define the state, maintain clear invariants, then walk through complexity and tests.

Problem Restatement

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.

Recommended Approach

Model the states explicitly and use BFS for unweighted shortest paths, Dijkstra for weighted non-negative paths, or topological DP for DAGs. Track visited states at the right granularity so cycles do not cause repeated work.

Correctness

The implementation should maintain an invariant after each loop or operation that directly matches the problem statement. At termination, that invariant implies the returned value has considered every valid candidate exactly once, or has preserved the required data-structure state after every API call.

Complexity

BFS is O(V + E) time and O(V) space for a standard graph. Expanded-state problems multiply those bounds by the number of state dimensions.

Edge Cases and Tests

Disconnected graph, source equals target, cycles, duplicate edges, unreachable target, and whether the answer counts nodes, edges, moves, or transfers.