Design Concurrent Structures

Three threads, one rule: whatever order the scheduler starts them in, the output has to read first, then second, then third. That prompt, the print-in-order problem, is the smallest honest test of the thing D. E. Shaw keeps returning to on its low-level design and coding rounds. Coordinate threads that share state so the result is correct no matter how they interleave. There is almost nothing to draw. The whole difficulty is that the scheduler can suspend any thread between any two instructions, and your code has to be right anyway.

The round draws three related shapes, and this lesson builds all three. Ordered execution, where threads must fire in a fixed sequence rather than a scheduler-decided one. A thread-safe bounded structure, where many threads read and write one container without tearing it. And a data structure built from scratch to a named complexity, most often an LFU cache with O(1) get and put. The first two are concurrency correctness, reasoned in words and static code because thread scheduling never runs the same way twice. The third is the constant-time design instinct that the min-stack and the insert-delete-getRandom prompts already probe, turned up a level.

The D. E. Shaw angle

Concurrency here is a Python-and-fundamentals conversation, and distributed systems stay out of it. D. E. Shaw's onsite grills the layer under the algorithms, and thread safety, deadlock, and the global interpreter lock come up by name. So the coordination prompt is graded the way the fundamentals grill is: can you name the interleaving that breaks first, then close it. Say the shared state out loud and say what guards it. Then name the bad ordering that must never happen: an output out of sequence, a container mutated past its bound, a signal lost to a sleeping thread. Then pick the primitive that makes each impossible and defend the cost. Reach for the primitive before naming the hazard and you are guessing; name the hazard first and the primitive follows.

D. E. ShawPremium lesson · System design round

The D. E. Shaw design, worked end to end.

1. 1The design, drawn outSystem design · 1 diagram

Get the D. E. Shaw questions

$49 a year · all 100 companies · cancel anytime

From 250 D. E. Shaw reports, forum threads behind logins and write-ups in Chinese.

Read a free D. E. Shaw lesson firstAlready a member? Sign in