CareerCup

classical quick select

use a min heap of size n. insert first n elements.
At subsequent elements(n+1, n+2,...) check heap root, if current element is greater than root, remove the root and insert current element. repeat.

finally heap root should have kth largest

step 1.sort the array in descending order
step 2. check size.
step 3. return value.(largest then return array[0], 2nd largest return array[1] if not equal to previous. else index++) .

class NtheLargest{

int findNthLargest(int [] input, int n){
int [] nLargestNumbers = new int[n];
//Assume that the first n elements are the largest n numbers
for(int i=0;i<n;i++){
nLargestNumbers[i] = input[i];
}
//Starting from the n+1 elements update the nLargestNumbers if we find any value greater
for(int j=n-1;j<input.lenght;j++){
for(k=0;k<nLargestNumbers.length;k++){
if(input[j] > nLargestNumbers[k]){
updateNLargest(nLargestNumbers,input[j]);
}
}
}

//Find the min in the nLargest numbers which will the nth Largest number in the array.
intNthLargestvalue = 0;
for(int v : nLargestNumbers){
if(v < intNthLargestvalue)
intNthLargestvalue = v;
}

return intNthLargestvalue;
}

updateNLargest(int [] array, int val){
for(int a:array){
if(val > a) {
tmp = array[i];
array[i] = val;
updateNLargest(array,tmp);
}
}
}
}

class NtheLargest{
	
	int findNthLargest(int [] input, int n){
		int [] nLargestNumbers = new int[n];
		//Assume that the first n elements are the largest n numbers
		for(int i=0;i<n;i++){
			nLargestNumbers[i] = input[i];
		}
		//Starting from the n+1 elements update the nLargestNumbers if we find any value greater		
		for(int j=n-1;j<input.lenght;j++){
			for(k=0;k<nLargestNumbers.length;k++){
				if(input[j] > nLargestNumbers[k]){
					updateNLargest(nLargestNumbers,input[j]);
				}
			}
		}
		
		//Find the min in the nLargest numbers which will the nth Largest number in the array.
		intNthLargestvalue = 0;
		for(int v : nLargestNumbers){
			if(v < intNthLargestvalue)
				intNthLargestvalue = v;
		}
		
		return intNthLargestvalue;
	}
	
	updateNLargest(int [] array, int val){
		for(int a:array){
			if(val > a) {
				tmp = array[i];
				array[i] = val;
				updateNLargest(array,tmp);
			}
		}
	}
}

Would this not be achievable faster using a BST.(std::map)
Getting an reverse iterator to the end and iterating for the set amount of time

def nth_largest(array, n):
	maxval = max(array)
	if n == 1:
		return maxval
	else:
		array.remove(maxval)
		return nth_largest(array, n - 1)

Quick Select

import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class NthLargestNumberInArray {
	public static void main(String[] args) {
		Integer[] numbers = {1,3,5,3,7,0,20,30,15,2,100};
		int position =9;
		System.out.println("Largest number on position "+position +" is: " +getNthLargestNumber(position, numbers));
	}
	
	public static int getNthLargestNumber(int position, Integer[] numbers){
		List<Integer> list = Arrays.asList(numbers);
		Collections.sort(list);
		for (int i=list.size()-1;i>=0;i--) {
			System.out.println("Position "+(list.size()-(i))+" = "+list.get(i));
		}
		return list.get(list.size()-position);
	}
}

---------------------

Output

Position 1 = 100
Position 2 = 30
Position 3 = 20
Position 4 = 15
Position 5 = 7
Position 6 = 5
Position 7 = 3
Position 8 = 3
Position 9 = 2
Position 10 = 1
Position 11 = 0
Larget number on position 9 is: 2

public void nthLaregstNumber(int[] numbers, int position) {
	System.out.println("Before sort: " + numbers);
	Arrays.sort(numbers);
	System.out.println("After sort: " + numbers);
	if (position < numbers.length) {
		System.out.println(numbers[(numbers.length - position)]);
	}
}

l = [1,4,2,6,8,9,5,67,67, 55]
sorted(set(l))[-2]  # For second largest
sorted(set(l))[-4]  # For fourth largest

Sort the array and give kth element.

Simple (reverse bubble sort)

function(arr,n){

document.write(" Array is "+ arr + "<p>");
	var  t;

	for(i= 0; i < n ; i++){

		for(j=i; j < arr.length; j++){
			if(arr[j] > arr[i]){
			
	
			document.write(arr[j] + " is greater than "+ arr[i]+" index is "+j+"\n <p>");
				
			t = arr[i];
			arr[i] = arr[j];
			arr[j] = t;
			}
		}

	}
return arr[n-1];

PS: Javascript code snippet

#include <iostream>
#include <queue>
#include <array>
using namespace std;


int nth_largest(vector<int> v, int pos) {
priority_queue<int> q;
int result;
for (auto i : v) {
q.emplace(i);
};
for (int j = 1; j <= pos; j++) {
result = q.top();
q.pop();
if (j == pos)
break;
}

return result;
}

int main()
{
vector<int> v = { 1, 8, 4, 5, 9, 7, 2, 10, 44, 55, 67 };
cout << "\t " << nth_largest(v, 2) << "\t" << nth_largest(v, 5) << endl;
return 0;
}

#include <iostream>
#include <queue>
#include <array>
using namespace std;


int nth_largest(vector<int> v, int pos) {
	priority_queue<int> q;
	int result;
	for (auto i : v) {
		q.emplace(i);
	};
	for (int j = 1; j <= pos; j++) {
		result = q.top();
		q.pop();
		if (j == pos)
			break;
	}

	return result;
}

int main()
{
	vector<int> v = { 1, 8, 4, 5, 9, 7, 2, 10, 44, 55, 67 };
	cout << "\t " << nth_largest(v, 2) << "\t" << nth_largest(v, 5) << endl;
    return 0;
}

public class NthLargest {
    public static void main(String[] args) {
        Integer[] array={1,8,4,5,9,7,2,10,55,67,3};
        findNthLargest(array, 5);
        //System.out.print(nthLargest);
    }
    static void findNthLargest(Integer[] array, int n){
        int counter=0;
        List<Integer> newList= new ArrayList(Arrays.asList(array));
      Collections.sort(newList);
        System.out.print("This is "+newList.get(newList.size()-n));
        //return newList.get(newList.size()-1);


    }

}

public class FindSecondLargestInArray {

public static void main(String[] args) {

int array[] = {1, 8, 4, 5, 9, 7, 2, 10, 44, 55, 67};

int largest = array[0];
int secondLargest = array[0];
int thirdLargest = array[0];
int fourthLargest = array[0];
int fifthLargest = array[0];

for(int i=0; i<array.length;i++){

if(array[i]>largest){
fifthLargest = fourthLargest;
fourthLargest = thirdLargest;
thirdLargest = secondLargest;
secondLargest = largest;
largest = array[i];
}
else if(array[i]>secondLargest){
secondLargest = array[i];
}
else if(array[i]>thirdLargest){
thirdLargest = array[i];
}
else if(array[i]>fourthLargest){
fourthLargest = array[i];
}
else if(array[i]>fifthLargest){
fifthLargest = array[i];
}
}
System.out.println("Second Largest Number in Array: "+secondLargest);
System.out.println("Fifth Largest Number in Array: "+fifthLargest);
}

}

public class FindSecondLargestInArray {

public static void main(String[] args) {

int array[] = {1, 8, 4, 5, 9, 7, 2, 10, 44, 55, 67};

int largest = array[0];
int secondLargest = array[0];
int thirdLargest = array[0];
int fourthLargest = array[0];
int fifthLargest = array[0];

for(int i=0; i<array.length;i++){

if(array[i]>largest){
fifthLargest = fourthLargest;
fourthLargest = thirdLargest;
thirdLargest = secondLargest;
secondLargest = largest;
largest = array[i];
}
else if(array[i]>secondLargest){
secondLargest = array[i];
}
else if(array[i]>thirdLargest){
thirdLargest = array[i];
}
else if(array[i]>fourthLargest){
fourthLargest = array[i];
}
else if(array[i]>fifthLargest){
fifthLargest = array[i];
}
}
System.out.println("Second Largest Number in Array: "+secondLargest);
System.out.println("Fifth Largest Number in Array: "+fifthLargest);
}

}

package org.test;

import java.util.Scanner;

//{1,2,4,5,7,8,9,10,44,55,67}
public class Test1 {
public static void main(String[] args) {

int n ;
int i,temp;

Scanner scanner= new Scanner(System.in);

System.out.println("Enter number of elements : ");
n= scanner.nextInt();
int a[] = new int[n];

System.out.println("Enter Elements :");

for(i = 0; i < n; i++)
{
a[i] = scanner.nextInt();
}
for(int k =0;k<n;k++)
{

for(int l=k+1;l<n;l++)
{
if(a[k]>a[l]){
temp =a[k];
a[k]=a[l];
a[l]=temp;
}
}
}
System.out.print("Ascending Order:");
for (int r = 0; r < n - 1; r++)
{
System.out.print(a[r] + ",");
}

int result =nth_largest(a, 2);;
System.out.println("Result is :"+result);


}

public static int nth_largest(int[] a , int pos)
{
return a[pos+1];
}
}

package org.test;

import java.util.Scanner;

//{1,2,4,5,7,8,9,10,44,55,67}
public class Test1 {
public static void main(String[] args) {

int n ;
int i,temp;

Scanner scanner= new Scanner(System.in);

System.out.println("Enter number of elements : ");
n= scanner.nextInt();
int a[] = new int[n];

System.out.println("Enter Elements :");

for(i = 0; i < n; i++)
{
a[i] = scanner.nextInt();
}
for(int k =0;k<n;k++)
{

for(int l=k+1;l<n;l++)
{
if(a[k]>a[l]){
temp =a[k];
a[k]=a[l];
a[l]=temp;
}
}
}
System.out.print("Ascending Order:");
for (int r = 0; r < n - 1; r++)
{
System.out.print(a[r] + ",");
}

int result =nth_largest(a, 2);;
System.out.println("Result is :"+result);


}

public static int nth_largest(int[] a , int pos)
{
return a[pos+1];
}
}

public static void main(String[] args) {

		int[] nums = { 3, 11, 55, 22, 33, 2 };
		System.out.println("kth largest ==> " + findKthLargest(nums, 4));
	}

	public static int findKthLargest(int[] nums, int k) {
		PriorityQueue<Integer> q = new PriorityQueue<Integer>(k);
		for (int i : nums) {
			q.offer(i);
			if (q.size() > k) {
				q.poll();
			}
		}
		return q.peek();
	}