19

How would you pick a uniform random element in linked list with unknown length in one pass or if not two passes?

Armen Tsirunyan
  • 130,161
  • 59
  • 324
  • 434
exlux15
  • 909
  • 1
  • 9
  • 16
  • 4
    I am afraid you'll have to put a little more effort in your question and make it crystal clear what you're asking – Armen Tsirunyan Feb 22 '12 at 19:15
  • ok. how would you pick a uniform random element in linked list with unknown length? – exlux15 Feb 22 '12 at 19:25
  • If that's your question, it's an interesting question. Please edit your question accordingly and I will upvote it – Armen Tsirunyan Feb 22 '12 at 19:31
  • ok fixed post. do you have any idea how I might approach this problem? I am trying to get use this method to get the pivot element in quicksort – exlux15 Feb 22 '12 at 19:38
  • Two passes is trivial. On first pass, calculate the length :) – Armen Tsirunyan Feb 22 '12 at 19:38
  • See? Bad question gets downvoted. good question gets upvoted. It's as simple as that :) – Armen Tsirunyan Feb 22 '12 at 19:39
  • thanks. what to do on the second pass? – exlux15 Feb 22 '12 at 19:42
  • Is this a homework or an interview question? – n. m. could be an AI Feb 22 '12 at 19:44
  • @AnilBabooram: chose a random number `i` such that `0 <= i < n` and iterate the list [on the second pass] until you find the nth element - and return it. – amit Feb 22 '12 at 19:45
  • @Amit thanks. how do I choose the random number i? Will use the rand() function? – exlux15 Feb 22 '12 at 19:49
  • it depends on the framework. in `c` you can use `rand() % n`, java has its own [nextInt(int)](http://docs.oracle.com/javase/1.4.2/docs/api/java/util/Random.html#nextInt%28int%29) for it... – amit Feb 22 '12 at 19:51
  • if I use a while loop to traverse the list and counting at same time. if I use ++n to count and i = rand() % n in the loop. will this generate the random number, i? – exlux15 Feb 22 '12 at 19:57
  • @amit ok if I use a while loop along ++length to traverse the list. If I use i= rand() % length, would "i" be the random choice at the current node? – exlux15 Feb 22 '12 at 20:02
  • @ArmenTsirunyan if I use a while loop along ++length to traverse the list. If I use i= rand() % length, would "i" be the random choice at the current node? – exlux15 Feb 22 '12 at 20:14

1 Answers1

32

Use reservoir sampling http://en.wikipedia.org/wiki/Reservoir_sampling . You need only one pass of the data.

For picking one element:

  1. Pick first element (probability 1)
  2. Later, for kth element pick it with probability 1/k (i.e. replace the existing selection with kth element)

I will let you prove that this results in uniform selection of elements.

ElKamina
  • 7,747
  • 28
  • 43
  • I tried to use that but this will pick k random elements. but I will need only to select the first element – exlux15 Feb 22 '12 at 19:53
  • @AnilBabooram Use k=1 ? Anyways, algorithm mentioned in the post (not wiki) is for one element case. – ElKamina Feb 22 '12 at 19:55
  • 1
    ok if I use a while loop along ++length to traverse the list. If I use i= rand() % length, would "i" be the random choice at the current node? – exlux15 Feb 22 '12 at 20:08