Mode, Median and Sort Across 10 Nodes with Send/Receive While Minimizing Traffic

A large collection of integers is spread across 10 machines (nodes), numbered 0 to 9. Every node runs the same program, knows its own number, and holds its own share of the data in memory. Nodes can communicate only through a minimal message-passing interface: - `send(dest, message)` delivers `message` to node `dest` without blocking. - `recv()` blocks until a message arrives, then returns `(source, message)`. The interface names are an assumed stand-in; the interviewer supplies a send and receive pair of this kind. Write the per-node program, in the style of a MapReduce job, for each of the three computations below. The goal in every part is to **minimize the amount of data sent over the network**, while producing an exact answer. ### Constraints and Clarifications These are working assumptions; confirm them with the interviewer. - The data on one node fits in that node's memory, but the full dataset does not fit on any single node. - Messages are delivered reliably and are never lost or duplicated. - Local computation is cheap compared with network transfer. ### Clarifying Questions - Where must each answer end up: on one designated node, or on every node? - What is the range of the integers, and are there many repeated values or mostly distinct ones? - How should ties be broken for the mode, and which median is wanted when the total count is even? - Are messages between a pair of nodes delivered in the order they were sent? - Is there a limit on message size or on the number of communication rounds? ### Part 1 — Mode Compute the most frequent value across all nodes. ```hint Shrink before you ship Consider what each node can compute from its own data that preserves everything needed for an exact global count, and which node should be responsible for each value. ``` #### What This Part Should Cover - Local pre-aggregation before any transfer - A partitioning scheme that spreads the merge work across nodes rather than funneling everything to one - The network cost in terms of distinct values, and the worst case when most values are distinct - A deterministic tie-breaking rule ### Part 2 — Median Compute the median of all values. ```hint Ask questions, not for data The coordinator does not need to see the values to find the middle one; it only needs to know, for a candidate value, how many values fall on each side of it. ``` #### What This Part Should Cover - A method whose network traffic does not grow with the size of the data - The number of communication rounds and the size of each message - Correct handling of an even total count, empty nodes and duplicate values - A comparison with shipping all the data, or samples of it, to one node ### Part 3 — Sort Sort all values so that node 0 ends up holding the smallest values in sorted order, node 1 the next range, and so on, with every node holding a similar number of values. ```hint Decide destinations first If every node agreed in advance on which value ranges belong to which node, how many times would each value need to cross the network? ``` #### What This Part Should Cover - How the range boundaries are chosen so that the nodes end up balanced - The total data moved, compared with the unavoidable minimum - Handling of heavily repeated values that could overload one node - Local work on each node before and after the exchange ### What a Strong Answer Covers - Working per-node code built on send and receive, with messages tagged by phase so that a fast node's later messages cannot be confused with earlier ones - Explicit accounting of the bytes or values each step sends - Correct coordination: no deadlock, and a clear point at which the answer is final - Awareness of when an exact answer is inherently expensive, and what an approximation would save ### Follow-up Questions - How would you find the top 10 most frequent values instead of only the mode? - One node is ten times slower than the others. Which of your three algorithms suffers most, and how would you mitigate it? - If an approximate median within 1 percent of rank were acceptable, how much traffic could you save? - How would these programs change if a node could fail partway through?