Design a hierarchical path registry

Implement an in-memory hierarchical path registry. Support: create(path, value) to create a new path with an integer value and get(path) to return its value or -1 if absent. Constraints: the root '/' exists implicitly; a path can be created only if its parent exists; creating an existing path fails; path segments use lowercase letters and '/' as separator. Describe data structures, APIs, and time/space complexity. Follow-ups: support update and delete (including subtree deletion rules), wildcard queries, and watch callbacks that trigger on changes to a path or subtree.

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?

Design a Hierarchical Path Registry

Implement an in-memory hierarchical path registry that processes a sequence of operations. Each path looks like a Unix filesystem path made of lowercase-letter segments separated by '/'. The root path '/' exists implicitly and holds value 0.

Implement a function that takes a list of operations and returns a list of results — one entry per operation, in order. Each operation is a tuple:

• ('create', path, value) — Create a new path (a string) holding integer value. A path may be created only if (a) it does not already exist and (b) its immediate parent exists. The parent of /a/b is /a; the parent of a top-level path like /a is the root /. On success append True; on failure (already exists, or parent missing) append False.
• ('get', path) — Append the integer value stored at path, or -1 if the path does not exist. get('/') returns 0.

Return the list of results.

Constraints

• The root '/' exists implicitly and holds value 0.
• A path can be created only if its immediate parent already exists.
• Creating a path that already exists fails (returns False).
• Path segments consist of lowercase letters; '/' is the separator.
• get on a non-existent path returns -1.
• 0 <= number of operations <= 10^5.

Examples

Example 1

Input: ([('create', '/a', 1), ('get', '/a'), ('get', '/b')],)
Output: [True, 1, -1]

Explanation: Create /a=1 under root succeeds; get /a returns 1; /b was never created so get returns -1.

Example 2

Input: ([('create', '/a/b', 5)],)
Output: [False]

Explanation: Parent /a does not exist, so creating /a/b fails.

Hints

1. Store every path as a key in a hash map from path-string to integer value; the root '/' starts already present with value 0.
2. Derive the parent of a path by cutting at the last '/'. The parent of a top-level path such as '/a' is the root '/'.
3. Before creating, check both that the path is absent AND that its parent is present; only then insert. This makes the parent-must-exist rule a single membership test.

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 path registry. Support: create(path, value) to create a new path with an integer value and get(path) to return its value or -1 if absent. Constraints: the root '/' exists implicitly; a path can be created only if its parent exists; creating an existing path fails; path segments use lowercase letters and '/' as separator. Describe data structures, APIs, and time/space complexity. Follow-ups: support update and delete (including subtree deletion rules), wildcard queries, and watch callbacks that trigger on changes to a path or subtree.

Recommended Approach

Choose traversal based on the required view or aggregate. DFS is natural for subtree computations and reconstruction; BFS is natural for level order or side views. Keep per-depth or per-position state when the output depends on columns, rows, or depths.

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

Most tree traversals are O(n) time and O(h) recursion stack for DFS or O(w) queue space for BFS, where h is height and w is maximum width.

Edge Cases and Tests

Empty tree, one node, skewed tree, duplicate values when reconstruction assumes uniqueness, deep recursion, and tie-breaking for same row/column nodes.