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)).
Answer

Interview Answer

3 Answers

2

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
0

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

Anamika Singh on Nov 15, 2014
2

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.