ITA's old “Hiring Puzzles” is still a treasure trove of good problems

These appeared during the post-dotcom bust pre-startup boom period of 2004-2008. If you look at CS enrollment rates of the time you’ll see they were at record lows. Software paid well, but not that well and most engineering jobs were really bad ones resembling Dilbert comics. The culture of treating engineers well, giving them good tools, snacks, unlimited pto didn’t happen until later.

At the time people solving hard problems and keeping up with changes in programming languages and tech were doing it because they loved it. Nearly everyone doing tech was doing it because they where obsessed and passionate about it. This is because if you weren’t there where much more pleasant ways to make about the same money.

These ITA puzzles were a way of signaling “hey! we’re a company of people that love to code and work on hard puzzles too! If you’re the type of person that sees puzzles like this and can’t get it out of your head for the rest of the day, you should check us out!”

These puzzles were not a leetcode like gates (in fact they very explicitly were NOT required for applicants), but rather a way of advertising to programmers that ITA was not just another boring big corp that would suck your passion for coding away.

For me, these puzzles were what got me to change careers; at that point I was in a non-technical job and didn't have any CS training. Still, I saw these puzzles and was hooked. Figuring out how to even set up a basic coding environment was part of the puzzle for me.

I spent a few weeks on "Strawberry Fields", eventually getting to a brute force solution that passed all the tests. I was about to send it in, and happened to meet one of the ITA folks at a social event. After a few minutes of talking to this gentleman, I realized he was in a completely different intellectual class from me, and that I had to do a lot better than hacking together a solution to a single optimization problem if I really wanted to work in this industry.

I persisted. I kept solving whatever coding problems I could find and rung by rung, climbed my way into some interesting and challenging software and data roles. I bombed plenty of whiteboard interviews along the way.

It sounds funny to write down, but it is not an understatement to say that those ads on the T changed my life!

I don’t see the question I remember pondering, which was simpler than these but more fun to think through on a short subway commute— something like “Create the longest possible string of connected movie names, like ‘Independence Day of the Dead Man Walking...’”

Edit: I found it! It was called “Sling Blade Runner” and it ran from 2007-2008 so my memory was off by a year. Solution: https://github.com/vy/ita-puzzles/blob/master/README.md#slin...

So much stuff on the internet (and business in general) thinks that "hey, it worked for someone - it must be a new paradigm!"

The people who wrote those puzzles would never think of writing them as incentives to join their company now - because that idea has long-since sailed.

So much of the crap part of hiring (and business in general) is because it involves taking something unique and interesting that someone has done, and rehashing it until it's a hollow, shallow, uncreative version of its original effect!

I eventually got an offer, but chose another job. They were acquired by Google soon after, and I sometimes regret not taking it!

- It was definitely fun working one's way to solve these

- And they are nothing like the LC problems thrown around in interviews nowadays

- Neither are these ITA problems a good fit for a 45 min interview from the duration perspective or getting `the right answer` perspective

[0] https://www.deepaksurti.com/blog/category/ita

edit: added the page link where I posted my solutions

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.