Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (newest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
Choose random array element satisfying certain property | Reply
Suppose I have a list, called elements, each of which does or does not satisfy some boolean property p. I want to choose one of the elements that satisfies p by random with equal distribution. I do not know ahead of time how many items satisfy this property p.

Will the following code do this?:
pickRandElement(elements, p)
     randElement = null
     count = 0
     foreach element in elements
          if (p(element))
               count = count + 1
               if (randFloat(0.0, 1.0) < 1.0 / count)
                    randElement = element
 
     return randElement

(randFloat(f1, f2) returns a random float f with f1 <= f < f2.)
Re: Choose random array element satisfying certain property (response to post by reiners) | Reply
No. It will have a 100% probably of picking the first element if the first element satisfies p.

To correct, you will need to count all elements first, and then call randFloat() once. (Or maybe you've just indented incorrectly?)

If you expect there to always be a sufficient percentage which satisfy p(), you can also use rejection sampling - just pick elements at random and reject picks where !p(element).

EDIT: I somehow thought there was a return after the assignment.
Re: Choose random array element satisfying certain property (response to post by eraserhd) | Reply
I've indented correctly.

That's true that it will set randElement to the first element that satisfies p, but the method doesn't return at that point. It continues iterating, possibly changing the value of randElement again. For example, when it reaches the second element satisfying p, it will replace the first element with a probability of 1/2.
Re: Choose random array element satisfying certain property (response to post by reiners) | Reply
It should work. Proof:

the elements that don't satisfy p are irrelevant, since they are simply skipped. So we have a list of n elements (1..n). The probability that element i is the output, is equal to the probability that it will be chosen and not replaced later on:
P(X = i) = 1/i * i/(i + 1) * (i + 1)/(i + 2) * ... * (n - 1)/(n)
= 1 / (i/i) / ((i+1)/(i+1)) / ... / n
= 1/n
Re: Choose random array element satisfying certain property (response to post by decowboy) | Reply
A bit more intuitive way to see it: after each iteration each element satisfying p up to that point is equally likely, by induction.
Re: Choose random array element satisfying certain property (response to post by decowboy) | Reply
Funny. I was asked that question (worded differently) in an interview at Google Belo Horizonte. I gave this same algorithm, but instead of if (randFloat(0.0, 1.0) < 1.0 / count) I used if (randInt(0, count) == 0), where randInt(0, n) returns a random integer (uniformly) in the range [0..n). As far as I can tell, it's exactly the same algorithm (even slightly better as there are no floating point operations), but the interviewer kept saying that it was not the right answer. First I showed him an empirical proof (using an example with a few items) and then I showed an inductive proof, but he just said I was wrong and it was time to move for the next question. Weird. Anyone can tell me what's wrong with it?

edit - in the question I was given there was no boolean property that had to be satisfied, just a collection of items (of course, the size of the collection was unknown and the algorithm had to be O(n) in time and O(k) in space AND we could only iterate once through the collection).
Re: Choose random array element satisfying certain property (response to post by gsais) | Reply
Probably he wanted to see how did you defend, and were you sure with your solution. :P
Re: Choose random array element satisfying certain property (response to post by gsais) | Reply
It's funny, I've heard the same kind of story from a few of people who've had Google interviews - the interviewers seem to have very rigid expectations for answers, and don't seem to understand arguments in favor of an alternative. Maybe this is some kind of strategy to test applicants reactions to unfair situations.

Or maybe I'm just bitter because of how my "interview" turned out.

I went to the Code Jam regionals and had an interview scheduled. I'm doing pretty well at my current job, but I thought maybe Google would have something cool, and I'd heard Google interviews were interesting in and of themselves.

Anyways, the interview was canceled after I arrived (and after I could change my schedule, though I did appreciate the chance to wander despondent around Seattle for a bonus day). Apparently my recruiter person couldn't find anyone willing to interview me because I'm apparently not qualified to work at Google in any capacity. Despite being reasonably clear on that last point, the recruiter said she'd arrange a phone interview.

Then I assume at some point while arranging the phone interview she rediscovered the fact that I'm a hopeless moron who could never work at Google, because the phone interview just kind of never happened.

Usually our response to someone who really isn't qualified is to tell them something like "We don't have anything for you right now" or "We had a lot of great applicants and only one position" or something. But I suppose Google's way works too. It certainly will prevent me from wasting their time in the future.
Re: Choose random array element satisfying certain property (response to post by jmzero) | Reply
I also had an interviewer who seemed to get a question wrong. It was on a similar topic, actually, about selecting N elements uniformly at random from a stream. I think they just do it to see if you can stick to your guns and also see how well you explain your (hopefully correct) thinking to somebody who is getting the wrong end of the stick.

Just one of them was like this, the rest of my interviews were very different.
RSS