Here is a similar interesting problem that I was once posed. Not sure how common or rare is this: You get a stream of words (using functions like getFirst(),

Here is a similar interesting problem that I was once posed. Not sure how common or rare is this: You get a stream of words (using functions like getFirst(), getNext(), boolNoneRemaining(), etc.). Once you reach the end of this stream, you have to output a random word uniformly chosen from this list. The first answer is of course to store the entire list and maintain the size of this list. The moment it finishes, you multiply the size by a random number ... Then comes the twist. What if there isn't enough memory to hold the whole list? The thing that stuck me first is that someone posing this problem by itself meant that there was probably a solution to this, which I could then think of and program shortly. Now frankly, when I interview, this is usually the last question on my list. Most candidates do not reach this far. Believe it or not, some half of the applicants are not able to draw a finite state machine that could identify if given binary number is odd or even (when its input stream is bits with LSB the last...).