TopCoder Forums

Register Now

TopCoder

Member Count: 484,566 - May 24, 2013 [Get Time]

forums

Round Tables News Discussions Algorithm Matches Marathon Matches NASA Tournament Lab Software Forums TopCoder Cookbook High School Matches Sponsor Discussions	Search	Watch Thread \| My Post History \| My Watches \| User Settings View: Flat (newest first) \| Threaded \| Tree Previous Thread \| Next Thread
Forums Round Tables TopCoder Algorithm Competitions Choose random array element satisfying certain property

Mon, Jun 8, 2009 at 2:03 PM EDT Choose random array element satisfying certain property \| Reply
reiners 40 posts	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`.)

1 edit \| Mon, Jun 8, 2009 at 2:10 PM EDT Re: Choose random array element satisfying certain property (response to post by reiners) \| Reply
eraserhd 1567 posts	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.

Mon, Jun 8, 2009 at 2:16 PM EDT Re: Choose random array element satisfying certain property (response to post by eraserhd) \| Reply
reiners 40 posts	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`.

2 edits \| Mon, Jun 8, 2009 at 2:31 PM EDT Re: Choose random array element satisfying certain property (response to post by reiners) \| Reply
decowboy 126 posts	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

1 edit \| Mon, Jun 8, 2009 at 10:37 PM EDT Re: Choose random array element satisfying certain property (response to post by decowboy) \| Reply
tomek 1195 posts	A bit more intuitive way to see it: after each iteration each element satisfying p up to that point is equally likely, by induction.

3 edits \| Tue, Jun 9, 2009 at 3:59 AM EDT Re: Choose random array element satisfying certain property (response to post by decowboy) \| Reply
gsais 808 posts	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).

Tue, Jun 9, 2009 at 9:35 AM EDT Re: Choose random array element satisfying certain property (response to post by gsais) \| Reply
ardiankp 677 posts	Probably he wanted to see how did you defend, and were you sure with your solution. :P

Tue, Jun 9, 2009 at 6:10 PM EDT Re: Choose random array element satisfying certain property (response to post by gsais) \| Reply
jmzero 796 posts	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.

Tue, Jun 9, 2009 at 6:17 PM EDT Re: Choose random array element satisfying certain property (response to post by jmzero) \| Reply
StevieT 943 posts	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.

Forums Round Tables TopCoder Algorithm Competitions Choose random array element satisfying certain property
Previous Thread | Next Thread

Copyright TopCoder, Inc. 2001-