## Google Interview Question for Software Engineer / Developers

• 1
of 1 vote

Country: United States
Interview Type: In-Person

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

This can be done in O(n log n)

Comment hidden because of low score. Click to expand.
2
of 2 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++;
}
}``````

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;
}``````

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

shouldn't this line be inside the first loop?

``int max_interval_ending = 0;``

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

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

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

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 ?

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

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;
}

}``````

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

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 ,[5,7],[4,5,7],[4,7]) that is equal to 27.
Any idea on why?

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

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)

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.

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

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

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;
}``````

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

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

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

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

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

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

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

were you allowed to use extra n^2 space?

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;
}

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 = new ArrayList<>();
for (int i = index + 1; i < nums.length; i++) {
if (nums[index] + nums[i] <= k) {
} else {
while (subset.size() > 2) {
subset.remove(1);
}
}
}
}
}``````

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) {
return;
}

if (s2.length() == 0) {
return;
}

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

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

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

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

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

ok

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) {
} else if (subset.size() > 1) {
}

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

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

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``

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:
result_set.append([vector_element]+element)
else:
if vector_element < element[-1]:
result_set.append([element]+[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)+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-,[5,7],[4,5,7],[4,7]
print(find_patterns([1, 1, 1, 1],2))``````

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;

}``````

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;

}``````

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;
}``````

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;
}``````

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;
}``````

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;
}``````

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

Assuming array not sorted, with duplicates. Time complexity: O(n**2), Space Complexity: O(1) + input

``````def count_subsets(arr: [int], k: int) -> int:
count = 0
for i in range(len(arr)): O(n)
if arr[i] <= k:
count += 1
j = i+1
min = arr[i]
max = arr[i]
while j < len(arr):  # O(n)
if arr[j] < min:
min = arr[j]
if arr[j] > max:
max = arr[j]
if min + max <= k:
count += 1
j += 1
return count``````

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

Idea is to calculate the number of subsets at including the ith element.

``````int ans = 0
for(i = 0; i < n; ++i) {
for(j = i; j >= 0; --j) {
int m = arr[i];
int M = arr[j];
if(m + M <= K) {
ans += pow(2, j + 1) - 1;
break;
}
}
}``````

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.