Google Interview Question
SDE1sCountry: United States
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;
}
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
# 2) start with i at 0 and j at n-1
# 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))
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.
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.
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.
int main() {
// your code goes here
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;
}
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;
}
}
return total;
}
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))
curr_set.add(element)
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
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.
Sort the array, then use two pointers to count subsets.
- ak_domi March 13, 2017