## Google Interview Question

Software Engineer / Developers**Country:**United States

**Interview Type:**In-Person

int max_interval_ending = 0;

is it in correct place?

I think it should in the first loop

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 ?

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

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?

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.

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

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

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

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;

}

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

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

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

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

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

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

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

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

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.

- tskrgulja1 February 24, 2019