Nice break. Time to get back with it; I'm running out of time, and I'm sure there's stuff I don't remember.

I finish studying up linked lists from *Programming Interviews Exposed*. Everything is pretty straightforward, but this last problem gets me: you're given a linked list; either the last node points to null (the list is normal, and *acyclic*), or the last node points to one of the earlier nodes in the list, in which case it has no end and is *cyclic*. Write an algorithm to determine which.

I progressed very quickly to the obvious answer: visit each node, and check whether it points to any of the earlier nodes in the list. No extra storage required, but it's O(n^2).

The answer, it turns out, I never would have gotten by myself: visit all the nodes at different rates. Have a slow pointer advancing one node at a time, and a fast pointer advancing two nodes at a time; if the fast pointer reaches an end, you're done, and you've only visited 1.5 times the nodes, which is O(n). If the fast pointer ever reaches the slow pointer, you've discovered a cycle visiting only 3 times the nodes... which is O(n). Of course, the author made an error that could result in a null pointer exception, and might accidentally skip the slow pointer the first time around, but those were easy to identify and rectify.

The brain teaser, Crazy Guy on the Airplane from techinterview, actually hammered home a rule of problem solving.

There are 100 passengers, numbered 1 through 100, boarding an airplane with 100 seats, also numbered 1 through 100. They'll be boarding in numerical order, and they'll sit in their numbered seat if it's available; otherwise they'll sit in a random available seat.

Problem is, passenger #1 is crazy. He randomly picks a seat, regardless of whether his seat is available.

What's the probability that passenger #100 will get to sit in his own seat?

Continue reading "Interview Day 8: Planes and Cycles" »