š Juspay Part B ā Thread-Safe Tree of Space: Complete Code & Concepts
This folder contains every thread-safe approach you can write for the Tree of Space problem. Each file covers one mechanism in depth: what it is, how it works internally, when to use it, and complete working code.
š File Index
| # | File | What It Covers |
|---|---|---|
| 1 | 01_mutex_explained.md | What is a Mutex? Internals (futex, CMPXCHG, kernel sleep). Global mutex ā Per-node mutex. Full code. |
| 2 | 02_custom_mutex_spinlock.md | Build your own Mutex using __sync_lock_test_and_set (TAS) and CAS. Ownership Mutex. Full code. |
| 3 | 03_atomic_operations.md | std::atomic<int>, AtomicInteger, CAS lock-free approach. compare_exchange_strong. Full code. |
| 4 | 04_synchronized_keyword.md | Java synchronized keyword. Monitor locks. ReentrantLock. How JVM implements it. Full code. |
| 5 | 05_semaphores.md | Binary vs Counting Semaphore. Internals. Why counting semaphore CANNOT work here. Full code. |
| 6 | 06_set_vs_count_optimal.md | ā
THE TWO OPTIMAL SOLUTIONS COMPARED ā
ā set<Node*> lockedDescendants vs int lockedDescCount. Time complexity, upgrade differences, which is truly optimal. |
| 7 | 07_software_algorithms.md | Peterson's Algorithm, Lamport's Bakery, Set-and-Test pattern. No hardware atomics at all. |
| 8 | 08_custom_scheduler.md | The "no synchronization primitives" approach: sibling scheduling. From your Attempt3 Java code. |
| 9 | 09_read_write_locks.md | shared_mutex, shared_lock vs unique_lock. Read-write separation for ancestors. |
| 10 | 10_interview_cheatsheet.md | Quick-reference: what to say at each stage, race conditions summary, traces. |
šÆ Quick Decision Tree: Which Approach When?
Interviewer: "Make lock() thread-safe"
ā
āā "Use any tool" āāāāāāāāāāāāāāŗ std::mutex (per-node) [File 01]
ā or std::atomic CAS [File 03]
ā
āā "No std::mutex allowed" āāāāāŗ Custom spinlock via __sync_* [File 02]
ā or std::atomic CAS [File 03]
ā
āā "No atomics either" āāāāāāāāāŗ Peterson's / Bakery Algorithm [File 07]
ā or Set-and-Test pattern [File 07]
ā
āā "No primitives at all" āāāāāāŗ Custom Thread Scheduler [File 08]
(sibling isolation)ā” The Two Optimal Part A Solutions (Critical Distinction)
| Approach | Descendant Check | Upgrade Complexity | Space |
|---|---|---|---|
set<Node*> lockedDescendants | O(1) ā set.empty() | O(K Ć log_M N) ā iterate set, unlock each | O(N) |
int lockedDescCount | O(1) ā count > 0 | O(N) ā must BFS subtree to FIND which nodes are locked | O(N) |
The
setapproach is the truly optimal one. Thecountapproach has O(1) descendant check but O(N) upgrade because you lose track of which descendants are locked.See File 06 for the full comparison.