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

Microsoft

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

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