Design a hierarchical path registry
Company: DoorDash
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
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.
Quick Answer: Design a hierarchical path registry 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.
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
Input: ([('create', '/a', 1), ('get', '/a'), ('get', '/b')],)
Expected Output: [True, 1, -1]
Explanation: Create /a=1 under root succeeds; get /a returns 1; /b was never created so get returns -1.
Input: ([('create', '/a/b', 5)],)
Expected Output: [False]
Explanation: Parent /a does not exist, so creating /a/b fails.
Hints
- Store every path as a key in a hash map from path-string to integer value; the root '/' starts already present with value 0.
- Derive the parent of a path by cutting at the last '/'. The parent of a top-level path such as '/a' is the root '/'.
- 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.