Design a hierarchical locking tree
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Design a LockingHierarchy data structure over a rooted tree of N nodes labeled 0..N-1, initialized with an integer array parent[] where parent[0] = -1 and parent[i] is the parent of i. Support operations:
(
1) lock(x): lock node x only if x is currently unlocked AND all its ancestors and descendants are unlocked; return true if the lock succeeds, else false.
(
2) unlock(x): if x is locked, unlock it and return true; otherwise return false.
(
3) isLocked(x): return whether x is locked. Constraints: up to 2e5 nodes and 2e5 operations; each operation should be O(log N) or better (amortized). Specify and justify the data structures and algorithms you will use (e.g., parent array initialization, subtree indexing, ancestor/descendant conflict checks, and maintaining counts of locked descendants), the time and space complexity, and key edge cases. Provide a brief set of unit tests covering boundary conditions (root, leaf, repeated locks/unlocks, conflicting locks, deep trees).
Quick Answer: This interview question evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer for Design a hierarchical locking tree states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.
Implement a `LockingHierarchy` over a rooted tree of `N` nodes labeled `0..N-1`. The tree is given by an integer array `parent[]` where `parent[0] = -1` (the root) and `parent[i]` is the parent of node `i`. Support three operations:
1. **lock(x)** — lock node `x` only if `x` is currently unlocked **and** none of its ancestors are locked **and** none of its descendants are locked. Return `true` if the lock succeeds, else `false`.
2. **unlock(x)** — if `x` is locked, unlock it and return `true`; otherwise return `false`.
3. **isLocked(x)** — return whether `x` is currently locked.
To make this executable, your `solution` consumes the `parent` array plus a list of operations `(name, x)` and returns the list of boolean results, one per operation (for `isLocked` the result is the current lock state).
**Approach.** Keep a `locked[]` boolean per node. The descendant check is the trap: a naive DFS over the subtree on every `lock` is O(N) per call. Instead maintain `locked_desc[]`, a count of how many nodes in each node's subtree are currently locked. On `lock(x)`, walk up the ancestor chain once (a) to check no ancestor is locked and (b) to increment each ancestor's `locked_desc`; the descendant check is then just `locked_desc[x] == 0`. On `unlock(x)`, walk up again to decrement. Each op is O(depth) — O(log N) on balanced trees, O(N) worst case on a degenerate chain; the ancestor walk is unavoidable without heavier machinery (e.g. Euler-tour + segment tree / BIT for O(log N) guaranteed).
Constraints
- 1 <= N <= 2*10^5 nodes; up to 2*10^5 operations.
- parent[0] == -1 (node 0 is the root); for i > 0, 0 <= parent[i] < i is not required but parent[i] must reference a valid node forming a rooted tree.
- 0 <= x < N for every operation.
- name is one of 'lock', 'unlock', 'isLocked'.
Examples
Input: ([-1, 0, 0, 1, 1, 2], [('lock', 0), ('isLocked', 0), ('lock', 3), ('unlock', 0), ('lock', 3), ('isLocked', 3)])
Expected Output: [True, True, False, True, True, True]
Explanation: Lock root 0 (ok). isLocked(0) is True. lock(3) fails because ancestor 0 is locked. unlock(0) succeeds. Now lock(3) succeeds (no locked ancestor/descendant). isLocked(3) is True.
Input: ([-1, 0, 1, 2, 3], [('lock', 2), ('lock', 0), ('lock', 4), ('unlock', 2), ('lock', 0), ('lock', 4)])
Expected Output: [True, False, False, True, True, False]
Explanation: Chain 0->1->2->3->4. lock(2) ok. lock(0) fails: descendant 2 is locked. lock(4) fails: ancestor 2 is locked. unlock(2) ok. lock(0) now ok. lock(4) fails: ancestor 0 is locked.
Hints
- The descendant check is the bottleneck. Instead of DFS-ing a node's subtree on every lock(), maintain locked_desc[v] = number of currently-locked nodes in v's subtree. Then 'no locked descendant' is simply locked_desc[x] == 0 in O(1).
- On lock(x), walk up the ancestor chain exactly once: it both verifies no ancestor is locked AND increments locked_desc on each ancestor. On unlock(x), walk up again to decrement.
- Edge cases: locking an already-locked node returns False; unlocking an unlocked node returns False; the root has no ancestors; a leaf has no descendants. Re-locking after an unlock must succeed once the conflicts clear.