|
178. Given a very large array of n integers.......
Microsoft Interview Questions and Answers
(Continued from previous question...)
178. Given a very large array of n integers.......
Question:
Given a very large array of n integers, find the kth largest value in the array efficiently. You may assume that k is much smaller than n.
e.g. the third largest (k=3) of [1,3,2,2] is 1, not 2.
maybe an answer:
int findKthLargestInArray(int arr[], int n, int k)
{
if(n < 1 || n < k)
return -1;
int lastCandidate = INT_MIN;
int candidate = INT_MIN;
int rank;
//first we find the largest number in array
for (int i = 0; i < n; i++)
{
if(arr[i] > candidate)
candidate = arr[i];
}
//lastCandidate is the largest number
lastCandidate = candidate;
if(k == 0)
return lastCandidate;
bool found = false;
for (rank = 1; rank <= k; rank++)
{
found = false;
candidate = INT_MIN;
for (int i = 0; i < n; i++)
{
if(arr[i] > candidate && arr[i] < lastCandidate)
{
found = true;
candidate = arr[i];
}
}
//now lastCandidate is the rankth largest number
lastCandidate = candidate;
}
if(found)
return lastCandidate;
return -1;
}
(Continued on next question...)
Other Interview Questions
| 