DSA interview question

Median of Two Sorted Arrays

Hard · Algorithms · Topics: binary search, array, divide and conquer

The problem

Two data centres each hold a sorted list of request latencies, and the SRE dashboard needs the median latency across both lists. Merging them costs O(m + n) time and memory, and these lists hold billions of entries. The famous O(log(min(m, n))) solution never merges anything. It binary-searches how many elements to take from the smaller array into the "left half" of the combined order, checking at each step whether the two halves are correctly separated.

Example: [1, 3] and [2] → 2.0; [1, 2] and [3, 4] → 2.5.

Function signature

double findMedianSortedArrays(const vector<int>& a, const vector<int>& b);  // not both empty

Test cases

Input `(a, b)`	Output	Explanation
`([1, 3], [2])`	2.0	Merged [1, 2, 3]
`([1, 2], [3, 4])`	2.5	Merged [1, 2, 3, 4]: (2 + 3) / 2
`([], [1])`	1.0	One array empty
`([0, 0], [0, 0])`	0.0
`([2], [])`	2.0
`([1, 3, 8, 9, 15], [7, 11, 18, 19, 21, 25])`	11.0	11 elements; the 6th smallest is 11

(Confirm: both arrays are sorted; the combined length is at least 1; O(log(min(m, n))) is the target.)

How interviewers phrase it

"Find the median of two sorted arrays in O(log(m + n))" (LeetCode 4, Hard).
A classic top-company question testing careful binary search with boundary cases.

Clarifying questions to ask

Are both arrays sorted? Can one be empty?
What's the required complexity? (O(m + n) merging is the easy answer.)
Should an even-length median be the average of the two middle values?

Follow-ups to expect

"What are you binary-searching?"
"How do you know a partition is correct?"
"Which way do you move if it's wrong?"
"Why search the smaller array?"
"How do you get the median from a correct partition?"

Practise questions like this with a real engineer

On Practick another engineer interviews you live for 60 minutes on a question from this bank. They have the full interviewer guide beside the call: the expected answer to every follow-up, hints to give if you stall, and a scoring rubric. You get the model solution once the session settles. It is free: interview someone for an hour and you have earned your own.

Book a free mock interview