Multi-Threaded Santa

Level: Advanced 60–90 min

Concepts: ConcurrencyDesign PatternsBoundariesEdge Cases

---

Make, wrap, load, and deliver 1 million presents on Christmas Eve — using the fewest elves (threads) and the least time possible.

Requirements

Pipeline

Presents flow through four stages, each running as a separate process/thread pool:

1. Making → Made queue (max 1,000)
2. Wrapping → Wrapped queue (max 2,000)
3. Loading → Loaded queue (max 5,000)
4. Delivering → Delivered (unlimited)

Each present must pass through all four stages in order.

Work Timing

Each operation on a Present takes simulated time:

• present.make() → 50ms
• present.wrap() → 10ms
• present.load() → 5ms
• present.deliver() → via sleigh (see below)

Delivery Constraint

• Only one delivery worker (Santa’s sleigh)
• Each delivery round takes 500ms, regardless of how many presents are on the sleigh
• No presents can be loaded while the sleigh is delivering

Elf Pool

• Worker threads (“elves”) are drawn from a shared Elf Pool
• Once assigned, an elf cannot be terminated — only reassigned
• Elves can move between stages via the pool

Cost Calculation

• 1 elf working for 1 second = 1 cookie
• Total cost = number of elves × total time in seconds
• Goal: minimize total cookie expenditure

Failure Rules

• If any worker process fails, the clock continues (costs accumulate)
• If the Elf Pool fails, the challenge is forfeited

Test Cases

Scenario	Expected
Make 1 present	Present exists in Made queue
Made queue full (1,000)	Making blocks until space available
Wrap 1 present from Made queue	Present moves to Wrapped queue
Load while sleigh delivering	Loading blocks
Deliver 1 round	All loaded presents move to Delivered
Elf reassignment	Elf moves from Making to Wrapping
Full pipeline, 10 presents	All 10 delivered in correct order

Bonus

• Implement auto-scaling — dynamically adjust elf allocation based on queue depths
• Add monitoring — report queue sizes, throughput per stage, and elf utilization in real-time
• Compare strategies: fixed allocation vs dynamic rebalancing
• Find the optimal elf distribution for minimum cost

Hint

Start without concurrency. Build the pipeline with a single thread processing one present through all four stages. Then add queues with size limits. Then add multiple workers per stage. Concurrency bugs are much easier to diagnose when the sequential logic is already proven correct.