ITA Software's Hiring Puzzles | Hacker News Reader

ITA Software's Hiring Puzzles

itasoftware.com

100 pointsehsanul44 comments

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'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.

One word: tries.

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.

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 was about to graduate graduate school, I had finals, final papers, and interviews. I had 2 companies which had hiring puzzles, and interviewed at 5 companies. I was really interested in ITA, unfortunately I couldn't schedule in the time to work on the hiring puzzle within the 2 week window this occurred.

I sort of imagine that these puzzles have an outlier effect: it removes the top and bottom users from a selection pool. Maybe that's okay, personally I was a bit disappointed at the missed opportunity.

One way they could improve this is by giving the puzzles expiration dates, removing the fear of completing one far ahead of the interview process, and having it expire. You'll still miss out on those who haven't heard of ITA until the near-graduation career fairs, but it will at least improve the situation.

Why do you think this would have adverse selection against the top of the pool? I can clearly see how it would act a barrier to application for the bottom candidates (a good thing for the company), and I can see how it would reduce the number of applicants who are applying "everywhere they can think of" (also probably good for the company in terms of getting a more qualified [in the sales-conversion-rate sense] base of applicants).

In my experience, the very top of the applicant pools aren't applying to a particularly large number of places.

Although the top tier candidates may not be applying at many places, they are receiving many more first, second, or even third interviews. Thus, their timing is tight in a two week window near the end of school when they start receiving offers. Near-Bottom-tier candidates may receive less interviews and are incentivized to perform more desperate acts in order to receive interviews, and thus have more time for puzzle-based applications.

But as I said, it's not too big of a deal, if they would only post ahead of time how long puzzles would be active, so one could complete them before this tightly-timed period.

Yesterday someone mentioned the Sling Blade Runner problem from their archives and I can't stop thinking about it.

* http://www.itasoftware.com/careers/puzzle_archive.html?catid...

* http://stuffthathappens.com/blog/2007/10/03/sling-blade-runn...

I'm in the middle of writing a web-based anagram server and there's some similarities in both these problems. You have a dictionary that you iterate through recursively to find a solution. For anagram, the solution is usually found with 3-5 recursions (100 word list, 3 recursions: 100^3 calculations - not a big deal for desktop software, too slow for web-app). For Sling Blade Runner, your goal is to keep increasing the depth of the recursion as much as possible so it's actually impossible to go through 100^200 calculations.

Does anyone have any idea if these problems could be better tackled by converting them to map-reduce problems? I'd like to play with Amazon's mapreduce service.

Edit: Neat. I came across: http://blog.xebia.com/2009/07/02/thinking-mapreduce-with-had...

Are you looking to pre-generate the results or generate them dynamically? I think MapReduce will only be effective for the former.

There are no map-reduce implementations that work in real-time? I thought Google search worked like that. I do want it to work dynamically.

MapReduce is used to build the search index (constantly), and your searches are run against the index.

You might find some of these links useful:

http://wiki.apache.org/hadoop/ProjectDescription

http://wiki.apache.org/hadoop/HadoopIsNot

You can use map-reduce on your search by partitioning up the starting keyspace alphabetically (26/num nodes), although with such an even partitioning the search will probably be unbalanced. But with some simple metrics on the starting letter frequency of words you could define a more balanced partitioning.

What do you mean by anagram solver? Find anagrams for a given word? Isn't that trivial by indexing words by the sorted version of the word? E.g. {"aep" -> ["ape", "pea"], ...}

Yes.

Until you get to multiple-word anagrammatic phrases, when it becomes a search problem.

(You could index a list of phrases the same way, but users wouldn't be able to type in their name and find out what phrases it jumbles into.)

I'm trying to built a better multi-word anagram solver. If you input a 32 character string, you'll end up with hundreds of thousands of potential anagrams and most of them are pretty useless. For example, "Florence Nightingale" returns 52k results on:

http://wordsmith.org/anagram/anagram.cgi?anagram=Florence+Ni...

And most of them are pretty lame e.g. "A Fleecer Tingling Hon", "A Fleecer Longing Hint" etc. It'll take hours before you come across "Flit on, cheering angel" - I want to make this process faster/easier.

Use random partitioning? If you have more than 10 letters, randomly split into roughly equal parts. Then do that 1000 times to the input string.

It's a fun project! I built one several years ago, after playing around with a bunch of different approaches. I wound up with a human-guided tool that seems to work pretty well for coming up with interesting ones:

http://anagramlogic.com/

Ah, interesting! This problem is NP-complete even in if you don't specifically want anagrams that are interesting to a human.

Suppose that you only have a single letter alphabet (say "a"). Now the input string can only contain a's, so it can be represented by a number n. The dictionary also consists only of words of a's, so the dictionary can be represented as a set of numbers D a subset of the natural numbers. Now the problem of finding an anagram is finding a subset of A of D such that sum(A) = n. But this is the subset sum problem, which is NP-complete!

How are you determining the interestingness of an anagram?

I wrote this snippet ~10 years ago when learning Perl:

  for(<>){chop;$s{join'',sort split'',lc}.=" $_"}for(sort%s){/. /&&print"$_\n"}

Running against wordlist.txt was fun (anemic cinema, bedroom boredom, etc.)

You're on the right track with the recursive dictionary search.

For the Sling Blade Runner problem, I would make a trie (http://en.wikipedia.org/wiki/Trie) out of hash tables, like this:

    trie = {
     'dracula': {'': None,
                'dead': {'and': {'loving': {'it': "Dracula: Dead and Loving It!"}}}},
     'the': {'brides': {'of': {'dracula': "The Brides of Dracula"}}},
    # ...
    }

Then, for each word in each movie title, walk the trie from the beginning until you run out of matches (no match), or run out of words (at least one match).

Your anagram server is similar, but since they're not ordered like movie titles, you have to walk your scrambled word(s) and only generate permutations that have a matching trie path.

It's also quite possible to do it for phrases, not just words.

You can cheat a little by representing your anagram as a 26-key multiset containing the number of times each letter appears (in Python, use a dict; in C, use an array of 26 integers).

For each letter that appears in your anagram multiset one or more times, make a copy of the original multiset, and recursively descend the Dictionary trie, removing each matching letter from a new copy of the multiset (they're tiny, so don't worry). For each complete word you find, add it to a list of result candidates, along with the multiset representing the remaining letters in the anagrammatic phrase.

Repeat the process for each result candidate, growing your list into a tree. Stop when you run out of matches, or when you run out of letters in your multisets. (You can set a maximum number of leftover letters to accept, if you're having trouble matching a phrase).

If you test the letters in alphabetical order, your result phrases will already be sorted.

> Then, for each word in each movie title, walk the trie from the beginning until you run out of matches (no match), or run out of words (at least one match).

I think that's the challenge ITA wants you to solve - recursing 300 levels deep into a list of 1000 movies will literally take forever. As you can see with the 2nd linked article, brute-force just doesn't work.

My original algo for the multi-word anagrams was nearly identical to what you described. The problem was when you entered a long phrase. You can form 8000 unique words from the letters in "William Jefferson Clinton." Even when I removed duplicates words with the same characters (art = tar = rat), it was still 7000+ long. Add in another 'r' or 's' to the original phrase and you're over 10,000 unique words. If I'm allowing my algorithm to make 5 word anagrams, that's 10^5 calculations for a single web query - absolutely impossible.

And even if I do magically return the 100k possible results in 0.1s, users can't parse through 100k results to find the ONE anagram that's funny or creative. I do have an idea of what I want to do. Maybe in a week or so, I'll have a demo working.

You're not recursing 300 levels deep; you abandon a subpath as soon as it doesn't match.

As for the anagrams, that sounds about right (if you install an anagram generator like wordplay, you can see that it generates a similar amount of matches).

You may want to devise a compact representation for a partly calculated results list, and just show n per page, with "prev" and "next" links that encode the original phrase and the first or last phrase on the current page.

When the user clicks "next", you run the algorithm as usual, but at each step of the trie search, you only search letters that are greater or equal to the current letter in the last known phrase.

You may also train a classifier like CRM114 to recognize "funny" and "boring" phrases, and omit the boring ones (except in your "prev" and "next" links!)

I agree, this is compelling for a lot of the same reasons as the anagrams problem. I spent weeks playing with anagram code at one point, and like you I felt an immediate compulsion to start writing code for Sling Blade Runner. So far my (ruby) code just does the obvious: builds the graph connecting up the movies and then uses brute force to find all chains of length two, then three, etc. Bogs down at chain length of about 11. Added some quick and dirty optimizations and pruning heuristics, and I'm geting chains in the mid-hundreds. I think this approach can be extended further, but isn't particularly clever :-/.

Dunno if they are good for hiring, but some look fun to try for a little hobbying.

I'm curious, how useful to people think these kinds of puzzles are in hiring?

To use a recent movie quote: "If you can dodge a wrench, you can dodge a ball."

ITA's business is all about dealing with fiendishly clever transforms on small-ish sets of data, and the results are needed Right Now. Most of the hiring puzzles revolve around that theme.

Much like any other company giving these kinds of problems, it's not about bringing out that cleverness every day, but it's about figuring out who has the ability to think in that way, along with the persistence to work on the problem until it's done.

I agree with the concept, but at some point it became trivia, which kills the point.

Classic ITA paper that shows you the complex problems they deal with:

http://www.demarcken.org/carl/papers/ITA-software-travel-com...

They produce more false negatives than false positives. If you aren't in a hurry to grow, thats a good thing. Even "cheating" (memorizing the techniques) to the point of being able to solve a problem on site (which is part of the interview) is not trivial.

What do you mean by false negative?

false negative = filtering out good candidates

false positive = allowing bad candidate to pass

False negative = Type I error

False positive = Type II error

Like you said, these problems filter out the people who would be great for getting stuff done and helping you build your software quickly (i.e. more practical people who find these problems a bother). But perhaps you don't always want that kind of person.

Personally, I find these problems interesting but the one I liked the most was the instant search because it had an element of user interaction rather than mere algorithmic problem solving, so I guess I might be the one filtered out :)

I solved the Instant Search problem when I was applying there for an internship. The puzzles aren't required for internships, but I figured it could only help, and I landed the internship. Was a great experience!

For my solution, I tried both tries and hash tables, and I found them to perform at more or less the same level. I later experimented with suffix trees, which I think is probably the best way to go for that problem.

I never liked the practice of hiring puzzles. I love coding useful things. Working on a hiring puzzle feels like jumping through hoops which is something I prefer to avoid.

Perhaps, but did you notice that one of the puzzles actually involves scraping through ITA's own database to find round-trip flights to Chicago? That seemed like a good touch, asking the interviewee to replicate a small part of ITA's own functionality so they could understand the magnitude of the problem.

Actually it sounds like a pretty easy problem from this far out, but maybe if I actually worked on it I'd discover it was trickier than I thought.

Sounds cool, I'd gladly do something like that if they were paying me. I think a good solution is to define a well-scoped project and bring candidates on board on a contract basis to implement them. This contract basis project can even be done remotely. This offers the candidate a chance to learn about you, you can learn about the candidate, and in the end you can both decide what is best for you.

Years ago when I was still in high school I somehow stumbled upon these and tried a few out (the one with the one time pad and the movie titles). I certainly was not ready to tackle them at the time, but even when failing I learned a lot. Years later I ran into a paper on finding the shortest path in a directed graph with negative cycles and it reminded me of all of my attempts to do the same.

It is a shame they don't have a post-mortem after they retire the problems. I really enjoyed reading the break down of one of them ( http://conway.rutgers.edu/~ccshan/wiki/blog/posts/WordNumber... ) even though I did not attempt it.

I like " Decrypting the Two-Time Pad (hard!)" (http://www.itasoftware.com/careers/puzzle_archive.html?catid... the Two-Time Pad)

In the past, ITA seemed to be focused on Lisp. I hadn't looked at the puzzles in a number of years, but the newer ones seem focused on Java. Anyone know if that signals a change at ITA? A move from Lisp to Java? Perhaps more customer-facing code?

In any case, their puzzles are always good for a brain workout.

ITA still uses Common Lisp. There are excellent blog entries on this matter by Dan Weinreb: <http://danweinreb.org/blog/category/ita-software>. However, they don't require Common Lisp knowledge from new hires. The beauty of Common Lisp is that there really is very little syntax to learn. Afaik, the simply use the excellent Practical Common Lisp book by Peter Seibel as a "training manual".

The problem with Common Lisp, unfortunately, is there's no standard and cross-implementation way to create an application that makes heavy use of network I/O, multi-processing/multi-threading and the file system.

That's would not be a problem internally at ITA (where must have built a standard set of libraries), but it would be a problem for taking submissions for web applications from applicants. On the other hand, even making a complete end-to-end webapp is a part of the Java standard. I am guessing that's why the puzzles that require talking HTTP either to or from a web server require Java.

Several of their other puzzles, however, don't specify a programming language (e.g., bit vector, word rectangle) and could probably be very well suited to being done in a Lisp.

Reply on news.ycombinator.com