## Goldman Sachs Interview Question for Software Engineers

• 0

Country: United States

Comment hidden because of low score. Click to expand.
1
of 1 vote

``````public static List<List<Integer>> findAllCombination(int num) {

List<List<Integer>>[] dp = new List[num];

Arrays.fill(dp, new ArrayList<>());

List<Integer> temp = Arrays.asList(1);
List<List<Integer>> combinations = new ArrayList<>();

dp[1] = combinations;

for (int i = 1; i <= num; i++) {
for (int j = 2; j < dp.length; j++) {

List<List<Integer>> prevCombinations = dp[j - 1];

for (List<Integer> list : prevCombinations) {
}
dp[j] = prevCombinations;
}
}
return dp[dp.length - 1];
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

The question is about possible combinations, not the permutations.
It means, that if we have a number 5 - then possible combinations are:
1+1+1+1+1
2+1+1+1
2+2+1
3+1+1
4+1

Comment hidden because of low score. Click to expand.
0
of 0 vote

No approximate algorithms required here. You just do an exhaustive search using DFS+Recursion to find the combination that sums up to target sum.

``````def combinationSum(nums, target):
nums.sort() # Sort the numbers so that you know when to stop (with respect to target)
res = []

def combinationHelper(nums, tempResult=[], sumSoFar=0, target=target, start=0):
if sumSoFar > target:
return
if sumSoFar == target:
res.append(tempResult[:])
return

for index in range(start, len(nums)):
tempResult.append(nums[index])
combinationHelper(nums, tempResult, sumSoFar+nums[index], target, index)
tempResult.pop()

combinationHelper(nums)
return res``````

You can definitely speed this up though using DP.

Comment hidden because of low score. Click to expand.
0
of 0 vote

def combinationSum(nums, target):
nums.sort() # Sort the numbers so that you know when to stop (with respect to target)
res = []

def combinationHelper(nums, tempResult=[], sumSoFar=0, target=target, start=0):
if sumSoFar > target:
return
if sumSoFar == target:
res.append(tempResult[:])
return

for index in range(start, len(nums)):
tempResult.append(nums[index])
combinationHelper(nums, tempResult, sumSoFar+nums[index], target, index)
tempResult.pop()

combinationHelper(nums)
return res

Comment hidden because of low score. Click to expand.
0
of 0 vote

public static List<List<Integer>> findAllCombination(int num) {

List<List<Integer>>[] dp = new List[num];

Arrays.fill(dp, new ArrayList<>());

List<Integer> temp = Arrays.asList(1);
List<List<Integer>> combinations = new ArrayList<>();

dp[1] = combinations;

for (int i = 1; i <= num; i++) {
for (int j = 2; j < dp.length; j++) {

List<List<Integer>> prevCombinations = dp[j - 1];

for (List<Integer> list : prevCombinations) {
}
dp[j] = prevCombinations;
}
}
return dp[dp.length - 1];
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````def fnc(list):
def helper(hi):``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

combinations of what? Any amount of any number and any operations? Of course its NP hard, as it is at least as hard as subset sum.

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.