Katkat
Back

Design a hierarchical locking tree

AmazonSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

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 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).