Facebook Interview Question
Software EngineersCountry: United States
Interview Type: Phone Interview
I feel this is a better solution:
-----------------------------------
Time Complexity = O(klogk)
Space Complexity = O(k)
-----------------------------------
Logic:
1. Create a minHeap of size k. (This heap stores the k largest elements in the array)
2. Initialize the heap with first k elements.
3. For the next elements,
verify if the next element is greater than heap.peek().
if it is greater remove the top and add this element to the heap.
otherwise continue.
4. After iterating through all the elements in the array return heap.peek()
-----------------------------------
public class Main {
public static void main(String[] args) {
int[] array = {5, 3, 9, 1};
int k = 4;
System.out.println(k+"th largest number is "+kthLargest(array,k));
}
public static int kthLargest(int[] array, int k){
PriorityQueue<Integer> queue = new PriorityQueue<Integer>(k+1);
if(array.length < k+1){
System.out.println("Array size is smaller than k.");
return 0;
}
for(int i=0;i<k+1;i++){
queue.add(array[i]);
}
for(int i=k; i<array.length; i++){
if(array[i] > queue.peek()){
queue.remove();
queue.add(array[i]);
}
}
return queue.peek();
}
}
Quick Select I found this implementation
public int findKthLargest(int[] nums, int k)
{
if (k < 1 || nums == null)
return 0;
return getKth(nums.length - k +1, nums, 0, nums.length - 1);
}
public int getKth(int k, int[] nums, int start, int end)
{
int pivot = nums[end];
int left = start;
int right = end;
while (true)
{
while (nums[left] < pivot && left < right)
left++;
while (nums[right] >= pivot && right > left)
right--;
if (left == right)
break;
swap(nums, left, right);
}
swap(nums, left, end);
if (k == left + 1)
return pivot;
else if (k < left + 1)
return getKth(k, nums, start, left - 1);
else
return getKth(k, nums, left + 1, end);
}
public void swap(int[] nums, int n1, int n2)
{
int tmp = nums[n1];
nums[n1] = nums[n2];
nums[n2] = tmp;
}
Create a min heap of first k elements vin the array. This heap represents the k largest elements in the array and kth largest will be at the root. Now process each element not in the heap from the array. If the element is smaller than root ignore it. Else add it to the heap. Finally return the root.
public static int kthBiggest(int[] a, int k) {
return kthSmallest(a, a.length-1-k, 0, a.length-1);
}
private static int kthSmallest(int[] a, int k, int from, int to) {
// modified quicksort
// error case
if (k>to || k<from) {
System.out.println("Oops, maybe we should throw an exception");
}
// base case
if (k==from && k==to) {
return a[k];
}
int pivot = a[from];
int left = from+1;
int right = to;
while(left<=right){
while (left<= to && a[left] < pivot){
left++;
}
while (right >= from && a[right] > pivot){
right--;
}
if (left<right){
//swap
int temp = a[right];
a[right] = a[left];
a[left] = temp;
}
}
//swap pivot with right which should point to the last smaller element
a[from] = a[right];
a[right] = pivot;
if (right == k) {
return pivot;
} else if (right > k) {
// continue on left side
return kthSmallest(a, k, from, right-1);
} else {
// continue on right side
return kthSmallest(a, k, right+1, to);
}
}
Best runtime of O(NlogK)
import java.util.Arrays;
import java.util.PriorityQueue;
public class KthLargest {
public static void main(String[] args) {
int[] array = {5, 3, 9, 1};
System.out.println(kthLargest(array, 2));
System.out.println(kthLargestEfficient(array, 2));
}
// O(NlogN)
public static int kthLargest(int[] array, int k) {
Arrays.sort(array);
return array[array.length - 1 - k];
}
// O(Nlogk)
public static int kthLargestEfficient(int[] array, int k) {
PriorityQueue<Integer> pq = new PriorityQueue<>();
for(int i=0; i<k+1; i++) {
pq.add(array[i]);
}
for(int i=k+1; i<array.length; i++) {
pq.add(array[i]);
pq.poll();
}
int kthLargest = pq.peek();
return kthLargest;
}
}
Presumably array length 'n' is very large relative to history depth 'k'.
The naive answer then is sorting on 'n' and taking the k'th index. That would be O(n) space and O(nlogn) time, both which are 'very large' because 'n' is 'very large'.
Use of a heap (or even insertion sort) of 'k' elements iterating without modifying the array gives the main improvement. So the final answer should be O(k) space complexity. Time complexity must still run over the entire N array so O(nlogk) for heap implementation or O(nk) for insertion sort.
The heap is clearly better here but given that n >> k, even the simple sliding insertion sort on k elements is still better than any answer involving sorting on n.
#include <stdio.h>
int arr[]={5,9,8,7,6,10,2,1};
int larg[10];
int main()
{
int dat;
int i,j,k=0,l;
scanf("%d",&dat);
for(i=0;i<dat;i++)
larg[i]=0;
for(i=0;arr[i]!=0x00;i++)
{
for(j=0;arr[j]!=0x00;j++)
{
if(arr[i]>=arr[j])
{
for(k=0;k<dat;k++)
{
if(arr[i]==larg[k])
{
k=dat;
}
else
{
if(arr[i]>larg[k])
{
for(l=dat-1;l>=k;l--)
{
larg[l+1]=larg[l];
}
larg[k]=arr[i];
k=dat;
}
}
}
}
}
}
printf("%d \n",larg[dat-1]);
}
for(int i=0;i<array.length;i++)
{
for(int j=i;j<array.length;j++){
if(array[i]<array[j])
{
int temp=array[i];
array[i]=arr[j];
array[j]=temp;
}
}
}
for(int i=0;i<arr.length;i++)
System.out.println(arr[i]);
System.out.println("Enter the k value to print kth largest value");
k=sc.nextInt();
System.out.println("Kth largest element is:"+arr[k-1]);
}
public static int kthBiggest(int[] a, int k) {
return kthSmallest(a, a.length-1-k, 0, a.length-1);
}
private static int kthSmallest(int[] a, int k, int from, int to) {
// modified quicksort
// error case
if (k>to || k<from) {
System.out.println("Oops, maybe we should throw an exception");
}
// base case
if (k==from && k==to) {
return a[k];
}
int pivot = a[from];
int left = from+1;
int right = to;
while(left<=right){
while (left<= to && a[left] < pivot){
left++;
}
while (right >= from && a[right] > pivot){
right--;
}
if (left<right){
//swap
int temp = a[right];
a[right] = a[left];
a[left] = temp;
}
}
//swap pivot with right which should point to the last smaller element
a[from] = a[right];
a[right] = pivot;
if (right == k) {
return pivot;
} else if (right > k) {
// continue on left side
return kthSmallest(a, k, from, right-1);
} else {
// continue on right side
return kthSmallest(a, k, right+1, to);
}
}
private static int getKthMax(int[] arr, int k) {
if (arr == null || arr.length == 0 || k <= 0) {
return -1;
}
int n = arr.length;
if (k > n) {
return -1;
}
PriorityQueue<Integer> q = new PriorityQueue<Integer>(Collections.reverseOrder());
for (int i = 0; i < n; i++) {
q.add(arr[i]);
}
for (int i = 0; i < k-1; i++) {
q.remove();
}
return q.peek();
}
I think this problem depends a lot on the range of the expected values and how large do we expect K to be.
We do know K <= N, where N is the length of the input array, otherwise it wouldn't make sense.
I've designed the class interface thinking that this could also be solved with a running stream of values.
My assumptions are that K is much smaller than N (very small!).
I've got a running time of O(N * K) and extra space of O(K). I could also improve the solution using a Heap of max size K but again, assuming K is very small, that would be extra complexity for little added value.
Here's my Python solution:
You can either call the static method to solve it in batch or keep pushing and querying the values (provided K is a constant).
class KthLargest(object):
def __init__(self, k):
self._largest = [None] * (k + 1)
def get_kth(self):
return self._largest[0]
def push(self, value):
if self._largest[0] and self._largest[0] > value:
return
i = 0
while i < len(self._largest) - 1 and self._largest[i + 1] < value:
self._largest[i] = self._largest[i + 1]
i += 1
self._largest[i] = value
@staticmethod
def kth_largest(iterable, k):
largest = KthLargest(k)
for value in iterable:
largest.push(value)
return largest.get_kth()
Runtime O(nlogn)
import java.util.Arrays;
public class KthLargest {
public static void main(String[] args) {
int[] array = {5, 3, 9, 1};
System.out.println(kthLargest(array, 3));
}
public static int kthLargest(int[] array, int k) {
Arrays.sort(array);
return array[array.length - 1 - k];
}
}
function insertSortedList(list, value, startIndex, endIndex) {
var i;
//if empty, insert it in the list
if(!list.length) {
list.push(value);
return;
}
//initialize start and end indecies
startIndex = startIndex || 0;
if(endIndex === undefined) endIndex = list.length -1;
//if start and end are the same, then insert it before or after
// don't insert if duplicate
if(startIndex === endIndex) {
if(value < list[startIndex]) {
//insert before
list.splice(startIndex, 0, value);
} else if( value > list[startIndex]) {
//insert after
list.splice(startIndex + 1, 0, value);
}
return;
}
var middle = Math.floor((startIndex + endIndex) / 2);
if(value === list[middle]) {
return;
}
if(value < list[middle]) {
//insert to bottom half
insertSortedList(list, value, startIndex, middle);
console.log("insert in the bottom half");
} else {
insertSortedList(list, value, middle + 1, endIndex);
console.log("insert in the top half");
}
}
function selectKLargest(array, k) {
var largestSet = [];
var i;
for( i = 0; i < array.length; i++) {
console.log(largestSet);
//fill the list
if(largestSet.length < k) {
insertSortedList(largestSet, array[i]);
} else {
if(array[i] > largestSet[0]) {
//remove the smallest entry, insert array[i]
largestSet.splice(0, 1);
insertSortedList(largestSet, array[i]);
}
}
}
console.log(largestSet[0]);
}
selectKLargest([5,3,9,1], 4);
This solution takes O(nlog(k)) time and O(k) space. I think it is the simplest coding solution, at least for Java:
public int largestValue(int[] array, int k){
PriorityQueue<Integer> heap = new PriorityQueue<>();
for(int i = 0; i < array.length; i++){
heap.add(array[i]);
if(heap.size() > k)
heap.poll();
}
return heap.peek();
}
Time Complexity = O(klogk)
Space Complexity = O(k)
Logic:
1. Create a minHeap of size k. (This heap stores the k largest elements in the array)
2. Initialize the heap with first k elements.
3. For the next elements,
verify if the next element is greater than heap.peek().
if it is greater remove the top and add this element to the heap.
otherwise continue.
4. After iterating through all the elements in the array return heap.peek()
public class Main {
public static void main(String[] args) {
int[] array = {5, 3, 9, 1};
int k = 4;
System.out.println(k+"th largest number is "+kthLargest(array,k));
}
public static int kthLargest(int[] array, int k){
PriorityQueue<Integer> queue = new PriorityQueue<Integer>(k+1);
if(array.length < k+1){
System.out.println("Array size is smaller than k.");
return 0;
}
for(int i=0;i<k+1;i++){
queue.add(array[i]);
}
for(int i=k; i<array.length; i++){
if(array[i] > queue.peek()){
queue.remove();
queue.add(array[i]);
}
}
return queue.peek();
}
}
create a MaxHeap (binomial heap) of size n. Iterate over array and insert every element into heap. Extract Max k times, kth element should be kth largest.
- guilhebl May 10, 2016Time: O(N log N) space : O(N).