Santa Claus Problem
Santa sleeps until either 9 reindeer return (deliver toys) or 3 elves arrive (consult). Reindeer take priority over elves. Tests selective wakeup + group barrier + priority, three classic primitives composed into one problem.
The setup
Trono posed this problem in 1994. The cast:
- Santa, asleep most of the time. He's the single consumer of wake-up events.
- 9 reindeer, on vacation in the South Pacific. They drift back to the North Pole one by one. When all 9 have returned, they're ready to deliver toys; Santa has to harness them up and lead the ride.
- A group of elves, who occasionally have problems making toys. An elf alone can't bother Santa — too many interruptions. Only when 3 elves are stuck together do they form a delegation that wakes Santa for a consultation.
Two more rules:
- Reindeer take priority. If a group of 9 reindeer and a group of 3 elves are both ready when Santa wakes, he deals with the reindeer first. (Christmas can't be late just because a few elves are confused.)
- Once Santa starts a task — toy delivery or elf consultation — he finishes it before going back to sleep. After that, he checks again.
The challenge: write Santa, the reindeer, and the elves so that nobody busy-waits, the group-of-N rendezvous works correctly, and reindeer always preempt elves when both are queued.
A picture of Santa's loop
The check order — reindeer first, elves second — is how priority is enforced. Both groups can signal Santa, but on each wake-up Santa drains the higher-priority queue before looking at the lower one.
A picture of how each group rendezvous works
Each group needs a "wait until N have arrived" gate (a barrier). Reindeer arrive one at a time and queue up; the 9th arrival is what triggers Santa.
The elves work the same way with a barrier of 3 instead of 9. A 4th elf who arrives while 3 are already inside has to wait at the barrier until the current group finishes consulting.
Why this problem is interesting
Three primitives composed in one problem
- Group rendezvous — all 9 reindeer (or all 3 elves) must be present before anyone can move. Implemented with a barrier of size N (
CyclicBarrier,threading.Barrier, channel counting). - Priority dispatch — Santa picks reindeer over elves when both signal. Implemented as check-order in the wake-up handler (look at high-priority counter first).
- Producer-consumer signaling — Santa is the consumer of "I am ready" events; the two groups are producers. Implemented with a single semaphore Santa blocks on.
Each primitive is interview-grade on its own. The lesson here is composition — recognizing that the problem is a stack of three known patterns, not one new one.
Where this kind of composition shows up
- Distributed leader coordination — leader services heartbeat replies (low priority) but preempts immediately on a reconfiguration message (high priority).
- Batch ML training — wait for N samples to form a gradient batch, but interrupt instantly on a shutdown signal.
- Trading engines — wait for N market events before recalculating a signal, but always preempt to handle a client cancel order.
In every case the structure is the same: gather a quorum of one kind of event, but let a higher-priority event jump the queue.
Interview move Decompose before coding: "This is three problems stacked — group rendezvous, priority dispatch, and producer-consumer signaling. Let me solve each, then combine." That signals senior-level thinking. Junior candidates write one giant function with nested locks; senior candidates layer primitives.
Common variants
- No priority — Santa serves whoever signals first. Drops the check-order rule; often what interviewers actually want first.
- Variable group sizes — pass N (reindeer) and M (elves) at construction. Generalizes barrier sizing.
- Cancellation — what if a reindeer can leave before all 9 arrive? Adds
tryAdvance/ timeout semantics to the barrier.
Implementations
Two semaphores let Santa wake up. When Santa wakes, he checks reindeer count first (priority). Two CyclicBarriers (size 9 for reindeer, size 3 for elves) gate the group rendezvous.
import java.util.concurrent.*;
class Santa {
private final Semaphore santaSem = new Semaphore(0);
private final CyclicBarrier reindeerGate = new CyclicBarrier(9);
private final CyclicBarrier elfGate = new CyclicBarrier(3);
private int reindeerCount = 0, elfCount = 0;
private final Object mu = new Object();
public void santa() throws InterruptedException {
while (true) {
santaSem.acquire();
synchronized (mu) {
if (reindeerCount == 9) {
deliverToys();
reindeerCount = 0;
} else if (elfCount == 3) {
consultElves();
elfCount = 0;
}
}
}
}
public void reindeer() throws InterruptedException, BrokenBarrierException {
synchronized (mu) {
reindeerCount++;
if (reindeerCount == 9) santaSem.release();
}
reindeerGate.await(); // wait for the other reindeer
}
public void elf() throws InterruptedException, BrokenBarrierException {
synchronized (mu) {
elfCount++;
if (elfCount == 3) santaSem.release();
}
elfGate.await();
}
}Key points
- •Santa sleeps until: 9 reindeer ready OR 3 elves waiting
- •Reindeer have priority, Santa serves them first if both are queued
- •Each group needs barrier-style synchronization (all 9 / all 3 must be present)
- •Composition: priority + group-of-N barrier + producer-consumer signaling