⚖️ File 06: The Two Optimal Solutions — `set` vs `count` (CRITICAL DISTINCTION)

This is the most important design decision in Part A that directly impacts Part B. Your interviewer WILL ask about optimization. Know both approaches cold.

🌳 The Problem

In the naive solution, lock() does a full BFS/DFS on the subtree to check if any descendant is locked → O(N). We want O(1).

Two approaches to get O(1) descendant checking:

Approach	Data Structure	Descendant Check
Approach A: Set	`set<Node*> lockedDescendants` per node	`set.empty()` → O(1)
Approach B: Count	`int lockedDescCount` per node	`count > 0` → O(1)

Both give O(1) descendant checks. But they differ dramatically in upgrade()!

✅ Approach A: `set<Node*> lockedDescendants` (THE TRULY OPTIMAL ONE)

Data Structure:

struct Node {
    string name;
    int lockedBy = -1;
    Node* parent;
    vector<Node*> children;
    set<Node*> lockedDescendants;  // ← stores WHICH descendants are locked
};

How It Works:

On Lock(X, uid):

Check: X.lockedBy != -1? → false           O(1)
Check: X.lockedDescendants.empty()? → O(1)
Walk ancestors: any ancestor locked? → O(log_M N)
All pass → X.lockedBy = uid
Walk UP from X to root:
   for each ancestor A:
       A.lockedDescendants.insert(X)           O(log_M N)

On Unlock(X, uid):

1. Check: X.lockedBy == uid? → O(1)
2. X.lockedBy = -1
3. Walk UP from X to root:
   for each ancestor A:
       A.lockedDescendants.erase(X)            O(log_M N)

On Upgrade(X, uid):

1. Check: X.lockedBy == -1? → O(1)
2. Check: X.lockedDescendants NOT empty? → O(1)
3. Check: ALL nodes in X.lockedDescendants have lockedBy == uid
   → Just iterate the SET! We know exactly which nodes to check.
   → O(K) where K = number of locked descendants
4. Check: no ancestor locked → O(log_M N)
5. Copy the set, unlock each descendant, lock X
   → O(K × log_M N)

Complexities:

Operation	Time Complexity	Why
Lock	O(log_M N)	Ancestor walk + propagate up
Unlock	O(log_M N)	Propagate up (erase from ancestor sets)
Upgrade	O(K × log_M N)	K = locked descendants, each unlock is O(log_M N)

Code (C++):

#include <bits/stdc++.h>
using namespace std;

struct Tree {
    string name;
    Tree* head;
    vector<Tree*> childrens;
    bool islocked;
    set<Tree*> lockedDescendants;  // ← THE KEY DATA STRUCTURE
    int locked;                    // uid (-1 = unlocked)
    
    Tree(string n, Tree* m) {
        name = n;
        locked = -1;
        head = m;
        islocked = false;
    }
};

struct TreeManager {
    Tree* root;
    unordered_map<string, Tree*> mp;
    
    // ... buildTree code ...
    
    void informAncestors(Tree* r, Tree* current, bool isLocking) {
        while (r) {
            if (isLocking) {
                r->lockedDescendants.insert(current);
            } else {
                r->lockedDescendants.erase(current);
            }
            r = r->head;
        }
    }
    
    bool lock(string name, int id) {
        Tree* r = mp[name];
        // Check self
        if (r->islocked || !r->lockedDescendants.empty()) return false;
        // Check ancestors
        Tree* par = r->head;
        while (par) {
            if (par->islocked) return false;
            par = par->head;
        }
        // Lock and propagate
        informAncestors(r->head, r, true);
        r->islocked = true;
        r->locked = id;
        return true;
    }
    
    bool unlock(string name, int id) {
        Tree* r = mp[name];
        if (!r->islocked || r->locked != id) return false;
        // Remove from ancestors
        informAncestors(r->head, r, false);
        r->islocked = false;
        r->locked = -1;
        return true;
    }
    
    bool upgrade(string name, int id) {
        Tree* r = mp[name];
        if (r->islocked || r->lockedDescendants.empty()) return false;
        
        // Check: all locked descendants belong to same uid
        for (Tree* it : r->lockedDescendants) {
            if (it->locked != id) return false;
        }
        
        // Check ancestors
        Tree* par = r->head;
        while (par) {
            if (par->islocked) return false;
            par = par->head;
        }
        
        // ⚠️ CRITICAL: Copy the set FIRST!
        // Because unlock() modifies the set (erase during iteration = UB)
        set<Tree*> toUnlock = r->lockedDescendants;
        for (Tree* it : toUnlock) {
            unlock(it->name, id);
        }
        lock(name, id);
        return true;
    }
};

⚠️ Approach B: `int lockedDescCount` (LOOKS OPTIMAL, BUT ISN'T FOR UPGRADE)

Data Structure:

struct Node {
    string name;
    int lockedBy = -1;
    Node* parent;
    vector<Node*> children;
    int lockedDescCount = 0;  // ← just a COUNT, not which ones
};

How It Works:

On Lock(X, uid):

Check: X.lockedBy != -1? → O(1)
Check: X.lockedDescCount > 0? → O(1)        ← same as set!
Walk ancestors: any locked? → O(log_M N)
All pass → X.lockedBy = uid
Walk UP: for each ancestor, ancestor.lockedDescCount++ → O(log_M N)

On Unlock(X, uid):

Check: X.lockedBy == uid? → O(1)
X.lockedBy = -1
Walk UP: for each ancestor, ancestor.lockedDescCount-- → O(log_M N)

On Upgrade(X, uid): ← HERE IS THE PROBLEM

1. Check: X.lockedDescCount > 0? → O(1)
2. But wait... WHICH descendants are locked??
   We only know HOW MANY, not WHICH ONES.
   We must BFS/DFS the entire subtree to FIND them!
   → O(N) in worst case!!! 🚨
3. Then check each found locked descendant has same uid
4. Unlock each, lock X

Complexities:

Operation	Time Complexity	Why
Lock	O(log_M N)	Same as set approach
Unlock	O(log_M N)	Same as set approach
Upgrade	O(N) 🚨	Must BFS to FIND which descendants are locked!

The Upgrade Problem — Worked Example:

              World
            /       \
         Asia       Africa
        /    \     /     \
     China  India SA     Egypt
     
Suppose China and India are locked by uid=5.
We call upgrade(Asia, 5).

WITH SET:
  Asia.lockedDescendants = {China, India}
  → Iterate the set: O(2) to check both are uid=5
  → Unlock China, India: O(2 × log N)
  → Total: O(K × log N) where K=2

WITH COUNT:
  Asia.lockedDescCount = 2  (we know there are 2, but WHERE?)
  → Must BFS from Asia: visit China ✓ (locked), India ✓ (locked)
  → But what if the tree has 1000 nodes under Asia?
  → We visit ALL 1000 to find the 2 locked ones
  → Total: O(N) worst case! 🚨

📊 Head-to-Head Comparison

Aspect	`set` Approach	`count` Approach
Lock time	O(log_M N)	O(log_M N)
Unlock time	O(log_M N)	O(log_M N)
Upgrade time	O(K × log_M N) ✅	O(N) ❌
Descendant check	O(1): `set.empty()`	O(1): `count > 0`
Memory per node	O(K) for the set	O(1) just an int
Thread safety	Harder (set isn't thread-safe)	Easier (`atomic<int>`)
Find locked descs	O(1) — they're IN the set	O(N) — must search

🤔 So Which Should You Use?

For Part A (Single-Threaded): Use the `set` approach

Meets all complexity requirements
Upgrade is O(K × log_M N) as required by the problem
The count approach fails the upgrade complexity requirement

For Part B (Multi-Threaded): It's complicated

The set approach is better algorithmically, but:

set<Node*> is NOT thread-safe for concurrent modifications
Two threads inserting into the same ancestor's set = memory corruption
You need per-node mutexes/spinlocks to protect the set

The count approach:

int lockedDescCount can be made atomic<int> → thread-safe with no lock!
fetch_add(1) and fetch_sub(1) are single instructions
Much simpler thread-safety, but worse upgrade complexity

The Interview Answer:

"For thread-safe implementation, I'd use the set approach for algorithmic correctness (O(K × log N) upgrade), protected by per-node spinlocks. The count approach is simpler to make thread-safe (just use atomic<int>), but it loses the ability to find which descendants are locked, making upgrade O(N)."

"If the interviewer specifically asks for a lock-free approach using only atomics, I'd switch to the count approach with atomic<int> because sets can't be made lock-free without concurrent data structures."

📝 The Code for Both — Side by Side

Set Approach (lock function):

bool lock(string name, int uid) {
    Tree* r = mp[name];
    if (r->islocked || !r->lockedDescendants.empty()) return false;  // ← set check
    Tree* par = r->head;
    while (par) {
        if (par->islocked) return false;
        par = par->head;
    }
    r->islocked = true;
    r->locked = uid;
    par = r->head;
    while (par) {
        par->lockedDescendants.insert(r);  // ← insert into ancestor's SET
        par = par->head;
    }
    return true;
}

Count Approach (lock function):

bool lock(string name, int uid) {
    Node* r = mp[name];
    if (r->lockedBy != -1 || r->descCount > 0) return false;  // ← count check
    Node* par = r->parent;
    while (par) {
        if (par->lockedBy != -1) return false;
        par = par->parent;
    }
    r->lockedBy = uid;
    par = r->parent;
    while (par) {
        par->descCount++;  // ← increment ancestor's COUNT
        par = par->parent;
    }
    return true;
}

The Critical Difference Shows in Upgrade:

// SET approach — O(K × log N)
bool upgrade_set(string name, int uid) {
    // ... checks ...
    // We KNOW which descendants are locked:
    for (Tree* desc : r->lockedDescendants) {  // ← iterate the set directly
        if (desc->locked != uid) return false;
    }
    set<Tree*> copy = r->lockedDescendants;
    for (Tree* desc : copy) {
        unlock(desc->name, uid);  // O(log N) each
    }
    lock(name, uid);
    return true;
}

// COUNT approach — O(N) 🚨
bool upgrade_count(string name, int uid) {
    // ... checks ...
    // We DON'T know which descendants are locked!
    // Must BFS the ENTIRE subtree to find them:
    queue<Node*> q;
    q.push(r);
    vector<Node*> lockedOnes;
    while (!q.empty()) {           // ← O(N) BFS!
        Node* cur = q.front(); q.pop();
        if (cur->lockedBy != -1) {
            if (cur->lockedBy != uid) return false;
            lockedOnes.push_back(cur);
        }
        for (Node* child : cur->children) q.push(child);
    }
    for (Node* desc : lockedOnes) {
        unlock(desc->name, uid);
    }
    lock(name, uid);
    return true;
}

📝 What to Say to the Interviewer

"There are two approaches for O(1) descendant checking:

The set approach stores a set<Node*> lockedDescendants in each node. This gives O(1) descendant check AND O(K × log_M N) upgrade because we know exactly which descendants are locked.

The count approach stores an int lockedDescCount. This also gives O(1) descendant check, but upgrade becomes O(N) because we only know HOW MANY descendants are locked, not WHICH ones — we must BFS the subtree to find them.

The set approach meets the problem's complexity requirements. The count approach does NOT for upgrade. However, the count approach is easier to make thread-safe using atomic<int>.

For production code, I'd use the set approach with per-node locks to protect concurrent set modifications."

06_set_vs_count_optimal.md

⚖️ File 06: The Two Optimal Solutions — set vs count (CRITICAL DISTINCTION)

🌳 The Problem

✅ Approach A: set<Node*> lockedDescendants (THE TRULY OPTIMAL ONE)

Data Structure:

How It Works:

Complexities:

Code (C++):

⚠️ Approach B: int lockedDescCount (LOOKS OPTIMAL, BUT ISN'T FOR UPGRADE)

Data Structure:

How It Works:

Complexities:

The Upgrade Problem — Worked Example:

📊 Head-to-Head Comparison

🤔 So Which Should You Use?

For Part A (Single-Threaded): Use the set approach

For Part B (Multi-Threaded): It's complicated

The Interview Answer:

📝 The Code for Both — Side by Side

Set Approach (lock function):

Count Approach (lock function):

The Critical Difference Shows in Upgrade:

📝 What to Say to the Interviewer

⚖️ File 06: The Two Optimal Solutions — `set` vs `count` (CRITICAL DISTINCTION)

✅ Approach A: `set<Node*> lockedDescendants` (THE TRULY OPTIMAL ONE)

⚠️ Approach B: `int lockedDescCount` (LOOKS OPTIMAL, BUT ISN'T FOR UPGRADE)

For Part A (Single-Threaded): Use the `set` approach