wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> Google interview question
        
(Message started by: diptendubhowmick on Mar 6^th, 2014, 7:31am)

Title: Google interview question
Post by diptendubhowmick on Mar 6^th, 2014, 7:31am

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.

Title: Re: Google interview question
Post by towr on Mar 6^th, 2014, 8:00am

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.

Title: Re: Google interview question
Post by diptendubhowmick on Mar 6^th, 2014, 8:10pm

on 03/06/14 at 08:00:07, 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.

Title: Re: Google interview question
Post by mttdbrd on Mar 9^th, 2014, 8:06pm

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?

Title: Re: Google interview question
Post by Grimbal on Mar 11^th, 2014, 7:47am

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.