rippling·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

May 2026

Summary

Rippling SWE interview with a classic hard algorithm problem. The O(log(m+n)) constraint is what separates the people who've seen this before from everyone else, and I was very much in the second group.

Questions Asked (1)

Given two sorted arrays, find the median of the combined elements without actually merging them, in O(log(m+n)) time.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

I knew the brute force immediately, merge them, find the middle, done.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use binary search on the smaller array to find a partition point that divides both arrays into left and right halves of equal size (or differing by one). The median is then computed from the max of the left half and min of the right half. This achieves O(log(min(m,n))) time, which is within O(log(m+n)).

Pro tip: Always clarify edge cases like empty arrays and ensure your partition logic handles odd/even total lengths correctly. Mention that you choose the smaller array for binary search to optimize time and simplify boundary conditions.

1. Clarify and Define

Confirm the problem details: arrays are sorted, median definition for even/odd total length, and constraints. State that you'll aim for O(log(min(m,n))) time.

2. Partition Concept

Explain that you'll partition both arrays such that the left half contains elements all ≤ right half, and the left half size is (m+n+1)/2. Use binary search on the smaller array to find the correct partition.

3. Binary Search Logic

Describe the binary search: for a partition index i in array A, compute j = (m+n+1)/2 - i in array B. Check if A[i-1] ≤ B[j] and B[j-1] ≤ A[i]. Adjust search bounds accordingly.

4. Compute Median

Once correct partition found, if total length is odd, median is max(left half). If even, median is average of max(left half) and min(right half). Handle edge cases with sentinels for out-of-bounds.

5. Complexity and Edge Cases

State time complexity O(log(min(m,n))) and space O(1). Mention handling empty arrays, single-element arrays, and all elements of one array smaller than the other.

Key Points to Mention

Binary search on the smaller array to achieve O(log(min(m,n))) time.
Partitioning arrays into left and right halves of equal size (or left one larger for odd total).
Conditions for a valid partition: max(left) ≤ min(right).
Handling edge cases with sentinels (e.g., -infinity and +infinity) for out-of-bounds indices.
Median calculation: max(left) for odd total, average of max(left) and min(right) for even total.
Space complexity O(1) and why merging is avoided.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.