How do you find median of two sorted arrays in log time?
Reported in Ubisoft European engineering loops. Hard interview classic requiring binary search partition logic.
Interview scenario
Context for Ubisoft candidates:
Given two sorted arrays, find median in O(log(min(m,n))).
Model answer
Try answering aloud first
Cover trade-offs, structure, and a concrete example before revealing the baseline response.
How to frame this at Ubisoft: Connect your answer to measurable impact, clarity of thought, and trade-offs the team cares about. Below is a strong baseline response you can adapt with your own project examples.
Binary search partition on the smaller array. Choose cut positions so left partition across both arrays has half the elements and all left values are less than or equal to all right values.
When partition is valid, median is derived from max left and min right depending on odd or even total length. If left max from first array is too large, move cut left; otherwise move right.
Explain boundaries carefully using negative and positive infinity sentinels for edge cuts. Interviewers mainly assess reasoning clarity, not rote memorization.
Discussion
Comments (0)
Share how this question came up in your loop, or add tips for others preparing.
Log in to comment on this question.