CareerCup

Use Randomized-Select to find nth max element in O(N) time where N=number of elements

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

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.

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;

}

Use heap to get nth element.. If array has m elements and we have to get nth largest.. then it will cost [m + n log m]. it will be better than sorting array approach [m log m] because n < m.

If we create min-heap of only n elements, then it will cost [n + m log n]

use selection sort and just make the enclosing loop n times is ok! and bubble sort in the same way…

@dheeraj123
Hi dheeraj ..Can you please tell did you apply adobe offcampus or adobe visited your college campus?
Thanks

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