Best Tech Interview Question I've Seen

We Recommend These Resources

I'm a curator of tech interview questions. I'm starting to work with our HR group on a tech recruiting strategy, so I've been looking for more questions. I got an email from a recruiter via a New York Java Meetup group (which is free). The email, of course describes the job requirements, but the best part of the email was the following section:

By starting at the top of the triangle and moving to adjacent numbers on the row below, the maximum total from top to bottom is 27.

5
9 6
4 6 8
0 7 1 5

I.e. 5 + 9 + 6 + 7 = 27. Write a program in a language of your choice to find the maximum total from top to bottom in triangle.txt, a text file containing a triangle with 100 rows. Send your solution and resume to [123456 AT yodle dot com], replacing 123456 with the maximum sum for the triangle.

I had to try to solve the puzzle to see what they did. I tried my first solution, and got my mail bounced back to me... I got immediate feedback from a "unit test." My second solution didn't work either. My third worked... I'm down to 5 lines of Groovy that take about 150 ms.

Yodle had a great job posting. Note: I don't work for Yodle, so if you want to speak with them, you'll have to figure out their culture. On the other hand, if you want a similar culture (at least in part of our HUGE company - SunGard is #380 on the fortune 500), and want to work in a variety of projects, you can always email me. If you can solve this puzzle (and possibly have some finance experience), the interview process will probably just a formality .

I'm going to have to work on something like yodle's for SunGard Consulting. We currently have job postings like this, which can definitely use some fine tuning.

<sales_pitch>If you want to hire some consultants who can solve those kinds of problems, you can email me for that as well.</sales_pitch>

From http://www.jroller.com/Solomon/entry/best_tech_interview_question_i

(Note: Opinions expressed in this article and its replies are the opinions of their respective authors and not those of DZone, Inc.)

Comments

Zqudlyba Navis replied on Thu, 2010/04/29 - 2:25am

Don't reinvent the wheel.

Reuse the puzzles used by Google in filtering out dud engineers.

LOL. If one can solve the puzzles used by Google, why wouldn't you apply for Google rather than CompanyX if CompanyX is using the same puzzles used by Google ?

Raveman Ravemanus replied on Thu, 2010/04/29 - 2:50am

I like the idea thay they send you unit test results.

The question is like all puzzle questions - something you will never do at work. However i dont care about this question at all, id give up and not even try to understand it. maybe i just dont like pointless math.

P.S.its a great question for mathematician, but they might not know how to write programs(however they should since we must know advance math)

Chris Treber replied on Thu, 2010/04/29 - 3:05am

1ms in Java on a 3GHz Dual Core machine (15ms with reading the file; 6 lines not counting imports, reading the file).

Thank you for posting the puzzle!

Chris

Endre Varga replied on Thu, 2010/04/29 - 3:32am

This is easy! The answer is Critical Path Method.

Endre Varga replied on Thu, 2010/04/29 - 3:37am

BTW, I read in an article, that those engineers, that scored bad in one of the Google questinons (1 or 2 from 5 IIRC), but the interviewer INSISTED on employing them anyway, tended to be perform ABOVE AVERAGE in the employed population. This is why I hate puzzles on interviews.

Chad Hahn replied on Thu, 2010/04/29 - 7:23am

In my experience, the guys who tend to excel at arbitrary problems like this are generally the ones that write the most unmaintainable code. Mark me down for 'least relevant to the work you'll actually be doing tech interview questions', I've seen.

Solomon Duskis replied on Thu, 2010/04/29 - 12:30pm in response to: Chad Hahn

Chad, I'd love to hear more about what you think works well.

Solomon Duskis replied on Thu, 2010/04/29 - 12:31pm in response to: Raveman Ravemanus

Raveman, do you have any better suggestions? I'm all ears.

Chad Hahn replied on Thu, 2010/04/29 - 1:04pm in response to: Solomon Duskis

Solomon,

Couple of thoughts of mine and then two good really good posts by Norman Richards and Neil McAllister, IMO.

http://codegoop.com/2010/01/the-tech-interview-test/

http://codegoop.com/2010/03/interview-the-process

Besides all of those things, I like to ask interview candidates what programming books they have read recently and ever. Bonus points for having read Clean Code, Coders at Work, Effective Java, Code Complete, and a whole bunch of others. Devs who don't read books throw up lots of red flags.

Bino B. Manjasseril replied on Thu, 2010/04/29 - 3:04pm

The interesting thing is, as a programmer/developer you wouldn't most likely be solving these kind of puzzles at work. I have been in software development for about 10 years and never came across a 'puzzle' kind of issue. I would rather check the candidate's design skills (e.g: OO concepts). Good design = maintainable/extensible/reusable code. Any intelligent person can solve puzzles, but experience and craftsmanship makes good programmers.

Johan Hoogenboezem replied on Fri, 2010/04/30 - 12:30am

That puzzle looks like problem#18 at The Euler Project. If you think it is easy, try #67.

Dimitris Andreou replied on Fri, 2010/04/30 - 1:08am in response to: Endre Varga

I hope this was a joke!

Artur Biesiadowski replied on Fri, 2010/04/30 - 1:16am

Trick is that it is neither MATH puzzle or pointless code. All you comments would make sense, if we were talking about some obscure math equations or 'ooh, I get it' puzzle. Here it is most basic thing from graph theory, difficulty is not in thinking about actual solution, but not messing up data structures to hold the intermediate data when implementing it. And it is real life, at least if you do anything else than CRUD web apps. We had almost exactly same problem (when we had to find minimum or maximum of elements in structured graph-like structure) in efficient way - and I'm talking about thousands of nodes, tens of thousands times per second. First implementation by a guy who didn't care was talking 1-2 seconds per batch of hundred or so... Another attempt by guy who cared was able to process is fast enough to no show in profile...

So no, you don't have to care - but then don't expect to find jobs in really well paid sectors like investment banking... Of course, being able to solve that triangle thingy is not enough by any means - but understanding how it relates to real problems is a good start.

Dimitris Andreou replied on Fri, 2010/04/30 - 1:29am

My suggestion is, be sure to find the best solution in the puzzle before criticizing it and all puzzles in general. In particular, failure to efficiently solve this one immediately suggests lack of understanding of a major algorithmic paradigm, which is pretty nasty if one claims to have studied CS.

Endre Varga replied on Fri, 2010/04/30 - 2:17am in response to: Artur Biesiadowski

I agree on this. There are many ways to solve the problem. One can build a graph and use a traditional CPM algorithm to solve it. This is also quite maintainable, as the shape of the graph could be arbitrary, not just the one given in the problem. If performance is an issue, then it is possible to exploit the special tiered structure of the graph and keeping only two lines in memory. If multi-core environment is available, and performance is really important, one can use paralellization. At first stage, one can divide the IO and CPU bound parts and build a pipeline. One can also divide the CPM calculation part quite easily. My opinion, however, that puzzles are good for a rough pre-filter, filtering out the really useless guys, but trial employment is the way to find the realy good ones.

Eric Samson replied on Fri, 2010/04/30 - 5:22am

Hi guys, I found the problem funny and I tried to solve it. NB: I'm not a programmer, but I used to be 2 decades ago. I decided to use Groovy, even if I'm new to it (I like the possibilities of this language). I faced some minor problems due to the Groovy syntax being new to me but I think I now have a solution, after 4 hours of work. I'd like to test my result, but I don't want to send my resume. Who can check my answer privately? Best regards, Eric.

Solomon Duskis replied on Sun, 2010/05/02 - 12:57pm in response to: Eric Samson

Hey Eric,

I don't have your email address... You're more than welcome to send me the answer. While I'm looking resumes, I'm definitely more interested in meeting techies and discussing what makes a good interview question. You can also send an email to the Yodle guys. The Yodle folks will also be more than happy to say hello without a resume. Their recruiter is a great guy; I got to meet him because of this exercise.

-Solomon

Abhishek Chavan replied on Mon, 2010/05/03 - 12:12am in response to: Chad Hahn

Chad, I am a amateur Java Developer in search for expanding my knowledge base. I have read Effective Java. Could you recommend some other good books/ Languages i can read/learn. Thanks Abhishek

Chris Treber replied on Wed, 2010/05/05 - 3:28am in response to: Chad Hahn

Amen.

Gilbert Le Blanc replied on Mon, 2010/05/10 - 2:32pm

You have the right idea in that problem solving can weed out those that don't know algorithms.

As long as the problem has something to do with the work to be done, problem solving has its place.

I participated in TopCoder speed coding contests a while back. I found that the problems were designed to differentiate between the top coders. Those of us on the lower tiers were lumped together as "coders that couldn't solve the problems quickly".

You have to be careful that you don’t weed out people that can contribute to your company, just not in a problem solving way.

I think I solved the triangle math puzzle. I coded two different algorithms, and was stuck on the second algorithm for a while because I ran out of memory space. My solution is 250+ lines of Java, but that includes some debugging code. Yes, I over engineered the solution. But I think coding displays and tests when solving an algorithm is important.