Adobe Interview Question
Software Engineer / Developersint sixthLargest(const int a[]) {
int max[6] = {INT_MIN};
for (int i = 0; i < N; ++i)
if (a[i] > max[0]) max[0] = a[i];
for (int x = 1; x < 6; ++x)
for (int i = 0; i < N; ++i)
if (a[i] > max[x] && a[i] < max[x - 1]) max[x] = a[i];
return max[5];
}
T: O(6n) = O(n)
S: O(6) = O(1)
The algorithm fails if the input has duplicates.
Ex: for the input 6,1,6,3,4,2,5 the algorithm returns 1
I think this works..
int sixthLargest(int[] a){
int[] max = {Integer.MIN_VALUE,Integer.MIN_VALUE,Integer.MIN_VALUE,
Integer.MIN_VALUE,Integer.MIN_VALUE,Integer.MIN_VALUE};
for(int i=0; i<a.length; i++){
int index=-1;
for(int j=0;j<max.length;j++){
if(a[i]>max[j]){
index = j;
break;
}
}
if(index!=-1){
//move all max[index] -> max[index+1]
for(int j=max.length-1; j>index; j--)
max[j]=max[j-1];
max[index]=a[i];
}
}
return max[5];
}
The space complexity is O(1) - constant
The time complexity is O(n)
1. Mark virtual boundary in a single dimensional with distance of 5 elements.
2. Sort these boundaries
3. Pick 5 elements using (i+2)th where i = 0 to 4
4. Sort these elements and find the pivot.
5. Apply partition using the above pivot.
6. Divide the problem and start again if necessary.
If k=r, then return m
If k<r, then return k thsmallest of the set L .(Bound time T7n/10)
If k>r, then return k-r thsmallest of the set R
Use Counting Sort.
It requires O(n) extra space with Linear time O(n). this sort also known as stable sort. Algorithm is in below.
for i =1 to K
do C[i] = 0;
for j = 1 to length[A]
do C[A[j]] = C[A[j]]+1
C[i] is now contains the number of elements equal to i
for i = 2 to k
do C[i] = C[i] + C[i-1];
C[i] now contains the number of elements less than or equal to i
for j = length[A] to 1
do B[C[A[j]]] = A[j]
C[A[j]] = C[A[j]]-1
here A is input array , B is output array and C is counter array
1)read first six numbers and create a min-heap of six elements....so that the root has minimum of the six.
2)now when you get a new number >root then pop the root and make root =new number
3) heapify the 6 element heap; takes O(log6) constant time
4)scan like this for whole array
5) the root gives the 6th greatest number
Overall complexity= O(nlog(6))==O(n)
code
#include<iostream>
#include<queue>
int main()
{
int a[]={10,23,44,2,1,4,56,23,56,75,35,73,354,1223,9};
priority_queue< int, greater<int> > min_h(a,a+5);
for(i=6;i<15;i++)
{
if(a[i]>min_h.top()) {min_h.pop(); min_h.push(a[i]);}
}
cout<<"6th greatest is "<<min_h.top();
return 0;
}
my approach
Read first 6 elements and keep them sorted in an array of size 6.
Now start reading from 7th element and see via binary search if the element is larger than greatest then ignore else place it in the array.
Iterate till end.
The loop invariant at any time maintains 6 s,mallest numbers in that array and return the last element of the temp array in the end
Space O(6) --- ie Constant space
time O(n)
A min_heap of size 6 suffices.
- Lord Darth Plagueis August 08, 2009