The Dining Philosophers solution and explanation
Google
3 more videos on this problem
LeetCode 1226 - The Dining PhilosophersLight Of Truth · 22:47 · 4K views
Apple Coding Interview Question | Leetcode 1226 | The Dining PhilosophersWorkWithGoogler · 4:51 · 948 views
The Dining Philosophers, Medium, LeetCode 1226H William Polenz · 14:57 · 251 views
No Sound Leetcode 1226: The Dining PhilosophersExtremeProgrammer · 2:59 · 17 views
The problem
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 spaghetti when they have both left and right forks. Each fork can be held by only one philosopher and so a philosopher can use the fork only if it is not being used by another philosopher. After an individual philosopher finishes eating, they need to put down both forks so that the forks become available to others. A philosopher can take the fork on their right or the one on their left as they become available, but cannot start eating before getting both forks.
Eating is not limited by the remaining amounts of spaghetti or stomach space; an infinite supply and an infinite demand are assumed.
Design a discipline of behaviour (a concurrent algorithm) such that no philosopher will starve; i.e., each can forever continue to alternate between eating and thinking, assuming that no philosopher can know when others may want to eat or think.
The problem statement and the image above are taken from wikipedia.org
The philosophers' ids are numbered from 0 to 4 in a clockwise order. Implement the function void wantsToEat(philosopher, pickLeftFork, pickRightFork, eat, putLeftFork, putRightFork) where:
philosopheris the id of the philosopher who wants to eat.pickLeftForkandpickRightForkare functions you can call to pick the corresponding forks of that philosopher.eatis a function you can call to let the philosopher eat once he has picked both forks.putLeftForkandputRightForkare functions you can call to put down the corresponding forks of that philosopher.- The philosophers are assumed to be thinking as long as they are not asking to eat (the function is not being called with their number).
Five threads, each representing a philosopher, will simultaneously use one object of your class to simulate the process. The function may be called for the same philosopher more than once, even before the last call ends.
Example 1:
Input: n = 1
Output: [[4,2,1],[4,1,1],[0,1,1],[2,2,1],[2,1,1],[2,0,3],[2,1,2],[2,2,2],[4,0,3],[4,1,2],[0,2,1],[4,2,2],[3,2,1],[3,1,1],[0,0,3],[0,1,2],[0,2,2],[1,2,1],[1,1,1],[3,0,3],[3,1,2],[3,2,2],[1,0,3],[1,1,2],[1,2,2]]
Explanation:
n is the number of times each philosopher will call the function.
The output array describes the calls you made to the functions controlling the forks and the eat function, its format is:
output[i] = [a, b, c] (three integers)
- a is the id of a philosopher.
- b specifies the fork: {1 : left, 2 : right}.
- c specifies the operation: {1 : pick, 2 : put, 3 : eat}.
Constraints:
1 <= n <= 60
Approach overview
Problem Overview: Five philosophers sit around a circular table with one fork between each pair. A philosopher must pick up both left and right forks before eating. Multiple threads run concurrently, so the challenge is coordinating fork access without causing deadlock or starvation.
Approach 1: Using Locks with a Fork Hierarchy (O(1) time per operation, O(n) space)
Represent each fork as a mutex or lock. Philosophers must acquire the two fork locks before eating and release them afterward. The deadlock problem appears when every philosopher picks up their left fork simultaneously and waits for the right fork. A fork hierarchy prevents this by enforcing a strict order: always lock the lower-numbered fork first, then the higher-numbered one. This removes circular wait, which is a required condition for deadlock. Each eating attempt performs constant-time lock and unlock operations, so the runtime per action is O(1), while storing fork locks requires O(n) space for n forks. This approach relies on classic concurrency control using locks to guarantee safe resource access.
Approach 2: Asymmetric Philosophers (O(1) time per operation, O(n) space)
Break the symmetry in how philosophers acquire forks. Instead of everyone picking the same fork first, alternate the order: even-numbered philosophers pick up the left fork first, while odd-numbered philosophers pick up the right fork first. Because not all threads compete for the same resource order, the circular dependency disappears. Deadlock becomes impossible while still allowing parallel eating whenever forks are available. Each philosopher performs a constant number of lock acquisitions and releases, so the operational cost remains O(1) with O(n) space for fork locks. This strategy is widely used in systems programming to prevent synchronization issues without introducing complex coordination logic.
Recommended for interviews: The fork hierarchy approach is the safest explanation during interviews because it directly addresses the deadlock condition using a deterministic ordering rule. Interviewers expect you to mention the four deadlock conditions and show how ordering removes circular wait. The asymmetric strategy is also valid and demonstrates deeper understanding of concurrency design trade‑offs.
Approach 1: Approach 1: Using Locks with a Fork Hierarchy
In this approach, we use a hierarchy for acquiring locks to avoid deadlock. By choosing an order in which the locks (forks) are acquired, we ensure that no circular wait occurs, thus preventing deadlock.
To implement this, a philosopher will first pick the fork with the lower index (among their left and right forks) before picking the one with the higher index. This breaks the circular dependency, allowing a safe locking mechanism.
from threading import Lock
class DiningPhilosophers:
def __init__(self):
self.forks = [Lock() for _ in range(5)]
def wantsToEat(self, philosopher: int,
pickLeftFork: 'Callable[[], None]',
pickRightFork: 'Callable[[], None]',
eat: 'Callable[[], None]',
putLeftFork: 'Callable[[], None]',
putRightFork: 'Callable[[], None]') -> None:
right = philosopher
left = (philosopher + 1) % 5
if right < left:
with self.forks[right]:
pickRightFork()
with self.forks[left]:
pickLeftFork()
eat()
putLeftFork()
putRightFork()
else:
with self.forks[left]:
pickLeftFork()
with self.forks[right]:
pickRightFork()
eat()
putRightFork()
putLeftFork()import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;
public class DiningPhilosophers {
private final Lock[] forks = new ReentrantLock[5];
public DiningPhilosophers() {
for (int i = 0; i < 5; i++) {
forks[i] = new ReentrantLock();
}
}
public void wantsToEat(int philosopher,
Runnable pickLeftFork,
Runnable pickRightFork,
Runnable eat,
Runnable putLeftFork,
Runnable putRightFork) {
int right = philosopher;
int left = (philosopher + 1) % 5;
if (right < left) {
forks[right].lock();
pickRightFork.run();
forks[left].lock();
pickLeftFork.run();
} else {
forks[left].lock();
pickLeftFork.run();
forks[right].lock();
pickRightFork.run();
}
eat.run();
putRightFork.run();
forks[right].unlock();
putLeftFork.run();
forks[left].unlock();
}
}#include <mutex>
#include <thread>
std::mutex forks[5];
void wantsToEat(int philosopher,
void (&pickLeftFork)(),
void (&pickRightFork)(),
void (&eat)(),
void (&putLeftFork)(),
void (&putRightFork)()) {
int right = philosopher;
int left = (philosopher + 1) % 5;
if (right < left) {
forks[right].lock();
pickRightFork();
forks[left].lock();
pickLeftFork();
} else {
forks[left].lock();
pickLeftFork();
forks[right].lock();
pickRightFork();
}
eat();
putRightFork();
forks[right].unlock();
putLeftFork();
forks[left].unlock();
}
int main() {
// Initialize and execute philosopher threads using wantsToEat
return 0;
}class DiningPhilosophers {
constructor() {
this.forks = [new Promise((res) => res()),
new Promise((res) => res()),
new Promise((res) => res()),
new Promise((res) => res()),
new Promise((res) => res())];
}
async wantsToEat(philosopher, pickLeftFork, pickRightFork, eat, putLeftFork, putRightFork) {
const right = philosopher;
const left = (philosopher + 1) % 5;
if (right < left) {
await this.forks[right];
pickRightFork();
await this.forks[left];
pickLeftFork();
} else {
await this.forks[left];
pickLeftFork();
await this.forks[right];
pickRightFork();
}
eat();
putLeftFork();
putRightFork();
}
}#include <pthread.h>
pthread_mutex_t forks[5];
void *wantsToEat(int philosopher,
void (*pickLeftFork)(),
void (*pickRightFork)(),
void (*eat)(),
void (*putLeftFork)(),
void (*putRightFork)()) {
int right = philosopher;
int left = (philosopher + 1) % 5;
if (right < left) {
pthread_mutex_lock(&forks[right]);
pickRightFork();
pthread_mutex_lock(&forks[left]);
pickLeftFork();
} else {
pthread_mutex_lock(&forks[left]);
pickLeftFork();
pthread_mutex_lock(&forks[right]);
pickRightFork();
}
eat();
putRightFork();
pthread_mutex_unlock(&forks[right]);
putLeftFork();
pthread_mutex_unlock(&forks[left]);
}
int main() {
for (int i = 0; i < 5; i++) {
pthread_mutex_init(&forks[i], NULL);
}
// Run philosopher threads...
return 0;
}using System;
using System.Threading;
public class DiningPhilosophers {
private Mutex[] forks = new Mutex[5];
public DiningPhilosophers() {
for (int i = 0; i < 5; i++) {
forks[i] = new Mutex();
}
}
public void WantsToEat(int philosopher,
Action pickLeftFork,
Action pickRightFork,
Action eat,
Action putLeftFork,
Action putRightFork) {
int right = philosopher;
int left = (philosopher + 1) % 5;
if (right < left) {
forks[right].WaitOne();
pickRightFork();
forks[left].WaitOne();
pickLeftFork();
} else {
forks[left].WaitOne();
pickLeftFork();
forks[right].WaitOne();
pickRightFork();
}
eat();
putRightFork();
forks[right].ReleaseMutex();
putLeftFork();
forks[left].ReleaseMutex();
}
}Python's threading library provides Lock objects to manage concurrent access. This solution employs context management (using 'with') to ensure forks are picked and put properly. Acquiring locks in an ordered fashion prevents deadlock by eliminating circular wait conditions.
Time Complexity: O(1) due to constant time lock operations.
Space Complexity: O(1) since the number of locks is fixed.
Approach 2: Approach 2: Asymmetric Philosophers
This approach relies on introducing asymmetry among philosophers. Instead of using a singular, uniform strategy for all philosophers to pick up the fork, we introduce a slight alteration in behavior. Specifically, we let some philosophers pick up the left fork first and others pick up the right fork first. This ensures that two neighboring philosophers don’t deadlock by waiting on each other's fork.
This approach adjusts the method by which philosophers grab the forks to further reduce potential conflict, leveraging the asymmetry to ensure progress without deadlock.
from threading import Lock
class DiningPhilosophers:
def __init__(self):
self.forks = [Lock() for _ in range(5)]
def wantsToEat(self, philosopher: int,
pickLeftFork: 'Callable[[], None]',
pickRightFork: 'Callable[[], None]',
eat: 'Callable[[], None]',
putLeftFork: 'Callable[[], None]',
putRightFork: 'Callable[[], None]') -> None:
right = philosopher
left = (philosopher + 1) % 5
if philosopher % 2 == 0:
with self.forks[left]:
pickLeftFork()
with self.forks[right]:
pickRightFork()
eat()
putRightFork()
putLeftFork()
else:
with self.forks[right]:
pickRightFork()
with self.forks[left]:
pickLeftFork()
eat()
putLeftFork()
putRightFork()import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;
public class DiningPhilosophers {
private final Lock[] forks = new ReentrantLock[5];
public DiningPhilosophers() {
for (int i = 0; i < 5; i++) {
forks[i] = new ReentrantLock();
}
}
public void wantsToEat(int philosopher,
Runnable pickLeftFork,
Runnable pickRightFork,
Runnable eat,
Runnable putLeftFork,
Runnable putRightFork) {
int right = philosopher;
int left = (philosopher + 1) % 5;
if (philosopher % 2 == 0) {
forks[left].lock();
pickLeftFork.run();
forks[right].lock();
pickRightFork.run();
} else {
forks[right].lock();
pickRightFork.run();
forks[left].lock();
pickLeftFork.run();
}
eat.run();
putLeftFork.run();
forks[left].unlock();
putRightFork.run();
forks[right].unlock();
}
}#include <mutex>
#include <thread>
std::mutex forks[5];
void wantsToEat(int philosopher,
void (&pickLeftFork)(),
void (&pickRightFork)(),
void (&eat)(),
void (&putLeftFork)(),
void (&putRightFork)()) {
int right = philosopher;
int left = (philosopher + 1) % 5;
if (philosopher % 2 == 0) {
forks[left].lock();
pickLeftFork();
forks[right].lock();
pickRightFork();
} else {
forks[right].lock();
pickRightFork();
forks[left].lock();
pickLeftFork();
}
eat();
putLeftFork();
forks[left].unlock();
putRightFork();
forks[right].unlock();
}
int main() {
// Initialize and execute philosopher threads using wantsToEat
return 0;
}class DiningPhilosophers {
constructor() {
this.forks = Array.from({ length: 5 }, () => []);
}
async wantsToEat(philosopher, pickLeftFork, pickRightFork, eat, putLeftFork, putRightFork) {
const right = philosopher;
const left = (philosopher + 1) % 5;
if (philosopher % 2 === 0) {
await this.acquire(this.forks[left]);
pickLeftFork();
await this.acquire(this.forks[right]);
pickRightFork();
} else {
await this.acquire(this.forks[right]);
pickRightFork();
await this.acquire(this.forks[left]);
pickLeftFork();
}
eat();
putLeftFork();
putRightFork();
}
async acquire(fork) {
while (fork.length > 0) {
await new Promise(resolve => setTimeout(resolve, 1));
}
fork.push(true);
}
release(fork) {
fork.pop();
}
}#include <pthread.h>
pthread_mutex_t forks[5];
void *wantsToEat(int philosopher,
void (*pickLeftFork)(),
void (*pickRightFork)(),
void (*eat)(),
void (*putLeftFork)(),
void (*putRightFork)()) {
int right = philosopher;
int left = (philosopher + 1) % 5;
if (philosopher % 2 == 0) {
pthread_mutex_lock(&forks[left]);
pickLeftFork();
pthread_mutex_lock(&forks[right]);
pickRightFork();
} else {
pthread_mutex_lock(&forks[right]);
pickRightFork();
pthread_mutex_lock(&forks[left]);
pickLeftFork();
}
eat();
putLeftFork();
pthread_mutex_unlock(&forks[left]);
putRightFork();
pthread_mutex_unlock(&forks[right]);
}
int main() {
for (int i = 0; i < 5; i++) {
pthread_mutex_init(&forks[i], NULL);
}
// Run philosopher threads...
return 0;
}using System;
using System.Threading;
public class DiningPhilosophers {
private Mutex[] forks = new Mutex[5];
public DiningPhilosophers() {
for (int i = 0; i < 5; i++) {
forks[i] = new Mutex();
}
}
public void WantsToEat(int philosopher,
Action pickLeftFork,
Action pickRightFork,
Action eat,
Action putLeftFork,
Action putRightFork) {
int right = philosopher;
int left = (philosopher + 1) % 5;
if (philosopher % 2 == 0) {
forks[left].WaitOne();
pickLeftFork();
forks[right].WaitOne();
pickRightFork();
} else {
forks[right].WaitOne();
pickRightFork();
forks[left].WaitOne();
pickLeftFork();
}
eat();
putLeftFork();
forks[left].ReleaseMutex();
putRightFork();
forks[right].ReleaseMutex();
}
}In this Python solution, an alternate ordering for even and odd-indexed philosophers guarantees asymmetric fork acquisition. Even-indexed philosophers pick their left fork first and odd-indexed philosophers pick their right fork. This ensures varied actions among philosophers and mitigates the chances of deadlock.
Time Complexity: O(1) since locks are dealt in constant operations per philosopher.
Space Complexity: O(1), with a set number of lock objects.
Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Using Locks with a Fork Hierarchy | Time Complexity: O(1) due to constant time lock operations. |
| Approach 2: Asymmetric Philosophers | Time Complexity: O(1) since locks are dealt in constant operations per philosopher. |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Locks with Fork Hierarchy | O(1) per operation | O(n) | Best general solution. Prevents deadlock by enforcing a global lock order. |
| Asymmetric Philosophers | O(1) per operation | O(n) | Good when you want a simple deadlock prevention technique without ordering all resources. |
Frequently asked questions
Is The Dining Philosophers easy or hard?
The problem is typically rated Medium because the implementation is straightforward once the deadlock issue is understood. The difficulty comes from reasoning about concurrent threads and designing a strategy that prevents circular waiting.
How to solve The Dining Philosophers efficiently?
Use synchronization primitives such as mutex locks for each fork. Prevent deadlock either by enforcing a lock hierarchy (always acquire forks in a fixed order) or by making philosophers asymmetric so they acquire forks in different orders. Both strategies ensure safe concurrent execution with O(1) operations.
What is the best approach for The Dining Philosophers?
The fork hierarchy approach is the most reliable solution. Each philosopher always locks the lower-numbered fork before the higher-numbered fork, eliminating circular wait and preventing deadlock. Every eating operation performs constant-time lock and unlock calls, giving O(1) time per action and O(n) space for fork locks.
What data structure is used in The Dining Philosophers?
The core structure is an array of mutex locks representing forks. Each philosopher thread attempts to lock two adjacent forks before eating and unlocks them afterward. The problem focuses more on synchronization primitives than traditional data structures.
What is the time complexity of The Dining Philosophers?
Both common solutions operate in O(1) time per philosopher action because each thread only performs a fixed number of lock and unlock operations. The total memory usage is O(n) to store the fork locks, where n is the number of philosophers.
The Dining Philosophers Python or Java solution approach?
In Python or Java, represent forks using threading locks or synchronized primitives. A philosopher thread acquires two locks (forks), executes the eat callback, then releases them. Deadlock is avoided using either ordered locking or asymmetric fork acquisition.
Is The Dining Philosophers asked at Google, Amazon, or Meta?
The Dining Philosophers is a classic concurrency interview problem used by companies that evaluate systems or multithreading knowledge. Variations of it appear in interviews at companies like Google, Amazon, and other systems-focused teams to test understanding of deadlocks, synchronization, and resource ordering.