3.6 of 5 7,025 reviews Redmond, WA 5000+ Employees

Microsoft Software Development Engineer(SDE) Interview Question (student candidate)

"Given a random array, how can you find the median without using any know sorting algorithm?"
Add Tags [?]
Answer Flag Question

Part of a Software Development Engineer(SDE) Interview Review - one of 3,166 Microsoft Interview Reviews

Answers & Comments

of 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 Flag Response
of 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 Flag Response

To comment on this question, Sign In with Facebook or Sign Up

Microsoft – Why Work for Us?

What do you want in a job? Do you want more than a paycheck? At Microsoft, you can discover potential you didn’t know you had, push your limits, turn your ideas into reality and make a real impact on the industry and… Full Overview

Provided by employer [?]

Tags are like keywords that help categorize interview questions that have something in common.

Glassdoor is your free inside look at Microsoft interview questions and advice. All interview reviews posted anonymously by Microsoft employees and interview candidates.