Goldman Sachs Interview Question: Given an integer, return all ... | Glassdoor

Interview Question

Software Engineer Interview

Given an integer, return all sequences of numbers that sum

  to it. (Example: 3 -> (1, 2), (2, 1), (1, 1, 1)).

Interview Answer

3 Answers


This problem boils down to the subset sum problem . Make an list(1,1,1,2,2,2,3,3,3,1,2,3) . Fins a subset in this list which equals the given number. Handle duplicates gracefully. For each list found, convert it to a string and add it to hashmap to check for duplicates

rohit ramesh on Nov 25, 2013

This approach would not work for larger integers.What if the integer is 1024 and not 3?

Anamika Singh on Nov 15, 2014

Could be done using recursion based on number of solutions variables you want in your sum. Define F(k,1) = (k) i.e. the set of vectors summing to k with one variable in the sum. Then F(k,2) = ( (F(k-1,1),1), (F(k-2,1), 2),...) union F(k,1).Generalize and do it for solutions with 1 variable to solutions with k variables

Anonymous on Nov 16, 2014

Add Answers or Comments

To comment on this, Sign In or Sign Up.