Find median between 2 sorted lists

Question

Hardik Shah · Accepted Answer

1.> Merge the sorted list and the element in the middle (in case of odd length) or mean of two middles( in case of the even length)
 Time complexity : O(n + m) Space Complexity : O(n + m)

Anonymous · Answer

1. Find index of final median = half of sum of sizes of lists
2. Iterate over both lists at once up to 'median' times. On each iteration pick smaller of two list's current values. Median'th value is your median
3. Address case where sum of given list sizes is even (mean of closest values)
O(n+m) time, O(1) extra space

AppDynamics

AppDynamics Interview Question

Interview Answers

Followed companies

Job searches

Bowls

Want the inside scoop on your own company?