Microsoft Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: In-Person
consider 5 4 6 7 8
I think need 6 comparison to find the first and second minimum .....
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
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).
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
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
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).
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;
}
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...
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)
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
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....
to find first and second minimum we need 4 comparison
- rashmi sampath June 28, 2012consider 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