> "Given an infinitely long linked list which you can only traverse once select a random item with O(1) storage."
My shot: pick some random number, go through that many linked list items and return the item you're at. Only needs to store the current item pointer and the random number. Maybe I'm missing something simple, though to be fair, it's a lot harder to answer these kinds of questions when you're under the scrutiny of an interview.
My shot: pick some random number, go through that many linked list items and return the item you're at. Only needs to store the current item pointer and the random number. Maybe I'm missing something simple, though to be fair, it's a lot harder to answer these kinds of questions when you're under the scrutiny of an interview.