Google Interview Question for Software Engineer / Developers


Country: United States
Interview Type: In-Person




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

This is my O(n^2), O(1) space solution.
Iterates over all possible intervals, and increases number of subsets by 1 (if valid).
If new number is reached (if we are furthest we have ever been), we multiple number of subsets by 2 because we now have subsets + subsets combined with new number.
Union of 2 valid subsets is a valid subset.

int countSubsets(vector<int> numbers, int k) {
	int num_valid_subsets = 0;
	int max_interval_ending = 0;
	for (int i = 0; i < numbers.size(); ++i) {
		int max = numbers[i];
		int min = numbers[i];
		for (int j = i; j < numbers.size(); ++j) {
			if (numbers[j] > max) {
				max = numbers[j];
			}

			if (numbers[j] < min) {
				min = numbers[j];
			}

			if (max + min <= k) {
				if(j > max_interval_ending) {
					max_interval_ending = j;
					//all intervals that we already counted can be in combination with or without this new number
					num_valid_subsets *= 2;
				}
				else {
					++num_valid_subsets;
				}
			}
			else {
				break;
			}
		}
	}

	return num_valid_subsets;
}

- tskrgulja1 February 24, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

shouldn't this line be inside the first loop?

int max_interval_ending = 0;

- Marcin March 02, 2019 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

int max_interval_ending = 0;
is it in correct place?
I think it should in the first loop

- Marcin G March 02, 2019 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Let say I have { 1, 1, 1, 1 } in my vector, and K = 2. Then the number of all not empty subsets is 15, where as this algorithm will produce (correct me if I am wrong) 14 ?

- Vahagn March 06, 2019 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Let's say my vector is a={1, 2, 3, 4} and K=8. Then all non empty subsets do satisfy the condition, therefore the answer should be 15 in this case. But the algorithm will produce 14. The reason is that when the algorithm considers j==3 case, it assumes that the set {2, 3} was already counted, but it was not.

If we move int max_interval_ending = 0; inside the loop, then that will not work either. In the case above it will produce more than 16. So perhaps we need to move also int num_valid_subsets = 0; inside the loop and then calculate sum of all num_valid_subsets?

But then the following example will not produce proper result I guess a={1, 2, 9, 3, 4} and K=8.

However, the idea is an interesting one. I came up with this solution:

int countSubsets(std::vector<int> numbers, int k)
{
	int total_sum = 0;
	for (int i = 0; i < numbers.size(); ++i) {

		if (2 * numbers[i] > k) {
			continue;
		}

		int sum = 1;
		int max = numbers[i];
		int min = numbers[i];
		for (int j = i+1; j < numbers.size(); ++j) {
			int tmp_max = std::max(max, numbers[j]);
			int tmp_min = std::min(min, numbers[j]);

			if (tmp_max + tmp_min <= k) {
				sum *= 2;
				min = tmp_min;
				max = tmp_max;
			}
		}
		total_sum += sum;
	}

	return total_sum;
}

- Vishap March 06, 2019 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I used both, the original code and the one that Vishap came with as more reliable in terms of result solution.
I have not found yet how this happens but [2,4,2,5,7] with k=10 gives the wrong result.
The correct result is 31 (as 2^5-1) - 4(options [7],[5,7],[4,5,7],[4,7]) that is equal to 27.
Any idea on why?

- MKisunko March 16, 2019 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

We can do it via queue manner ;
Queue Node{
int set[],
int min, max;
}
in each queue node, keep the index of element instead element( that will utilise in step 2)
1. start pushing element in the queue until no more element left, of length
1 having min& max as same as element and set would contain the index of this
element.

2. pop element from the queue, and start adding one element [ increase the set count]
in this set from starting from index in (set[set.length-1]) +1 (so that same element don't get add up
, it's constant time to check min and max. and the condition;

3. Keep doing this until you won't be able to add any further element in the queue.

4. finalCount = setCountSoFar + queue.size()

Complexity:
We are traversing each element of given set at max n times. so O(n^2)
Space complexity; at any given point of time, queue will contain at max n set only
why? since we keep popping the less length set from the queue in each iteration
and adding bigger length set in the queue (+1 size of previous ). At max the length of element would lie
between length=1 to length=n,
So, O(n^2)

O(n^2)/O(n^2)

- nitinguptaiit April 12, 2019 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

I don't understand the question. Why are {2} and {4} are allowed as subsets and not {5} and {7} ? 5 and 7 are also less than 8.

- Joe February 27, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
2
of 2 votes

min of {5} is 5, max of {5} is 5, then max+min = 5+5=10>8

- Anonymous March 07, 2019 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

void subset(int* data, int n, int start, list<list<int>>& ret)
{
	if (start == n)
	{
		ret.resize(ret.size() + 1);
		return;
	}

	list<list<int>> with;
	subset(data, n, start + 1, with);	// use data[start]
	for (list<int>& set : with)
		set.push_front(data[start]);

	list<list<int>> without;
	subset(data, n, start + 1, without);	// not use data[start]
	ret.assign(with.begin(), with.end());
	ret.insert(ret.end(), without.begin(), without.end());
}

int countSubsets(vector<int> data, int K) {
	sort(data.begin(), data.end());

	int count = 0;
	int n = data.size();
	for (int i = 0; i<n; i++) {
		if (data[i]>K)
			break;

		int below_max = K - data[i];
		for (int j = i; j<n; j++) {
			if (data[j]>below_max)
				break;

			// if has inner set like set [{2 4 6 7}. min=2 max=7], so we consider just how many sub set with {4 6} can make
			/*
				2 4 6 7
				2 4 7
				2 6 7
				2 7
				is like
				{4 6}
				{4}
				{6}
				{}
			*/
			if (i < j)
			{
				int* inner_set = &data[i + 1];
				int inner_n = j - i - 1;

				list<list<int>> ret;
				subset(inner_set, inner_n, 0, ret);
				count += ret.size();

				for (list<int>& sub : ret)
				{
					cout << data[i];
					if (sub.size() > 0)
					{
						for (int v : sub)
							cout << ", " << v;
					}
					cout << ", " << data[j] << endl;
				}
			}
			else
			{
				++count;

				cout << data[i] << endl;
			}
		}
	}
	return count;
}

- lesit.jae February 24, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This prints 4 , but the actual answer is 5 in the above example.I think instead of ++count we should increment count by j-i diff

- samayragoyal990 February 24, 2019 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

this cannot work because you only count contiguous intervals. one set could be made up of several intervals

- tomislavskrgulja February 24, 2019 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I agree my mistakes. I didn't consider the inner set of subset.
So, I updated again my code

- lesit.jae February 25, 2019 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

were you allowed to use extra n^2 space?

- tomislavskrgulj February 24, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is my solution in c++. I think it is OK. O(n^2) time and O(1) space.
It works by iterating over all possible intervals, and if new number is reached multiples current number of subsets by 2 (now we have all the old subsets + old subsets combined with new number).
If no new number then just increase subsets by 1.

int countSubsets(vector<int> numbers, int k) {
//compute lengths of valid max interval starting at each index
int num_valid_subsets = 0;
int max_interval_ending = 0;
for (int i = 0; i < numbers.size(); ++i) {
int max = numbers[i];
int min = numbers[i];
for (int j = i; j < numbers.size(); ++j) {
if (numbers[j] > max) {
max = numbers[j];
}

if (numbers[j] < min) {
min = numbers[j];
}

if (max + min <= k) {
if(j > max_interval_ending) {
max_interval_ending = j;
//all intervals that we already counted can be in combination with or without this new number
num_valid_subsets *= 2;
}
else {
++num_valid_subsets;
}
}
else {
break;
}
}
}

return num_valid_subsets;
}

- tomislav_skrgulja February 24, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class Random {

    public static void main(String[] args) {
        int[] nums = {2,4,5,7};
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            calculateSubSets(nums, 8, i, result);
        }
        System.out.println(result);
        System.out.println(result.size());
    }

    public static void calculateSubSets(int[] nums, int k, int index, List<List<Integer>> result) {
        if (index == nums.length || nums[index] > k) {
            return;
        }

        List<Integer> subset = new ArrayList<>();
        if (nums[index] * 2 <= k) {
            subset.add(nums[index]);
            result.add(subset);
        }

        subset = new ArrayList<>();
        subset.add(nums[index]);
        for (int i = index + 1; i < nums.length; i++) {
            if (nums[index] + nums[i] <= k) {
                subset.add(nums[i]);
                result.add(new ArrayList<>(subset));
            } else {
                while (subset.size() > 2) {
                    subset.remove(1);
                    result.add(new ArrayList<>(subset));
                }
            }
        }
    }
}

- sj February 25, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This can be done in O(n log n)

- Arash February 25, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public List<String> mergeStrings(final String s1, final String s2) {
        final List<String> ans = new ArrayList<>();
        helper(s1, s2, "", ans);

        return ans;
    }

    private void helper(final String s1, final String s2, final String merged, final List<String> ans) {
        if (s1.length() == 0) {
            ans.add(merged + s2);
            return;
        }

        if (s2.length() == 0) {
            ans.add(merged + s1);
            return;
        }

        helper(s1.substring(1), s2, merged + s1.charAt(0), ans);
        helper(s1, s2.substring(1), merged + s2.charAt(0), ans);
    }

- Anonymous February 25, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

# Solution made by lucasmrdt
# Alogrithm O(n log n)
def find_subsets(numbers: [int], k: int):
    subsets = []
    for i1, n1 in enumerate(numbers):
        for i2, n2 in enumerate(numbers[i1:]):
            if n1 + n2 <= k:
                subset = numbers[i1 : i1+i2+1]
                subsets.append(subset)
                if len(subset) != 2 and i1 != i1+i2:
                    subsets.append([n1, n2])
    return subsets

if __name__ == '__main__':
    numbers = [2, 4, 5, 7]
    k = 8
    subsets = find_subsets(numbers, k)
    print(subsets)
    print(len(subsets))

- lucasmrdt February 26, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

# Solution made by lucasmrdt
# Alogrithm O(n log n)
def find_subsets(numbers: [int], k: int):
    subsets = []
    for i1, n1 in enumerate(numbers):
        for i2, n2 in enumerate(numbers[i1:]):
            if n1 + n2 <= k:
                subset = numbers[i1 : i1+i2+1]
                subsets.append(subset)
                if len(subset) != 2 and i1 != i1+i2:
                    subsets.append([n1, n2])
    return subsets

if __name__ == '__main__':
    numbers = [2, 4, 5, 7]
    k = 8
    subsets = find_subsets(numbers, k)
    print(subsets)
    print(len(subsets))

- lucasmrdy February 26, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

# Solution made by lucasmrdt
# Alogrithm O(n log n)
def find_subsets(numbers: [int], k: int):
    subsets = []
    for i1, n1 in enumerate(numbers):
        for i2, n2 in enumerate(numbers[i1:]):
            if n1 + n2 <= k:
                subset = numbers[i1 : i1+i2+1]
                subsets.append(subset)
                if len(subset) != 2 and i1 != i1+i2:
                    subsets.append([n1, n2])
    return subsets

if __name__ == '__main__':
    numbers = [2, 4, 5, 7]
    k = 8
    subsets = find_subsets(numbers, k)
    print(subsets)
    print(len(subsets))

- lucasmrdt February 26, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

ok

- lucasmrdt February 26, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

TIME: O(n^2)

public static void main(String[] args) {
	int[] nums = {2,4,5,7};
        int k = 8;
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> subset = new ArrayList<>();
        calculateSubSetsTwo(nums, k, -1, result, subset);
        System.out.println(result);
}

public static void calculateSubSetsTwo(int[] nums, int k, int index, List<List<Integer>> result, List<Integer> subset) {
        if (index == nums.length || (index >= 0 && nums[index] > k)) {
            return;
        }

        if (subset.size() == 1 && nums[index] * 2 <= k) {
            result.add(new ArrayList<>(subset));
        } else if (subset.size() > 1) {
            result.add(new ArrayList<>(subset));
        }

        for (int i = index + 1; i < nums.length; i++) {
            subset.add(nums[i]);
            if (index == -1 || subset.get(0) + nums[i] <= k) {
                calculateSubSetsTwo(nums, k, i, result, subset);
            }
            subset.remove(subset.size() - 1);
        }
}

- sj February 27, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

qsort + upper_bound will reduce time complexity to O(n*log(n))

- mem February 27, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

and

{int NES (vector<int> in, int k)
{
int ret =0;

sort(in.begin();i < in.size();i++);

for(int i=0 ; i<in.size() && input.at(i)<=k/2; i++) //possible min members
{
int num = 0; //number of possible max number

for(j=i+1; j<in.zise() && in.at(j)+in.at(i)<=k; j++,num++); //possible max number

ret += 1<<num; //subset of possible max number set
}

return ret;
}

and

- Yang Xiang Ting March 07, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Can be solved using 2 Pointers technique. Complexity - O(n logn) for sorting. If the data is sorted then O(n)

sort(V.begin(), V.end());
    int p1 = 0,p2 = V.size()-1;
    int ans = 0;
    while(p1<=p2)
    {
        if(V[p1] + V[p2] > k)
        {
            p2--;
        }
        else
        {
            ans = ans + 1<<(p2 -p1);
            p1++;
        }
    }

- Anonymous March 10, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I decided to get not only the number of subsets but also subsets themselves to check how stable solution is.

def find_patterns(vector, K):
    def append_to_result_set():
        if vector_element < element[0]:  
            result_set.append([vector_element]+element)
        else:
            if vector_element < element[-1]:  
                result_set.append([element[0]]+[vector_element]+element[1:])
            else:
                result_set.append(element+[vector_element])
    result_set = []
    for vector_element in vector:
        if vector_element > K:
            continue
        max_existing_element = len(result_set)
        for i, element in enumerate(result_set):
            if i >= max_existing_element:
                break
            if element and (min(vector_element, element[0])+max(vector_element, element[-1]) <= K):
                append_to_result_set()
        if 2*vector_element <= K:
            result_set.append([vector_element])
    return result_set, len(result_set)


print(find_patterns([2,4,5,7],8))
print(find_patterns([2,4,2,5],10))
print(find_patterns([2,4,2,5,7],10))  #31-[7],[5,7],[4,5,7],[4,7]
print(find_patterns([1, 1, 1, 1],2))

- MKisunko March 16, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static  int findNonEmptySubsets(ArrayList<Integer> values,int sum)
	{
		Collections.sort(values);
		int count =0;
		
		for(int i=0;i<values.size();i++)
		{
			int minVal = values.get(i);
			for(int j=i;j<values.size();j++){
				if(values.get(j) + minVal <=sum)
				{
					// 2,4,5,6 = 2,4,6  2,5,6  2,6  2,4,5,6 (2^2) + 2 , 6
					if(j==i) count= count + 1;
					else
					count= count + 2 ^(j-i-1);
				}
				else{
					break;
				}
			}
		}
		return count;
		
	}

- Anonymous March 23, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static  int findNonEmptySubsets(ArrayList<Integer> values,int sum)
	{
		Collections.sort(values);
		int count =0;
		
		for(int i=0;i<values.size();i++)
		{
			int minVal = values.get(i);
			for(int j=i;j<values.size();j++){
				if(values.get(j) + minVal <=sum)
				{
					// 2,4,5,6 = 2,4,6  2,5,6  2,6  2,4,5,6 (2^2) + 2 , 6
					if(j==i) count= count + 1;
					else
					count= count + 2 ^(j-i-1);
				}
				else{
					break;
				}
			}
		}
		return count;
		
	}

- Anonymous March 23, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static int printAllSubsets(int [] arr, int k) {
        int count = 0;
        int n = arr.length;
        for (int i = 0; i < (1 << n); i++) {
            // System.out.print("subsets : ");
            int max = Integer.MIN_VALUE, min = Integer.MAX_VALUE;
            int minIdx = -1, maxIdx = -1;
            for (int j = 0; j < n; j++) {
                if ((i & (1 << j)) != 0) {
                    // System.out.print("\t" + arr[j]);
                    if (min > arr[j]) {
                        min = arr[j];
                        minIdx = j;
                    }
                    if(max < arr[j]) {
                        max = arr[j];
                        maxIdx = j;
                    }
                }
            }
            if (max != Integer.MIN_VALUE && min != Integer.MAX_VALUE && min + max <= k) {
                count++;
                System.out.println("min : " + min + "-" + minIdx + " max : " + max + "-" + minIdx);
            }
        }
        return count;
    }

- prateekgupta.3991 March 30, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

C++ solution N^2. The counter is incremented using the number of subsets that can be obtained from the interval (min, max) of every iteration.

#include <iostream>

int findSubsets(vector<int> &v, int k)
{
	int counter = 0;
	int n = v.size();

	std::sort(v.begin(), v.end());

	for (int i = 0; i < n; ++i)
    {
        for (int j = i; j < n; ++j)
        {
            if (v[i] + v[j] <= k)
            {
                if (i == j)
                    ++counter;
                else
                    counter += 1 << (j - i - 1);
            }
        }
    }

	return counter;
}


int main()
{
    vector<int> v = {2, 4, 5, 7};
    
    std::cout << findSubsets(v, 8) << std::endl;
}

- bertelli.lorenzo April 14, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is my simple dp solution. O(n^2) and O(1). The idea is to keep two pointers,
sumSoFar = max count you have encountered so far that meets the condition and by including current element.
result = final result updated after adding sumSoFar after iteration of every element.

public static int count(int[] inp,int N){
		if(inp==null || inp.length==0)
			return -1;
		
		Arrays.sort(inp);
		int sumSoFar = 0;
		int result = 0;
		
		for(int i=0;i<inp.length;i++){
			for(int j=i;j<inp.length;j++){
				if(i==j)
					sumSoFar=inp[i]+inp[j]<= N?1:0;
				else{
					int temp = (inp[i]+inp[j]<= N)?sumSoFar*2:sumSoFar;
					sumSoFar = temp;
				}
			}
			result+=sumSoFar;
		}
	
		return result;
	}

- mail2chandreshv May 05, 2019 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is my simple dp solution. O(n^2) and O(1). The idea is to keep two pointers,
sumSoFar = max count you have encountered so far that meets the condition and by including current element.
result = final result updated after adding sumSoFar after iteration of every element.

public static int count(int[] inp,int N){
		if(inp==null || inp.length==0)
			return -1;
		
		Arrays.sort(inp);
		int sumSoFar = 0;
		int result = 0;
		
		for(int i=0;i<inp.length;i++){
			for(int j=i;j<inp.length;j++){
				if(i==j)
					sumSoFar=inp[i]+inp[j]<= N?1:0;
				else{
					int temp = (inp[i]+inp[j]<= N)?sumSoFar*2:sumSoFar;
					sumSoFar = temp;
				}
			}
			result+=sumSoFar;
		}
	
		return result;
	}

- mail2chandreshv May 05, 2019 | Flag Reply


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