Concurrency

LeetCode tag: Concurrency (~20–30 problems). Depth tier: < 50 problems — core concepts, main patterns, key primitives.

---

Core Concepts

Thread — an independent sequence of execution sharing memory with other threads in the same process. Multiple threads can run the same function simultaneously, causing races if shared state is not protected.

Race condition — two or more threads read-modify-write shared state without coordination, producing results that depend on scheduling order. The source of almost every concurrency bug.

Critical section — a code region that must execute atomically with respect to other threads. Correctness requires that at most one thread (or a bounded number) is inside it at any time.

Atomicity — an operation that completes entirely before any other thread observes its effect. Hardware provides atomic reads/writes for native word sizes; everything else needs explicit synchronization.

Mutual exclusion (mutex / lock) — a binary synchronization object; at most one thread holds it at a time. A thread that cannot acquire it blocks until the holder releases it.

Semaphore — an integer counter with two operations: acquire (decrement; block if count reaches 0) and release (increment; unblock one waiting thread). A mutex is a semaphore initialized to 1. Counting semaphores coordinate bounded resources or signal between threads.

Condition variable — a wait/notify mechanism always paired with a lock. wait() atomically releases the lock and suspends the thread; notify() / notify_all() wakes waiting threads, which must reacquire the lock before returning.

Barrier — a rendezvous point: all N threads must arrive before any may proceed. Used when the next phase requires the previous phase to complete across all threads.

Event — a boolean flag with blocking semantics. wait() blocks until set() is called; clear() resets it. One-shot signalling with no counting.

Monitor — the combination of a lock + one or more condition variables protecting a shared object. Python's threading.Condition is a monitor.

Deadlock — a cycle of threads each waiting for a resource held by the next. Requires: mutual exclusion, hold-and-wait, no preemption, circular wait. Breaking any one condition prevents it.

Starvation — a thread is perpetually denied a resource because others are always preferred. Distinct from deadlock: the system makes progress, but unfairly.

Spurious wakeup — a thread woken from condition.wait() without a corresponding notify. Always recheck the predicate in a loop after waking.

---

Structural Invariants

---

Types / Variants

---

Key Algorithms

Semaphore-Based Ordering

Enforce that method B executes after method A completes by initializing a semaphore to 0, releasing it at the end of A, and acquiring it at the start of B. Generalizes to chains.

• Time: O(1) per operation. Space: O(1).

sem = Semaphore(0)
# in A: do work, then sem.release()
# in B: sem.acquire(), then do work

Condition Variable with Predicate Loop

Wait until a shared condition becomes true. Always wrap wait() in a while loop (not if) to handle spurious wakeups and the window between notify and reacquiring the lock.

• Time: O(1) amortized. Space: O(1).

with cond:
    while not predicate():
        cond.wait()
    # safe to proceed

Barrier Synchronization

Use threading.Barrier(n) when n threads must all reach a checkpoint before any continues. Each thread calls barrier.wait(); the (n)th arrival unblocks all.

• Time: O(1) per thread. Space: O(n) for the waitlist.

Lock-Protected Counter / State Machine

Protect a shared integer (or state enum) with a lock. Threads acquire the lock, check/update the value, then release. Used for turn-based alternation.

with lock:
    shared_state += 1

Event-Based One-Shot Signal

Initialize threading.Event(). The blocking thread calls event.wait(); the signalling thread calls event.set(). Unlike semaphores, set() on an already-set event is idempotent and all waiters unblock.

---

Problem Taxonomy

By Problem Category

Problem Signal → Technique

---

Common Patterns

---

Edge Cases & Pitfalls

• Releasing a semaphore too many times. If release() is called more times than acquire(), the count exceeds its logical maximum and extra threads enter the critical section. Use BoundedSemaphore to catch this.

• Using if instead of while for condition variables. Between notify and the waiter reacquiring the lock, another thread may change the predicate. Always while not predicate(): cond.wait().

• Spurious wakeups. condition.wait() may return without a notify. The while-loop fix covers this simultaneously with the previous pitfall.

• Deadlock from acquisition order. If thread A holds lock-1 and waits for lock-2 while thread B holds lock-2 and waits for lock-1, neither can proceed. Fix: always acquire multiple locks in the same global order across all threads.

• Forgetting to notify after state change. A thread updates shared state under a condition variable but omits notify_all(). Waiting threads sleep indefinitely even though the predicate is now true.

• Calling condition.wait() without holding the lock. In Python this raises RuntimeError. Always use the with cond: context manager.

• Reusing a one-shot Event. Event.set() is permanent until Event.clear() is called. If the event is meant to signal once, do not call clear(); if it must reset per round, call clear() before the next cycle while under a lock.

• Thread starvation with non-fair semaphores. Python's semaphore uses a FIFO waitlist, so starvation is unlikely in practice, but logical starvation can occur if one thread acquires and releases in a tight loop, always re-acquiring before others wake.

• Not joining threads before checking results. Reading shared state before calling thread.join() is a race: the thread may not have written its result yet.

---

Implementation Notes

• Python's threading.Lock is non-reentrant: a thread that calls acquire() twice without releasing will deadlock with itself. Use RLock if re-entrant locking is needed.
• threading.Semaphore in Python is internally protected by a Condition, making it thread-safe, but release() does not enforce an upper bound — use BoundedSemaphore for that.
• The GIL does not protect custom data structures. Even though only one Python bytecode executes at a time, compound read-modify-write operations are not atomic; still use locks.
• condition.notify() wakes exactly one waiter; condition.notify_all() wakes all. Prefer notify_all() when multiple threads might satisfy the predicate after a state change, to avoid missing a thread.
• LeetCode concurrency problems are run in a multi-threaded harness; the solution class is instantiated once and methods are called from different threads concurrently. Initialize all synchronization objects in __init__.
• threading.Barrier raises BrokenBarrierError if a thread times out or if abort() is called. In interview settings, assume no timeout.

---

Cross-Topic Relations

---

Interview Reference

Must-Know Problems

Ordered Execution

• Print in Order (LC 1114) — three methods, enforce A→B→C; classic semaphore chain
• Print FooBar Alternately (LC 1115) — two threads alternating output; ping-pong semaphores

Categorized Output

• Print Zero Even Odd (LC 1116) — three threads, one counter, each thread handles one category; condition variable + counter
• Fizz Buzz Multithreaded (LC 1195) — four threads, divisibility-based categories; condition variable pattern

Producer-Consumer

• Building H2O (LC 1117) — two resource types must combine in fixed ratio; two semaphores + barrier
• The Dining Philosophers (LC 1226) — classic deadlock avoidance; ordered lock acquisition or a waiter semaphore

Barrier / Phasing

• Web Crawler Multithreaded (LC 1242) — crawl level-by-level; thread pool + barrier or concurrent queue

Clarification Questions to Ask

• How many threads will call each method — exactly as specified, or up to N?
• Is the method called at most once per thread, or can the same thread call it multiple times?
• Is output order guaranteed to be observed by the grader, or just that the calls complete?
• Are there timing guarantees, or can threads be delayed arbitrarily?

Common Interview Mistakes

• Initializing a semaphore to 1 when it should be 0 for ordering (1 means "one unit available now", 0 means "wait for a signal").
• Using a bare Lock when a Condition is needed — a lock alone cannot express "wait until counter == 3".
• Not calling notify / notify_all after updating the shared state, leaving waiting threads permanently blocked.
• Using if instead of while around condition.wait(), making the solution fragile under spurious wakeups.
• Releasing locks in the wrong order or forgetting release on an exception path — use with statements to guarantee release.
• Deadlocking the Dining Philosophers by having all philosophers pick up the left fork simultaneously — fix by making one philosopher pick up right-first.

Typical Follow-Up Escalations

• "Now allow up to K threads to execute concurrently" → replace the binary semaphore with Semaphore(k).
• "Now make it work for N threads instead of 2" → generalize ping-pong to a semaphore ring of N elements.
• "How would you detect deadlock at runtime?" → cycle detection on a resource-allocation graph; or timeout + retry with backoff.
• "How does this change if we use processes instead of threads?" → multiprocessing.Semaphore uses OS-level shared memory; the GIL no longer applies; Value / Manager needed for shared state.
• "What if release can be called from a different thread than acquire?" → Lock is not suited (owner-based); use a Semaphore, which has no ownership concept.