DSA & Algorithms
Part 14 of 16 · DSA Advanced & Company FavoritesConcurrency Interview Basics - locks, barriers, bounded buffer
LeetCode concurrency patterns: locks, barriers, bounded buffer, print-in-order style problems.
- 1Gist
- 2Maps
- 3Q&A
- 4Sandbox
Voice readout needs Web Speech Synthesis in this browser.
Several threads share a structure
Prefer
Lock, then wait on a predicate
The mutex excludes. The condition variable sleeps.
- Wait inside while, not if.
- Notify after the state change.
- A bounded queue blocks both sides.
Alternative
Busy-wait on a flag
It wastes a core and still races.
- You lose a wakeup.
- You lock in two orders and deadlock.
- You treat JavaScript as the multithreaded runtime.
Lock, change, signal
Waiters recheck the predicate.
- 1
Take the mutex
Shared fields change only while holding it. - 2
Wait in a while
The predicate may still be false after wakeup. - 3
Signal after the write
Then release.
Overview
LeetCode concurrency patterns: locks, barriers, bounded buffer, print-in-order style problems.
When companies ask this
Recognition cues: Print in Order; FizzBuzz multithreaded; bounded blocking queue; dining philosophers; traffic light / H2O.
Note: Language APIs differ. Interviews care about correctness invariants more than syntax.
Mental model
Decisions
- 1
Step 1 Shared state needs coordination
- nextStep 2 What must wait?
- ?
Step 2 What must wait?
- mutual exclusionStep 3a Mutex around the critical section
- until a condition holdsStep 3b Condition variable - wait in a while loop
- N threads meet, reusableStep 3c Barrier
- wait for N events, one shotStep 3d CountDownLatch
- 3
Step 3a Mutex around the critical section
- 4
Step 3b Condition variable - wait in a while loop
- nextStep 4 Signaler changes the predicate under the same lock, then notifies
- if instead of while, or predicate changed without the lockFailure path - spurious or lost wakeup
- 5
Step 3c Barrier
- 6
Step 3d CountDownLatch
- 7
Step 4 Signaler changes the predicate under the same lock, then notifies
- 8
Failure path - spurious or lost wakeup
Lesson map
Concurrency Interview Basics - locks, barriers, bounded buffer
LeetCode concurrency patterns: locks, barriers, bounded buffer, print-in-order style problems.
Architecture. Step 1 Shared state needs coordination Ready. Step 2 What must wait? Ready. Step 3a Mutex around the critical section Ready. Step 3b Condition variable - wait in a while loop Ready. Step 3c Barrier Ready. Step 3d CountDownLatch Ready. Step 4 Signaler changes the predicate under the same lock, then notifies Ready. Failure path - spurious or lost wakeup Ready
Select a node to see why it exists, or an edge to see the protocol, direction, effect, and consequence.
Mermaid export
flowchart TB S["Step 1 Shared state needs coordination Ready"] K["Step 2 What must wait? Ready"] M["Step 3a Mutex around the critical section Ready"] CV["Step 3b Condition variable - wait in a while loop Ready"] BR["Step 3c Barrier Ready"] LT["Step 3d CountDownLatch Ready"] P["Step 4 Signaler changes the predicate under the same lock, then notifies Ready"] F["Failure path - spurious or lost wakeup Ready"] S -->|continues| K K -->|mutual exclusion| M K -->|until a condition holds| CV K -->|N threads meet, reusable| BR K -->|wait for N events, one shot| LT CV -->|continues| P CV -->|if instead of while, or predicate changed without the lock| F
Core template (Python)
Press Run. Snippets must be self-contained — no network, files, or native modules.
Core template (TypeScript)
Press Run. Snippets must be self-contained — no network, files, or native modules.
Complexity + pitfalls
- Correctness over micro-opts; avoid busy-wait.
- Pitfalls: spurious wakeup (wait in a while loop); lost wakeup (change the predicate and notify under the same lock); deadlock (fixed lock order).
Interviewer traps
LeetCode drill (real problems)
- Print in Order
- Print FooBar Alternately
- Print Zero Even Odd
- Fizz Buzz Multithreaded
- Building H2O
- Design Bounded Blocking Queue
- The Dining Philosophers
- Traffic Light Controlled Intersection
- Web Crawler Multithreaded
YouTube
Interview Q&A
Mutex vs semaphore?
Answer
Mutex ownership; semaphore counting permits.
Condition wait?
Answer
Release lock, sleep, reacquire; loop on predicate.
Bounded buffer?
Answer
Wait if full/empty; notify.
Deadlock prevention?
Answer
Global lock order; avoid hold-and-wait.
Print in order?
Answer
Events/latches chain first->second->third.
Dining philosophers?
Answer
Limit eaters or asymmetric forks.
Related?
Answer
queue-deque, design DS, system-design-lite.
JS note?
Answer
Event loop; LC uses Java/Python/C++ for true threads.