Google Interview Question for Software Engineer / Developers


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;
		HashMap<Integer, LinkedList<Integer>> subsets = new HashMap<Integer, LinkedList<Integer>>();
		subsets.put(0, new LinkedList<Integer>());
		for(int n : numbers) {
			HashSet<Integer> keys = new HashSet<Integer>(subsets.keySet());
			for(int i : keys) {
				int sum = (i+n) % M;
				if(sum == 0) {
					subsets.get(i).add(n);
					return subsets.get(i);
				}
				if(subsets.containsKey(sum))
					continue;
				LinkedList<Integer> list = (LinkedList<Integer>)subsets.get(i).clone();
				list.add(n);
				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 + " ");
		}
	}
}

- Sunny November 14, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

this is wrong:

$ java SubsetSum 1 1 1 1 5
None found

Should return 5

- Anonymous November 14, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Sunny November 14, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- mee November 17, 2014 | Flag
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.

- eugene.yarovoi November 19, 2014 | Flag
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.

- united November 14, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous November 20, 2014 | Flag
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.

- cydrain November 25, 2014 | Flag
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

- Anonymous November 13, 2014 | Flag Reply
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];
            sOSAddingToMultipleOfLen(0, 0, 0, output);
}

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] != 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;
        }

- ad November 15, 2014 | Flag Reply
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) {
				subset.add(current);
				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++) {
			list.add(Integer.parseInt(args[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);
	}

}

- tk November 16, 2014 | Flag Reply
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;
}

- Mhret November 16, 2014 | Flag Reply
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

- Paddy November 17, 2014 | Flag Reply
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<>();
		lst.add(1);
		lst.add(2);
		lst.add(1);
		lst.add(4);
		lst.add(5);
		ArrayList<Integer> lst2=findSubset(lst);
	}

- Sercan November 24, 2014 | Flag Reply
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{

    BufferedReader in;
    StringTokenizer str = null;
    PrintWriter out;

    private String next() throws Exception{
    	if (str == null || !str.hasMoreElements())
    	    str = new StringTokenizer(in.readLine());
    	return str.nextToken();
    }
	
    private int nextInt() throws Exception{
	   return Integer.parseInt(next());
    }
	
    public void run() throws Exception{
    	in = new BufferedReader(new InputStreamReader(System.in));
    	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[0][a[0] % 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][0]) 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;
            r.add(a[pos]);
            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;
            r.add(a[pos]);
            backtrack(pos - 1, nmod, r);
        }
    }

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

- Darkhan.Imangaliev December 23, 2014 | Flag Reply
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;
}

- pavel.kogan December 31, 2014 | Flag Reply
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

- Sara January 20, 2015 | Flag Reply
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

- saumya January 26, 2015 | Flag Reply
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?)

- andy March 12, 2015 | Flag Reply
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.

- varsrm November 13, 2014 | Flag Reply
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)

- CT November 14, 2014 | Flag Reply
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.

- RG November 14, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- CT November 14, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- CT November 14, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@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.

- eugene.yarovoi November 19, 2014 | Flag


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More