That was the entire phone screen, and they failed me. This still burns me years later because it was such an obvious communication failure on their part - if you're one of the rare interviews that actually require me to write working code, you better be darn sure to mention that upfront, rather than 5 minutes before the end of the hour! - and yet I was the one who failed.
As soon as we settled on the problem to be solved, I ran to my nearest copy of Knuth's _Seminumerical Algorithms_ (having copies of Knuth's three volumes both at home and at work has been well worth the investment). Because I had studied the book carefully a decade earlier, I vaguely recalled that it contained several algorithms for problems like this. After spending a few minutes considering several possible designs that we'll study shortly, I realized that Algorithm S in Knuth's Section 3.4.2 was the ideal solution to my problem.
If Bentley needed to go look up an algorithm that he vaguely recalled studying in the past, just how awful of programmers are the rest of us that look things up, really?
And yet somehow interviewers think that this will give them a good picture of how you'd do work on the job. Baffling.
But yes, this is asinine. Sharing your desktop through a video conferencing program and using the IDE of your choice would be far more realistic test, but Google likes to put hoops up to jump through that are smaller than your body.
Why can't you contort yourself like an octopus!? Fail!
I don't get how my interviewer (an engineer), didn't see the problem with it. I know that Google wants to use their own products, but that can't possibly be the norm for other Google interviews.
Their loss.
I just said, that can be solved with a topological sort, and then we moved on.
But I failed with another interviewer. He kept asking how to prevent hashing from producing collisions. The answer was universal hashing, but I had forgotten about that
However, that was not the case. The interviewer wanted me to code it all out over Google Docs, but I didn't remember the exact algorithm so I basically had to re-figure it out on the fly, which took most of the interview (I even similarly mention "in any real situation I would just look this up", but that didn't help). At the end, I had a bunch of pseudo-C++-code that should do it correctly.
I thought I was done, then the interviewer said she would go go copy my code and compile it after the interview to see if I was right, which blew my mind. It was never mentioned previously that the code would actually be compiled and run, and with no syntax highlighting or ability to compile and test the code myself there is zero chance it was ever going to work.
I never heard back, so I'm assuming my code failed and they left it at that. Anyway, I'm much happier now that I think I would have been at Google.