News for hackers. Stuff that matters.
Re:My Google Interview by btilly on Friday July 16, 2010 @10:42AM (#1521268)
>"How can you detect loops in a singly-linked list without modifying nodes / keeping accounting information around?"

What do you mean by "accounting" information?

The usual way to state this problem is, "How can you detect loops in a singly-linked list without modifying nodes and using O(1) data."

The answer is that you start with 2 pointers to the beginning of the list. Then follow the pattern of advancing the first twice, and the second one once. You have your answer when the first reaches the end, or the first and second point at the same spot.

There are a lot of problems with a trick like that. And it is true that if you've seen the problem before, you're going to be at an advantage. So practice a few of them to get use to the form. But there are enough such problems out there that it is significantly easier to become a good developer than to learn a broad enough selection of them to have a good chance of getting through a set of interviews off of memory.

There are no comments on this comment yet.