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

31–40 of 45 posts

Re: ITA Software's Hiring Puzzles

#31

Post by rman666 »

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.

Re: ITA Software's Hiring Puzzles

#32

Post by dfranke »

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

Re: ITA Software's Hiring Puzzles

#33

Post by jules »

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…

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?

Re: ITA Software's Hiring Puzzles

#34

Post by sokoloff »

kaddar wrote: post #18

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

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.

Re: ITA Software's Hiring Puzzles

#35

Post by r00k »

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.

One word: tries.

Re: ITA Software's Hiring Puzzles

#37

Post by kaddar »

sokoloff wrote: post #34
kaddar wrote: post #18

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

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…

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.

Re: ITA Software's Hiring Puzzles

#38

Post by r00k »

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…

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.

Re: ITA Software's Hiring Puzzles

#39

Post by Psyonic »

yesimahuman wrote: post #25
ynniv wrote: post #8

Earlier quoted context omitted.

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

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.

Re: ITA Software's Hiring Puzzles

#40

Post by pge »

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.

Post reply on HN