rippling·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say

Jun 2026

Summary

Rippling software engineer interview, got hit with the median of two sorted arrays problem and they wanted the full O(log(m+n)) solution, not the lazy merge approach. Pretty classic hard leetcode but the explanation requirement made it trickier than just coding it up.

Questions Asked (1)

Given two sorted integer arrays, find the median of all their combined elements in O(log(m+n)) time. You need to explain the algorithm and prove its correctness, then implement it.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

This one stung a little because I knew the binary search partition approach conceptually but explaining WHY it's correct while also coding it is a different beast.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying the problem constraints and edge cases, then explain the binary search partition approach that achieves O(log(min(m,n))) time. Walk through the algorithm step-by-step, prove its correctness by maintaining the invariant that the left partition contains exactly half the elements and all left elements are ≤ all right elements, and finally implement it with careful handling of boundaries.

Pro tip: Mention that you can optimize to O(log(min(m,n))) by always binary searching the smaller array, and be prepared to discuss how this approach generalizes to finding the k-th element in two sorted arrays.

1. Clarify and Define

Restate the problem, confirm assumptions (e.g., arrays are sorted, may be empty, median definition for even/odd total length), and discuss edge cases like one array being empty.

2. High-Level Approach

Explain that you will use binary search to partition the arrays such that the left half contains exactly half the elements and all left elements are ≤ all right elements. Emphasize the O(log(min(m,n))) time complexity.

3. Detailed Algorithm

Describe the binary search on the smaller array: choose a partition point i, compute j = (m+n+1)/2 - i, and check if the partition is valid (maxLeft ≤ minRight). Adjust the search range based on comparisons.

4. Correctness Proof

Prove that the algorithm finds the correct partition by showing that the invariant holds and that the median is computed correctly from the partition boundaries.

5. Implementation and Edge Cases

Write clean code with proper handling of boundaries (using sentinels like -∞ and +∞), and test with examples including empty arrays and arrays of different sizes.

Key Points to Mention

Time complexity: O(log(min(m,n))) due to binary search on the smaller array.
Space complexity: O(1) as only constant extra space is used.
Handling of edge cases: empty arrays, all elements in one array smaller than the other, etc.
Use of sentinels (e.g., Integer.MIN_VALUE, Integer.MAX_VALUE) to simplify boundary checks.
The partition invariant: left partition size = (m+n+1)/2, and maxLeft ≤ minRight.
Generalization to finding the k-th element in two sorted arrays.

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