Saturday, January 8, 2011

Given two lists find the k-th sum

You are given two lists A and B of size n and m respectively and a number k < n * m, find the k-th sum (a+b), where a is in A and b is in B.

Please solve this problem if you come to my interviews


  1. Isn't this the same question as Dec 16th (without the arrays being presorted)?

  2. One rather simple solution could be: O(m*n * log(m*n) [insert each possible sum into max heap] + k [k*O(1) for heap extract-max]) if am not mistaken

  3. Maybe we can solve it by finding median in O(n) and then reduce the lists, and reduce k - depends on a few cases.