Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

ITA Software's Hiring Puzzles

itasoftware.com

Post reply on HN
Print view View original

41–45 of 45 posts

Re: ITA Software's Hiring Puzzles

#41

Post by gradschool »

rman666 wrote: post #31
r00k wrote: post #27

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…

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.

Re: ITA Software's Hiring Puzzles

#42

Post by rimantas »

jules wrote: post #11
chime wrote: post #4

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 f…

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"], ...}

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

Re: ITA Software's Hiring Puzzles

#43

Post by mukyu »

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.

Re: ITA Software's Hiring Puzzles

#44

Post by strlen »

pge wrote: post #40

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: " rel="nofollow">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.

Re: ITA Software's Hiring Puzzles

#45

Post by infinite8s »

chime wrote: post #9
brown9-2 wrote: post #5

Earlier quoted context omitted.

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.

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.
Post reply on HN