Design a hierarchical locking tree

Q: Design a hierarchical locking tree

This question evaluates a candidate's ability to design efficient tree-based data structures and algorithms for maintaining hierarchical lock state, including handling ancestor/descendant constraints and ensuring amortized time complexity.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

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: (

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. (
unlock(x): if x is locked, unlock it and return true; otherwise return false. (
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).

Design a hierarchical locking tree

Overview

Comments (0)