Author |
Topic: Google interview question (Read 4305 times) |
|
diptendubhowmick
Newbie
Posts: 11
|
 |
Google interview question
« on: Mar 6th, 2014, 7:31am » |
 Quote  Modify
|
Recently I was asked this question in Google interview -
Suppose you have a set of n random positive numbers. You can pick p numbers at a time where p is a constant. Come up with a strategy to select p numbers every time in such a way that all the big numbers come in the end with highest probability.
|
|
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender: 
Posts: 13730
|
|
Re: Google interview question
« Reply #1 on: Mar 6th, 2014, 8:00am » |
Quote Modify
|
What sort of constraints are there? 'cause as long as p >=2 you can just sort the set as long as you're allowed to pick p numbers often enough.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
diptendubhowmick
Newbie
Posts: 11
|
|
Re: Google interview question
« Reply #2 on: Mar 6th, 2014, 8:10pm » |
Quote Modify
|
on Mar 6th, 2014, 8:00am, towr wrote:| What sort of constraints are there? 'cause as long as p >=2 you can just sort the set as long as you're allowed to pick p numbers often enough. |
|
The constraint here is that you are not given the dataset beforehand so you won't be able to any kind of preprocessing like sorting on it. You will be given p + constant number of elements at a time and you need to run your algo on that. The catch here is that you don't have the visibility of the entire dataset so that you can place the big numbers in the end by sorting the whole array.
|
|
IP Logged |
|
|
|
mttdbrd
Newbie
Posts: 1
|
|
Re: Google interview question
« Reply #3 on: Mar 9th, 2014, 8:06pm » |
Quote Modify
|
To make sure we understand this correctly: you select p elements such that each selection increases the probability that all of the biggest numbers will come in the final selection? Or is it that they must come closest to the maximum index position in the p buffer?
This set is not sorted, cannot be sorted, and does not contain duplicate elements, correct?
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Google interview question
« Reply #4 on: Mar 11th, 2014, 7:47am » |
Quote Modify
|
Is the question how to pick the p largest numbers in a long stream, given that you can only store p values at a time?
You just need to discard the smallest number if it is smaller than the next number you examine.
To do it efficiently, you can use a heap.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print