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)

Sigiloso · 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

Pergunta de entrevista da empresa AppDynamics

Respostas da entrevista

Empresas seguidas

Buscas de vagas