Input Array: {7,1,2,12,4,5,6,15,8,9}
Find the Kth largest element.
Solution one:
Algorithm:
1. Sort array
2. array[k] is the kth largest element
First sort the array:
There are many sorting techniques available. Most of the people use the bubble sort in the interviews as they feel it is easy. But most of the interviewers in the product based companies expect you to solve the code using other sorting techniques. As if you see the bubble sort the complexity is high
Better use selection sort or Quick Sort for solving this.
If you use quick you will get more impression as most of the candidates who appear for the interview won’t be able to write quicksort as it is little difficult to understand
Array After sorting: {1,2,4,5,6,7,8,9,12,15}
Now the Kth largest element is array[k]
Implementation:
Quick Sort:
public void kthlargestElement(int[] inputArr) {
if (inputArr == null || inputArr.length == 0) {
return;
}
length = inputArr.length;
int [] array = quickSort(inputArr,length,0, length - 1);
}
private int[] quickSort(int[] array, int lenght, int lowerIndex, int higherIndex) {
int i = lowerIndex;
int j = higherIndex;
int pivot = array[lowerIndex + (higherIndex - lowerIndex) / 2];
while (i <= j) {
while (array[i] < pivot) {
i++;
}
while (array[j] > pivot) {
j--;
}
if (i <= j) {
exchangeNumbers(i, j);
i++;
j--;
}
}
if (lowerIndex < j){
quickSort(lowerIndex, j);
}
if (i < higherIndex){
quickSort(i, higherIndex);
}
}
private void exchangeNumbers(int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}