Interview Question
Developer Program EngineersCountry: India
Interview Type: Phone Interview
It has O(nlgn) in worst case, if your array is already sorted and heapify process takes O(lgn) time for n elements
If the heap is of size 3, then the heapify takes log(3), which is constant. So the algorithm is O(n).
order statistics with rank n-3.
can be solved in O(n) time.
However, is it any better than O(3n)? Maintaining a buffer to hold three elements sounds better because we don't have to participate and call recursively which is pretty expensive by itself.
Use QuickSelect, modification of quicksort. I have written algorithm to find kth smallest number, you can modify it to find 3rd largest number.
seesharpconcepts.blogspot.in/2012/05/linear-solution-finding-kth-smallest.html
This algo may look like nonlinear but in practical it works in O(n).
This is my approach. I believe Complexity is O(n). Correct me if I'm wrong.
public class ThirdLargestEle {
static int thirdLargEle(int[] nums) throws Exception {
if(nums.length < 3) {
throw new Exception("This array is too small to obtain the 3rd LargestElement");
}
int[] topThree = new int[3];
topThree[0] = nums[0];
topThree[1] = nums[1];
topThree[2] = nums[2];
for(int i = 3 ; i < nums.length ; i++) {
int min = Math.min(Math.min(topThree[0],topThree[1]), topThree[2]);
if(nums[i] > min ) {
if(topThree[0] == min) {
topThree[0] = nums[i];
} else if(topThree[1] == min) {
topThree[1] = nums[i];
} else if(topThree[2] == min) {
topThree[2] = nums[i];
}
}
}
return Math.min(Math.min(topThree[0],topThree[1]), topThree[2]);
}
public static void main(String[] args) throws Exception {
int[] a = {100,100,3};
System.out.println(thirdLargEle(a));
}
}
below is my code [implemented order statistics] which has linear (0(n)) complexity
public class RandomizedSelect {
public static void main(String[] args) {
int[] A = {7,4,11,3,19,25,21,20,43,1,12,2,9};
// for 3rd largest one
System.out.println(randomizedSelect(A,0,A.length-1,A.length -1-3));
}
public static int randomizedSelect(int[] A, int p, int r, int i){
if(p == r)
return A[p];
int q = randomizedPartition(A,p,r);
int k = q - p + 1;
if(i == k)
return A[q];
else if(i < k)
return randomizedSelect(A,p,q-1,i);
else
return randomizedSelect(A, q+1, r, i-k);
}
public static int randomizedPartition(int[] input, int left, int right){
int randPivot = left + (int)Math.random()*((right-left)+1);
swap(input, right,randPivot);
return partition(input,left,right);
}
public static int partition(int[] input, int left, int right){
int pivot = input[right];
int i = left -1;
for(int j =left ; j < right; j++){
if(input[j] <= pivot){
i++;
swap(input,i,j);
}
}
swap(input,i+1,right);
return i+1;
}
public static void swap(int[] input,int p, int q){
int tmp = input[p];
input[p] = input[q];
input[q] = tmp;
}
what about tournament tree. it's kind of like merge sort, but we dont need to actually sort, just select the largest. first round we will cut half of the players. 2nd round 1/4....
the last run, say nth run, will have to compare the largest two. so the result should be in n - 1 run and there we have 4 element to compare. so its n complexity.
using buffer but one loop
private void thirdhighest() {
// how to find the Third largest Element in an array of integers..?
//I suggested a logic using a buffer that can hold three elements..
//But it is of O(3n) complexity..Can someone give a better algorithm
int [] arr = new int []{11,1,10,9,8,7,6,5,4,2,3};
int[] temp = new int[3];
temp[0]=arr[0];
temp[1]=arr[1];
temp[2]=arr[2];
for (int i = 3; i < arr.length; i++) {
if(temp[0]>temp[1]){
int a = temp[0];
temp[0]=temp[1];
temp[1]=a;
}
if(temp[1]>temp[2]){
int a = temp[2];
temp[2]=temp[1];
temp[1]=a;
}
if(temp[0]>temp[1]){
int a = temp[0];
temp[0]=temp[1];
temp[1]=a;
}
if(temp[0]<arr[i])
temp[0]=arr[i];
}
System.out.println("temp[0]="+temp[0]+"=temp[1]="+temp[1]+"=temp[2]="+temp[2]);
System.out.println("third highest:::"+temp[0]);
}
Order statistic will take nlogn to build the tree, Even modified quick sort that does recursive partition takes nlogn.
I dont think any thing better than 3buffer for this problem is possible.
No, there are order statistics algorithms for finding a number with any chosen rank in O(n).
eugene.yarovoi :
Sure but there are no sublinear algorithms for finding the smallest k numbers in O(n). I think the original question is more about minimizing the number of comparisons rather than big-Oh complexity
@ dr.house: I'm not claiming any sublinear algorithms.
My response was a response to the claim that order statistics will take O(nlogn). I'm saying no, we can do order statistics in O(n) with the right algorithm.
I do agree that 3-buffer will be a good solution. If we only need the third largest, using quickselect or the like is overkill unless we want our algorithm to be able to generalize efficiently to finding other order statistics.
why not using min heap of size 3
- siva November 22, 2012parse the array, when ever the element in the array is greater than the root of min heap, replace the root with new element and run min heapify on root
at the end, root will contain the third largest number
this can also be modified to find kth largest element where k = 1 to n