2 ms·
I was hired at ITA in 2002 on the strength of solving one of their puzzles. The thing about the puzzles was that, once you start thinking about one, you want t
by ncmncm 7y ago
I was hired at ITA in 2002 on the strength of solving one of their puzzles.
The thing about the puzzles was that, once you start thinking about one, you want to see what a solution would look like, and the only way to find out is to solve it. Having solved it, you want to know how it compares to others'. So you send it off, even if you aren't really interested in moving cross-country.
In my case, the puzzle was "add-a-gram": given a word list, find the longest sequence of words in which each word after the first is an anagram of the previous word, with one letter added.
I thought about it for a day or two until I realized I had a workable strategy. Then I sat down at my laptop, checked the clock, and started coding. Exactly two hours later, I had a program that, after reading in the dictionary, was a one-page, deeply-nested loop that exited when it found the answer.
It ran in ten seconds. How could I know if that was any good? I sent it off to ITA. The next day I got a call. We talked a little about setting up a phone screen, but she let slip that their solution was faster than mine. That could not stand. I spent the day inverting the control flow, with memoizing, and got a 10x speedup for less than 2x as much code, and sent that off.
I went on to interview. At the interview, they assigned a programming task that was a simplified version of the puzzle. I worked there for three years, until I got fired for being depressed. (I found treatment five years later.) I don't remember much of it because I was sleep-deprived, from having toddlers who would only sleep in the daytime. But I encountered there the most intelligent people I have ever known. Most were musicians, on the side.
I had been there three months before I thought to check their solution. My second version was faster. (Bitwise operations FTW!)
While there, I encountered a problem that I have used in conducting dozens -- maybe over a hundred -- interviews: Undergraduates solve it in two minutes, graduates in five, MSs in 20 or more, PhDs either never, or as fast as an undergrad. Every single person who has solved it used the same hand gesture in describing the solution.
Sometime later, ITA were bought up by Google, and I got some cash for stock. Taking care to owe only long-term capital gains did no good because Google paid cash, so we all ended up owing "alternative minimum" taxes as if we had made all the money in one day, not over N years. (The same thing happened when my next employer was bought by IBM.) Alternative minimum taxation is a terrible thing.
The version of the puzzle I was assigned during the interview is one we sent to candidates between phone screen and scheduling an interview, at my next employer. If it ever took more than an hour from problem statement to solution, it was too long; although I heard of people taking 12+ hours. Some sent code that ran 12+ hours, and was wrong. (Our best ran in <1 ms, which no candidate matched.) Some candidates posted their solutions online, after being rejected, but every posted solution was really bad, so that was OK. Cheaters disqualified themselves.
In 2010 I solved the "bitvector" problem in the posted article, during two weeks of sharply heightened intelligence I had while adjusting to the new antidepressant. To this day I marvel at that code. But by then, there was noplace to send it. Google took down the puzzles a little later.
I sometimes wonder what Carl went on to do, after he left ITA.
- monk_e_boy 7y agoWhat was the problem that you gave to the interviewees? Sounds interesting.
- ncmncm 7y agoIt is a file distribution problem, copying a file to a large number of destinations through a slow link. At ITA, the file was the airlines' seat availability record, that really indicated which price points on each flight could be offered for sale right then. I always tell them that undergraduates solve it quickly, but that never seems to help MSes. There was a similar problem, back in the 80s, that made starting an Occam program on a network of transputers very, very slow, that was solved the same way.