Microsoft Interview Question Software Engineer / Developers
0of 0 votesFind the kth smallest element in a sorted array
Country: India
Interview Type: In-Person
if the array is like 1,2,2,2,3,5,5,7,7,7,7,10
i=1,c=1;
while(c<k && i<n)
{
if(a[i-1]!=a[i])
c++;
i++;
}
if(c==k)
small=a[i-1];
Assuming the problem is for a 2-D (r*c) array, here is my solution.
We maintain a min-heap which initially contains the first element of each column (total c elements). We also maintain the row,column index of each element along with the element.
struct arrayelem
{
int elem;
int rowIndex;
int colIndex;
};
// Initially the min-heal contains the first element of each column.
while (--k > 0)
{
topelem = min-heap->pop();
// The element int the next row in the same column as topelem is pushed in the heap
newRowIndex = ++topelem->rowIndex;
newColIndex = topelem->colIndex;
newelem = new arrayelem(array[newRowIndex ][newColIndex],
newRowIndex, newColIndex);
min-heap->push(newelem);
}
return newelem->elem;
No the array is a sorted linear array.
Just think of an array like 1 1 2 2 3 3 4.
In this 2rd smallest element (k=2) is 2 which is not a[2-1].
Use a K size max heap to keep tack of the k smallest elements. And if it needs to deal with the remove values, just input the distinguished values into heap.
Why you want to use heap here, as unnecessarily it will increase the time complexity to O(k log n). On the other hand, if you just see Sachin's solution, its simply O(k).
//nth smallest element in arrat arr[][] having r rows and c columns is
if (n<(r*c)
small=arr[(n%r)-1][(n/r)+1]
Assuming the problem is for a 2-D (r*c) array, here is my solution.
We maintain a min-heap which initially contains the first element of each column (total c elements). We also maintain the row,column index of each element along with the element.
struct arrayelem
{
int elem;
int rowIndex;
int colIndex;
};
// Initially the min-heal contains the first element of each column.
while (--k > 0)
{
topelem = min-heap->pop();
// The element int the next row in the same column as topelem is pushed in the heap
newelem = new arrayelem(array[++topelem->rowIndex][topelem->colIndex], ++topelem->rowIndex, topelem->colIndex);
min-heap->push(newelem);
}
return newelem->elem;
Assuming the problem is for a 2-D (r*c) array, here is my solution.
We maintain a min-heap which initially contains the first element of each column (total c elements). We also maintain the row,column index of each element along with the element.
struct arrayelem
{
int elem;
int rowIndex;
int colIndex;
};
// Initially the min-heal contains the first element of each column.
while (--k > 0)
{
topelem = min-heap->pop();
// The element int the next row in the same column as topelem is pushed in the heap
newRowIndex = ++topelem->rowIndex;
newColIndex = topelem->colIndex;
newelem = new arrayelem(array[newRowIndex ][newColIndex],
newRowIndex, newColIndex);
min-heap->push(newelem);
}
return newelem->elem;
class FindKthSmallestElementInSortedArray
{
public int[] array;
public FindKthSmallestElementInSortedArray()
{
array = new int[10];
for (int i = 0; i < array.Length; i++)
{
array[i] = 0;
}
array[0] = 1;
array[1] = 1;
array[2] = 1;
array[3] = 5;
array[4] = 5;
array[5] = 9;
array[6] = 20;
array[7] = 20;
array[8] = 50;
array[9] = 50;
}
public int Solve(int k)
{
if (k < 1 || k > array.Length)
{
return -1;
}
if (k == 1)
{
return array[0];
}
int cnt = 1;
for (int i = 0; i < array.Length - 1; i++)
{
if (array[i] != array[i + 1])
{
cnt++;
}
if (k == cnt)
{
return array[i + 1];
}
}
return -1;
}
}
class FindKthSmallestElementInSortedArray
{
public int[] array;
public FindKthSmallestElementInSortedArray()
{
array = new int[10];
for (int i = 0; i < array.Length; i++)
{
array[i] = 0;
}
array[0] = 1;
array[1] = 1;
array[2] = 1;
array[3] = 5;
array[4] = 5;
array[5] = 9;
array[6] = 20;
array[7] = 20;
array[8] = 50;
array[9] = 50;
}
public int Solve(int k)
{
if (k < 1 || k > array.Length)
{
return -1;
}
if (k == 1)
{
return array[0];
}
int cnt = 1;
for (int i = 0; i < array.Length - 1; i++)
{
if (array[i] != array[i + 1])
{
cnt++;
}
if (k == cnt)
{
return array[i + 1];
}
}
return -1;
}
}
class FindKthSmallestElementInSortedArray
{
public int[] array;
public FindKthSmallestElementInSortedArray()
{
array = new int[10];
for (int i = 0; i < array.Length; i++)
{
array[i] = 0;
}
array[0] = 1;
array[1] = 1;
array[2] = 1;
array[3] = 5;
array[4] = 5;
array[5] = 9;
array[6] = 20;
array[7] = 20;
array[8] = 50;
array[9] = 50;
}
public int Solve(int k)
{
if (k < 1 || k > array.Length)
{
return -1;
}
if (k == 1)
{
return array[0];
}
int cnt = 1;
for (int i = 0; i < array.Length - 1; i++)
{
if (array[i] != array[i + 1])
{
cnt++;
}
if (k == cnt)
{
return array[i + 1];
}
}
return -1;
}
}
class FindKthSmallestElementInSortedArray
{
public int[] array;
public FindKthSmallestElementInSortedArray()
{
array = new int[10];
for (int i = 0; i < array.Length; i++)
{
array[i] = 0;
}
array[0] = 1;
array[1] = 1;
array[2] = 1;
array[3] = 5;
array[4] = 5;
array[5] = 9;
array[6] = 20;
array[7] = 20;
array[8] = 50;
array[9] = 50;
}
public int Solve(int k)
{
if (k < 1 || k > array.Length)
{
return -1;
}
if (k == 1)
{
return array[0];
}
int cnt = 1;
for (int i = 0; i < array.Length - 1; i++)
{
if (array[i] != array[i + 1])
{
cnt++;
}
if (k == cnt)
{
return array[i + 1];
}
}
return -1;
}
}
class FindKthSmallestElementInSortedArray
{
public int[] array;
public FindKthSmallestElementInSortedArray()
{
array = new int[10];
for (int i = 0; i < array.Length; i++)
{
array[i] = 0;
}
array[0] = 1;
array[1] = 1;
array[2] = 1;
array[3] = 5;
array[4] = 5;
array[5] = 9;
array[6] = 20;
array[7] = 20;
array[8] = 50;
array[9] = 50;
}
public int Solve(int k)
{
if (k < 1 || k > array.Length)
{
return -1;
}
if (k == 1)
{
return array[0];
}
int cnt = 1;
for (int i = 0; i < array.Length - 1; i++)
{
if (array[i] != array[i + 1])
{
cnt++;
}
if (k == cnt)
{
return array[i + 1];
}
}
return -1;
}
}
int kthSmallestElementUnsorted(vector<int> V, int k)
{
V.erase(std::unique(V.begin(), V.end()), V.end());
priority_queue<int> pq(V.begin(), V.end());
for (unsigned int i=0; i<V.size()-k; i++)
pq.pop();
return pq.top();
}
int kthSmallestElementSorted(vector<int> V, int k)
{
V.erase(std::unique(V.begin(), V.end()), V.end());
return V[k-1];
}
struct element{
int data;
int row;
int col;
}
//assume a MinHeap class is available to contain element(s)
if (k==1) return a[0][0];
heap.insert(element(a[0][0], 0,0);
Element ele;
while (ele = heap.getElement());
{
k--; if (k ==0) return ele.data;
if (ele.row+1< m) {heap.insert(element(a[ele.row+1][ele.col], ele.row+1, ele.col));};
if (ele.col+1<n) {heap.insert(element(a[ele.row][ele.col+1], ele.row, ele.col+1));};
/*not cleanest of the code, but the idea will work*/
}
One can do it like a quicksort.
1. Take one arbitrary element (first one).
2. Those who are smaller go to its left, those who are bigger go to its right. Position of the element is say pos
3. If the pos=k, then we are done
4. If k<pos we repeat the reasoning starting from the left array.
5. Else repeat the reasoning with the right array.
Well there are multiple approaches.
Approach 1:
Take a max heap & insert first k unique elements[can be easily checked]. Heapify the heap.
Now, when a new element is smaller than the head of the heap,replace head with this new element heapify it. At the last, the head of the heap indicates kth smallest element if size of the heap is k else kth smallest element doesn't exist.
Time complexity: O(NlogK)
Space complexity: O(K)
Approach 2[A better approach]:
The elements may be duplicated right. So, check for unique elements by comparing with its previous elements & stop if unique variables found so far counts to k.
Time complexity: O(N)
Space complexity: O(1)
Approach 3[A better approach(may be)]:
A modified version of quick sort partition algorithm can also be used. But possibly it will lead to a worst case as the array is already sorted.
here two questions arise:
1. Does it work if the array contain duplicates?
2. Would it be better than my second approach?
Approach 4:
Here's an O(kLogN) solution:
Using a variation of Binary Search to find the last occurrence of a given value,
Get 1st value - O(1).
Search for last occurrence of this value O(logN), then look at next element to get 2nd value - O(1).
Repeat until kth value is found.
Another approach.
Probably this would be better i the number of duplicates are more.
1. Pick the first element.Find the last occurrence of this element.
2. Increment the pointer to pointer to next unique element. In this way, number of unique elements can be tracked[with the help of count].
3. Anytime if cunt==k, print corresponding element.
As said earlier, if the number of unique elements are duplicated manier times, this approach is efficient[Lets say all elements are duplicated]. However, if all elements are unique, then this will fall into the worst case of nlogn.
I am presenting this idea as it can be used as per the situation.
int findLastOcurrence(int *arr,int item ,int l,int h)
{
int mid;
if(l==h)
return arr[l]==item?l:INT_MAX;
if(l==h-1)
return (arr[h]==item?h:(arr[l]==item?l:INT_MAX));
mid=(l+h)>>1;
if(item>=arr[mid])
return findLastOcurrence(arr,item,mid,h);
else
return findLastOcurrence(arr,item,l,mid-1);
}
void find(int *arr,int size,int k)
{
int count=1,i,last;
for(i=0;i<size;count++)
{
if(count==k)
{
printf("%d ",arr[i]);
return;
}
last=findLastOcurrence(arr,arr[i],i,size-1);
i=last+1;
}
printf("Not found");
}
Complete code: ideone.com/LKtfl
u r kidding right, in a sorted array kth smallest elem would be arr[k-1](if its non-decreasing). Did MS really as this Qs.
array is row wise and column wise sorted... see the example
1 10 20 30
2 12 21 31
4 15 50 52
do you think 5th smallest is arr[5-1] element that is 2 ???
this is tough question unless you know the algorithm...
Qs. doesn't tell any such specifics. Let me think on this.
Edit:
This problem can always be converted into finding kth elem in n=N/s(distibution size) sorted arrays.
But here we will not be able to take advantage of column-wise sorting scenario.May be someone can put more light on it.
-1 for rdo.
A big slap to neo(the OP). First he does not mention the array is 2D and then questions rukawa's reasonable interpretation as if it is rukawa's fault.
Unfortunately, neo is not the only ONE to post questions like this. And wtf neo? You forgot to mention MATRIX? The "Array Revolutions"? LOL.
@rukawa: For 1D array, a version that might interest you: Perhaps the elements can be non-unique and the kth smallest is based on distinctness?
@anonymous
Obviously it was a very generic description so i made a few assumptions and just solved it with the idea that it was 2d array. If you want to use a distinct 1d array just use a hash table with a size count to return the kth element.
@anonymous: Give some work to your common sense. When i say array no one assumes its 2D so stop using ur extra brains and think for the solution.
Its a sorted linear array and i want the kth smallest element. If you have questions u have to clarify not assume. ofcourse kth smallest element means its distinct coz if its repeated then its not smallest.
That is exactly the wording from the interviewer. And there is a way to clarify not to talk nonsense out here.
Shut up again, neo. You can always add a paragraph in the ORIGINAL POST saying you asked for clarification and so and so is the definition of kth smallest you got.
Kth smallest is NOT well defined and needs clarification.
You made an assumption (when you wrote the question) that it assumes distinct. But that need not be the case, as the "nonsense" posts out here suggest.
Then you appear 3 days later (which is internet eternity!) and talk about "there is a way to clarify" as if you intended that all the while. BullShit.
It is good that you are posting questions with the intention of helping. But you have a negative effect if you post incomplete and ambiguous questions.
If there was a dialogue with the interviewer about clarifications, include that!
if an array is 0 0 0 0 0
any person will answer 2nd smallest as 0 ??? ... please grow up... if u read the post i clarified the first day ...
so just stop ur stinky posts... its not helping anyone
- Sachin June 02, 2012#include<stdio.h> int main() { int a[20]; int num,k,i,c; printf("Enter number of elements\n"); scanf("%d",&num); printf("Enter elements\n"); for(i=0;i<num;i++) { scanf("%d",&a[i]); } printf("Enter k\n"); scanf("%d",&k); c=1; for(i=1;i<num;i++) { if(c==k) { printf("kth Smallest with k=%d is %d",k,a[i-1]); break; } if(a[i]!=a[i-1]) c++; } scanf("%d",&i); return 0; }