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.
1 import java.util.concurrent.*;
2
3 class Santa {
4 private final Semaphore santaSem = new Semaphore(0);
5 private final CyclicBarrier reindeerGate = new CyclicBarrier(9);
6 private final CyclicBarrier elfGate = new CyclicBarrier(3);
7 private int reindeerCount = 0, elfCount = 0;
8 private final Object mu = new Object();
9
10 public void santa() throws InterruptedException {
11 while (true) {
12 santaSem.acquire();
13 synchronized (mu) {
14 if (reindeerCount == 9) {
15 deliverToys();
16 reindeerCount = 0;
17 } else if (elfCount == 3) {
18 consultElves();
19 elfCount = 0;
20 }
21 }
22 }
23 }
24
25 public void reindeer() throws InterruptedException, BrokenBarrierException {
26 synchronized (mu) {
27 reindeerCount++;
28 if (reindeerCount == 9) santaSem.release();
29 }
30 reindeerGate.await(); // wait for the other reindeer
31 }
32
33 public void elf() throws InterruptedException, BrokenBarrierException {
34 synchronized (mu) {
35 elfCount++;
36 if (elfCount == 3) santaSem.release();
37 }
38 elfGate.await();
39 }
40 }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