Microsoft Interview Question: Given a random array, how can... | Glassdoor

Interview Question

Software Development Engineer(SDE) Interview(Student Candidate)

Given a random array, how can you find the median without

  using any know sorting algorithm?
Answer

Interview Answer

2 Answers

0

Grab an element from the array and count the number of items greater than, and less than that element. If there is an odd number of values just find the value that has the same number less than and greater than. You can save some checks, ie if there are 10 greater than values and just 4 less than, your next pick should be a value that is less than your current one.
If it is even number of elements, find one where there are n less than values and n+1 greater than values (or vice versa, which ever comes up first). Then on the side with more find the value closest to your chosen median and average the values.

Kris Reynolds on Apr 27, 2013
0

Kris above describes quickselect. You could also use the so-called "median of medians" algorithm if you wanted to.

Anonymous on Nov 4, 2013

Add Answers or Comments

To comment on this, Sign In or Sign Up.