I've tackled one of ITA's puzzles (word rectangle, I think I found a 7x7 in 60-ish seconds). I got through a phone screen and interview, but was ultimately turned down for 'lack of experience.'
If you're trying to get hired at ITA by solving one of these puzzles, here's something to keep in mind: the point of solving a puzzle is to GET A PHONE SCREEN. That's all. Many of these puzzles have no 'perfect solution.' I'd be surprised if any of them do. Instead, they're a proving-ground for your coding chops. So write tests, write comments, and make the code as clear as you can. Provide your best solution, but remember: the point is to write something good enough that they'll pick up the phone and CALL YOU. I spent much too long on my solution before I realized it was already good enough to clear this bar.
If you do get an interview, plan for a full day. You'll get another problem of this nature (though much simpler) at the end of the day, plus the usual salvo of whiteboard coding exercises.
I disagree with this advice. My bitvector solution was memorable enough that I spent a good portion of my in-person interview discussing it (it took advantage of multiple cores even during parsing, and had some passages of hand-written assembly in order to exploit SSE2). A good-enough solution will be good enough to get you in the door, but an excellent solution may carry you further.
Some other things I've remembered since posting this.
1. I wrote my solution in lisp, which likely helped quite a bit toward getting me in the door. I imagine my 'not as great' solution had some more leniency being in a hard-to-find-developers language.
2. The problem I solved called for finding the largest rectangle. This was tricky, so I just ignored that and searched for the largest square (yes, I know a square is a rectangle), which helped simplify things greatly. I stated clearly that I was doing this in my solution. I still got an interview so it seems simplifying the problem in this way was acceptable. This lends further proof to my idea that these problems are just an excuse to see some of your code (and prove you like solving problems).
3. After nearly every snippet of code I wrote in the interview, someone asked me: "what's the pathological case for this? What kind of input would cause this to take forever?" It's an interesting question, and clearly something they're quite concerned with (you can't just not respond to a web request for flights if the user happens to enter tricky data). If you're going to interview, it'd be a good idea to get in the habit of asking yourself this question about your code.
I've been working on the word rectangle problem, too. Care to share your '7x7 in 60-ish seconds' solution? Or at least some hints on how you approached the problem? I'd be much obliged, as they say.
I agree that tries are good. There is also an 8x8 solution if you wait long enough. Strangely there don't seem to be any non-square solutions up to the sizes I was able to check, so you might as well search only for squares, which speeds it up a lot. I'm not sure if I should post a solution but I'm happy to email it to you.
If you're trying to get hired at ITA by solving one of these puzzles, here's something to keep in mind: the point of solving a puzzle is to GET A PHONE SCREEN. That's all. Many of these puzzles have no 'perfect solution.' I'd be surprised if any of them do. Instead, they're a proving-ground for your coding chops. So write tests, write comments, and make the code as clear as you can. Provide your best solution, but remember: the point is to write something good enough that they'll pick up the phone and CALL YOU. I spent much too long on my solution before I realized it was already good enough to clear this bar.
If you do get an interview, plan for a full day. You'll get another problem of this nature (though much simpler) at the end of the day, plus the usual salvo of whiteboard coding exercises.