rippling·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say

Jun 2026

Summary

Rippling SWE interview with a classic hard algorithm problem. Nothing too surprising about the topic but the complexity constraint is what makes it actually hard.

Questions Asked (1)

Given two sorted arrays of sizes m and n, find the median of the combined elements in O(log(m+n)) time.

Algorithms & Data Structures

Author's notes

The naive approach is obvious, merge and find the middle, but they want logarithmic time so you have to do binary search on the partition.

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 where the left half of the combined arrays contains exactly half of the total elements. Ensure that the maximum of the left half is less than or equal to the minimum of the right half, then compute the median based on the total number of elements.

Pro tip: Always handle edge cases like empty arrays and ensure your binary search boundaries are correctly set to avoid infinite loops. Mention that you choose the smaller array for binary search to optimize time complexity to O(log(min(m,n))).

1. Understand the problem and constraints

Clarify that the arrays are sorted and we need O(log(m+n)) time. Confirm that the median definition for even total length is the average of the two middle elements.

2. Choose the smaller array for binary search

To achieve O(log(min(m,n))), perform binary search on the smaller array. This reduces the search space and simplifies edge cases.

3. Define the partition and binary search conditions

For a partition in the smaller array at index i, compute the corresponding partition in the larger array at j = (m+n+1)/2 - i. Check if maxLeftX <= minRightY and maxLeftY <= minRightX.

4. Adjust binary search bounds based on conditions

If maxLeftX > minRightY, move the partition left (decrease i). If maxLeftY > minRightX, move the partition right (increase i). Continue until the correct partition is found.

5. Compute and return the median

If total length is odd, median is max(maxLeftX, maxLeftY). If even, median is (max(maxLeftX, maxLeftY) + min(minRightX, minRightY)) / 2.

Key Points to Mention

Time complexity O(log(min(m,n))) and space complexity O(1).
Handling edge cases: empty arrays, all elements of one array smaller than the other.
Using sentinels (e.g., -Infinity and +Infinity) to simplify boundary conditions.
The importance of integer division and correct index calculations.
The invariant that the left half contains exactly half of the total elements (or one more if odd).
Testing with examples like arrays of different sizes and overlapping ranges.

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