Directi Interview Question
Software Engineer / DevelopersIf you are peddling your blog, at least give the right answer!
THe problem is to find the kth smallest element, not search for an element.
O(k) is possible and is a tough problem. Search for Young's tableau selection or something like that.
Or perhaps X+Y problem.
Research papers were written on this problem...
O(k log k) is easier I believe, and more suitable for an interview.
I think a min heap of size k should do. First insert the largest element in min heap. Now delete the smallest element from heap (i,j), insert its neighbours which are candidates for the smaller element (i-1,j) & (i, j-1). Keep doing this (deletion & insertion) k-1 times. The smallest element in the heap will be the kth largest.
we can start traversing the matrix from [0][0] and mark it 1 and maintain another array min[] of max size k.
look up at the [1][0] and [0][1] element.
the one whch is greater add it to min[] and mark the smaller one as 2.
now look at the next left and down elemnt of 2. add them to array min[].
find the smallest one from min and mark it 3 and look its left right and so on...
print the element marked k.
I thought of something similar. Except I used a Priority Queue instead of a min[] array. This should have a Time Complexity of O(k).
import java.util.*;
class Node
{
Node(int data,int x,int y)
{
this.data=data;
this.x=x;
this.y=y;
}
int data;
int x;
int y;
}
class SmallestFind
{
int a[][];
int k;
int kthValue;
SmallestFind(int a[][],int k)
{
this.a=a;
this.k=k;
findk();
}
PriorityQueue<Node> list = new PriorityQueue<Node>(1, new Comparator<Node>()
{
public int compare(Node n1, Node n2)
{
return (n1.data - n2.data);
}
}
);
void findk()
{
int x=0,y=0;
boolean passed[][]=new boolean[a.length][a.length];
list.add(new Node(a[x][y],x,y));
passed[x][y]=true;
while(k>0)
{
Node n=list.peek();
x=n.x; y=n.y; list.remove();
if((x+1)<a.length&&!passed[x+1][y])
{
list.add(new Node(a[x+1][y],x+1,y));
passed[x+1][y]=true;
}
if((y+1)<a[0].length&&!passed[x][y+1])
{
list.add(new Node(a[x][y+1],x,y+1));
passed[x][y+1]=true;
}
k--;
}
System.out.println(a[x][y]);
}
int getk()
{
return kthValue;
}
}
class KthSmallest
{
public static void main(String[] args)
{
int a[][]= {
{1,3,4,6},
{2,8,11,12},
{5,9,13,15},
{7,10,14,26},
};
int k=16;
SmallestFind s= new SmallestFind(a,k);
int v=s.getk();
}
}
import java.util.Scanner;
public class kthSmallest {
public static void main(String[] args) {
Scanner kbd=new Scanner(System.in);
System.out.println("Rows: ");
int r=kbd.nextInt();
System.out.println("Cols: ");
int c=kbd.nextInt();
int[] a[]=new int[r][c];
System.out.println("Elements: ");
for(int i=0;i<c;i++)
{
for(int j=0;j<r;j++)
{
a[j][i]=kbd.nextInt();
}
}
for(int i=0;i<c;i++)
{
for(int j=0;j<r;j++)
{
System.out.print(a[j][i]);
}
System.out.println("");
}
System.out.println("Enter Kth number to be found: ");
int k=kbd.nextInt();
int ctr=0;
for(int i=0;i<c;i++)
{
for(int j=0;j<r;j++)
{
if(ctr==(k-1))
{
System.out.println(a[j][i]);
}
ctr++;
}
}
}
}
Not sure if this is the least complexity code but the problem statement is satisfied.
This comment has been deleted.
- Administrator September 03, 2011