surprisedThe fire alarm continued for nearly the entire time alloted for the interview; by the time the fire truck had left, we had five minutes remaining, and J. asked me a single question on algorithms before handing me off to another manager, R.
R. opened the interview with an emphatic belch, and I knew immediately I was going to like him. He asked a single question about SQL syntax, after which we talked at length about my qualifications, mountain-climbing, new technologies, and caffeine. If he was sizing me up, he did it in a manner so nonchalant that it didn't even appear on radar. He handed me off to E.
E. was the most intense fellow of the three: no metaphor, no formalities: the first thing he did was throw an algorithm at me -- a good one, too -- "What's the most efficient way to accomplish this?" About three minutes in, I had a solution of order O(n2), which I thought might be optimal. "It's good," he said, "but what if I told you there was a solution in linear time?"
"Well, I'm not sure I'd believe you. But if you tell me it's so, I'll stay up all night until I find it," I said.
"There is a solution in O(n). Think a little."
So I did. I came up with optimizations, but quickly came to the realization that they weren't enough to get to linear time. In about ten minutes, I had a solution that was better than O(n2) but I wasn't sure if it was in linear time, and I'm still not. It was good enough for him to cede the answer, which, once revealed, was amazingly simple, and I burst into laughter. I should have immediately seen the minute he told me there was an algorithm in linear time. "I didn't want you to stay up all night," he said.
So, on the ride back home through Issaquah -- gorgeous country -- I heard back from them; they liked me. Irony of ironies: that's how I came to get a job with Microsoft.
