Google

  www.google.com
Work in HR? Unlock Free Profile

Google Software Engineer New Grad Interview Question

"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
Add Tags [?]
Answer

Part of a Software Engineer New Grad Interview Review - one of 3,052 Google Interview Reviews

Answers & Comments

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

0
of 0
votes

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
of 1
vote

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

- Sarah on Feb 20, 2012
0
of 0
votes

It can be done using Selection algorithm

- Anonymous on Apr 30, 2012

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

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