Coding · Trees
Lock and Unlock Nodes in an N-ary Tree
- Reported once
- Hard
- intern
- 1 source
One candidate write-up. Treat it as a single data point.
Solve it in the playground, with tests
Design a LockTree over n nodes numbered 0 to n-1, built from a parent array in which the single root has parent -1 (node 0 in the example below). lock(node, user) returns true and locks the node only if the node is unlocked and none of its ancestors and none of its descendants is locked, and unlock(node, user) returns true and frees the node only if that same user locked it; otherwise a call returns false and changes nothing. The input is an operation list like a LeetCode design problem: run(ops, args) returns null for the constructor "LockTree" and a boolean for every later call, so with parent [-1,0,0,1,1,2] the calls lock(1,7), lock(3,8), unlock(1,8) return true, false (ancestor 1 is locked), false (wrong user). There are up to 100,000 nodes and calls, user ids are positive integers, and the tree height stays under 1,000.
Restated in our own words, not a quote from Juspay or any page. The answer below is written for this site.
Clarify first
Pin down the input before you touch the keyboard.
I would pin down the semantics first. Does locking a node that is already locked fail even for the same user? Can one user hold many locks at once, as long as no two are on the same root-to-leaf path? What do unlock and lock return when the node does not exist or the user is wrong: a boolean, with the state unchanged? Is the tree given once up front, or does it change? And how deep can it get, because that decides how much a walk up to the root costs.
Assumptions I would state: the tree is fixed, node ids are valid, a failed call changes nothing, locking an already locked node returns false, and the height is small enough that walking to the root is cheap.
Brute force
Say the obvious answer and why it is too slow.
The direct way to answer lock is to inspect every node that could block it. Walk up the parent pointers and check each ancestor, then run a depth-first search over the whole subtree of the node and check each descendant. Unlock is trivial, just compare the owner.
The cost sits in the subtree scan. Locking the root of a tree with 100,000 nodes touches all of them, so one call is O(n), and 100,000 calls on a wide tree reach around ten billion node visits. The scan is wasteful because it re-discovers, call after call, a fact that changes only when somebody locks or unlocks: whether anything below this node is locked. It also needs child lists, which the parent array did not give us.
The insight
The one idea that makes it fast, and why it is correct.
- Brute force
- O(n) per lock
- Time
- O(h) per call, h = tree height
- Space
- O(n)
The pattern is tree with ancestor and descendant counters. The two blocking conditions have different shapes, so give each its own cheap check.
Ancestors are easy to reach: a node has exactly one parent chain, so walking up and looking at each owner costs the height h. Descendants are the expensive side, so we never look at them. Instead every node keeps a counter, lockedBelow, that says how many locked nodes sit strictly below it. When a node is locked, add one to the counter of every ancestor. When it is unlocked, subtract one. A node has a locked descendant exactly when its counter is above zero, which is a single comparison.
Why is it correct? The rule itself keeps the set of locked nodes free of any ancestor and descendant pair, because lock refuses to create one. The counters are only ever changed along the exact ancestor chain of the node being locked or unlocked, and every successful lock is matched by one unlock that undoes the same additions. So after any sequence of calls, each counter equals the number of locked nodes in that subtree. Failed calls touch nothing, so they cannot corrupt the state.
Out loud: "I store the owner of each node and, per node, how many locks are below it. Lock checks the node, its counter and the ancestor chain, then bumps the chain. Unlock checks the owner and reverses the bump. Every call is O(h) with no subtree scans."
Walk it through
A dry run on the example, step by step.
| Step | Call | What decides it | Result | Locked (node:user) | lockedBelow |
|---|---|---|---|---|---|
| 1 | lock(1, 7) | nothing blocks it | true | 1:7 | 0:1 |
| 2 | lock(3, 8) | ancestor 1 is locked | false | 1:7 | 0:1 |
| 3 | lock(2, 8) | nothing blocks it | true | 1:7 2:8 | 0:2 |
| 4 | lock(0, 9) | lockedBelow[0] is 2 | false | 1:7 2:8 | 0:2 |
| 5 | unlock(1, 8) | owner is 7, not 8 | false | 1:7 2:8 | 0:2 |
| 6 | unlock(1, 7) | owner matches | true | 2:8 | 0:1 |
| 7 | lock(3, 8) | ancestors 1, 0 free | true | 2:8 3:8 | 0:2 1:1 |
Use parent = [-1,0,0,1,1,2]: node 0 is the root, nodes 1 and 2 are its children, nodes 3 and 4 hang under 1, and node 5 under 2. The table lists the calls in order.
lock(1,7) finds nothing blocking and succeeds, and node 0 now counts one lock below it. lock(3,8) fails because ancestor 1 is locked. lock(2,8) succeeds, so node 0 counts two. lock(0,9) fails because node 0 counts locks below it. unlock(1,8) fails because node 1 belongs to user 7. unlock(1,7) succeeds and node 0 drops to one. Now lock(3,8) succeeds, since node 1 is free, and both node 1 and node 0 gain a count. The last two columns show the locked nodes and the nonzero counters after each call.
The code
Runnable JavaScript, checked against test cases.
class LockTree {
constructor(parent) {
this.parent = parent;
this.owner = new Array(parent.length).fill(null);
this.lockedBelow = new Array(parent.length).fill(0);
}
hasLockedAncestor(node) {
for (let up = this.parent[node]; up !== -1; up = this.parent[up]) {
if (this.owner[up] !== null) return true;
}
return false;
}
adjustAncestors(node, delta) {
for (let up = this.parent[node]; up !== -1; up = this.parent[up]) {
this.lockedBelow[up] += delta;
}
}
lock(node, user) {
if (this.owner[node] !== null) return false;
if (this.lockedBelow[node] > 0 || this.hasLockedAncestor(node)) return false;
this.owner[node] = user;
this.adjustAncestors(node, 1);
return true;
}
unlock(node, user) {
if (this.owner[node] !== user) return false;
this.owner[node] = null;
this.adjustAncestors(node, -1);
return true;
}
}
function run(ops, args) {
const tree = new LockTree(args[0][0]);
return ops.map((op, i) => (i === 0 ? null : tree[op](...args[i])));
}Runs here in your browser, in a sandboxed worker. Nothing is sent anywhere.
Try your own input
Write JavaScript that calls the code above and prints with console.log. It runs after the solution.
Edge cases
What to test before you say you are done.
Locking an already locked node fails on the owner check, even for the same user, and so does a second lock by another user.
- Unlocking a free node: the owner is null, which never equals a user id, so it returns false.
- Wrong user: unlock leaves the lock and the counters alone.
- The root: its parent is -1, so the upward walk ends at once, and a locked root blocks every other lock.
- Single node tree: both walks are empty and the node locks and unlocks freely.
- Parents with larger ids: only parent pointers are followed, so the order of ids does not matter.
- Sibling subtrees: two nodes that are neither ancestor nor descendant of each other can both be locked.
Follow-ups to expect
Where the interviewer pushes next.
- How would you add an upgrade call that replaces every lock below a node, all held by one user, with a single lock on that node?
- How would you keep each call at O(log n) on a very deep tree, for example with an Euler tour and a Fenwick tree?
- How would you make lock and unlock safe when many threads call them at once?
- How would you list every node a given user currently holds in time proportional to the answer?
Where candidates slip
The mistakes this problem punishes.
The most common slip is checking only one direction, for example looking at ancestors but forgetting that a locked descendant also blocks the lock.
- Scanning the subtree on every lock, which is exactly the cost the counters remove.
- Updating the counters before the checks pass, so a failed lock leaves stale counts.
- Including the node itself in its own counter, which makes a node block itself.
- Forgetting to subtract on unlock, so the counters only ever grow.
- Letting any user unlock a node instead of comparing the owner.
Have a go before you read.
Interviews reward the sketch you make cold. Clarify out loud, draw it, then compare with the answer.
Now make it stick
Where this was reported
Public pages only. Companies do not confirm these, and they rotate their questions, so treat each link as one person's account or one list's tag.