🔥 Hackathon Part B — Complete Guide (Tailored to YOUR Solution)

This guide is written specifically for YOUR Part A approach:

• unordered_map<string, int> for name → index mapping
• vector<vector<int>> adj for adjacency list (parent → children)
• vector<int> parent where parent[i] gives parent of node i
• vector<int> locked where locked[i] stores uid (-1 = unlocked)
• Separate helper functions for ancestor check, descendant check, etc.

Every answer below is written from YOUR perspective. Memorize these explanations.

📋 Table of Contents

1. What to Expect — The Full Day Flow
2. PHASE 1: Explaining Your Part A Solution
3. PHASE 2: Optimization Questions
4. PHASE 3: The Thread-Safety Core Task
5. PHASE 4: Identifying Race Conditions
6. PHASE 5: Solutions — Coarse to Fine-Grained
7. PHASE 6: Building Your Own Mutex
8. PHASE 7: The "No Primitives" Solution — Software Algorithms & Set-and-Test
9. PHASE 8: Finding Bugs in "Thread-Safe" Solutions
10. PHASE 9: Thread Interleaving Traces
11. PHASE 10: OS / CN / Fundamentals Questions
12. PHASE 11: Resume & Project Deep-Dive
13. Every Possible Question — With Full Answers
14. Quick-Reference: Things to Say Out Loud
15. Common Mistakes to Avoid
16. Mental Preparation & Endurance Tips

1. 📅 What to Expect — The Full Day Flow

Format

• You are assigned a mentor on Slack, sometimes paired with a Google Meet call
• Duration is wildly inconsistent — reports range from ~6 hours to 9am–9pm to spanning two days
• One account describes a 17-hour stretch
• Budget for a full day. Eat well beforehand. Keep water nearby.

The Step-by-Step Flow

Important Clarification You Should Ask Early

Based on real experiences, ask this question early:

You: "Just to clarify -- in Part B, are we making only the lock() method thread-safe, or all three methods (lock, unlock, upgrade)?"

In most cases the answer is: "We just care about lock method in Part B hackathon."

But be mentally prepared if they say all three.

2. 🎤 PHASE 1: Explaining Your Part A Solution

This is the FIRST thing that happens. The interviewer opens your submitted code. You need to walk through it confidently.

Question 1: "Explain the logic that you used to solve the Hackathon Part A question and its time and space complexity."

How You Should Answer (Full Script):

You: "I approached this problem by first converting every node name to an integer index using an unordered_map<string, int>. This way, all subsequent operations work purely with integer indices, giving me O(1) lookup from name to index.

Then I built three core data structures:

1. vector<vector<int>> adj -- An adjacency list where adj[i] gives me all the children of node i. I built this by processing the input nodes in BFS (level-order) fashion, assigning up to M children to each node.

2. vector<int> parent -- Where parent[i] gives me the parent of node i. The root has parent[0] = -1. This gives me O(1) access to any node's parent.

3. vector<int> locked -- Where locked[i] stores the uid that locked node i. Initially all values are -1, meaning no node is locked. When a node is locked, I store the uid there.

For the three operations:

Lock(node, uid):

• First, I check if the node itself is already locked: if (locked[node] != -1) return false;
• Then I check all ancestors by walking up using the parent array: cur = parent[node] and keep going until cur == -1 (root's parent). If any ancestor has locked[ancestor] != -1, return false.
• Then I check all descendants by doing a BFS/DFS through adj[node]. If any descendant has locked[desc] != -1, return false.
• If all checks pass, I set locked[node] = uid and return true.

Unlock(node, uid):

• Check if locked[node] == uid. If not, return false.
• If yes, set locked[node] = -1 and return true.

UpgradeLock(node, uid):

• Check that the node itself is NOT locked: locked[node] == -1
• Check that at least one descendant IS locked
• Check that ALL locked descendants are locked by the same uid
• Check that no ancestor is locked
• If all pass: unlock all locked descendants (set their locked[desc] = -1), then lock the node itself (locked[node] = uid)"

Time Complexity (Derive Verbally -- Practice This):

You: "For the time complexity:

Lock: O(log_m N) for the ancestor check -- because I walk from the node up to the root, and the height of a balanced M-ary tree with N nodes is log base M of N. But the descendant check is O(N) in the worst case because I'm doing a BFS/DFS through the subtree rooted at the node, and in the worst case that subtree could be the entire tree.

So overall, lock is O(N) because the descendant check dominates.

Unlock: O(1) -- I just check locked[node] == uid and set locked[node] = -1. There's no ancestor/descendant walk needed for unlock.

Upgrade: O(N) -- because I need to traverse all descendants to check if they're all locked by the same uid, then unlock them. Plus the ancestor check which is O(log_m N), so overall O(N).

Space Complexity: O(N) -- the adjacency list, parent array, and locked array each take O(N) space."

Question 2: "Why did you use adjacency list with integer indices instead of a Node struct with pointers?"

How You Should Answer:

You: "I chose this approach because:

1. Simplicity and speed -- Integer indices on flat vectors give O(1) direct array access. There's no pointer chasing overhead. The memory is contiguous, which is cache-friendly.

2. Easy to build -- Given the BFS-order input, I can build the parent and adjacency list arrays with a simple loop and a queue. The index arithmetic maps naturally to the level-order input.

3. O(1) parent access -- parent[i] is a direct array lookup. No hash map needed for the parent relationship.

4. Familiar and less error-prone -- I'm comfortable with index-based graph representations from competitive programming. It reduces the chance of bugs with pointer management.

The trade-off is that I don't have a lockedDescendants set in each node, so my descendant check is O(N) instead of O(1). If I had maintained a lockedDescendants set per node, I could achieve O(1) for that check. I can discuss how to optimize that."

Question 3: "Walk me through what happens when Lock(China, 9) is called."

How You Should Answer (Trace Through Your Code):

You: "Let me trace through my code step by step.

First, I look up 'China' in my nameToIndex map. Say China maps to index 4.

Step 1: Check locked[4]. It's -1, so China is not already locked. Pass.

Step 2: Walk up ancestors. parent[4] gives me, say, index 1 (Asia). Check locked[1] -- it's -1, Asia is not locked. Pass. Then parent[1] gives me index 0 (World). Check locked[0] -- it's -1, World is not locked. Pass. Then parent[0] is -1, meaning we've reached above the root. All ancestors are clear. Pass.

Step 3: Check descendants. I do BFS starting from node 4 (China). I look at adj[4] -- if China is a leaf, adj[4] is empty. No descendants to check. Pass.

Step 4: All checks passed. Set locked[4] = 9. Return true.

Now China is locked by uid 9."

Question 4: "What are the edge cases in your solution?"

How You Should Answer:

You: "The key edge cases I handle are:

1. Locking an already-locked node -- Even if the same uid tries to lock it again, it returns false because locked[node] != -1.

2. Unlocking with wrong uid -- locked[node] != uid, so it returns false.

3. Unlocking an already-unlocked node -- locked[node] == -1, which is not equal to any valid uid, so it returns false.

4. Upgrade on a leaf node -- A leaf has no descendants, so the 'at least one locked descendant' check fails. Returns false.

5. Upgrade when the node itself is already locked -- First check catches this. Returns false.

6. Upgrade with mixed uids among descendants -- If China is locked by uid 1 and India by uid 2, upgrade on Asia fails for both uid 1 and uid 2.

7. Sibling nodes -- China and India are siblings (both children of Asia). Locking China does NOT prevent locking India, because neither is an ancestor/descendant of the other.

8. Single node tree -- The root has no parent and no children. Lock works (no ancestors or descendants to check). Upgrade always fails (no descendants).

9. After upgrade, descendants are unlocked -- If I upgrade Asia (which unlocks China and India), then trying to unlock China returns false because it's already unlocked."

Question 5: "What happens if you receive 10,000 operations in sequence?"

How You Should Answer:

You: "Each lock operation is at most O(N) because of the descendant check. Each unlock is O(1). Each upgrade is O(N). So 10,000 operations would be at most O(10,000 x N) in the worst case.

For reasonable values of N (say N = 10,000 nodes), that's 10^8 operations -- borderline but should run within the time limit on modern hardware.

If performance is critical, I could optimize the descendant check from O(N) to O(1) by maintaining a lockedDescendants count or set in each node -- but that would require updating ancestors on every lock/unlock, which is O(log_m N) per operation. The trade-off is: faster descendant checks but slightly more work on each lock/unlock. Net result would be O(log_m N) per lock/unlock, which is much better."

3. 🔧 PHASE 2: Optimization Questions

The interviewer will now push you to improve your solution.

Question 6: "Can you improve these complexities?"

How You Should Answer:

You: "Yes. The bottleneck in my current solution is the descendant check in lock(), which is O(N) because I do a BFS/DFS through the entire subtree.

Optimization 1: Maintain a locked descendants count/set per node.

Instead of searching the subtree every time, I can maintain additional information. Two options:

Option A: vector<int> lockedDescCount -- Where lockedDescCount[i] counts how many locked descendants node i has. When I lock node X:

• Walk up from X to root, incrementing lockedDescCount[ancestor] for each ancestor. When I unlock node X:
• Walk up from X to root, decrementing lockedDescCount[ancestor] for each ancestor. Then to check if any descendant is locked: just check lockedDescCount[node] > 0. This is O(1).

Option B: vector<unordered_set<int>> lockedDescendants -- Where lockedDescendants[i] is a set of indices of all locked descendants of node i. When I lock X, I walk up and insert X into each ancestor's set. When I unlock, I walk up and erase X.

• Checking descendants locked: lockedDescendants[node].empty() -- O(1)
• For upgrade, I can iterate the set to check all locked descendants are same uid -- O(K) where K = number of locked descendants

With either option:

• Lock: O(log_m N) -- ancestor check O(log_m N) + descendant check O(1) + propagate up O(log_m N)
• Unlock: O(log_m N) -- propagate up to update ancestor counts/sets
• Upgrade: O(K x log_m N) -- unlock K descendants, each requiring O(log_m N) propagation

Optimization 2: If I'm using set, I can switch to unordered_set for O(1) amortized insert/erase instead of O(log K) for set. The asymptotic complexity stays the same but the constant factor improves -- the code runs faster in practice."

Question 7: "So what will be the final complexity after this change? Same or different?"

How You Should Answer:

You: "The asymptotic Big-O complexity stays the same -- O(log_m N) for lock and unlock, O(K x log_m N) for upgrade. But unordered_set has O(1) average-case insert/erase compared to set's O(log K), so the actual runtime is faster in practice. The time complexity notation doesn't change because the dominant term is the ancestor walk (O(log_m N)), not the set operations."

Question 8: "Why is Lock O(log_m N) and not O(N)?"

How You Should Answer:

You: "With the optimization, the lock operation does three things:

1. Check if the node itself is locked -- O(1)
2. Check if any descendant is locked -- O(1) (just check lockedDescCount[node] > 0)
3. Walk up from the node to the root checking ancestors -- O(height)
4. If all checks pass, walk up again to propagate (update ancestor counts/sets) -- O(height)

The height of a balanced M-ary tree with N nodes is log_M(N). This is because at each level, the number of nodes multiplies by M. Level 0 has 1 node, level 1 has M nodes, level 2 has M^2 nodes... So to accommodate N total nodes, we need log_M(N) levels.

Since the only operation that scales with input size is the ancestor walk, and the ancestor walk is O(height) = O(log_m N), the overall lock operation is O(log_m N).

Without the optimization, I have to BFS the entire subtree for descendant checking, which is O(subtree size) = O(N) in worst case. That's why my original solution was O(N)."

Question 9: "Implement the optimization now."

How You Should Answer (Write This Code):

If they ask you to modify your existing code, here's what to add:

Key point to mention: "Notice that I copy lockedDescendants[node] into a vector before iterating, because each unlock() call modifies the set (removes elements from ancestors' sets). If I iterate the set while modifying it, that's undefined behavior."

4. ⚡ PHASE 3: The Thread-Safety Core Task

This is the main event of Part B. The interviewer will now ask:

Question 10: "Let's say you are running lock/unlock on a multi-core machine. Now you want to let multiple threads run lock(). Will doing lock on two nodes cause a race condition? If yes, how will you solve it?"

Additional Constraints (Mentioned Explicitly):

• Multiple threads running simultaneously should NOT affect correctness
• Try to make the critical sections more granular -- don't create big atomic/synchronized blocks that will kill parallelism
• Consider each individual memory operation (read or write of one variable) as atomic

First Thing You Should Say:

You: "Yes, there will absolutely be race conditions. Let me identify the exact cases where they happen.

Before I list them, let me clarify one thing -- when you say 'consider each operation is atomic', you mean each individual read or write to a single variable (like locked[i] or parent[i]) is atomic, but a compound operation like 'read locked[i], check if it's -1, then write locked[i] = uid' is NOT atomic as a whole -- a context switch can happen between the read and the write. Is that correct?"

(This shows the interviewer you understand the subtlety. They will confirm yes.)

5. 🔍 PHASE 4: The Complete 8 Race Conditions Catalogue

THIS IS THE MOST IMPORTANT SECTION. The #1 thing that separates selected candidates from rejected ones is being able to name the race conditions YOURSELF before the interviewer points them out.

Note on Race Condition 2 vs 4: These are the SAME fundamental problem (concurrent mutation of a shared ancestor's tracking data) but manifest differently depending on your data structure choice:

• If you use unordered_set<int> lockedDescendants → you get Race Condition 2 (Set Corruption / Crash).
• If you use int lockedDescCount → you get Race Condition 4 (Lost Update on counter).
• You will only have ONE of these, not both — whichever matches the data structure you chose.

🔴 Group 1: Lock vs Lock Races (The 3 Classic Ones)

Race Condition 1: Two threads locking THE SAME node simultaneously (TOCTOU)

The Setup:

Expected Behavior:

One should return true, the other should return false. Order doesn't matter -- but exactly ONE must succeed.

What Goes Wrong (Trace Through YOUR Code):

Result: BOTH return true. India is "locked" by uid 7 but T1 also thinks it locked India. BUG!

Why It Happens:

"The check-then-set on locked[node] is not atomic. Thread T1 reads locked[4] == -1, passes the check, but before it can write locked[4] = 5, Thread T2 also reads locked[4] == -1 and also passes. Both proceed to set the lock. This is a classic TOCTOU (Time-Of-Check to Time-Of-Use) bug."

Race Condition 2: Shared Ancestor Mutation — Set Corruption (Sibling Collision)

(This race applies when using unordered_set<int> lockedDescendants. If using integer counter instead, see Race Condition 4.)

The Setup:

Expected Behavior:

Both should succeed -- China and India are siblings, neither is ancestor/descendant of the other.

What Goes Wrong (With the Optimized Version Using lockedDescendants):

When both threads try to propagateUp, they both need to update lockedDescendants[Asia] and lockedDescendants[World].

If the set operations are NOT thread-safe (and std::set / std::unordered_set are NOT thread-safe for concurrent modifications), the insert operations could corrupt the internal data structure -- memory corruption, segfaults, or silently lost data.

Why It Happens:

"Both threads are concurrently modifying the same shared data structure -- lockedDescendants[Asia]. The set container is not thread-safe for concurrent writes. Even if individual memory reads/writes are atomic, a set insertion involves multiple internal operations (rebalancing a tree, updating pointers). Two concurrent inserts can corrupt the set."

Race Condition 3: Ancestor-Descendant conflict -- One thread locks parent, another locks child

The Setup:

Expected Behavior:

Exactly one should succeed. If World is locked, Asia (its descendant) cannot be locked. If Asia is locked, World (its ancestor) cannot be locked.

What Goes Wrong:

Result: BOTH succeed! World is locked AND its descendant Asia is locked. This violates the fundamental invariant.

Why It Happens:

"Thread T2 checks if its ancestor (World) is locked at time T4, sees it's unlocked, and proceeds. But between T4 and T6, Thread T1 locks World. T2 doesn't re-check -- it already passed the ancestor check and continues to lock Asia. The two checks (T2's ancestor check and T1's locking) are not coordinated."

Race Condition 4: Shared Ancestor Mutation — Lost Update on Counter (Alternative to RC 2)

(This race applies when using int lockedDescCount instead of a set. If using set, see Race Condition 2 instead. You will have ONE of these, not both.)

If you use a lockedDescCount integer instead of a set:

Result: lockedDescCount[Asia] should be 2 (two locked children), but it's 1. Lost update bug.

Why It Happens:

"The increment lockedDescCount[i]++ is a read-modify-write: read current value, add 1, write back. If two threads do this concurrently, one update is lost. This is the classic lost update problem."

🟡 Group 2: Lock vs Unlock Races (Very Subtle!)

Race Condition 5: The "Ghost Lock" False Rejection (Lock during Unlock)

• Node India was locked. Thread 1 calls unlock(India).
• Thread 1 sets locked[India] = -1 and begins walking up to remove India from ancestor sets.
• Before Thread 1 updates World, Thread 2 calls lock(World).
• Thread 2 checks World.lockedDescendants → still sees India listed!
• Result: Thread 2 is falsely rejected even though India is already completely unlocked.

Race Condition 6: Stale Ancestor Lock (Lock during Ancestor Unlock)

• World was locked. Thread 1 calls unlock(World).
• Thread 2 calls lock(India).
• Thread 2 checks if ancestor World is locked → reads locked[World] before Thread 1's write to -1 reaches main memory → Thread 2 falsely fails.

🟡 Group 3: Unlock vs Unlock Race

Race Condition 7: Double Unlock on Same Node

• Thread 1 and Thread 2 both call unlock(India, uid=5) at the exact same moment.
• Both read locked[India] == 5 → both pass the check!
• Both walk up to decrement ancestor counters → ancestor's lockedDescCount becomes negative (e.g. -1), corrupting future lock() calls forever.

🔴 Group 4: Lock vs UpgradeLock Race (The "Interleaved Hijack")

Race Condition 8: Descendant Hijack During Upgrade Window

• Thread 1 calls upgrade(Asia, uid=9).
• Thread 1 verifies all descendants (China, India) belong to 9. ✅
• Thread 1 unlocks China and India (they become -1).
• 🚨 Context switch!
• Thread 2 calls lock(China, uid=2) → China is now free, so Thread 2 successfully locks China for user 2!
• Thread 1 resumes and locks Asia for user 9.
• Result: Asia is locked by user 9 AND China is locked by user 2! A complete violation of mutual exclusion — the subtree containment invariant is broken.

🟣 Group 5: The "Rollback Collision" Race

Race Condition 9: Rollback Colliding with a Live Lock

• Thread 1 tries lock(China) → inserts China into Asia.lockedDescendants.
• Thread 1 reaches World and sees World is locked → Thread 1 fails and triggers a Rollback to erase China from Asia.
• At the exact same millisecond, Thread 2 calls lock(India) and tries to insert India into Asia.
• Result: Thread 1's erase() and Thread 2's insert() collide on Asia's set → memory corruption during error recovery!

Summary: All Race Conditions to Name (Say This to the Interviewer)

You: "I can identify race conditions across multiple groups:

Lock vs Lock (the 3 classic ones):

1. Same node, two threads -- The check-then-set on locked[node] is not atomic. Both threads can read 'unlocked', both proceed, both write 'locked'. Result: both return true.
2. Ancestor-descendant conflict -- One thread locks a parent while another thread is still checking if that parent is locked. The check and the lock happen in different threads without coordination.
3. Shared ancestor data corruption -- When two threads lock sibling nodes, both try to update the shared ancestor's lockedDescendants set or counter concurrently. Sets are not thread-safe for concurrent writes, and counter increments are not atomic read-modify-write operations.

Cross-operation races (if the interviewer asks 'any other?'): 4. Lock vs Unlock -- A thread can be falsely rejected if it reads an ancestor's descendant set before an unlock propagation finishes clearing it. 5. Lock vs Upgrade -- A third thread can hijack and lock a newly-freed descendant in the split-second window between when Upgrade unlocks descendants and when it locks the ancestor. 6. Rollback races -- An aborted lock's rollback erase can collide with a concurrent valid lock's insertion on shared ancestors."

6. 🛡️ PHASE 5: Solutions -- Coarse to Fine-Grained

The interviewer will now ask you to solve the race conditions. They expect you to start with the simplest solution and progressively refine when they add constraints.

Solution Level 1: Global Mutex (Will Be Rejected)

You: "The simplest solution is to wrap the entire lock() function in a global mutex. Only one thread can execute lock() at a time."

Interviewer will say: "You are not allowed to lock the complete tree. Multiple threads should be allowed to lock different nodes of the tree simultaneously. If you make the function synchronized, you're not allowing other threads to work on the tree."

Your response: "You're right. A global mutex serializes everything -- it kills all parallelism. Two threads trying to lock completely independent nodes (say, one in Asia's subtree and one in Africa's subtree) would unnecessarily block each other. We need a more granular approach."

Solution Level 2: Synchronized on lock() Method Only (Will Be Rejected)

You: "How about making just the lock() method synchronized?"

Interviewer: "Same problem -- synchronized on the method means only one thread can run it at a time. We need multiple threads to be able to work simultaneously on independent parts of the tree."

Solution Level 3: Per-Node Mutex (Partially Accepted, Then Constrained)

You: "We can give each node its own mutex. When locking node X:

1. Acquire mutexes on node X and all its ancestors (in a consistent order -- always leaf-to-root to prevent deadlocks)
2. Perform the checks
3. If checks pass, mark node as locked and update ancestor data
4. Release all mutexes

This way, two threads operating on independent subtrees can proceed in parallel -- their paths to the root don't overlap until a common ancestor, and by that point we coordinate properly."

Key Point About Deadlock Prevention (And the Upgrade Trap!):

You: "For lock() operations, acquiring locks strictly from leaf to root (bottom-up) prevents deadlocks between concurrent lock() calls because the wait-for graph has no cycles.

HOWEVER, there is a critical deadlock trap when upgrade() is introduced:

• lock(China) acquires locks leaf-to-root (China $\to$ Asia $\to$ World).
• upgrade(Asia) checks/locks descendants root-to-leaf (Asia $\to$ China).
• If Thread 1 calls upgrade(Asia) and acquires Asia's lock, while Thread 2 calls lock(China) and acquires China's lock:
  • Thread 1 holds Asia, waiting for China.
  • Thread 2 holds China, waiting for Asia.
  • 💥 CIRCULAR WAIT $\to$ DEADLOCK!

How to solve this completely:

1. Global Node ID Ordering (Deterministic Order): Assign each node a unique integer ID (e.g., $0$ to $N-1$ in BFS level order). Whenever any operation (lock, unlock, or upgrade) needs to acquire multiple locks, it MUST acquire them in strictly increasing order of Node ID. Since the ordering is globally monotonic, circular wait (Coffman Condition 4) is mathematically impossible.
2. Try-Lock with Backoff: In upgrade(), acquire locks using try_lock(). If any descendant lock cannot be acquired immediately, release all currently held locks, wait a randomized backoff period, and retry."

Why the Interviewer Rejects std::mutex (The "OS Sleep / Futex Overhead"):

Interviewer will say: "Mutex will introduce lag in operations. We are not allowed to use mutex/semaphores. Why is mutex slow?"

Your response: "std::mutex relies on OS primitives like Linux futex (FUTEX_WAIT). Under lock contention, the OS transitions from User Mode (Ring 3) to Kernel Mode (Ring 0), deschedules the thread, enqueues it, and triggers a full context switch (saving CPU registers, flushing TLB, cold CPU cache penalty).

• A Tree of Space path check takes only ~20–40 nanoseconds in L1 cache.
• An OS sleep + context switch + wake-up takes ~1,000–5,000 nanoseconds (thousands of wasted CPU cycles). Putting a thread to sleep for 3,000 ns to wait for a 30 ns operation kills throughput. That's why low-latency systems demand user-space spinlocks or lock-free atomic operations."

Solution Level 4: Lock-Free with Atomic Variables (std::atomic / CAS)

You: "If atomic variables are permitted, we can eliminate locking entirely by using lock-free hardware atomic instructions (std::atomic<int> in C++ or AtomicInteger in Java)."

What is an "Atomic Variable"?

• Regular variable (int x = 0;): Operations like x++ or checking if (x == -1) x = uid; are non-atomic (multiple CPU assembly steps: MOV, CMP, JNE, MOV). A context switch in between causes race conditions (TOCTOU / lost updates).
• Atomic variable (std::atomic<int> x{-1};): Operations like x.compare_exchange_strong(...) and x.fetch_add(1) are executed as a single, indivisible hardware instruction (LOCK CMPXCHG, LOCK XADD). The CPU hardware guarantees that no other core can read or write x midway through the operation.

Tree of Space with std::atomic Implementation:

Why Interviewers Ban Atomic Variables:

Interviewer: "This is clean, but now: I am NOT allowing you to use any atomic variables (std::atomic) or standard libraries. How will you solve it?"

Your response: "Understood. std::atomic is powerful because the hardware and standard library handle the synchronization under the hood. When atomic variables are banned, we must demonstrate how concurrency actually works from first principles:

1. Phase 6: Building our own custom spinlock/mutex using compiler intrinsics (__sync_* / CAS).
2. Phase 7: Pure software-only mutual exclusion algorithms (Peterson's / Lamport's Bakery) using only raw memory reads and writes."

7. 🔨 PHASE 6: Building Your Own Mutex

When the interviewer says "we can't use mutex/semaphores", you respond:

You: "Okay, I can implement my own mutex using compiler-level atomic intrinsics -- specifically __sync_lock_test_and_set and __sync_lock_release. This gives me a spin-lock."

What is Test-and-Set? (Explain This Clearly)

You: "__sync_lock_test_and_set(&variable, new_value) is a hardware-level atomic instruction. It does THREE things as a single, indivisible, uninterruptible operation:

1. Reads the current value of variable
2. Writes new_value into variable
3. Returns the OLD value that was there before the write

Because it's atomic, no other thread can read or write variable between steps 1 and 2. This is guaranteed by the CPU hardware itself."

Implementation Level 1: Basic TAS Spinlock (No Ownership)

⚠️ THE OWNERSHIP FLAW IN BARE SPINLOCKS (Crucial Interview Point!): Notice that SpinLock above only toggles a binary flag (0 vs 1). It has no concept of thread ownership.

• If Thread A calls lock(), Thread B can call unlock() and release the lock!
• This means it technically behaves like a binary semaphore, not a true Mutex.
• In a true Mutex, ONLY the thread that locked the mutex is permitted to unlock it.

Implementation Level 2: The True Mutex (With Strict Thread Ownership)

You: "To make it a true Mutex rather than a binary semaphore, we must record the Thread ID of the locking thread and verify ownership inside unlock(). We use Compare-And-Swap (CAS) to atomically claim ownership."

Why volatile vs Memory Barriers? (Crucial CS Fundamentals Distinction)

Interviewer: "Why did you use volatile? Does volatile make a variable thread-safe in C++?"

Your response: "No! In C and C++, volatile only prevents the compiler from caching the variable in a CPU register or optimizing away reads/writes. It does NOT emit CPU memory fences, does not guarantee atomicity, and does not prevent out-of-order CPU memory reordering (unlike Java's volatile).

To ensure true thread safety across multi-core CPUs:

1. We rely on hardware atomic intrinsics (__sync_lock_test_and_set, __sync_val_compare_and_swap) or C++ std::atomic.
2. __sync_lock_test_and_set provides an Acquire barrier (subsequent memory reads/writes cannot be moved before it).
3. __sync_lock_release provides a Release barrier (prior memory reads/writes must complete and flush before the lock is cleared)."

Why This Is a "Spin Lock":

You: "This is called a spin lock because the thread that fails to acquire the lock doesn't go to sleep or yield the CPU -- it literally spins in a while loop, repeatedly trying to grab the lock. This is fast for short critical sections (no context switch overhead) but wastes CPU cycles if the lock is held for a long time."

Why the Naive Approach Doesn't Work:

You: "This naive version has the same TOCTOU race condition. Between the if check (READ) and the assignment (WRITE), another thread can swoop in and also see isLocked == 0. Both threads then set it to 1 and both think they acquired the lock. The __sync_lock_test_and_set version fuses the read and write into a single atomic instruction, eliminating this gap."

Interviewer Follow-Up: "Now implement thread-safe lock() using your custom mutex."

You: "I can now use my custom Mutex class exactly like std::mutex. Each node gets its own Mutex, and I acquire/release along the ancestor path."

Why this preserves parallelism: "Two threads locking nodes in completely independent subtrees (e.g., one under Asia, one under Africa) acquire spin-locks on completely different nodes. They don't contend at all and proceed in parallel. Only when their paths share common ancestors do they need to coordinate -- and even then, the spin-lock hold times are very short."

8. 🧠 PHASE 7: The "No Primitives" Solution -- Software Algorithms & Set-and-Test

This is the hardest and most commonly failed part. The interviewer will now challenge:

Interviewer: "Now implement thread-safe locking WITHOUT using ANY libraries, atomic variables (std::atomic), compiler atomic intrinsics (__sync_*), mutexes, semaphores, or the synchronized keyword. You ONLY have standard, raw memory reads and writes."

⚠️ The Trap Most Candidates Fall Into: The x++ Myth

Many candidates attempt to write:

CRUCIAL CS FUNDAMENTAL: In C/C++, x++ is NEVER an atomic write. It compiles into 3 separate assembly instructions:

1. MOV EAX, [lockedCount] (Read from RAM to register)
2. INC EAX (Modify register)
3. MOV [lockedCount], EAX (Write back to RAM)

If a context switch occurs between (1) and (3), another thread's update is permanently lost. If you claim x++ is atomic, the interviewer will reject you for failing basic computer architecture!

The True Answer: Pure Software Mutual Exclusion Algorithms

When hardware atomic instructions (LOCK CMPXCHG, XCHG) do not exist, computer science provides pure software mutual exclusion algorithms that rely strictly on atomic single-word memory reads and writes.

Solution A: Peterson's Algorithm (2 Threads per Resource)

If 2 threads compete for a node, Peterson's Algorithm guarantees Mutual Exclusion, Progress, and Bounded Waiting without any hardware primitives:

Proof of Correctness: For both threads to be in the critical section, flag[0] == true and flag[1] == true. But turn can only be 0 or 1, not both. The last thread to write turn will be trapped in the while loop.

Solution B: Lamport's Bakery Algorithm ($N$ Threads)

For $N$ concurrent threads, we use Lamport's Bakery Algorithm (based on ticket numbers in a bakery).

• Each thread takes a ticket number number[i] = 1 + max(all ticket numbers).
• Threads are served in order of smallest ticket number: (number[i], thread_id).
• It relies only on reading and writing memory variables.

Solution C: The Juspay "Set-and-Test" Optimistic Pattern (With Caveats)

If the interviewer specifically asks: "Can we do an optimistic check without building full Peterson/Bakery queues?", then you present the Set-and-Test pattern:

You: "Instead of 'test-then-set' (checking if 0 then setting to 1, which has a huge TOCTOU window), we can use 'set-then-test' (claiming first, then verifying no collision).

However, I must emphasize that for lockedCount++ to be safe, the hardware must support single-instruction increment or we must accept that under raw memory, interleaved increments can still lose updates unless guarded by a software protocol."

The Difference: "Test-and-Set" vs "Set-and-Test"

You: "The philosophical difference is:

• Test-and-Set (Naive): Read first (if == 0), then write (val = 1). A context switch between read and write allows another thread to pass too (TOCTOU).
• Set-and-Test (Optimistic): Write first (val++), then read (if > 1). Both threads register their intent before checking, making collision detection possible."

9. 🐛 PHASE 8: Finding Bugs in "Thread-Safe" Solutions

THE PSYCHOLOGICAL TRAP: The interviewer will present a solution (sometimes yours, sometimes one they suggest) and tell you it's thread-safe. The test is whether you push back and find the bug rather than accepting it.

How to Respond When Interviewer Says "This is thread-safe":

You: "Hmm, I think there might still be some issues. Can I take a minute to think through some specific thread interleavings?"

NEVER just agree. Always trace through specific scenarios.

Bug 1: Same Node -- Both Threads Get Rejected (No One Locks)

The Scenario:

The Buggy Trace:

Result: Both return false. Nobody locked India. lockedCount is back to 0. BUG! Expected one of them to succeed.

Why It Happens:

"The early check (condition1) before the increment creates a window. Both threads pass condition1 seeing lockedCount == 0, then both increment, then both see lockedCount > 1 and both roll back. The 'set-and-test' pattern can cause both threads to fail, violating the requirement that at least one should succeed."

Bug 2: Ancestor-Descendant -- Both Succeed (MAJOR BUG)

The Scenario:

The Buggy Trace:

Result: BOTH return true! World is locked AND Asia (its descendant) is locked. VIOLATES THE INVARIANT.

Why It Happens:

"Thread T1 was about to increment lockedCount[0] but got context-switched before doing so. Thread T2 proceeds with locking Asia, checks World's lockedCount[0] which is still 0, sees no conflict, and locks Asia successfully. Then T1 resumes, increments, and since World is the root (no parent to check), it also succeeds. Neither thread saw the other's lock because the increment happened too late."

The Key Insight to Communicate (The Interview Differentiator):

You: "This bug reveals the fundamental limit of naive Optimistic Concurrency Control (OCC) without coordination:

1. Multi-Variable Invariant Problem: A single variable read or write being atomic is not enough when our business invariant spans multiple separate nodes (locked[World] and locked[Asia]). The state of the tree can change midway between checking node $A$ and modifying node $B$.
2. How Systems Actually Solve This:
   • Path 1 (Hardware Atomics Permitted): In real production systems (and when compiler intrinsics are allowed), we use fine-grained per-node spinlocks or CAS state transitions (std::atomic<int> or __sync_val_compare_and_swap), always acquiring locks in a Global Node ID order to eliminate deadlocks.
   • Path 2 (Strict Software-Only, No Hardware Atomics): When hardware atomic instructions are strictly prohibited, we protect the critical section using Lamport's Bakery Algorithm (or Peterson's Algorithm for 2 threads), which guarantees mutual exclusion using only ordinary atomic memory reads and writes.

The key is understanding why naive check-then-set and set-and-test break across multi-node trees, and knowing the exact theoretical and practical primitives that fix them."

10. 🧵 PHASE 9: Thread Interleaving Traces

The interviewer will ask you to trace specific scenarios on demand. Here are the ones to practice:

Trace Format (Use This Exact Format):

Scenario 1: Two threads lock same node (same uid)

Scenario 2: Two threads lock same node (different uid)

Scenario 3: Parent and child lock attempt

Scenario 4: Siblings lock (should both succeed)

But the race condition is in propagateUp -- both threads insert into lockedDescendants[Asia] concurrently. Need synchronized access to the set.

11. 📚 PHASE 10: OS / CN / Fundamentals Questions

These come toward the end of Part B. Prepare these specific answers.

Q: "What is a process vs a thread?"

You: "A process is an independent program in execution with its own memory space -- its own code segment, data segment, heap, and stack. Two processes don't share memory (unless explicitly using IPC like shared memory).

A thread is a lightweight unit of execution within a process. Multiple threads in the same process share the same code, data, and heap, but each thread has its own stack and program counter. This makes thread creation faster and inter-thread communication easier (they can directly access shared variables), but it also introduces synchronization challenges -- which is exactly what we've been discussing with the tree of space problem.

When to use processes: when you need isolation (one crash shouldn't affect another). When to use threads: when you need shared data and fast communication within the same task."

Q: "What happens when you play a song and write code on a single-core PC?"

You: "On a single-core CPU, true parallelism is impossible -- only one thread/process runs at a time. The OS creates the illusion of parallelism through context switching -- rapidly switching between the music player process and the code editor process.

When a context switch happens:

1. The OS saves the current process's state (register values, program counter, stack pointer) into its PCB (Process Control Block)
2. The OS loads the saved state of the next process from its PCB
3. The CPU resumes executing the next process

This happens so fast (typically every 1-10 milliseconds) that it feels like both programs are running simultaneously. The scheduler (using algorithms like Round Robin) decides which process gets CPU time next.

The overhead: each context switch takes time to save/restore state, flush caches, etc. This is why on a single-core machine, running too many programs slows everything down."

Q: "What are the DNS record types?"

You:

• A record -- Maps a domain name to an IPv4 address (e.g., google.com -> 142.250.190.46)
• AAAA record -- Maps a domain name to an IPv6 address
• CNAME record -- Canonical Name -- creates an alias. Maps one domain name to another (e.g., www.google.com -> google.com). It's a redirect at the DNS level.
• MX record -- Mail Exchange -- specifies the mail server responsible for receiving emails for the domain
• NS record -- Name Server -- specifies which DNS servers are authoritative for the domain
• TXT record -- Text -- stores arbitrary text. Used for domain verification (SPF, DKIM for email authentication), and other metadata"

Q: "What is idempotency and why does it matter in payment systems?"

You: "Idempotency means that making the same request multiple times produces the same result as making it once. For example, if I send 'charge 500 to card ending 1234' twice due to a network retry, the customer should only be charged 500 once, not 1000.

Why it's critical in payments:

• Network failures cause automatic retries
• Users may double-click the 'Pay' button
• Mobile apps may resend requests on reconnection

How to implement: Each transaction gets a unique idempotency key (a UUID generated by the client). The server stores: idempotency_key -> response. When a duplicate request arrives with the same key, the server returns the stored response without processing the transaction again.

At Juspay specifically, this is critical because they process 300M+ transactions per day across multiple payment providers. Every retry must be idempotent."

Q: "How does SSL/TLS certificate validation work? How does your computer validate a CA?"

You: "When you visit https://google.com:

1. Client Hello -- Your browser sends supported TLS versions and cipher suites
2. Server Hello -- Server responds with its chosen cipher suite and its certificate (containing its public key, signed by a Certificate Authority)
3. Certificate Validation -- Your browser validates the certificate:
   • Checks the certificate isn't expired
   • Checks the domain matches
   • Traces the certificate chain up to a Root CA
   • Your OS/browser ships with a pre-installed trust store of Root CA certificates (like DigiCert, Let's Encrypt). If the chain leads to one of these trusted roots, the certificate is valid.
4. Key Exchange -- Client generates a pre-master secret, encrypts it with the server's public key (asymmetric encryption), sends it. Both sides derive the session key.
5. Symmetric Encryption -- All further communication uses the shared session key (symmetric encryption like AES) -- it's faster than asymmetric."

Q: "How does HashMap work internally?"

You: "A HashMap stores key-value pairs using a hash-based approach:

1. Hash Function -- When you insert a key, the HashMap computes hashCode(key) to get an integer, then uses hash % bucketCount to determine which bucket the key goes into.

2. Buckets -- Internally, it's an array of buckets. Each bucket holds entries that hash to the same index.

3. Collision Resolution -- When two keys hash to the same bucket:

   • Before Java 8: Each bucket is a linked list. On collision, the new entry is appended. Lookup in a bucket is O(n) where n = chain length.
   • After Java 8: When a bucket's chain exceeds 8 entries, it's converted from a linked list to a red-black tree. This improves worst-case lookup from O(n) to O(log n).

4. Load Factor & Rehashing -- When the number of entries exceeds capacity x loadFactor (default 0.75), the HashMap doubles its bucket count and rehashes all entries.

5. Average case: O(1) for get/put. Worst case: O(n) (all keys hash to same bucket, pre-Java 8) or O(log n) (Java 8+)."

Q: "What are the four conditions for deadlock?"

You: "A deadlock occurs when all four of these conditions hold simultaneously:

1. Mutual Exclusion -- At least one resource is held in a non-shareable mode (only one thread can use it at a time)
2. Hold and Wait -- A thread holds at least one resource and is waiting to acquire additional resources
3. No Preemption -- Resources cannot be forcibly taken from a thread; they must be released voluntarily
4. Circular Wait -- A circular chain of threads exists where each thread holds a resource the next thread wants

Prevention: Break any one condition.

• Break circular wait: impose an ordering on resource acquisition (e.g., always lock nodes from leaf to root)
• Break hold and wait: require threads to acquire all resources at once (or release all before requesting new ones)
• Break no preemption: allow the OS to forcibly reclaim resources

In our tree locking problem, we prevent deadlocks by always acquiring node locks in a consistent order (leaf-to-root), which breaks the circular wait condition."

Q: "What is cache coherence? What is the MESI protocol?"

You: "In a multicore processor, each core has its own cache (L1, L2). When multiple cores access the same memory location, their caches can hold different (stale) values. Cache coherence protocols ensure that all cores see a consistent view of memory.

MESI Protocol -- Each cache line is in one of four states:

• M (Modified) -- This core has modified the data. No other cache has a valid copy. Must be written back to main memory before anyone else reads it.
• E (Exclusive) -- This core has the data and no one else does. It's clean (matches main memory). Can be promoted to Modified without bus traffic.
• S (Shared) -- Multiple cores have this data. All copies match main memory. To modify, must invalidate other copies first.
• I (Invalid) -- This cache line is stale/empty. Must fetch from main memory or another cache.

This is directly relevant to our tree problem -- when one thread modifies locked[node], the MESI protocol ensures other cores see the updated value (eventually). But 'eventually' is the problem -- without proper synchronization, a thread might read a stale cached value."

12. 🎤 PHASE 11: Resume & Project Deep-Dive

This typically comes toward the end. For EVERY project on your resume, prepare:

1. Problem Statement -- What problem does it solve? (1 sentence)
2. Architecture -- High-level components and how they interact
3. Tech Stack -- Why you chose each technology
4. Your Contribution -- What specifically YOU built
5. Challenges -- Hardest technical challenge and how you solved it
6. Scale -- How many users/requests/data?
7. Trade-offs -- What design trade-offs and why?
8. What Would You Change -- If you rebuilt it, what differently?

Cross-questioning patterns to expect:

• "Why did you use X instead of Y?"
• "What happens if this component fails?"
• "How would you scale this to 10x users?"
• "What's the time complexity of your critical path?"
• "How would you make this thread-safe?"

"Why Juspay?"

"Juspay is building the infrastructure layer for digital payments in India -- processing over 300 million transactions per day for companies like Amazon, Flipkart, and Google Pay. I'm excited about the engineering challenges at this scale: ensuring zero-downtime, idempotent transaction processing, low-latency routing across multiple payment gateways, and building systems that handle India's peak traffic volumes like during sale events. The concurrency and data structure challenges in the hackathon are a great reflection of the kind of engineering problems Juspay solves daily."

13. 📋 Every Possible Question -- With Full Answers

Here is a comprehensive list of every question that has been asked in Part B:

Additional: What About Unlock and Upgrade Thread Safety?

If the interviewer asks about making unlock() and upgrade() thread-safe too:

Unlock Thread Safety:

"Unlock has a simpler race condition -- two threads could try to unlock the same node. With the lockedCount approach, unlock decrements lockedCount. If two threads call unlock simultaneously on the same node, and lockedCount is 1, both read 1, both decrement to 0, and we get lockedCount = -1. The fix is the same -- use atomic decrement or test-and-set."

Upgrade Thread Safety:

"Upgrade is the most complex because it does three things: checks descendants, unlocks them all, then locks the node. The window between unlocking descendants and locking the node is dangerous -- another thread could lock one of those descendants in between. In a production system, you'd hold a lock on the entire path during the upgrade operation."

Key Concepts You Must Be Able to Explain

14. 🗣️ Quick-Reference: Things to Say Out Loud

When Explaining Your Part A Solution:

"I used flat vectors with integer indices for O(1) direct array access. I have an unordered_map for name-to-index mapping, a parent vector for O(1) parent lookup, an adjacency list for children, and a locked vector storing uids. The ancestor check walks up using the parent array in O(log_m N). My original descendant check was O(N) via BFS, but I can optimize it to O(1) using a lockedDescendants set propagated up during lock/unlock."

When Naming Race Conditions:

"There are three key race conditions:

1. Same node, two threads -- the check-then-set on the locked flag is not atomic. Both read 'unlocked', both set 'locked'.
2. Ancestor-descendant conflict -- one thread checks the ancestor is unlocked, another thread locks it between the check and the actual lock.
3. Shared data corruption -- when two threads lock sibling nodes, both try to update the shared ancestor's lockedDescendants set concurrently, corrupting the container."

When Asked "Is This Thread-Safe?":

"Let me trace through a specific interleaving to verify. Suppose Thread A reaches this line, then a context switch happens..."

(NEVER just say "yes looks good" -- always trace!)

When Asked About Approach Without Mutex:

"If hardware atomic primitives are strictly prohibited, the mathematically sound answer is a pure software mutual exclusion algorithm like Peterson's Algorithm (for 2 threads) or Lamport's Bakery Algorithm (for N threads), which requires only atomic single-word memory reads and writes. If we want an optimistic approach, we can discuss set-and-test with lockedCount, but note that lockedCount++ is a 3-step read-modify-write that still requires coordination across multi-node trees to avoid race windows."

When Finding Bugs in Presented Code:

"I think this may have an issue. Let me trace through a specific case: suppose T1 is trying to lock node X and T2 is trying to lock node Y, where X is an ancestor of Y. If T1 reaches [point] and gets context-switched..."

15. ⚠️ Common Mistakes to Avoid

16. 💪 Mental Preparation & Endurance Tips

Before the Interview:

• Sleep well the night before -- some Part B rounds last 8-12 hours
• Eat a proper meal -- you might not get a lunch break
• Keep water and snacks nearby
• Have your code open and ready -- they'll ask you to screen-share your Part A solution
• Practice explaining race conditions OUT LOUD -- hearing yourself say it builds confidence

During the Interview:

• Think out loud -- let the interviewer see your reasoning. Silence feels like you're stuck.
• Start with brute force, then optimize -- show progression
• Don't be afraid to say "I need a minute to think" -- it's better than blurting a wrong answer
• Ask for hints if stuck -- say "Could you give me a direction to think in?" Interviewers want to help.
• If you disagree with the interviewer, say so respectfully -- "I think there might be a case where this breaks. Let me trace through it."
• Stay calm when things go sideways -- unexpected questions, bugs in your code, interviewer challenging you -- it's all part of the process

The Psychological Warfare:

• The interviewer will sometimes deliberately present wrong solutions as correct to test if you push back
• They will sometimes not respond after you point out bugs -- this doesn't mean you're wrong
• They may give you impossible constraints (no atomics, no mutex, no synchronized) -- the point is to see how you reason about the problem, not to reach a perfect solution
• Your goal is to demonstrate understanding, not to write production-ready lock-free code in an interview

After Each Phase:

If there's a break (e.g., "think about this and we'll meet after lunch"):

• Actually think about it -- write notes
• Prepare 2-3 specific interleavings to show when you reconvene
• Review the concepts you were shaky on

Appendix A: Your Part A Code -- Quick Reference for the Interview

When the interviewer opens your submission, this is the structure they'll see. Be ready to explain each part:

Appendix B: The Optimized Version (What to Present When Asked to Improve)

Appendix C: Complexity Summary Card

Last updated: August 29, 2026 Tailored to YOUR vector/index-based adjacency list Part A solution. Sources: Real interview experiences from GeeksforGeeks, LeetCode Discuss, Glassdoor, Medium, Unstop -- 2022 through 2026 batches.