4 ms·

I applied for a summer internship with Google between 2009-2010 (remember: Australian summer!). I ended up making it through but even for an intern there were f

• axiak 16y ago
  That's actually not a trick question, and one that I've actually encountered in my job a few years ago. Email me if you want to know the answer.
• tung 16y ago
  > "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.
  • nostrademons 16y ago
    That's not quite random, because you're selecting items with probability 1/RAND_MAX. The elements beyond RAND_MAX will never be selected.
• munificent 16y ago
  > "Given an infinitely long linked list which you can only traverse once select a random item with O(1) storage." If the goal of the question is to select a random item where all items have the same probability of being selected, it's impossible. If you're willing to ditch even distribution, then one answer is: value pickRandomItem(node* list) { /* Always return first item. */ return list.value; } Or maybe I'm missing something here?
• evo 16y ago
  > "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/
  • Smerity 16y ago
    Your confusion is the exact problem my friend had. After some nudging the interviewer rephrased it to be a linked list of finite but unknown length. The issue was more that when my friend didn't get it within about a minute the interviewer decided the interview was over and hung up abruptly. If the question is "select a random element from a linked list of finite but unknown length that you can traverse only once" then yes it's at least solvable but I don't think it's a reasonable interview question to demand in less than a minute when the question was additionally ill formed to begin with.
• dadkins 16y ago
  "Given an infinitely long linked list which you can only traverse once select a random item with O(1) storage." I assume they meant arbitrarily long instead of infinitely long. In which case, I just wrote that code today: val := nil for i, x in range a { if rand.Intn(i+1) == 0 { val = x } }
  • astrofinch 16y ago
    The probability that a given list item will be selected is not uniform.
    • dadkins 16y ago
      Sure it is. Base case: In a one item list, the first element is selected with probability 1. Induction: Assume we've picked an element uniformly at random from the first n elements. When we encounter the n+1'th element, we pick it with probability 1/(n+1). Thus, we now have a uniformly random sample from the first n+1 elements.
      • astrofinch 16y ago
        Sorry, I misunderstood your algorithm description. I thought the word "pick" meant "return this item as your answer". I guess your intended meaning should have been clear from your code (Scala?).
• vlad 16y ago
  If a data structure can be arbitrarily long, this implies some kind of a data structure involving a linked list to avoid wasting memory. Unfortunately, it really is a bare-bones linked list, which means that we don't know the length until we traverse it. What would we have done if we knew the length? We could pick a random number between 1 and the length, and then traverse that many items to get to our random item. Since we don't know the length, it means the question is, how will you know where to stop? Constant growth for storage means you start with a fixed number of slots (lets call this number X) and keep them through the process. You could put items into these X slots, such as one out of every ten that you pass. That would mean you could pick items by rolling a 10-sided dice that shows a 10, and put them into one of the slots. A problem is that you would have to remove past randomly-selected numbers to make room for new ones, and you would be biased towards items that appear later in the series. This would not be random. And what about a string one character long (in this case, we can pretend we had been given an array, a string, a queue, or whatever) ? What if, at the start, we always select the first item to be the random choice? That would mean that an abrupt stop would give us the correct answer for a length of one. Another interesting thing is that we can store item one into a single container, instead of needing X (where X is a constant) slots. What about two? Well, we would compare the container with item two and decide that the random choice for the container should be either what it already contains (item one) or item two, with a 50/50 split. Great! So our algorithm works for a length of one as well as two. This is starting to feel like we've established a base case (what happens when the list has only one item?). We may be on track to show that constantly looking at the next item and comparing it to the one in the container may just work. If so, we could have a proof by induction. So if we were at item three where the whole list is only three items long, then a random generator would have picked it with a probability of 1/3. So if we're comparing item three to whatever is in the container, then if a 3-sided dice rolls a 1, we can set container to be item three. That works. But what about the other 2/3 chance, where it could be item one or two? In that 2/3 chance, we pick the container. The container contains only one item (the first or the second, whichever one won the first coin flip previously.) For this to be a valid idea, both item one and item two should have had a fair chance to be in the container currently with a 50/50 split, correct? And we know that it was. So when we come to item four, we replace the container with item four with a probability of 1/4, or use the value in the container with probability of 3/4 (e.g. 1-1/4 = 3/4, or the rest of the time.) The point is that at each step, the container contains the random value of the previous n-1 number of items.
• nostrademons 16y ago
  I cheated. I googled it: http://stackoverflow.com/questions/1840618/fast-random-selection-algorithm http://stackoverflow.com/questions/1840618/fast-random-selec... BTW, this actually is a practical question, because it's isomorphic to "How do you select a random element from a stream of elements when you don't know the length of the stream a priori?" This is crucial for many online algorithms. For example, imagine that you're FaceBook and you're trying to display a News Feed of a massive number of events coming in from a large number of apps. You don't have the computational power to handle all of them, and so you need to drop some of them on the floor. How do you fairly drop events and display only a random sampling of them?