## Microsoft Interview Question for Software Engineer / Developers

Country: India
Interview Type: In-Person

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

to find first and second minimum we need 4 comparison
consider 5 4 1 2 3
(5,4) ,(4,1) ,(4,2), (4,3)
for third element
compare (1,2)->swap
compare(2,3)->swap

6 comparison

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

correct me if i am wrong

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

consider 5 4 6 7 8
I think need 6 comparison to find the first and second minimum .....

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

``````dear the answer is correct
but it goes lke...i will xplain it with ur xmple..

comp 1.   1st and 2  nd elent 2nd is smaller
comp. 2     smaller with 3rd ....3rd is more smaller i.e 1
so order till now is 1st then 2nd then 3rd
even if 3rd was larger than 2nd we would be havng our 3rd largest element......
we dnt need to consider order f 1st nd hence some of our comparisons are saved

comp 3.       smalller with 4    if 4 is smaller it comes to 3rd position else position of 3 that is going to be place of median remains same..

comp. 4   smaller with 5th elemnt ...nd if 5 th is smaller

then means would be 3rd element
minimus 4 comparison aswer``````

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

Yes it would be 6 comparison ...

Comment hidden because of low score. Click to expand.
1
of 3 vote

We would need 4.
For a list of size n, we would need at least n-1 comparisons.
Every element has to be compared at least once, nothing better than this can exist.
If we use quick sort until we end up with pivot as the median element the complexity on average would be O(n).

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

The question is to find minimum comparisons not complexity in terms of array size. With your quicksort approach if we continuously end-up with bad pivot we need (n-1)+(n-2)+(n-3)...+(n-n/2) comparisons.

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

we can do it in 4 comparision

if a[0]>a[2] swap them
if a[4]>a[2] swap them
if a[1]>a[2] swap them
if a[3]>a[2] swap them

a[2] is the median

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

We always need atleast 3*n/4 comparisions at best.

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

Consider the example 5,4,3,2,1.
Your approach fails. It gives 5 as median.

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

Thnx for pointing that out.

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

Doesn't it depend on order of input? It can vary accordingly.

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

are comparisons the only operation allowed ?
what if we first add all the elements and divide by the no. of elements,
and then compare it with all the elements to find the one closest to the absolute value
e.g.

``````// dummy code

int median = -1, diff = -1;
int mid = ( arr[0]+arr[1]+arr[2]+arr[3]+arr[4] )/5;

median = 0;
diff = abs(mid - arr[0]);
for(int i =1;i<5;i++)
{
if( abs(mid-arr[i]) < diff )
{
diff = abs(mid - arr[i])
median = 0;
}
}``````

so that should count for 5 comparisons, but the total no. of accesses would be 10

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

It will need 6 comparisons.
1. First make the array such that a[1] < a[2], a[4] < a[5] and a[1] < a[4].
a. compare a[1] and a[2]. swap if necessary.
b. compare a[4] and a[5]. swap if necessary.
c. compare a[1] and a[4]. if a[4] is smaller than a[1] then swap a[1] with a[4] and s[2] with a[5].
2. if a[3] > a[2]. if a[2] > a[4], median = min(a[2], a[5]) else median = min(a[3], a[4]).
3. if a[3] < a[2]. if a[3] > a[4], median = min(a[3], a[5]) else median = min(a[2], a[4]).

So in total 6 comparisons.
To extend it for a list of size n, use select algorithm (media of medians algorithm).

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

doesn't work with case 5,4,3,2,1

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

how much will take for 7 elements? 9 or 16? can any tell ?

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

We can do it in 4 comparision.

Logic is to find: First largest element -> Second Largest element ->Third Largest Element.

Third Largest element will be median, if there are 5 unsorted elements in array.

void Median() {

int a[] = {4,5,2,3,1};
int larg, secLarg, i, Median;
int len = (sizeof(a)/sizeof a[0]);

larg = a[0]; secLarg = a[1], Median = a[2];

for(i=1; i < len; i++) {

if(larg > a[i]) {
if (secLarg < a[i]) {
secLarg = a[i];
}
if(Median < a[i] && Median <= secLarg && i>2)
Median = a[i];
}
else {
secLarg = larg;
larg = a[i];
if(Median < a[i] && Median <= secLarg && i>2)
Median = a[i];
}
}

cout << "Median is :" << Median << endl;
}

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

Yes, above code will work. are you really doing 4 comparision?

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

4.
Test cases.
( 1 3 5 7 6), ( 1 6 7 5 2). To find median is possible in O(n) time complexity with space complexity O(1)

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

I think the question is a little bit weird...
now, consider an example with 3 numbers: a0, a1, a2
step 1:
we compare a0 and a1. result a0<a1

step 2:
we compare a1 and a2. result a1<a2 (yet we cannot guarantee it)

in this specific case, the number of comparison is 2, we have a0<a1<a2, so median is a1.

I think this is the minimum comparison number. Yet we need the number sequence satisfies some conditions.

We still use the previous example. If a1>a2. We would not know which one is median. So we need to compare a0 and a2 again.

For this case, the number of comparison would be 3. But this is worst case.

Basically, for n number , we need to do at least n-1 comparisons to find the median if data sequence satisfies some conditions.

So if we have 5 numbers, we need 4 comparison times.

Please correct me if I am wrong...

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

``````The best I can comeup with is 7.
- Need three to get three elements in order: x1  x2  x3
- Now need three more to order x2   x4   x5
- If x4 and x5 fall on either sides of x2 then x2 is median
- If x4 and x5 fall on the same side of x2 (both are greater or smaller then x2) then compare x4 (the element which is closer to x2) with x1 (if x4 is less than x2) or x3 (if x4 is greater than x2)``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

I think the answer is 8

find the first and second minimum number in 5 numbers,I think need 6 comparison
then find the biggest number in the left 3 numbers,need 2 comparison

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

eh....say wrong:
the second step is find the smallest in the left 3 numbers....

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

I am wrong....please don't see it....

Comment hidden because of low score. Click to expand.
-1
of 1 vote

first of all, sort the given array with selection sort because selection sort do less no of comparision for sorting and then pick the mid elements of the array which is the median....
in worst case,selection sort compares n-1 elements..hence in this case n=5 so ans is 4 comparision required....

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

Well as soon as you used the word selection sort, you ruined your post. They are asking about O(n) algo. And even the best sorting algos on a list of length n will take a time of nlogn.

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

It's an unsorted array.

Name:

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

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### 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.