## Google Interview Question for Java Developers

• 4

Country: United States
Interview Type: Phone Interview

Comment hidden because of low score. Click to expand.
10
of 14 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;``````

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

``ans += (j-i+1);``

it should be:

``ans += (j-i);``

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

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

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

Thanks

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

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

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.

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.

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)

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

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

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

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

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)

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).

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

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.

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.

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.

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.``````

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.

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.

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)

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

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

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

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

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.

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

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);``````

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.

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.

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

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.

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)).

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

LOL.

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

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).

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

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

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

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

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) {
}

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

Map.Entry<Integer, Set<Integer>> integerSetPair = new AbstractMap.SimpleEntry<Integer, Set<Integer>>(number, integerIntegerSortedMap);
}
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);
}

}``````

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

Why do you say O(log n) ?

``````for (Integer number : integers) {
}``````

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.

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.