Adobe Interview Question
Software Engineer / DevelopersThe algorithm is based on slight modification to quick sort & is of time complexity log(n).
1. select an element r randomly from the array.
2. partition the array into 2 halves, left & right such that left have elements less than or equal to the selected element r and right has elements of higher value than r.
3. now count the number of elements in left.
4. if n = size(left) return element r.
5. else if n < size (left) repeat the process on left array and ignore the right array elements.
6 else if n > size (left), ignore left array & randomly selected element r and repeat the process on right array to fine the element of order [n - size(left) - 1]. (-1 for randomly selected element).
how can this be O(logn)? partitioning and arranging the elements so that left is less than r and right is greater than r, would on an average be of O(n). so the total complexity would be O(n.logn)
I think the solution is really nice and the complexity is O(n).
Please point out if you find any mistakes.
Since the number to choosen is random number about which we have to partition the array.On an average we can assume that,choosing this random number leads to two arrays with half no. of elements every time.
And for worst case we can assume that we only found the nth element when we had only a single element in the array.
Suppose that there are k elements initially,
Initially,
k elements -----to partition we need k comparisions which leads to 2 arrays of k/2 elements.
k+k/2 (k/2 comparisions in the array of k/2 elements)
k+k/2+k/4 (k/4 comparisions for array of k/4 elements)
k+k/2+k/4+k/8+........k/2(power i) ,where k=2(power i) since we assumed that we found nth element when we had only single element in array
k(1+1/2+1/4+1/8+.....1/2(power i))
k(1-1/2(power i)/(1-1/2)
2k(2(power i)-1)/2(power i)
2k(2(power i)-1)/k
2(k-1)
O(k)
generally O(n),where n is size of problem
using quicksort for finding nth largest value.
Here is a working c code
#include "stdio.h"
#include<conio.h>
using namespace std;
int quicksort ( int *, int, int, int ) ;
int split ( int*, int, int ) ;
int main( )
{
int arr[10] = { 11, 2, 9, 13, 57, 25, 17, 1, 90, 3 } ;
int i ;
int nth = 5; //finding 5th largest value
int num = quicksort ( arr, 0, 9, nth-1 ) ;
printf ( "%d\t", num ) ;
getch();
return 0;
}
int quicksort ( int a[ ], int lower, int upper, int nth)
{
int i ;
if ( upper > lower && i !=nth )
{
i = split ( a, lower, upper ) ;
quicksort ( a, lower, i - 1, nth ) ;
quicksort ( a, i + 1, upper,nth ) ;
}
return a[nth];
}
int split ( int a[ ], int lower, int upper )
{
int i, p, q, t ;
p = lower + 1 ;
q = upper ;
i = a[lower] ;
while ( q >= p )
{
while ( a[p] < i )
p++ ;
while ( a[q] > i )
q-- ;
if ( q > p )
{
t = a[p] ;
a[p] = a[q] ;
a[q] = t ;
}
}
t = a[lower] ;
a[lower] = a[q] ;
a[q] = t ;
return q ;
}
The solution that comes instantly to the mind is sort the array and then traverse the sorted array ignoring repetion of elements in the array while counting.
Not the most optimal solution as sorting would require nlog(n) time. The optimal solution is in log(n) time.
int FindNthMaximum(int arr[],size_t size,int n)
{
if(arr == NULL || size == 0 || n < 1 || n > size) return -1;
int max = 0,tmp=0;
int *a = new int[size];
memcpy(a,arr,size*sizeof(int));
for(int i = 0;i<n;++i)
{
max = i;
for(int j=i+1;j<size;++j)
{
if(a[j] > a[max] ) max = j;
}
if(i + 1 == n)
{
tmp = a[max];
delete []a;
a = NULL;
return tmp;
}
tmp = a[i];
a[i] = a[max];
a[max] = tmp;
}
return 0;
}
This is code for quickselect ( similar technique used by quicksort )
void swap( int *input, int a, int b)
{
int temp;
temp = input[a];
input[a] = input[b];
input[b] = temp;
}
int GetPivot(int *input, int beg, int end )
{
int pivot;
int middle = (beg + end)/2;
if ( input[beg] <= input[end] && input[beg] >= input[middle] )
pivot = beg;
else if (input[end] <= input[beg] && input[beg] >= input[middle])
pivot = end;
else
pivot = middle;
swap(input, pivot, end ); /* put pivot at end */
return input[end];
}
int QuickSelect ( int *input, int beg, int end, int k )
{
// 1 choose the pivot by median of 3
int pivot = GetPivot( input, beg, end );
swap(input, pivot, end ); /* put pivot at end */
// 2 move elements
int i = beg;
int j = end – 1;
while( 1 )
{
while( input[i] <= pivot )
i++; // move right until meet some one > pivot
while( input[j] >= pivot)
j--; // move left until meet some one < pivot
if ( i < j )
swap(input, i, j );
else
break;
}
swap(input, i, end ); // put pivot back
// 3 select recursively
if ( end – i > k - 1 )
return ( input, i + 1, end, k ); // the kth is in the second half
else if ( end – i == k – 1)
return input[i]; // the kth is the one
else
return (input, beg, i – 1, k -1 –(end – i ) ); // the kth is in the first half
}
findNthMax(a[],n)
{
if(a.length<n)
{
throw new Exception("No Sufficient Data");
}else
{
Queue q;
for(int i =0; i<a.length;i++)
{
if(a[i] >= q.peek(q.front))
{
if(q.isEmpty() || q.size() ! = n)
{
q.insert(a[i]);
}else{
q.delete();
q.insert(a[i]);
}
}
}
SOP("nth largest element:::" + q.delete());
}
}
Its O(n)
package arrays;
/**
* Returns the kth largest element in the array of elements
* Uses partitioning (order statistics) technique to arrive
* at kth element.
*
* Usage: Kth largest element returned will be the element at index
* k-1;
*
*/
public class KthLargest {
public static void main(String[] args) {
int a[] = { 1, 6, 2, 9, 13, 5, 3, 8 };
int k = 7;
int index = findKth(a,0, a.length -1, k);
System.out.println(k+ "th largest element: "+ a[index]);
}
private static int findKth(int[] a, int low, int high, int k) {
int partitionIndex = partition(a,low,high);
if( k == partitionIndex - low) {
return partitionIndex;
} else if(k < partitionIndex){
return findKth(a, low, partitionIndex-1, k);
} else if(k> partitionIndex) {
return findKth(a, partitionIndex+1, high, k-(partitionIndex+1));
}
return partitionIndex;
}
private static int partition(int[] a, int low, int high) {
if(low<high){
int pIndex = Math.abs((low + high) / 2);
int pivot = a[pIndex];
swap(a, pIndex, high);
int i = low;
int j = high - 1;
while (i <= j) {
while (i < high && a[i] <= pivot) {
i++;
}
while (j >= low && a[j] >= pivot) {
j--;
}
if (i < j) {
swap(a, i, j);
i++;
j--;
}
}
swap(a, i, high);
return i;
} else {
return low;
}
}
private static void swap(int[] a, int i, int pIndex) {
int t = a[i];
a[i] = a[pIndex];
a[pIndex] = t;
}
}
Use Randomized-Select to find nth max element in O(N) time where N=number of elements
- Sriram August 06, 2011