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

3 comments:

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

    ReplyDelete
  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

    ReplyDelete
  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.

    ReplyDelete