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

21–30 of 45 posts

Re: ITA Software's Hiring Puzzles

#21

Post by chime »

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

Re: ITA Software's Hiring Puzzles

#22

Post by chime »

jjs wrote: post #20
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…

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

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

Re: ITA Software's Hiring Puzzles

#23

Post by hugh3 »

raffi wrote: post #19
roundsquare wrote: post #2

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

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.

Re: ITA Software's Hiring Puzzles

#24

Post by jjs »

chime wrote: post #22
jjs wrote: post #20

Earlier quoted context omitted.

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

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

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.

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

Re: ITA Software's Hiring Puzzles

#25

Post by yesimahuman »

ynniv wrote: post #8
roundsquare wrote: post #2

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

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.

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

Re: ITA Software's Hiring Puzzles

#26

Post by tedunangst »

chime wrote: post #21
jules wrote: post #11

Earlier quoted context omitted.

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

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.

Re: ITA Software's Hiring Puzzles

#27

Post by r00k »

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.

Re: ITA Software's Hiring Puzzles

#28

Post by pwk »

chime wrote: post #21
jules wrote: post #11

Earlier quoted context omitted.

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

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/

Re: ITA Software's Hiring Puzzles

#29

Post by pwk »

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…

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 :-/.

Re: ITA Software's Hiring Puzzles

#30

Post by raffi »

hugh3 wrote: post #23
raffi wrote: post #19

Earlier quoted context omitted.

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

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