📋 File 10: Interview Cheatsheet — Quick Reference for Part B
Print this. Read it 10 minutes before your interview. It has everything you need to remember.
⚡ The Progression (What to Say in Order)
1. "Yes, there will be race conditions." (name them YOURSELF)
2. "The simplest fix is a global mutex." (then immediately say why it's bad)
3. "Per-node mutex preserves parallelism." (leaf-to-root order)
4. "If mutex is banned, I build my own spinlock with __sync_lock_test_and_set."
5. "If atomics are banned, Peterson's Algorithm (2 threads) or Bakery (N threads)."
6. "For maximum elegance, a custom scheduler that only allows sibling threads."🔴 Race Conditions to Name (Say These FIRST)
The 3 Core Races (Lock vs Lock):
| # | Race | One-line Description |
|---|---|---|
| 1 | Same node, two threads | Both read "unlocked", both write "locked" → both succeed. TOCTOU. |
| 2 | Ancestor-descendant | Thread checks ancestor unlocked, another locks it before Thread finishes. |
| 3 | Shared data corruption | Two threads insert into same ancestor's lockedDescendants set concurrently. |
Extra Races (If Asked "Any Others?"):
| # | Race | One-line Description |
|---|---|---|
| 4 | Lock during Unlock | Thread reads stale lockedDescendants before unlock propagation finishes. |
| 5 | Lock during Upgrade | Thread locks a descendant in the gap between upgrade's unlock-all and lock-self. |
| 6 | Rollback collision | Failed lock's cleanup collides with a valid lock's insertion on shared ancestor. |
| 7 | Double unlock | Two threads unlock same node → ancestor counter goes negative. |
🛡️ Solution Summary Table
| Level | Approach | Allows Parallelism? | Interview Status |
|---|---|---|---|
| 1 | Global mutex | ❌ No | ❌ Rejected immediately |
| 2 | synchronized on method | ❌ No | ❌ Rejected |
| 3 | Per-node std::mutex | ✅ Yes | ⚠️ Accepted then challenged |
| 4 | Per-node custom spinlock (TAS) | ✅ Yes | ✅ Good answer |
| 5 | Lock-free with std::atomic (CAS) | ✅ Yes | ✅ Very good |
| 6 | Peterson's / Bakery (no hardware) | ✅ Yes (limited) | ✅ Shows deep knowledge |
| 7 | Custom scheduler (no primitives) | ✅ For siblings | ✅ Shows creativity |
🗣️ Key Phrases to Use
When Naming Critical Sections:
"The critical section includes three shared variables:
locked[node](the lock flag),lockedDescendants(the tracking set/counter), andlockedBy(the uid). Any concurrent read-modify-write on these is unsafe."
When Explaining Mutex Overhead:
"Our tree check takes ~30 nanoseconds in L1 cache. An OS context switch takes ~3000 nanoseconds. Putting a thread to sleep for 3000 ns to wait for a 30 ns operation kills throughput."
When Building Custom Spinlock:
"
__sync_lock_test_and_setmaps to x86XCHG. It atomically reads and writes in one CPU cycle. I use TTAS optimization to avoid cache-line invalidation during spinning."
When Asked About Deadlock:
"I prevent deadlocks by acquiring locks in leaf-to-root order, breaking circular wait. But if upgrade() is involved, it acquires downward, so I switch to global node-ID ordering."
When Asked About volatile:
"In C++,
volatileonly prevents compiler caching in registers. It does NOT guarantee atomicity or emit memory fences. In Java,volatileIS a memory fence — it guarantees visibility across threads."
When Asked About x++:
"
x++is NOT atomic. It's three instructions: MOV (read), INC (modify), MOV (write). A context switch between read and write causes a lost update."
📊 Complexity Quick Reference
| Operation | Without Optimization | With Set Optimization |
|---|---|---|
| Lock | O(N) — BFS descendants | O(log_M N) — set.empty() + ancestor walk |
| Unlock | O(1) | O(log_M N) — propagate up (erase from sets) |
| Upgrade | O(N) | O(K × log_M N) — K = locked descendants |
Set vs Count:
| Set | Count | |
|---|---|---|
| Lock | O(log_M N) | O(log_M N) |
| Unlock | O(log_M N) | O(log_M N) |
| Upgrade | O(K × log_M N) ✅ | O(N) ❌ |
🔍 Thread Interleaving Trace Template
Time | Thread A | Thread B | Shared State
-----|------------------------------------|------------------------------------|------------------
T1 | [action: what A does] | | [state change]
T2 | | [action: what B does] | [state change]
T3 | [action] | | [state change]
T4 | | [action] | [state change]
RESULT: [both succeed / one fails / invariant violated]Template for Same-Node Race:
T1: lock(India, 5) T2: lock(India, 7)
T1: read locked[India] = -1 → PASS
T2: read locked[India] = -1 → PASS (stale read!)
T1: locked[India] = 5, return true
T2: locked[India] = 7, return true ← OVERWRITE!
RESULT: Both return true. BUG.Template for Ancestor-Descendant Race:
T1: lock(World, 1) T2: lock(Asia, 2)
T1: check descendants(World) → empty → PASS
T2: check ancestors(Asia) → locked[World]==-1 → PASS
T1: locked[World] = 1, return true
T2: locked[Asia] = 2, return true ← Both locked!
RESULT: Invariant violated (ancestor AND descendant locked).⚠️ Don'ts (Common Mistakes)
| ❌ Don't | ✅ Do Instead |
|---|---|
| Say "yes it's thread-safe" without checking | ALWAYS trace through 2+ interleavings |
| Jump straight to global mutex | Start with global mutex, explain why it's bad, then improve |
Claim x++ is atomic | Explain it's 3 instructions (MOV, INC, MOV) |
| Claim spinlock = mutex | Spinlock has no ownership; mutex does |
| Say leaf-to-root prevents ALL deadlocks | Mention the upgrade trap (root-to-leaf vs leaf-to-root) |
| Give up when atomics are banned | Present Peterson's or Bakery algorithm |
| Stay silent for more than 30 seconds | Think out loud: "Let me consider what happens if..." |
| Accept interviewer's "this is correct" | Push back: "Let me trace a specific case to verify..." |
🧠 The Mental Model
HOW DO WE PREVENT RACE CONDITIONS?
┌────────────────────────────────────┐
│ MUTUAL EXCLUSION │
│ (only one thread in CS at once) │
└────────────────────────────────────┘
╱ │ ╲
┌────────────┐ ┌──────────┐ ┌────────────────┐
│ BLOCKING │ │BUSY-WAIT │ │ COORDINATION │
│ (OS SLEEP)│ │ (SPIN) │ │ (SCHEDULING) │
└────────────┘ └──────────┘ └────────────────┘
│ │ │
┌─────────┐ ┌──────────┐ ┌──────────────┐
│ Mutex │ │ Spinlock │ │ Custom │
│ Semaphore│ │ TAS/CAS │ │ Scheduler │
│ Monitor │ │ Peterson │ │ (sibling │
└─────────┘ │ Bakery │ │ isolation) │
└──────────┘ └──────────────┘🏆 The "A+" Answer Structure
If you nail this structure, you will pass:
1. Name race conditions BEFORE being asked (shows you understand)
2. Start with global mutex, explain why it's bad (shows progression)
3. Move to per-node mutex with leaf-to-root order (shows granularity)
4. Explain mutex overhead (futex, context switch) (shows depth)
5. Build custom spinlock with TAS (shows systems knowledge)
6. Present CAS lock-free approach (shows advanced knowledge)
7. When atomics banned: Peterson's / Bakery (shows CS fundamentals)
8. Push back on "this is correct" with traces (shows confidence)
9. Discuss set vs count for upgrade complexity (shows optimization thinking)📂 Files in This Guide
| File | What It Covers | When to Reference |
|---|---|---|
| 01_mutex_explained.md | Mutex internals, per-node code | "Use any tool" stage |
| 02_custom_mutex_spinlock.md | Build your own with TAS/CAS | "No std::mutex" stage |
| 03_atomic_operations.md | atomic<int>, CAS lock-free | "Use atomics" stage |
| 04_synchronized_keyword.md | Java synchronized, ReentrantLock | Java-specific interviews |
| 05_semaphores.md | Why counting semaphore fails | If asked about semaphores |
| 06_set_vs_count_optimal.md | Set vs count for upgrade | Optimization discussion |
| 07_software_algorithms.md | Peterson's, Bakery, Set-and-Test | "No hardware atomics" stage |
| 08_custom_scheduler.md | Sibling scheduling, no primitives | "No primitives at all" stage |
| 09_read_write_locks.md | shared_mutex, read-write separation | Maximizing parallelism |
Good luck. You've got this. 🚀