Google Interview Question: Given a list of integers that... | Glassdoor

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?
algorithm, median, selection algorithm

Interview Answer

5 Answers

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


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

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

Sarah on Feb 20, 2012

It can be done using Selection algorithm

Anonymous on Apr 30, 2012

Given the range is small, create an array of size 100; Iterate once and insert the values AT the array indexes; count each insert. Then iterate from the start of the array (skipping most blanks) up to the count/2 indexed value.

Tim S. on Jun 3, 2016

Add Answers or Comments

To comment on this, Sign In or Sign Up.