Google Interview Question
Web:
www.google.com
|
HQ:
Mountain View, CA
Overview |
| |
Salaries |
| |
Reviews |
| |
Interviews |
| |
Photos |
| |
Jobs |
| |
|
1,223 Interview Reviews |
Back to all Google Interview Questions & Reviews
Interview questions and reviews posted anonymously by interview candidates
Interview Question for Software Engineer New Grad at Google:
Jan 5, 2012
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 See more , See less 8 |
Add Tags
[?]
See more for this Google Software Engineer New Grad Interview
Helpful Question?
Yes |
No
Inappropriate?
Answers & Comments (4)
Feb 19, 2012
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...
Helpful Answer?
Yes |
No
Inappropriate?
Feb 20, 2012
median finding algorithm. Works in O(n) time.
Helpful Answer?
Yes |
No
Inappropriate?
Apr 30, 2012
It can be done using Selection algorithm
Helpful Answer?
Yes |
No
Inappropriate?
To comment on this
question,
Sign In with Facebook or
Sign Up
You might also be interested in: Interview Questions, Software Engineer New Grad Interview Questions, Google Interview
by ✳✳✳✳✳✳✳✳