Google phone screen

Revision en1, by Pie-Lie-Die, 2022-03-15 08:57:10

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?

Tags google, backtracking, greedy, constructive

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English Pie-Lie-Die 2022-03-15 08:57:10 420 Initial revision (published)