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

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

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

This post has been removed.

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
0

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