Блог пользователя Pie-Lie-Die

Google phone screen
Автор Pie-Lie-Die, история, 3 года назад, По-английски

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?

  • Проголосовать: нравится
  • -23
  • Проголосовать: не нравится

»
3 года назад, # |
← Rev. 16   Проголосовать: нравится 0 Проголосовать: не нравится
  • 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

→ Ответить
»
3 года назад, # |
← Rev. 2   Проголосовать: нравится +18 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    can you elaborate a bit more

    → Ответить
    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

      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.

      → Ответить
»
3 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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.

→ Ответить
»
3 года назад, # |
← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

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.
→ Ответить
  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    → Ответить