Lately I've been admiring how candidly some bloggers write about their job interviews, regardless of how well or badly the interviews go. I want to take a stab at being like that, as long as I'm allowed to. So! Radical transparency: go!
Yesterday I had two 45-minute phone interviews with software engineers at Google. My first interviewer was all business. She immediately led off with a question which we spent the rest of the 45 minutes discussing: "Suppose that you've kidnapped your neighbor's dog (assuming your neighbor has a dog), and now you need to write a ransom note. You have a magazine to cut letters out of. How do you go about it?"
As we continued talking, the problem evolved into "Supposing you know what you'd like your note to say, and you have the text of the magazine in electronic format, what's the most efficient way to find out whether the magazine contains the characters you need for writing the note?" My interviewer also threw several interesting wrenches in, such as "What if the magazine pages are printed on both sides?" Whenever I suggested an algorithm for something, she asked what data structures I'd choose to implement it and what the time complexity would be. In the last 20 minutes or so of the interview, she asked me to code up a solution. We had a shared Google document open, and I saw that she had already written the Java type signature of the function she wanted me to write, so I said that I'd rather write Python, if she didn't mind. (She didn't.)
It turns out it's hard to write code with someone looking over my shoulder, even if they're doing so electronically. My solution was very, very sketchy -- for instance, I said things like "Assume we have a helper function
index_in_alphabet() that, given a character of the alphabet, returns its index from 0 to 25." (I didn't know about Python's built-in
ord(), which returns a character's Unicode code point.)
Moreover, I really wish that I had written the code in my own editor and just pasted it into the shared document every so often. I use readline bindings everywhere (I'm pretty much useless without them), and they worked in Google Docs (hooray!), so that was just enough to make it tolerable as a text editor. But I'm willing to bet that if I'd been using either Emacs or TextMate, then it might have occurred to me to, oh, I don't know, maybe try running my code once or twice. I didn't think to do that until several hours after the interview was over, and when I did, I realized that it had lots of bugs: syntax errors, both misspelling the name of a function and calling it with the wrong parameter (ouch), and failure to initialize the elements of an array with values before writing into them (betraying my sordid past as a Perl programmer). Those were the things I had to fix just to get it to work, and even then, my code wasn't using one of the little optimizations that I had been perfectly happy to talk about in the interview. Once I had it working, I was unable to resist putting in that optimization and then sending the working code to my interviewer with a quick note of thanks. I figure that can't hurt.
After a 15-minute break, the second interview began. My second interviewer was more conversational than the first had been; I thought we hit it off pretty well. He asked me several questions regarding a distributed database system not entirely unlike Bigtable. I don't know very much about distributed systems, but I was able to use some of what I knew about database concurrency.
One question was: Suppose you have numerous machines that are performing ten transactions per second, and every transaction has to have a unique ID. Roughly how many transaction IDs will you need? We made up some numbers for how many machines we were talking about and for how long the system was expected to run, and the order-of-magnitude answer I eventually came up with was "ten billion", which led to him asking whether I could represent transaction IDs with a 32-bit integer, which was one of very few yes/no questions I was asked in either interview. (My answer: Nope. We can only represent 232 = about 4 billion distinct values in 32-bit ints, so we're going to need to go to 64 bits for this.) We also discussed ways to make sure that transaction IDs were strictly increasing over time. In a centralized system, one could just use timestamps, and so that was my first suggestion, but then I realized out loud that the timestamp idea was error-prone because it seemed like it would be hard to keep all the machines synchronized. "Why does that seem hard?" "Well, it's hard just to keep my own laptop and desktop computers synchronized," I said. He said, "Yes, and in fact, it's so hard that distributed systems people usually turn up their noses at the use of timestamps for this purpose."
Later, the interviewer switched to asking me questions related to things I'm studying in particular. "If you were implementing a Scheme compiler, what do you think the hardest parts would be?" Talking about this stuff was so interesting and pleasant that I flat-out forgot to be nervous. "I think that the hardest parts would be dealing with features like higher-order functions and first-class continuations -- you know, the stuff that makes Scheme special." Then I thought to myself, Stuff that makes Scheme special... "And macro expansion!" I added hurriedly.
At the end of the interview, I expressed interest in knowing more about Bigtable, and his response was to give me a reading list. "Your adviser's going to hate me!" I assured him that no one would hate.
And that was it. In all honesty, this interview ended up being fun -- the most fun I've ever had in a job interview, in fact. It remains to be seen how I did, and I think it depends largely on whether my numerous Python mistakes were forgivable. I should know within a couple of weeks. Meanwhile, it's time to attack this pile of homework that isn't going to go away by itself.