How do you approach Dining Philosophers?

Resource hierarchy: every philosopher tries to grab the lower-numbered fork first. That breaks circular wait.

What is the time complexity of Dining Philosophers?

Time complexity: O(n) over the wish list. Space complexity: O(n) for the deferred queue.

What are common mistakes on Dining Philosophers?

Re-checking a condition with if instead of while after waiting. Spurious wakeups are real. Holding a lock across a blocking call, which serialises every other thread behind the slowest one and is how these solutions deadlock. Assuming statements execute in program order without a barrier, a volatile read, or an atomic.

gitGood.dev

← Back to problems

Dining Philosophers

HardOperating Systems

Description

**Concurrency design problem (paper-only).** Threading is not available in the sandbox; the auto-grader validates a simulation of a deadlock-free fork-acquisition order. Five silent philosophers sit at a round table with bowls of spaghetti. Forks are placed between each pair of adjacent philosophers. Each philosopher must alternately think and eat. However, a philosopher can only eat when they have both the left and right forks. Each fork can be held by only one philosopher at a time. After eating, they need to put down both forks so they become available to others. Naïve "pick up left then pick up right" deadlocks if every philosopher grabs a left fork simultaneously. You must produce a deadlock-free schedule. **For the auto-grader:** given an integer array `order` of length `5 * meals` representing the order in which philosophers `0..4` would *like* to eat (each value 0..4, each value appears exactly `meals` times), return an array of the same length giving the order in which they actually eat under the **odd-even** strategy: philosopher `i` is allowed to eat next iff neither of their forks is currently held. The simulation processes the wish-list from left to right; if the current wisher's neighbours are eating they are skipped to the back of a waiting queue, and you re-check the queue first on each step. The output array must be a valid deadlock-free permutation in which no two adjacent philosophers (mod 5) ever appear in adjacent positions of the output.

Example 1

Input: order = [0,1,2,3,4]

Output: [0,2,4,1,3]

Explanation: Philosopher 0 eats; 1 wants to eat but 0's fork is busy → defer. 2 can eat (uses forks 2,3 - free). Then 4. Now queue head is 1: forks 0,1 are free (0 finished long ago, the simulation step model releases on dequeue). The arrangement is deadlock-free.

Constraints

- order.length == 5 * meals - 1 <= meals <= 50 - 0 <= order[i] <= 4 - Each value 0..4 appears exactly meals times.

Dining Philosophers: approach, complexity and pitfalls

A hard concurrency problem, graded against 3 test cases (1 of them hidden).

The pattern: Concurrency

Coordinating threads with locks, semaphores, and condition variables.

Reach for it when you see: Ordering guarantees between threads, bounded buffers, or classic synchronisation puzzles.

More Concurrencyproblems →

If you are stuck

Show the 3-step hint ladder

Resource hierarchy: every philosopher tries to grab the lower-numbered fork first. That breaks circular wait.
For the simulation: maintain a 'currently eating' set and a deferred queue. Pop the next wisher; if both their forks are free, eat (and immediately release - this is a one-step bite). Else queue them.
Re-check the queue head before reading the next wish-list entry.

The optimal approach

Show the approach: Real concurrent design: Resource Hierarchy

Number the forks 0..4. Philosopher `i` always picks up `min(left, right)` first, then `max(left, right)`. Because there is a strict acquisition order across the whole system, no cycle can form in the wait-for graph - and Coffman's circular-wait condition is broken, so the system is deadlock-free.

```

philosopher(i):

while True:

think()

l, r = i, (i + 1) % 5

first, second = (l, r) if l < r else (r, l)

forks[first].lock()

forks[second].lock()

eat()

forks[second].unlock()

forks[first].unlock()

```

Other valid schemes: Chandy-Misra (each philosopher requests forks from neighbours), or limit concurrent eaters to 4 with a counting semaphore.

Simulation walkthrough

Starvation isn't a concern in this small grader - we just need a feasible deadlock-free schedule. The simulation does single-step "bites": a philosopher with both forks free is added to the output and immediately releases. Adjacent philosophers can never both be in the eating set within the same step, so the output never has neighbours back-to-back.

Time: O(n) over the wish list
Space: O(n) for the deferred queue

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Duplicate values. Repeated values appear in the input, so any logic that assumes distinct elements - or that skips over equal neighbours - is exercised.
Zero. Zero appears in the input, which is the value most likely to break a truthiness check used in place of an explicit comparison.

Common Concurrency mistakes

These apply to the pattern as a whole, not just this problem.

Re-checking a condition with `if` instead of `while` after waiting. Spurious wakeups are real.
Holding a lock across a blocking call, which serialises every other thread behind the slowest one and is how these solutions deadlock.
Assuming statements execute in program order without a barrier, a volatile read, or an atomic.