How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Amazon.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Amazon during technical interviews.

Design a hierarchical locking tree | Amazon Coding Question

Quick Overview

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.

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.

Input: ([-1], [('isLocked', 0), ('lock', 0), ('lock', 0), ('unlock', 0), ('unlock', 0)])

Expected Output: [False, True, False, True, False]

Explanation: Single-node tree. Initially unlocked. lock(0) ok. lock(0) again fails (already locked). unlock(0) ok. unlock(0) again fails (already unlocked).

Input: ([-1, 0, 0], [('lock', 1), ('lock', 2), ('lock', 0), ('unlock', 1), ('lock', 0)])

Expected Output: [True, True, False, True, False]

Explanation: Root 0 with children 1 and 2. lock(1) ok, lock(2) ok. lock(0) fails: two locked descendants. unlock(1) ok. lock(0) still fails because descendant 2 remains locked.

Input: ([-1, 0, 1, 2, 3, 4], [('lock', 5), ('lock', 0), ('isLocked', 5), ('unlock', 5), ('lock', 0), ('isLocked', 3)])

Expected Output: [True, False, True, True, True, False]

Explanation: Deep chain 0->1->2->3->4->5. lock(5) ok (leaf). lock(0) fails: descendant 5 locked. isLocked(5) True. unlock(5) ok. lock(0) now ok. isLocked(3) is False (only 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.

Quick Overview