Saturday, October 15, 2005

answer to linked list problem

The answer is that you start both pointers at the head of the list and you move them both down it but you move the second pointer (call it B) twice as fast as you move pointer A. If there is a cycle, you'll eventually detect it. Set A to head if list. Set B to A->next. If B->next = A, you have already detected a cycle. Otherwise, advance B one node and compare to A again. Now advance A one node. Advance B two nodes, comparing to A each time.

programming problem for interviews

This one is old school: we're dealing with pointers and very limited memory. Here's the set up: You are given a pointer to the head of a linked list. Your job is to figure out if the linked list has a cycle (i.e. one of the nodes has a next pointer that points back to some earlier node in the list). The trick is that you only have enough memory on the stack for two node pointers. How do you do it?

public speaking == bad

I'm delivering a talk next week on "Object Caching for High-Performance Web Sites" at the Zend/PHP Conference & Expo. As d-day approaches I grow ever more incredulous that I actually volunteered for this torture: public speaking is not my cup of tea. Worse than that (or so it seems now) is the prep work. Then again the prep work isn't really necessary; it just makes me a tiny bit less likely to make a total idiot of myself in front of a couple hundred peers.

Actually, I resolved to get myself into this mess several months ago while attending a similar conference. The presenters were smart and they knew their stuff but the presentations themselves were about as interesting as doing laundry. I vainly figured I could do better. I suppose this is my punishment.