Interview Question

Software Engineer New Grad Interview

Given a list of integers that fall within a known short but

  unknown range of values, how to find the median value?
Tags:
Answer

Interview Answer

4 Answers

This post has been removed.
Please see our Community Guidelines or Terms of Service for more information.

0

given that the range of values is small, we can do a partial selection sort. In the first iteration, find the min of the list. Repeat the process for n/2 times to find the median. This is efficient and linear time since the range is small. Other complex algorithms such as median of median can be used which also takes linear time...

Anonymous on Feb 19, 2012
1

median finding algorithm. Works in O(n) time.

Sarah on Feb 20, 2012
0

It can be done using Selection algorithm

Anonymous on Apr 30, 2012

Add Answers or Comments

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