> "Given an infinitely long linked list which you can only traverse once select a random item with O(1) storage." This question seems ill-defined. Assuming you

> "Given an infinitely long linked list which you can only traverse once select a random item with O(1) storage." This question seems ill-defined. Assuming you interpret "random" as "have an equal probability of returning any given element", then the probability is 1/infinite which is undefined. I think there could be three possiblities: A) The interviewer was baiting your friend into trying to elaborate the problem, in a "my client is asking me to do something absurd but I'll try to piece out his actual intent" sort of way. If so, you could come up with some hypothetical scenarios this algorithm would solve and show how actual problems would have actual bounds on how far the random window needs to go. B) You could be remembering the problem wrong. It could be "Given a finite linked list whose length you don't know a priori..." instead. This is much more tractable as a stereotypical tech interview question. C) Return the ninth element. http://dilbert.com/strips/comic/2001-10-25/ http://dilbert.com/strips/comic/2001-10-25/