Amazon Interview Question Software Engineer / Developers
please check my code:
#include<stdio.h>
int findKthsmallest(int a[],int m,int b[],int n,int k)
{
int i=0,j=0,ti=0,tj=0,I=0,J=0,M=m,N=n;
while(1)
{
ti = (int)((double)m/(m+n) * (k-1));
tj = (k-1)-ti;
i = I+ti;
j= J+tj;
//printf(" i=%d j=%d\n",i,j);
if(j>0 && j<N && i<M && a[i]>b[j-1] && a[i]<b[j])
return a[i];
if(i>0 && i<M && j<N && b[j]>a[i-1] && b[j]<a[i])
return b[j];
if(j==0 && i<M && a[i]<b[j])
return a[i];
if(i==0 && j<N && b[j]<a[i])
return b[j];
if(j==N && a[i]>b[j-1])
return a[i];
if(i==M && b[j]>a[i-1])
return b[j];
if(i<M && j<N)
{
if(a[i]<b[j])
{
k=k-ti-1;
m=m-ti-1;
I=i+1;
}
else
{
k=k-tj-1;
n=n-tj-1;
J=j+1;
}
}
else if(i>=M)
{
k=k-tj-1;
n=n-tj-1;
J=j+1;
}
else
{
k=k-ti-1;
m=m-ti-1;
I=i+1;
}
}
}
int main()
{
int a[]={1,2,3};
int b[]={4};
int m=3,n=1,k=3;
printf("%d",findKthsmallest(a,m,b,n,k));
return 0;
}
Hi can you please explain your code?? I wanted to crack this code for a long time now. and found one solution.. Please comments your code.. It would be helpful..
Thanks.
Idea is like this since both the arrays may not be of same length lets divide (k-1) smallest elements proportionally in both the arrays:
let i point the array A by
i=m/(m+n) * (k-1) [since we have to divide k-1 elements among two]
j=(k-1) - i
then try to insert A[i] between B[j-1] and B[j] if three are not in asc order try to insert B[j] between A[i-1] and A[i]
If any one of the above satisfies we found kth smallest element else,
check which one is smallest among A[i] and B[j] its logical that if A[i] is smallest then we can A[0] to A[i] for the next iteration and
k becomes k-i-1 also m becomes m-i-1 i.e now we have only m-i-1+n elements out of which we have to find k-i-1th smallest thus the iteration goes on until we
find our kth smallest element.
Consider 2 arrays
A={5,7,9,20}; length of A: m=4
B={10,12,21,27,35,50}; length of B: n=6
let K be 4
i=4/10*3=1; A[1]=7;
j=3-1=2; B[2]=21;
B[1]=12 A[1]=7 B[2]=21 [not in asc order]
A[0]=5 B[2]=21 A[1]=7 [not in asc order]
so now,
k=k-i-1 =4-1-1=2
m=m-i-1=4-1-1=2
n=6
A={9,20}; length of A: m=2
B={10,12,21,27,35,50}; length of B: n=6
i=2/8*1=0; A[0]=9;
j=1-0=1; B[1]=12;
(acutally A[-1] is just for understanding)
B[0]=10 A[0]=9 B[1]=12 [not in asc order]
A[-1]=-INF B[1]=12 A[0]=9 [not in asc order]
now,
k=k-i-1=2-0-1=1;
m=m-i-1=2-0-1=1;
n=6;
A={20}; length of A: m=1
B={10,12,21,27,35,50}; length of B: n=6
i=1/7*0=0; A[0]=20;
j=0-0=0; B[0]=10;
(acutally A[-1] and B[-1] are just for understanding)
B[-1]=-INF A[0]=20 B[0]=10 [not in asc order]
A[-1]=-INF B[0]=10 A[0]=20 [in asc order]
We got the Kth(4th) smallest element which is 10.
Hope this code seems to be short...
import java.io.DataInputStream;
import java.io.IOException;
public class FindSmallElement {
public static void main(String arg[]) throws NumberFormatException, IOException{
int A[]={2,5,8,10};
int B[]={1,4,6,8};
int i=0;
int j=0;
int count=0;
DataInputStream dis=new DataInputStream(System.in);
Integer val=Integer.parseInt(dis.readLine());
if(count<=A.length+B.length){
while((count<val && (i==A.length||j==B.length))|| i+j<val){
if(A[i]<B[j]){
i++;
}
else if(B[j]<A[i]){
j++;
}
else{
i++;
j++;
}
count++;
System.out.println("I:"+i+" J:"+j+" Count:"+count);
}
}
else{
System.out.println("Count entered is invalid");
}
if(val>count)
System.out.println("Invalid Value found Array with duplicates"+B[i]+A[j]);
else{
if(i<j) System.out.println(val+" smallest element is "+B[i]);
else System.out.println(val+" smallest element is "+A[j]);
}
}
}
1. constant (assuming the combined array is also sorted.)
2. n-1
3. 3n/2
please correct if i am wrong.
Final array is not already "combined". If you want to do it in O(1) then dont forget to add the cost of combining arrays.
i would say:
1. O(k) this is very intuitive, just stop as soon you find kth element while combining arrays. There must be a logarithmic time algo for this problem i am sure.
2. (n-1)
3. I would take only 'n'. Since there is no restriction on space, I would travel entire list once and keep storing elements in nodes in an array. After I know size of list (say n), merely (n/2)th element of array is the median.
truekool, how much time did u get to solve these questions? did they ask for exact runnable code? or just psuedo code?
- gurusamy June 16, 2011