## Microsoft Interview Question Software Engineer / Developers

Comment hidden because of low score. Click to expand.
0
of 0 vote

It's basically find kth element of two sorted arrays when merged. In you case, find the mid point i.e. (m+n)/2 th element. (m,n being sizes of arrays). Worst case complexity would be just merging until we get (m+n)/2 elements i.e. O((m+n)/2). Am working on a better algo. has a complexity
O(m/2 + log2m).

Comment hidden because of low score. Click to expand.
0

You would need extra memory for this, won't you?

Comment hidden because of low score. Click to expand.
0
of 0 vote

Google for "dichotomic search". That is the most efficient algorithm.

Comment hidden because of low score. Click to expand.
0

I will check that out, thanks.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Check
geeksforgeeks.org/?p=2105

for O(log n) time algorithm.

Comment hidden because of low score. Click to expand.
0

Awesome solution and discussion.
Thanks

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#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;
}``````

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book walking you through every aspect of getting a job at a top tech company, while focuses on software engineering interviews.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.