Google Interview Question
Java DevelopersCountry: United States
Interview Type: Phone Interview
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.
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;
}
bucker sort is O(n) and then search the integer array in reverse order, so it can be found in O(n)time.
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)
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).
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.
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.
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.
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)
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
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;
}
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.
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);
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.
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.
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)).
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).
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);
}
}
- Anonymous October 05, 2013