Longest Consecutive Ones Across Distributed Partitions
Updated
Problem statement
A binary sequence is split into contiguous partitions stored on different machines. You receive the partitions as String[] partitions in their original left-to-right order. Each string contains only 0 and 1; an empty partition is allowed.
Return the length of the longest consecutive run of 1 characters in the global sequence. The global sequence is the concatenation of the partitions in the given order. A run may cross any number of partition boundaries, including empty partitions, but it cannot cross a zero. Do not reorder partitions, and do not change any bit. Return 0 when the global sequence is empty or contains no ones.
For the distributed follow-up, design the solution so each machine can summarize its own partition independently and an ordered reduction can combine those summaries without sending the full raw sequence to one coordinator. The finite judge provides all partitions to one function to verify the same result; it does not simulate a network or failures.
Function
longestDistributedOnes(partitions: String[]) → intExamples
Example 1
partitions = ["011","1101"]return = 4The global sequence is 0111101. The first partition ends with two ones and the second begins with two ones, forming a run of four across the boundary.
Example 2
partitions = ["11","","111","001"]return = 5The first and third partitions contribute two and three consecutive ones. The empty partition between them does not break the run, so its length is five. The two zeros in the last partition stop that run.
Constraints
0 ≤ partitions.length ≤ 100.- Each partition contains from
0through1000binary characters. - The total number of characters across all partitions is at most
1000. - The given partition order is authoritative, including when a partition is empty.
Similar questions at other companies
- Merge Sort Report with a Noisy ComparatorMercor · ONSITE INTERVIEWMercor interview questions
- Customer Bootstrap APIDoorDash · PHONE SCREEN · ONSITE INTERVIEWDoorDash interview questions
- Propagating Fraud DetectorAffirm · PHONE SCREEN · ONSITE INTERVIEWAffirm interview questions
- Deep Copy a Random-Pointer ListAmazon · ONSITE INTERVIEW
- Digit-Coded Card ValidationCapital One · ONSITE INTERVIEWCapital One interview questions
- Instant-Runoff Voting WinnerWise · ONSITE INTERVIEW
- Candy Crush Grid Matching and GravityRoblox · PHONE SCREEN · ONSITE INTERVIEWRoblox interview questions
- Online Meeting Scheduler with Fixed RoomsUber · ONSITE INTERVIEWUber interview questions
- Compress Editor Actions into Operational Transform OperationsReplit · OA · PHONE SCREEN · ONSITE INTERVIEW
- Spiral MatrixNike, Inc. · ONSITE INTERVIEWNike, Inc. interview questions