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.

Why Firefox Matters

I don't know if you've been following all the bruhaha surrounding the beta release of IE7 but it's done something that I would have scarcely thought possible a couple years ago: revived shrillness in the pointless debate over which web browser will save humanity from itself. I admit to caring about web browsers but then I'm a web developer: the capabilities and bugs of the browser du jour have an impact on the quality of my waking hours.

I used to like IE but that's only because it's competition at the time was Netscape 4. I realize now that's like being into Britney Spears because you've only every heard elevator music your whole life. But now there's Firefox and it's like I've just discovered Tom Waits.

For a while I wanted Firefox to be successful if for no other reason than that it would make my life as a developer easier. I wondered what kind of market-share it would have to garner in order for websites to take notice and start designing, if not explicitly for Firefox than at least not implicitly for IE.

Now, I don't care.

I no longer care because Firefox has already succeeded. It succeeded the moment IE7 was conceived. Because what I really care about is not what browser people use but whether I can use transparent PNGs or CSS 3, and the fact of the matter is that most of the world uses IE and IE will soon support those things. But, and this is the important part, it took Firefox to bring IE to that point.

Most of the foregoing doesn't exactly constitute a sharp observation. But when you start to view Firefox not as the carrot that leads us to a better web, but as the stick that drives IE, that's where things start to get interesting.

Take Google for instance. They designed the first web apps that weren't painfully clunky. Gmail compares well to my desktop mail client and Google Maps is the best mapping software I've ever used. And the minute browsers start supporting things like SVG and XForms I'm sure Google will come out with something else that amazes everyone. But Google, like everyone else on the web that cares about staying in business, can only do cool things in so far as those cool things work in IE.

And Google can't exactly force Microsoft to upgrade its browser.

Or can it?