CareerCup

int kthLargest(int[] list, int k) {
		int left = 0;
		int right = list.length-1;
		while(true) {
			int pivIndex = (left+right)/2;
			int newPiv = partition(list, left, right, pivIndex);
			if(newPiv == k)
				return list[newPiv];
			else if(newPiv < k) {
				left = newPiv+1;
			}
			else {
				right = newPiv-1;
			}
		}
	}
	private static int partition(int[] list, int left, int right, int pivot) {
		int pivValue = list[pivot];
		swap(list, pivot, right);   //put pivot value on the end
		int storePos = left;
		for(int i=left; i<right; i++) {
			if(list[i] < pivValue) {
				swap(list, i, storePos);
				storePos++;
			}
		}
		swap(list, storePos, right);
		return storePos;
	}
	
	private static void swap(int[] list, int a, int b) {
		int temp = list[a];
		list[a] = list[b];
		list[b] = temp;

}

selection algorithm - O(n)

Maintain a min heap of size N. Go through the Array and load the elements in the heap. When the heap becomes full remove the min element and add this new element.

Once u have traverses through the entire array,you are left with the 7 largest element in the heap with the topmost being the minimum of the lot or the 7th largest in the array.

COmplexity : n + timeforheapcreation(N) . O(n)

Solution described above unnecessarily uses pointers (it doesnt even use the 'first' pointer).
Here's my take at this:
1) In response to this question, "communicate with your interviewer": Ask him just one follow up question: Ask him/her the range of numbers stored in the array. Suppose that range is (min,max). No number larger than max will be stored. Now..
2) Note that there is no constraint on space. Allocate a new array B of size (max-min).
3) Walk through the original array (say A) once, so O(n), and store every data value A[i] in new array B at B[A[i]-max+min] ... basically B is now a 'direct map'.
4) Now eturn B[max-N].

Solution described above unnecessarily uses pointers (it doesnt even use the 'first' pointer).
Here's my take at this:
1) In response to this question, "communicate with your interviewer": Ask him just one follow up question: Ask him/her the range of numbers stored in the array. Suppose that range is (min,max). No number larger than max will be stored. Now..
2) Note that there is no constraint on space. Allocate a new array B of size (max-min).
3) Walk through the original array (say A) once, so O(n), and store every data value A[i] in new array B at B[A[i]-max+min] ... basically B is now a 'direct map'.
4) Now, traverse B "backwards" from position corresponding to max and count nonzero data. Return data B[max-<Nth nonzero data>]. Note that this is just the second traversal, so only adds a constant multiple of 2 to the O(n) complexity => algo is O(2n) => O(n).

Done.

what about partition function....can it be used using A[n-1] as pivot?....I guess it should do...Logic behind is the partition function of quick implemented as mean sort...will that do?

sorry the above method is wrong....

We need to have a complexity of O(n) where 'n' is no of element in array and 'N' are the largest integers to be found.
Have a sorted linked list of size N. i.e first element of linked list is the Nth largest no and last element is the largest no. Have two pinters to linked list which are head and tail.
Traverse the array and compare each element(say X) with the head of linked list(i.e Nth largest). If X is greater than head, then delete the head and insert X(maintain sorted linked list).
Since maintaining the sorted linked list is easy O(N), the overall comlexity of algorithm is O(n).

i dnt know the code for that program . can any one provide code pleaz. i need full code n detailed code.

Have a queue of size 'N' and traverse the array from the beginning.
Have a variable i to contain first element value.
When you find a number bigger than i, enqueue it.
At the end of the traversal, u will have the queue filled with N biggest elements!

The answer has already been posted. It is definitely "Selection algorithm". It doesn't use sorting instead just the partition method described in quick sort (refer CLRS). No need to use pointers. You are complicating the solution too much for such a simple problem!

The following method sort & return Nth largest element. I accpets 2 parms (1. Array, Nth highest Element to be found)

Public Integer findNthLargestElement(Array numberList, Integer nthElement){
//Sort the incoming array
numberList = numberList.sort();
If (numberList.size() < nthElement){
// throw exception / error and return.
}
for (int i=numberList.size(); i<nthElement ; i--){
if (i==nthElement){
System.out.println("Nth Largest Array element is " + i);
return i;
}}}

Keep in Mind Whenever we wants to find the kth or nth largest or top k elements or use Min Heap because logic is simple behind this. when we build the min heap in each iteration we remove the min from the min-heap so call to heapify operation its overall complexity is O(n*logn) but gives us desired result suppose k=3 means u wants to find out 3rd largest inn unsorted array of 100 elements

1st solution is to sort the array which is also a solution but not sounds good to interviewer in this scenario he wanst to hear from us about Heap DS
2nd solution is to build min heap in (nlogn) keep removing min element which is nothing but minimum element in heap until k=0 when when k=0 we have 3rd largest element at top & that's what we are looking for ..soon i will post solution here using min heap.

Keep in Mind Whenever we wants to find the kth or nth largest or top k elements or use Min Heap because logic is simple behind this. when we build the min heap in each iteration we remove the min from the min-heap so call to heapify operation its overall complexity is O(n*logn) but gives us desired result suppose k=3 means u wants to find out 3rd largest inn unsorted array of 100 elements

1st solution is to sort the array which is also a solution but not sounds good to interviewer in this scenario he wanst to hear from us about Heap DS
2nd solution is to build min heap in (nlogn) keep removing min element which is nothing but minimum element in heap until k=0 when when k=0 we have 3rd largest element at top & that's what we are looking for ..soon i will post solution here using min heap.

Keep in Mind Whenever we wants to find the kth or nth largest or top k elements or use Min Heap because logic is simple behind this. when we build the min heap in each iteration we remove the min from the min-heap so call to heapify operation its overall complexity is O(n*logn) but gives us desired result suppose k=3 means u wants to find out 3rd largest inn unsorted array of 100 elements

1st solution is to sort the array which is also a solution but not sounds good to interviewer in this scenario he wanst to hear from us about Heap DS
2nd solution is to build min heap in (nlogn) keep removing min element which is nothing but minimum element in heap until k=0 when when k=0 we have 3rd largest element at top & that's what we are looking for ..soon i will post solution here using min heap.

The simplest solution is to use the RANDOMIZED_SELECT algorithm. The amortized average case running time of this algorithm is O(n). This algorithm uses PARTITION function similar to Quick Sort.

This is the simplest solution and it needs NO sorting.

Read through the list and create a binary search tree. ->O(n)
Start a pointer from root to keep going right of the tree to find the maximum.Start another pointer after n hops. When the first pointer reaches the last node(no more left nodes) the 2nd pointers position will give nth largest

Hiral, creating binary tree is not O(n), it is O(log n), you just counted the traversal in the array that is O(n) so the solution is not O(n)

See this : cse(dot)ust(dot)hk/~dekai/271/notes/L05/L05(dot)pdf . It explains kth smallest/largest elem in O(n) and is not a randomized algo

And this link also for other methods with non linear complexity : geeksforgeeks(dot)org/archives/2392

Also, someone above posted that selection algo (as used in selection sort)is O(n). But I guess it will be O(kn). Please clarify, if someone has idea.

A solution similar to that of UWCSE ; with less comparisons but more copy operations

private static int  partition(int[] array, int left, int right)
        {

            int pivot = array[left];//choose first element as pivot
            int i = left + 1;//i points to the left most elemnt > pivot
            for (int j = i; j <= right; j++)
            {
                if (array[j] < pivot)   //if  array[j] >= pivot do nothing          
                    utils.swap(array, j, i++);   //two things swap i&j and increment i             

            }
            utils.swap(array, left, i - 1);
            return i-1;//position of pivot
        }
public static int FindNthItem(int[] array, int n)
        {
            if (array.Length == 0) return -1;
            
            int left=0;
            int right = array.Length - 1;
            int i = partition(array, left, right)+1;
            if (i == n) return array[i - 1];
            if (i > n)
            {
                // destarray=Array.CreateInstance( typeof(System.Int32), i-1 );
                int[] destarray =(int[]) Array.CreateInstance(typeof(int), i - 1);
                Array.Copy(array, destarray, i - 1);
                return FindNthItem(destarray, n);
            }
            else
            {
                int[] destarray = (int[]) Array.CreateInstance(typeof(int), array.Length - i);
                Array.Copy(array, i, destarray, 0, array.Length - i);
                return FindNthItem(destarray, n-i);

            }            
        }

public static int quickSelection(int[] array, int k) {
		return quickSelectionT(array, 0, array.length - 1, k);
	}

	private static int quickSelectionT(int[] array, int left, int right, int k) {
		if (left == right) {
			return array[left];
		}
		int pivotNewIndex = partition(array, left, right, right - 1);
		int pivotDist = pivotNewIndex - left + 1;
		if (pivotDist == k) {
			return array[k];
		} else if (k < pivotDist) {
			return quickSelectionT(array, left, pivotNewIndex - 1, k);
		} else {
			return quickSelectionT(array, pivotNewIndex + 1, right, k
					- pivotDist);
		}
	}

	private static int partition(int[] array, int left, int right, int pivot) {
		int pivotValue = array[pivot];
		swap(array, pivot, right);// move it to the right place
		int index = left;
		for (int i = left; i < right - 1; i++) {
			if (array[i] < pivotValue) {
				swap(array, i, index);
				index++;
			}
		}
		swap(array, right, index);
		return index;
	}

Guys dont copy paste from other site, codes can be identified easily from which side you are copying it

Find k-th largest element

int findKth(int [] elements, int k, int start, int end)
{
	if(elements == NULL || start <0|| start > end || k <0|| k> end) throw 1;
	int pivot = elements[k];
	// swap first and pivot
	int temp = elements[start];
	elements[start]=pivot;
	elements[k]=temp;
	int i=start;
	int j=end;
	while (i <j)
	{
		while(elements[i]>pivot && i <j) i++;
		while(elements[j]<=pivot  && j >i) j--;
		if(i<j)
		{
			temp=elements[i];
			elements[i]=elements[j];
			elements[j]=temp;
		}
	}
	elements[0]=elements[i];
	elements[i]=pivot;
	
	if(i > k)
	{
		return findKth(elements, k, start, i);
	}
	else if (i < k)
	{
		return findKth(elements, k,i, end);
	}
	else
		return pivot;
}

You mean Nth largest element in a sorted array starting from the smallest element. I do not believe that it is doable for an unsorted array.

If you know the length of the array, try to find the Length-N+1 item by going through the nodes from the beginning

If you do not know the length of the array, use two pointers to transverse the array. One goes first, the other goes N steps later than the first one. When the first one reaches the end, the second one is the Nth largest.