Google Interview Question for Java Developers


Country: United States
Interview Type: Phone Interview




Comment hidden because of low score. Click to expand.
11
of 15 vote

// perform radix sort - O(n). now the array is sorted
// now, remove duplicates if you wish. and now perform the following algorithm
int i(0), j(n-1), ans(0);
while (i < j)
{
       if (a[i] + a[j] <= threshold ) {
                ans += (j-i+1);
                i++; 
       }
       else { j--; } 
}
return ans;

- Anonymous October 05, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
5
of 5 votes

I think instead of:

ans += (j-i+1);

it should be:

ans += (j-i);

- Yuval October 15, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

I think the radix sort is O (nlog(r)m) instead of O(n)

- Bob October 16, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Please see my solution below. I think I have a O(N) average case and O(1) space.

Thanks

- houseUrMusic October 18, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

radix sort is not O(N)

- houseUrMusic October 18, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think it should be:
ans += i;
because you are sure that for that j sum with all elements for indexes smaller than i will be smaller than the threshold. You`re adding the numbers between i and j and you do not know if summed up they are smaller than the threshold.

- pittbull November 10, 2013 | Flag
Comment hidden because of low score. Click to expand.
2
of 4 vote

To count the number of pairs in an efficient way, we need to have some ordering on the numbers.
Besides sorting, i think the most efficient way is to use binary search for each number to count the number of other valid integers such that the sum is <= threshold. So, I think O(n log n) is the best we can do.

- Miguel Oliveira October 04, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

In case sorted array we can get
''''''the number of pairs (x, y) of distinct elements with condition x + y <= Threshold''''''
in complexity O(n)

- PKT October 05, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static int getPairs(int[] integers,int threshold){
//n*(n-1)/2
int result=0;
int[] newIntegers=bucketSort(integers,threshold);
int pro=newIntegers[newIntegers.length-1];
int pre=newIntegers[newIntegers.length-1];
if(2*pro<=threshold){return newIntegers.length*(newIntegers.length-1)/2;}
else{
if(newIntegers.length-2<0){return -1;}
pre=newIntegers[newIntegers.length-2];
}

for(int i=newIntegers.length-2;i>0;i--){
if(pro+pre<=threshold){
return result=pre*(pre-1)/2+(pro-pre)*pre;
}
else{
if(pre==pro-1)
pro=pre;
else{
pre=newIntegers[i-1];
}
}

}
return result;

}

public static int[] bucketSort(int[] integers,int threshold){
int[] max=new int[threshold+1];
for(int i=0;i<integers.length;i++){
max[integers[i]]++;
}
int index=0;
for(int j=0;j<threshold;j++){
while(max[j]>0){
integers[index]=j;
max[j]--;
index++;
}
}
return integers;
}

- yy October 04, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

bucker sort is O(n) and then search the integer array in reverse order, so it can be found in O(n)time.

- yy October 04, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Doesn't work..
int[] integers = {4, 1, 5, 2, 3, -1, 6};
int threshold = 4;

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 5
at CareerCup.Theshold.bucketSort(Theshold.java:51)
at CareerCup.Theshold.getPairs(Theshold.java:9)
at CareerCup.Theshold.main(Theshold.java:71)

- Anonymous October 07, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Yes, it can be done in O(n).
First of all, let's sort our array in O(n) time using radix sort. Then, create two pointers i and j pointing to first and last elements of the sorted array. Let's iterate pointer i over our array, shifting pointer j to the left, maintaining a[i] + a[j] < threshold and incrementing result by j at each iteration. It is obvious that both pointers will pass entire array only once, so total complexity is still O(n).

- Flux October 04, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

radix sort runs in O(n*k), where k is the average key length. I think it's unlikely that this k is smaller (or considerably smaller) than log(n) in this case.

- Miguel Oliveira October 04, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

In this problem we operate with integers, so key length in radix sort is 4 (for int32) or 8 (for int64). It is definitely smaller than log(n) for n > 256. In practice, radix sort is faster than quicksort for n > 600 when sorting 8-byte integers.

- Flux October 04, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think bucket sort is the right approach. N is size of our array, k is the threshold. Now have 6 buckets - 0<=x<k/4 k/4<=x<k/2 x= k/2 k/2<x<3k/4 3k/4<=x<=k x>k
Keep adding elements into each bucket.
Total num of distict pairs would be

sizeof(0-k/4 bucket) * { sizeof(k/4-k/2 bucket) + sizeof(k/2-3k/4 bucket) + sizeof(3k/4-k bucket) } +
sizeof(k/4-k/2bucket) * sizeof(k/2-3k/4 bucket)

We need to be very careful about the bucket boundaries. And also, obviously this cannot be applied to floats/doubles or non integers.

- adi October 04, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

In case sorted array we can get 
''''''the number of pairs (x, y) of distinct elements with condition x + y <= Threshold''''''
in complexity O(n) 

Lets say we have a sorted array as follows:
1--3--3--4--6--7--8--9--12--13--15--17--70

Threshold is 12

Start traversing in array from end side with rightIteratorIndex (1 <= 3 <= 3 <= 4----------17 <= 70)
-Compare array element with Threshold
-If ArrayElement > Threshold then move to previous element
-If ArrayElement < Threshold then 
--Start traversing ArrayElement from left side with another leftIteratorIndex 
	until Array[leftIteratorIndex] + Array [rightIteratorIndex] < Threshold 
	also have a counter initialized to zero and increase counter.
        in case repeated element as previous move  leftIteratorIndex to one more left without updating counter

--When ever Array[leftIteratorIndex] + Array [rightIteratorIndex] > Threshold found
	move rightIteratorIndex to left ArrayElement , 
	update counter = counter + leftIteratorIndex
	and start traversing from 'Array[leftIteratorIndex]' for Array[leftIteratorIndex] + Array [rightIteratorIndex] < Threshold 
	for Array[leftIteratorIndex] + Array [rightIteratorIndex] > Threshold again move 'rightIteratorIndex' to left
	repeat above procedure until rightIteratorIndex != 0

--At last print counter which has been asked in qus.

- PKT October 05, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

It is possible that for every pair (x, y) in the array has the property of x + y < threshold.
Then the output size is of order n^2. Runtime complexity must be no smaller than that for the worse case.

- Anonymous October 10, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Given an arrray [1,2,3,4,5] and threshold of 200,

you should be printing out all pairs of numbers the array, that will be o(n^2) no matter if the array is sorted or not.

- anon October 11, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Can we use a form of quickselect here? Your pivot is the minimum number in the array, Put all numbers that your pivot value + vi is less then the threshold on the left of the pivot. Once that is done you can print the pairs of your pivot + all the numbers of the left of it. After, repeat the process with the left hand side of your pivot.

Average case O(N)

- houseUrMusic October 17, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

QuickSelect should work here. Your pivot is the minimum number in the array, Put all numbers that your pivot value + vi < threshold on the left of the pivot. Once that is done you can print the pairs of your pivot + all the numbers of the left of it. After, repeat the process with the left hand side of your pivot.

Average case O(N)
space O(1)

public static void swap(int [] arr, int i, int j)
    {
        int tempi = arr[i];
        arr[i] = arr[j];
        arr[j] = tempi;
    }
    
    public static int partitionThreshold(int [] arr, int leftInc, int rightExc, int threshold)
    {
        int front = leftInc;
        int pivot = minMaxIndex(arr, leftInc, rightExc, true);
        int pivotValue = arr[pivot];
        
        swap(arr, pivot, rightExc - 1);
        
        for (int i = leftInc; i < rightExc; i++)
        {
            if (arr[i] + pivotValue <= threshold)
            {
                swap(arr, front, i);
                front++;
            }
        }
        
        return front - 1;
    }
    
    public static int pairs(int [] arr, int leftInc, int rightExc, int threshold)
    {
        int newPivot = partitionThreshold(arr, leftInc, rightExc, threshold);
        int length = rightExc - leftInc;
        
        if (length <= 1)
            return 0;
        //if the max of the sub array * 2 < threshold we know there are no possible pairs
        if (minMaxIndex(arr, leftInc, rightExc, false) * 2 < threshold)
            return 0;
        
        return newPivot + partitionThreshold(arr, 0, newPivot, threshold);
    }
    
    
    public static void main(String [] args)
    {
        int [] arr = {1, 0, 3, 10, 4};
        int threshold = 5;
        System.out.println(pairs(arr, 0, arr.length, threshold));
    }

output:
5

- houseUrMusic October 18, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

forgot to post my minMaxIndex function..

public static int minMaxIndex(int [] arr, int leftInc, int rightExc, boolean findMin)
    {
        int minMax = leftInc;
        
        for (int i = leftInc + 1; i < rightExc; i++)
        {
            if (findMin)
                minMax = arr[i] < arr[minMax] ? i : minMax; 
            else
                minMax = arr[i] > arr[minMax] ? i : minMax;
        }
        
        return minMax;
    }

- houseUrMusic October 18, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Brilliant solution. Just a couple note,
1) I think you can optimize the code further by getting rid of minMaxIndex, instead keep an update of the the minimum on the left as you pivot. Ofcourse, to get the very first minimum you still have to iterate.
2) Thought on O(1) average case - the term average need to be explained. If the "threshold" is close to the range of values within the array, the O(1) average is true (and I think this is what you meant). If the threshold is really large compared to the range, it'll O(n^2). However, we have no info on which case is more likely.

- Emkay November 10, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Hi, please correct me if I'm wrong.

In my understand, your code executes partitionThreshold() twice. First in the range (0, n), second in the range (0, minimumIndex). In this case, shouldn't we only get the number of pairs with minimum (in the first partition) and the second-smallest element (in the second partition)?

If I am correct about that, we need to do a partition for every element until pivot index is 0. In this case, the average complexity is still O(n ^ 2), and the best case is O(n).

Below is my code, which is based on houseUrMusic's work:

private int getNumPairs(int[] array, int threshold) {
		if (array == null || array.length < 2) return 0;
		
		int maxIndex = 0;
		for (int i = 0; i < array.length; i++) {
			if (array[i] > array[maxIndex]) {
				maxIndex = i;
			}
		}
		if (array[maxIndex] * 2 < threshold) return 0;
		
		int count = 0;
		int newPivot = partitionThreshold(array, 0, array.length - 1, threshold);
		while (newPivot >= 1) {
			count += newPivot;
			newPivot = partitionThreshold(array, 0, newPivot - 1, threshold);
		}
		
		return count;
	}
	
	private int partitionThreshold(int[] array, int start, int end, int threshold) {
		if (start == end) return 0;
		
		int index = start;
		int minIndex = 0;
		for (int i = 0; i <= end; i++) {
			if (array[i] < array[minIndex]) {
				minIndex = i;
			}
		}
		int minimum = array[minIndex];
		swap(array, minIndex, end);
		
		for (int i = start; i <= end; i++) {
			if (array[i] + minimum <= threshold) {
				swap(array, index++, i);
			}
		}
		
		return index - 1;
	}
	
	private void swap(int[] array, int x, int y);

- clallenlin May 24, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

In case threshold is not big, another approach is this: You are not interested in the numbers bigger than threshold, so you can store occurences of all the integers lower than threshold and then for each i-th element check for all 0->threshold-A[i] if they are in the array or if they are not.

- Demo May 03, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

How could it be O(n) for the arrays with each element greater than a threshold?

For instance int[] a = new int[]{2, 3, 9, .....} and threshold = 0.
The number of pairs would be equal to n*(n-1)/2. You'd spend O(n^2) just iterating over the answer.

- Andrey October 04, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

The question asks for the *number* of pairs. In order to compute the number of pairs you don't necessarily need to iterate over each pair.

- cristian.botau October 04, 2013 | Flag
Comment hidden because of low score. Click to expand.
-2
of 2 vote

Yup. Create a Hashtable.

Say you have the following array ; [4, 1, 5, 2, 3] and threshold = 4

Now, you get 4 and create a Hashtable entry for it <4 , List<0>>.

Now, do the same for the rest :

<4, [0]>
<1, [0,1,2,3]>
<5, [-1]>
<2, [0,1,2]>
<3, [0,1]>

Now, iterate again. For 4, you need to get 0. Is zero present in the Hashtable ? Nope.
For 1, you need 0,1,2,3... you have 2 and 3. Display that or add it to the return List.

And continue like that and you will get the answer. Not exactly O(n) but certainly less than O(n2) or O(log(n)).

- AAT October 04, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

LOL.

- Anonymous October 04, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

First, cannot assume only positive integers present. This results that you need to check all the other elements.
Second, I believe it is a typo, it cannot be better than O(log n).

- maillist.danielyin October 04, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@AAT @maillist, isn't O(logn) better than O(n).

- karaamaati October 04, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

O(n * threshold) complexity and memory usage?
Good try, dude, but NO.

- Flux October 04, 2013 | Flag
Comment hidden because of low score. Click to expand.
-2
of 2 vote

my solution is log(n)
in the question they ask for the number of pairs, i did find the pairs though.

import java.util.*;
 
/**
 * Input - array of integers size N, integer Threshold.
 * Output - the pairs (x, y) of distinct elements with condition x + y <= Threshold.
 * Is that possible to implement is with O(n) ?
 */
class FindPairsUnderThreshold {
 
 
    public List<Map.Entry<Integer, Set<Integer>>> solve(Integer[] integers, Integer threshold) {
 
        // the complexity > O(n), sorted list is the key in this solution
        SortedSet<Integer> sortedSet = new TreeSet<Integer>();
 
        // first put values into the sorted set
        for (Integer number : integers) {
            sortedSet.add(number);
        }
 
        // then get the range from the head (smallest value) to the maximum value that satisfies the condition
        List<Map.Entry<Integer, Set<Integer>>> result = new ArrayList<Map.Entry<Integer, Set<Integer>>>();
        for (Integer number : integers) {
            // headSet is not inclusive, +1 is to make it include the exact sum
            int diff = threshold - number + 1;
            Set<Integer> integerIntegerSortedMap = sortedSet.headSet(diff);
 
            Map.Entry<Integer, Set<Integer>> integerSetPair = new AbstractMap.SimpleEntry<Integer, Set<Integer>>(number, integerIntegerSortedMap);
            result.add(integerSetPair);
        }
        return result;
    }
 
 
    public static void main(String[] args) {
        Integer[] integers = {4, 1, 5, 2, 3, -1, 6,};
        Integer threshold = 4;
        List<Map.Entry<Integer, Set<Integer>>> solution = new FindPairsUnderThreshold().solve(integers, threshold);
        for (Map.Entry<Integer, Set<Integer>> entry : solution) {
            Integer first = entry.getKey();
            for (Integer second : entry.getValue()) {
                System.out.print("(" + first + ", " + second + "), ");
            }
        }
        System.out.println(solution);
    }
 
}

- ??? October 04, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Why do you say O(log n) ?

for (Integer number : integers) {
     sortedSet.add(number);
}

this alone is O(n log n). each operation in a TreeSet costs O(log n).

With a bit enough threshold, there are n*(n-1)/2 pairs. You can't find the actual O(n^2) pairs in O(n) time.

- Miguel Oliveira October 04, 2013 | 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