Pie-Lie-Die's blog

Google phone screen
By Pie-Lie-Die, history, 2 years ago, In English

I recently had a google phone screen where i was asked the following question.

Given an array of n integers ( -1e9 <= A[i] <= 1e9 ) return top k combination sum where k <= 1500, n <= 1e5

eg. if n = 4, array = [8, 4, 2], k = 3, the answer will be [14, 12, 10] corresponding to the combinations (8, 4, 2), (8, 4) and (8, 2).

I only know the backtracking solution. How to solve this efficiently?

  • Vote: I like it
  • -23
  • Vote: I do not like it

Comments Comments (12)
| Write comment?
»
2 years ago, # |
← Rev. 16   Vote: I like it 0 Vote: I do not like it
  • sort the array in descending order
  • find smallest x such that (2^x)-1 >= k
  • say you have p positive items. If p>x then merge (p-x) smallest positive items into one, then add it to the largest x positive numbers (ex: [10,8,7,5,4,2,-2,-2,-123], k=7, x=3 then after this step array will be [10+11,8+11,7+11,-2,-2,-123])
  • Take first x elements of the array, generate all possible combi sum. store it in a multiset S
  • while( S.size() > k) keep removing min element from S
  • say, N[] is the array with all negative values. make it decreasing
  • for(i=0; i<N.size; i++) do this =>
    1. if(N[i]+ Max(S)) <= Min(S) then break
    2. let L = []
    3. iterate over S in decreasing order, add (N[i]+ Curr_of_S) to L if it is > MIN(S) , else break
    4. merge L with S; keep removing smallest if S.size > k

voila, S is your ans

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks dGreen. This is so elegant.

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I'm not sure if it is the correct soln

      → Reply
      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Maybe a case where adding ith element again will be better. Like if top two maximum num are 20, 19 and A[i] = -2, A[i+1] = -10 then it makes sense to add -2 to 20 as well as 19. Our current soln will add -2 to 20 and -10 to 19.

        → Reply
        • »
          »
          »
          »
          »
          2 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Edited, This one should be correct

          → Reply
»
2 years ago, # |
← Rev. 2   Vote: I like it +18 Vote: I do not like it

I think this can be solved using Fracturing Search. To handle the different sizes of each possible subset, we can insert $$$n$$$ $$$0$$$'s into the array. Thus, on your example, $$$(8, 4, 2), (8, 4), (8, 2)$$$ can be seen as $$$(8, 4, 2), (8, 4, 0), (8, 2, 0)$$$. CMIIW.

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    can you elaborate a bit more

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Consider the simpler version of the problem:

      Given an array $$$A$$$ of $$$N$$$ integers, you need to find $$$K$$$-th maximum sum subsequence of fixed size $$$L \leq N$$$.

      For example, if $$$A = [9, 6, 4, 2, -1, -3]$$$, these are the subsequences of size $$$L = 3$$$ sorted by their sum:

      Subsequences

      Among all $$$\binom{N}{L}$$$ subsequences, the $$$3$$$-rd subsequence is $$$[9, 4, 2]$$$. This simpler version of the problem can be solved using Fracturing Search.

      By inserting $$$N$$$ $$$0$$$'s into $$$A$$$, I was trying to reduce the original problem into the simpler version. Now, we are trying to find the $$$K$$$-th maximum sum subsequence of fixed size $$$N$$$ from the new array $$$A$$$ (new length is $$$2N$$$).

      Using the previous example, $$$A$$$ would now become $$$[9, 6, 4, 2, \underbrace{0, 0, 0, 0, 0, 0}_{N}, -1, -3]$$$ and these would be its length $$$N$$$ subsequences:

      Subsequences

      However, this approach is apparently wrong because we would end up with a total of $$$\binom{2N}{N}$$$ subsequences instead of $$$2^N$$$ subsequences.

      If we insist on solving the original problem using Fracturing Search, we would have to run $$$N$$$ separate fracturing searches simultaneously for each $$$1 \leq L \leq N$$$ and maintain it using something like Segment Tree.

      → Reply
»
2 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Divide the array into two sets let call them A and B, where all the positive elements will be in A, and negative in B, find the top K sum in both the set individually, and then use a priority queue to find the top K from both A and B.

Top K for each set can be found by sorting and some observations.

→ Reply
»
2 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

Very interesting problem thought.

Let's make simpler the problem

  1. All integers are positive (Problem 1)
  • Sum all positive integers
  • Take the first 11 (2^11 > k) lowers integers
  • use simple bitwise or backtracking to generate all possible combinations for those 11.
  • substract the sum those subset from the whole sum.
  • the top k values inialSum — subSetSum is your answer.
  1. All integers are negative. (Problem 2)
  • Take the 11 greater integers
  • use bitwise or backtracking to generate all posible combinations for those 11.
  • the top k sum are your answer.
  1. Getting back to the original problem.(Original Problem)
  • x number of positive values
  • y number of negative values
  • if 2^x >= K go for solution 1.
  • Generate all subset for positive (x <= 10)
  • Generate all subset for the greater 11 negatives.
  • Combine positive and negatives subset and take the top k.
→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How would why handle this case — -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -3 -4 and k = 1000

    I am not sure that taking only 11 elements would work.

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Agree, needs to be considered all as well for negative

      → Reply