Katkat
Back

Compute an Exact Distributed Median with Limited Communication

AnthropicSoftware Engineer · Onsite
HardSoftware EngineerOnsiteSoftware Engineering Fundamentals

Last updated

Compute an exact distributed median through global rank selection and count reductions, accounting for integer range, local search work, communication rounds, and even-size semantics.

Compute the exact median of values distributed across workers. Explain partitioning, parallel work, and communication cost using send/receive-style primitives. Compare the task with computing a distributed mode.

Constraints & Assumptions

The source does not define numeric type, even-size behavior, or transport API. State them. For one concrete exact protocol, assume finite integers in stable worker partitions; use the middle value for odd N and the mean of the two middle values for even N. Define empty-input behavior separately.

Clarifying Questions

Are local partitions sorted? Is the value range bounded? Must the result be exact? How expensive are communication rounds relative to bytes? Can local data be rescanned or sorted?

Follow-up questions

  • Why is the median of local medians generally wrong? How would you change the protocol for non-integer ordered values? When might gathering a small dataset be simpler and faster?