## Google Interview Question for SDE1s

• 2

Country: United States

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

Sort the array, then use two pointers to count subsets.

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

``````public static int countSubSet(int[] nums, int target){
if(nums.length==0)
return 0;
Arrays.sort(nums);
int subsets=0;
int start=0, end=nums.length-1;

while(start<=end){
if(2*nums[start]>=target)
return subsets;
if(nums[start]+nums[end]<target){
if(start==end)
subsets=subsets+1;
else
subsets= subsets+(int)Math.pow(2,end-start-1);

start++;
}
else
end--;
}
return subsets;
}``````

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

For example, if target will be equal 2*Max + 1 (Max - is a maximum element in the array) we have to print all possible subsets N * (N + 1) / 2
So, solution can't be faster than O(N*N) ?

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

the idea is to learn from past subsets, if you increase the lower bound, the upper bound may stay the same or decrease... maybe be neatly expressed in a DP recursion as well, here the hands-on solution in O(n*log(n)) due to sort, O(n) if nums is passed already sorted (and nums.sort() is removed)

``````#
# 1) sort the array
# 3) repeat as long as nums[i] < target
# 4) try to find an upper bound which is smaller or equal than last j
# 5) add j - i + 1 or at least 1
# 6) increment goto 3)
#
# example with sorted input for simplicity:
# nums: [1, 4, 5, 7, 11, 14, 20]
# 1..11: 5 subsets: {1}, {1,4}, {1,4,5}, {1,4,5,7}, {1,4,5,7,11}
# 4..7:  3 subsets: {4}, {4,5}, {4,5,7}
# 5..7:  2 subsets: {5}, {5,7}
# 7:     1 subset: {7}
# 11:    1 subset: {11}
# total: 5+3+2+1+1 = 12 subsets
#
def countSubSet(nums, target):
nums.sort()
count = 0
j =  len(nums) - 1
i = 0
while nums[i] < target:
while nums[i] + nums[j] >= target: j -= 1
count += max(j - i + 1, 1)
i += 1
return count

print(countSubSet([1, 4, 5, 7, 11, 14, 20], 14))``````

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

If I got this correct then this is basically a combination problem. If we simplify this Lets say I give you 10 numbers then you have to generate possible combination of two numbers [ Because I think max(subset) and min(subset) is the length of subsets] that will sum to a value less than 10.

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

If i understand this correct we need to generate K-subsets here. Given a number lets say 10 then we need to generate all possible combination of its subsets. for eg {1},{1,2},{5,6,7,9} having length 1,2,4 etc etc. So basically this boils down to combination problem where we need to find all possible 2 element combination of Target numbers and choose only those numbers whose sum is less than Target Value.

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

If i understand this correct we need to generate K-subsets here. Given a number lets say 10 then we need to generate all possible combination of its subsets. for eg {1},{1,2},{5,6,7,9} having length 1,2,4 etc etc. So basically this boils down to combination problem where we need to find all possible 2 element combination of Target numbers and choose only those numbers whose sum is less than Target Value.

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

dd

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

int a[] = {1,4,5,7,11,14,20};
Arrays.sort(a);
int target = 14;

int i =0;
int j = a.length -1;
int count =0;

while(a[i] < target) {
while (a[i] + a[j] >= target) {
j --;
}
count += Math.max(j - i + 1, 1);
i ++;
}
System.out.println(count);

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

``````int main() {
int n;
vector<int> v;
int x;
cin>>n;
for(int i=0;i<n;i++) {
cin>>x;
v.push_back(x);
}
cin>>x;
sort(v.begin(), v.end());
int i = 0;
int j = n-1;
while(v[i]+v[j] > x) j--;
int count = 0;
while(v[i] <= x - v[j]) i++;
cout<<i<<" "<<j<<endl;
count += ((pow(2, i)-1) * (pow(2, j-i+1)));

for(;i<n;i++) {
if(v[i] <x) count++;
}

cout<<count<<endl;
return 0;
}``````

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

``````int countSubSet( const vector<int>& nums , int target ){
int total = 0;
sort( nums.begin() , nums.end() );

for( int i = 0 ; i < nums.size(); ++i ){
auto it = lower_bound( nums.begin() , nums.end() , target - nums[i] );
if( it - nums.begin() > i )
continue;

int j = ( nums[i] + *it == target ) ? it - nums.begin() - 1 : it - nums.begin();
while( j >= 0 ){
total += pow( 2 , max( 0 , i - j - 1 ) );
--j;
}
}
}``````

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

Here a solution that doesn't sort the array.

``````def countSubset(arr, target):
r = []
count = 0
for element in arr:  # O(n)
if element < target:
temp_r = []
for r_set in r:  # O(m)
curr_set = r_set.copy() # O(len(r_set))
sorted_set = sorted(curr_set) # O(len(curr_set) * log len(curr_set))
max = sorted_set[-1]
min = sorted_set[0]
if max + min < target:
temp_r.append(set(sorted_set))
count += 1
temp_r.append({element})
count += 1
r.extend(temp_r) # O(len(temp_r))
return count``````

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

The solution is wrong since it ll fail for case

1 1 1 3 and target = 4.

The reason is that we 'll be missing {1, 1} while using 2 pointers. The correct approch should involve fixing each number as part of subset.

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

We don't need to sort the array! First we find the minimum by one pass. If 2*minimum is not less than the target, there is no such subset and the count is zero. Other wise, we do another pass and count all elements that minimum plus such element is less than the target, say we get N. Since any subset with the above property must be a subset of such elements, and vice versa, the answer is 2^N. So the solution is O(n)!

Note that there no repeated elements, otherwise we would need to sort.

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

The answer does not have the form 2^N for some N, so this is blatantly wrong.

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.