Google Interview Question for SDE1s


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.

- ak_domi March 13, 2017 | Flag Reply
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;       
}

- deep March 14, 2017 | Flag Reply
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) ?

- dmitry.labutin March 13, 2017 | Flag Reply
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
# 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))

- Chris March 13, 2017 | Flag Reply
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.

- Rohit March 14, 2017 | Flag Reply
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.

- SO90 March 14, 2017 | Flag Reply
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.

- testuser8190 March 14, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

dd

- Anonymous March 17, 2017 | Flag Reply
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);

- Srikanth Raj March 18, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Janani March 24, 2017 | Flag Reply
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;
		}
	}
	return total;
}

- anonymous March 25, 2017 | Flag Reply
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))
                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

- nicolarusso March 01, 2020 | Flag Reply
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.

- Rajat.nitp July 21, 2020 | Flag Reply
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.

- Maryam March 14, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Evg March 01, 2020 | Flag


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More