## Google Interview Question for Software Engineer / Developers

• 0

Country: United States

Comment hidden because of low score. Click to expand.
10
of 12 vote

O(n^2) solution. Basically for each number that is 0 to N-1, we want to keep track of which subsets of the input will add up to that number after modulo N. So that's what my code does below with the HashMap, and the parameter M can actually be N or 2N.

``````import java.util.*;

class SubsetSum {

static List<Integer> findSubset(int[] numbers, int M) {
int N = numbers.length;
for(int n : numbers) {
HashSet<Integer> keys = new HashSet<Integer>(subsets.keySet());
for(int i : keys) {
int sum = (i+n) % M;
if(sum == 0) {
return subsets.get(i);
}
if(subsets.containsKey(sum))
continue;
subsets.put(sum, list);
}
}
return null;
}

public static void main(String[] args) {
int len = args.length;
int[] numbers = new int[len];
for(int i=0; i<len; i++) {
numbers[i] = Integer.parseInt(args[i]);
}
List<Integer> subset = findSubset(numbers, 2*len);
if(subset == null) {
System.out.println("None found");
} else {
for(int n : subset)
System.out.print(n + " ");
}
}
}``````

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

this is wrong:

``````\$ java SubsetSum 1 1 1 1 5
None found``````

Should return 5

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

Oh that's because my main method calls findSubset(numbers, 2*len), meaning it looks for multiples of 2N.

If you looking for multiples of N then you should change that to just len and recompile first.

Sorry if I didn't make this clear.

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

i don't think the complexity is O(n^2), your inner loop iterates over all the subsets which means it is 2^n, therefore the complexity is O(n(2^n)).

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

@mee: The inner loop doesn't iterate over all the subsets. It iterates over each distinct subset sum mod M, which means the inner loop executes O(MN) times. If M = N or M = 2N, the inner loop executes O(N^2) times.

Now, it does appear at first that maybe the solution is actually O(N^3), because the line LinkedList<Integer> list = (LinkedList<Integer>)subsets.get(i).clone(); actually takes O(N) time to execute. However, that line is only hit if the current subset sum mod M is distinct from any other subset sum mod M seen so far. Since there can only be M different subset sums mod M, the line can only be executed M times, for a total of O(MN) time spent on that line.

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

Solution to (1):
Let Fk (1<=k<=N) be the first k elements in the list. Let sk be the sum of elements in Fk.
If there exists k such that sk%N = 0, then return elements in Fk.
Otherwise, every sk%N is between 1 and N-1. So, among s1%N, s2%N, ..., sN%N, there must exist i, j, si%N = sj%N. Return elements in Fj but not in Fi (suppose j > i).

This takes O(N) time. The same solution doesn't apply for question (2). But it seems a BFS approach should still use O(N) time.

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

Solution to (1) is excellent.
Could you explain how you use BFS to solve the Q2

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

Solution to (1) is also in-correct.
It's possible that you cannot find i, j to let si%N == sj%N.
This problem doesn't request a continous subset, you solotion missed many subset combinations.

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

hi, not sure, if am giving the correct answer...

my solution is:
using recursion on DP calculate if a subset product is possible for N, 2N, 3N so on until it becomes more than the maximum product of the array.

when the multiple is more than max product come out of the loop

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

I think both the questions have a similar solution. We would need to change the target variable below from N to 2N

``````static int[] input = new int[] { 3, 5, 2, 7, 6, 1, 8 };
static int target = input.Length;
static void Main(string[] args)
{
int output = new int[input.Length];
}

static bool sOSAddingToMultipleOfLen(int currIndex, int sumSoFar,int filled, int[] output)
{
if (input == null || currIndex >= input.Length)
return false;

if ((sumSoFar) % target == 0 && output != 0)
{
Console.WriteLine("--------");
foreach (int i in output)
Console.Write(i + ", ");
return true;
}
if (currIndex < input.Length)
{
output[filled] = input[currIndex];
bool with = SOSAddingToMultipleOfLen(currIndex + 1, sumSoFar + Input[currIndex], filled + 1, output);
output[filled] = 0;
bool wo = SOSAddingToMultipleOfLen(currIndex + 1, sumSoFar, filled, output);

return with || wo;
}
return false;
}``````

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

``````import java.util.ArrayList;

public class SubsetSumMultiOfN {

public static void findSumMultiOfN(ArrayList<Integer> list, int n) {
// start from the first number in the list.
ArrayList<Integer> subset = new ArrayList<Integer>();
int allowed_complement = n;

for (int i=0; i<n; i++) {
int current = list.get(i);

// if a number is already a multi of n, then stop and
// return a subset contain only that number
if (current % n == 0) {
// print out the result
System.out.println("Subset element: "+current);
return;
}

int complement = current % n;
if (complement <= allowed_complement) {
allowed_complement -= complement;
}
// check if subset found
if (allowed_complement == 0) {
// print out the result
System.out.print("Subset element:");
for (int j=0; j<subset.size(); j++) {
System.out.print(" "+subset.get(j));
}
System.out.println();
return;
}
}

// if none found
System.out.println("None found!");
}

public static void findSumMultiOf2N(ArrayList<Integer> list, int n) {
findSumMultiOfN(list, n*2);
}

public static void main(String[] args) {
// args contains the input numbers
// put them in an ArrayList
ArrayList<Integer> list = new ArrayList<Integer>();
int length = args.length;
for (int i=0; i<length; i++) {
}

// give the list to the functions
System.out.println("Result for N:");
findSumMultiOfN(list, length);
System.out.println("Result for 2N:");
findSumMultiOf2N(list, length);
}

}``````

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

Brute force solution.

Go through all subsets (there are 2^n - 1) until you find one that is divisible by N (or 2N).

``````#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool contains(vector<int> &v, int value) {
return find(v.begin(), v.end(), value) != v.end();
}
vector<int> findSubset(vector<int> A, int divisibleBy) {
for(auto i = 0; i < pow(2, A.size()) - 1; i++) {
vector<int> subset;
int sum = 0;
for(decltype(A.size()) idx = 0; idx < A.size(); idx++)	{
if(i & (1 << idx) && !contains(subset, A[idx])) {
sum += A[idx];
subset.push_back(A[idx]);
if(sum > 0 && (sum % divisibleBy) == 0) {
return subset;
}
}
}
}
return vector<int>();
}
int main() {
for(auto i : findSubset({2,3,3,6,1}, 10))
cout << i << " ";
return 0;
}``````

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

1. Find the minimum element in Array. this will give the minimum multiple of N call it min
2. Find the sum of all elements = > This will give us maximum element of N for that array call it max
3.Apply Find all subsets of an int array whose sums equal a given target for all multiple from min to max

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

still O(n^2) solution, but simpler code

``````public static ArrayList<Integer> findSubset(ArrayList<Integer> lst){
int N = lst.size();
int[] arr = new int[N];
int i = 0,j=0;
for(; i<N;i++){
for(j=0;j<=i;j++){
arr[j] = (arr[j] + lst.get(i))%N;
if(arr[j] == 0)
return new ArrayList<Integer>(lst.subList(j, i+1));
}
}
return null;
}

public static void main(String[] args) {

ArrayList<Integer> lst = new ArrayList<>();
ArrayList<Integer> lst2=findSubset(lst);
}``````

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

That's dynamic programming problem, can be solved in O(n^2) - time with O(n^2) memory usage

``````import java.util.*;
import java.io.*;

public class Main{

StringTokenizer str = null;
PrintWriter out;

private String next() throws Exception{
if (str == null || !str.hasMoreElements())
return str.nextToken();
}

private int nextInt() throws Exception{
return Integer.parseInt(next());
}

public void run() throws Exception{
out = new PrintWriter(System.out);

int n = nextInt();
int []a = new int[n];
for(int i = 0; i < n; ++i) a[i] = nextInt();
List<Integer> first = dp(a, n);
out.println(first);
List<Integer> second = dp(a, 2 * n);
out.println(second);

out.close();
}

boolean [][]dp;
int N;
int []a;
private List<Integer> dp(int []a, int N) {
this.a = a;
int n = a.length;
this.N = N;
dp = new boolean[n][N];
dp[a % N] = true;
for(int i = 1; i < n; ++i) {
dp[i][a[i] % N] = true;
for(int j = 0; j < N; ++j) {
dp[i][j] |= dp[i-1][j];
dp[i][(j + a[i]) % N] |= dp[i-1][j];
}
}
// for(int i = 0; i < n; ++i) {
//     System.out.println(Arrays.toString(dp[i]));
// }
if (!dp[n-1]) return null;
List<Integer> ret = new ArrayList<Integer>();
backtrack(n - 1, 0, ret);

return ret;
}

private void backtrack(int pos, int mod, List<Integer> r) {
if (pos == 0) {
if (mod == 0) return;
return;
}
if (dp[pos][mod] == dp[pos - 1][mod]){
backtrack(pos - 1, mod, r);
}else {
int nmod = mod - a[pos];
if (nmod < 0) nmod += N;
backtrack(pos - 1, nmod, r);
}
}

public static void main(String args[]) throws Exception{
new Main().run();
}
}``````

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

Unfortunately I don't understand what is the difference between N and 2N case. Below 2 general solutions: 1 recursive, 1 iterative.

``````//Recursive solution O(N!)
//cumSum in first call equals 0
//dstSum is N or 2N
bool FindSubsetRecursive(int dstSum, int cumSum, int *pData, int N)
{
if (N == 0)
return false;

if (N == 1)
return ((cumSum + *pData) % dstSum == 0) ? true : false;

for (int i=0; i<N; i++)
{
if (FindSubsetRecursive(dstSum, cumSum + pData[i], pData+i+1, N-i-1))
return true;
}

return false;
}

//Iterative solution O(N * 2^N)
bool FindSubsetIter(int dstSum, int *pData, int N)
{
for (int i=1; i<(1<<N); i++)
{
int tmp = i, sum = 0, cnt = 0;
while (tmp > 0)
{
sum += (tmp&1) * pData[cnt++];
tmp = tmp >> 1;
}

if (sum % dstSum == 0)
return true;
}

return false;
}``````

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

If the questions just asking find "a" subset, we can just first adding all the numbers together and then if Sum%N==0, return, else, Sum-someNum, where someNum can make (Sum-someNum)%N = 0

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

This is a classic problem from Discrete Mathematics. Consider the following sums: a1, a1 + a2, a1 + a2 + a3, ..., a1 + a2 + ... + an. By pigeonhole principle, either one of these sums is exactly 0 mod n or two of these sums have the same remainder mod n. Hence, their difference will be 0 mod n.

This can be translated into a linear time algorithm which computes the sums: a1, a1 + a2, a1 + a2 + a3, ..., a1 + a2 + ...+ an. Also, at the same time computes their remainder modulo n. Then, amongst the remainders we search for 0 or two identical remainders. All of these can be done in linear time

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

By subset, is this in the true meaning of a set (i.e. all unique values in the output even if input arraylist has repeated values?)

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

If the array list consists of all the numbers until n. Sum of all numbers including n would be n(n+1)/2. Now, we want to find 'a' subset whose sum is a multiple of n.

When n is odd, n+1 is even, hence, the sum of all the numbers including n would be a multiple of n. Hence, the answer here is a subset with all the numbers including n.

When n is even, sum of all even numbers until and including n is (n)(n+2)/2 which again is a multiple of n. Hence, the answer here is a subset with all the even numbers until and including n.

Same approach can be followed for multiples of 2N.

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

1) If you make a simple recursive search, it shoul be O (N) because it is likely that amoung N numbers there will be one that is mod N 0, and if not, it is even more likely to have one with remainder N - x mod N where x any of the other number (so they compliment each other) and so on. So the search must stop in O(N) amortized time.

1.5) Is not asked, but lets say the question about devisability on number much larger than N. Than such search is simply exponential.

2) This one is tough. Each of 2N reminder can be as likely as present as not present. Having subset of one number is 50% likely. Complimenting pair is probably very likely. because if you don't find compliment for one number you are likely to find for another. That's seems like O(n^2).

EDIT: See my comment below, 2nd problem is really O (n log n)

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

The question doesn't say the numbers are distinct, or that they are in order, or that they are sequential. This problem is NP hard with an O(n^2) solution.

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

I did not say distinct, sequential, in order. On arbitrary input, amortized time complexity can be assumed. Due to the probability of the resulting subset to consist from one integer in problem 1 and from two integers in problem 2, I suggest that amortized time is O(n) in problem 1 and O(n^2) in problem 2.

If we had random integers and did int mod N, we would have distribution of 1 to N numbers whith N elements. For the 2nd problem it would be distribution of 1 to 2N numbers within N elements. Those are the numbers that you can sum up instead of originals.

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

On the second thought, it will be O (n log n) for the second problem. Because when we look for the pair that is 2N - int mod 2N, you are exponentially more and more likely to find it with every new int.

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

@RG: This problem is far more restricted than the general subset-sum problem, so there's no reason to believe it's NP-complete. In fact, it's not. For example, Sunny gives a worst-case O(n^2) solution.

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.