Compute the Longest Run of Ones Across Multiple Machines
Company: Molocoads
Role: Machine Learning Engineer
Category: System Design
Difficulty: medium
Interview Round: Onsite
# Compute the Longest Run of Ones Across Multiple Machines
A binary sequence is too large for one machine and is split into contiguous, ordered shards. Design a distributed computation that returns the exact length of the longest contiguous run of `1` values in the original sequence. Shards may have different lengths, and the longest run may cross one or many shard boundaries.
Explain the per-shard summary, the merge operation, correctness, communication cost, fault handling, and how the design preserves global shard order.
### Clarifying Questions to Ask
- Are shard boundaries contiguous and nonoverlapping, and is their global order known?
- Must the result be computed once for an immutable input or updated as shards arrive?
- Can a coordinator retain one constant-size summary per shard?
### What a Strong Answer Covers
- A constant-size summary containing shard length, all-ones status, prefix run, suffix run, and internal maximum.
- A merge rule that handles runs spanning a boundary and composes summaries in global order.
- An argument that the summary is sufficient even when an all-ones shard bridges two neighbors.
- A tree reduction or ordered aggregation plan with bounded communication.
- Retry, duplicate-result, missing-shard, and skew considerations.
### Follow-up Questions
- Can the merge operation be made associative so a tree reduction is safe?
- How would you update the answer after replacing one shard?
- What metadata prevents duplicate or out-of-order shard summaries from corrupting the result?
Overview: Design an exact distributed reduction for the longest run of ones when a binary input is split across ordered machines. The solution derives a constant-size shard summary, proves the ordered merge rule, and covers all-one bridges, retries, shard identity, and reduction cost.
Read the full Molocoads Machine Learning Engineer interview experience this question came from