Katkat
Back

Compute the Longest Run of Ones Across Multiple Machines

MolocoadsMachine Learning Engineer · Onsite
MediumMachine Learning EngineerOnsiteSystem Design

Last updated

This problem tests the ability to design a distributed data reduction pattern where partial results can be combined using associative operators to compute a global property.

Problem Statement

You are tasked with computing the length of the longest consecutive sequence of 1s in a binary stream that is partitioned into $N$ ordered shards, each stored on a different machine.

Each machine $i$ receives a sequence $S_i$ of 0s and 1s. You need to design a distributed system that computes the global longest run of 1s efficiently. Since the stream is ordered ($S_1$ comes before $S_2$, ..., $S_N$), a run of 1s may span across the boundary of two machines.

Requirements

  1. Define a data structure (the "shard summary") that each machine can compute locally in one pass to represent its contents.
  2. Define a merge operation that takes two summaries and produces a new summary representing the combined stream.
  3. Explain the architecture for performing this reduction across $N$ machines.

Constraints

  • Each machine must process its local shard independently.
  • The merge operation must be associative to allow for hierarchical reduction (e.g., a tree-based aggregation).
  • You must handle the case where a shard consists entirely of 1s.

Example

  • Shard 1: [1, 1, 0, 1] -> Summary should capture the prefix run, suffix run, overall max run, and total length.
  • Shard 2: [1, 1, 1, 0] -> Merging these reveals a bridge: the suffix of Shard 1 (length 1) and prefix of Shard 2 (length 3) form a run of length 4.

Hints

Hint 1

Consider storing the length of the longest run of 1s starting from the left, ending at the right, and the global maximum within the shard.

Hint 2

A shard that consists entirely of 1s is a special case: you need to track the total length of the shard separately to know if a bridge spans the entire machine.

Hint 3

Use a tree-based reduction (MapReduce style) where each parent node merges the summaries of its two children until only one root summary remains.

Follow-up questions

  • How does your merge logic change if the input is not just binary, but a stream of integers where you are looking for the longest run of a specific target value K?
  • If a machine fails during the reduction process, how do you ensure the system recovers without recomputing the entire stream from scratch?
  • How would you adapt this design if the machines are not ordered in a simple sequence but form a directed acyclic graph (DAG) of dependencies?