Google Interview Question Software Engineer / Developers
Country: United States
Interview Type: In-Person
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;
}
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?
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)
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))
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;
}
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;
}
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;
}
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;
}
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;
}
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;
}
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
This can be done in O(n log n)
- Arash February 25, 2019