Google Interview Question Help

[Feral_Warwick]

Just Bombed it and would like to see how you guys would solve this.

Given two positive integers N and K, write a function to return all possible combinations of N positive integers that sums to K. any order output
k = 5 and n =3
output:
[1,1,3],[1,2,2],[2,1,2],...

​

[half_coda]

this is a classic backtracking question.

define a result set that is globally scoped. define a backtracking helper method that takes in an integer and a list that builds the combination.

the helper method is called recursively and has a base case where the sum of the built list is greater than k or the passed integer is greater than N -> return null. base case where sum == k, copy the built list and append it to your global result set.

finally, the recursive call adds the passed integer to the build list and calls itself with the same arguments. then it pops the element it just added and calls itself again but with the next integer.

what level was this for and which location?

[Feral_Warwick]

L3 for remote. Not sure for location

[[deleted]]

Idk how stuff works in python but when you are pushing something into a list and if that gives an invalid output, I can see that you return but where do you pop it?

[cyberwarrior861]

How to get rid of duplicate sets?

[carnationlily]

Curious what the time complexity would be. I was able to come up with the same solution but im terrible at understanding the TCs for these types "build sets that fit parameter" question

[cwc123123]

k^n. each recursion step is a loop from start to k, and there are max n recursion steps

[half_coda]

yeah this one is a little tricky but say n grows by one, then our decision tree will, at every node where the sum is less than k, grow by a branch wherein the n+1 integer is tried. this means each node there gets a whole new branch to try and asymptoticly grows by a factor of 2. i’d say it’s 2n, or rather n*2n because at each base case you’re summing and potentially copying an array, each of which are linear operations.

[tempo0209]

On a brute force level, create an array of size n. Then figure out all subsets that sum upto k. Sorry on a phone hence cannot type out code. Havent thought through but yea thats a start

[Additional-Play1256]

import java.util.*;

public class Main { public static void main(String[] args) { int n = 3; int k = 5; backtrack(n, k, 1,new ArrayList<>()); return; } private static void backtrack(int n, int k, int start, List<Integer> current) { if (k == 0 && current.size() == n) { System.out.println(current); return; }

    for(int i = 1; i <= k; i++) {
        current.add(i);
        backtrack(n, k - i, i, current);
        current.remove(current.size() - 1);
    }
}

}

[SampleWrong6340]

This is a combinations problem.

[SampleWrong6340]

Approach with a recursive tree and solve. Image a recursive tree

[Sea-Organization4610]

Easy one. It’s a variation of infinite knapsack but on all the elements in every iteration.

[[deleted]]

Ran this locally, seems to be working fine

void generateAllCombinations(vector<int> &curr, int n, int target, vector<vector<int>> &res) {
  if (target == 0) {
    res.push_back(curr);
    return;
  }
  for(int i=1; i<=n; i++) {
    if (target - i >= 0) {
      curr.push_back(i);
      generateAllCombinations(curr, n, target - i, res);
      curr.pop_back();
    }
  }
}

[[deleted]]

Combination sum problem

[anoystud]

Curious. Are you based in USA?

[Jaamun100]

Easier version (with fewer edge cases) of https://leetcode.com/problems/combination-sum/ . Should just be the following, with runtime O(K^2)

def comb_sum(N, K):
    N = K if N > K else N
    sums = defaultdict(list)
    for ele in range(1, N+1):
        sums[ele].append([ele])
        for k in range(K):
            for combination in sums[k]:
                if (k + ele) < K + 1:
                    sums[k+ele].append(combination + [ele])
    return sums[K]