Concurrency Problems
6 Concurrency LeetCode problems · Browse tasks by difficulty and choose your next practice problem.
Express ordering with synchronization state
Concurrent workers can run in any order. A correct solution makes the required output order follow from locks, semaphores, or condition predicates, regardless of which thread the scheduler runs first. Print FooBar Alternately is a small example of handing permission from one worker to another.
When to use it
Use a semaphore for a transferable permit, and a condition variable when a worker must wait for shared state to satisfy a predicate. For multiple resources, as in Dining Philosophers, also reason about cycles in the order in which locks are acquired.
Worked example
Two workers must produce foobar twice. Initialize fooPermit = 1 and barPermit = 0.
- The foo worker acquires fooPermit, prints foo, then releases barPermit.
- The bar worker acquires barPermit, prints bar, then releases fooPermit.
- Each worker repeats twice. Even if bar starts first, it waits until foo supplies its permit.
The output is foobarfoobar. Neither worker uses a sleep or assumes a particular execution speed.
Time and space
For n pairs, this design performs O(n) synchronization operations and uses O(1) coordination state. Wall-clock completion also depends on scheduling and the print callbacks, so counting operations does not bound waiting time.
Mistakes to check
- With condition variables, test the predicate in a loop while holding its lock. Waking up does not prove the desired state still holds.
- A notification does not release a condition's lock. Keep state changes and the notification coordinated under that lock.
- Define failure behavior if a callback throws; otherwise its peer can wait forever for a permit that will never be released.
Further reading: Python threading: condition objects and semaphores
Guide reviewed .