The title of this post can be misleading. Nevertheless, just wanted to highlight the importance of sleep. I read about this problem of “finding a random byte from a stream of n bytes with O(1) storage” and the solutions out there on the web. Couldn’t wrap my head around this until it dawned on me the next morning, during my regular walk, which I’d like to attribute to a good night’s sleep.

Back to the problem. The solution is simple – when the first byte arrives, make that the random byte. When the second arrives, the previously selected byte and the current one have a 1/2 probability each and you generate a random number in the range of  1-2 and if it is 2, select the recently arrived as the random byte replacing the previous random byte. When the third bytes arrives, the previously selected random byte has a 2/3 probability, while the 3rd byte has a 1/3 probability – hence the 3rd byte is the random byte if the random number generated in the range of 1-3 is equal to 3 at this step.

Implementation of this algorithm can be found here:

http://www.geeksforgeeks.org/select-a-random-number-from-stream-with-o1-space/