The biggest total requires the optimal path for the stated constraints, those being the path must yield that biggest total.

They aren't asking for a good enough path, but for the best possible path, the one that gives the biggest total. That's the optimal path for this problem.

Probably a brute force search is the way to go, I certainly can't think of any way to thin this problem out without doing research, especially given the requirement that the optimal (maximum value) solution is required.

99 levels below the top, each time a binary decision, there's 2^99 = 6.34 * 10^29 paths only, won't take too long relative to the life of the universe since 2^99 nanoseconds is only 20 trillion years. That's the answer, might have a little problem with the sun burning out before the computation completes, but by that time you should be able to relocate using a warp drive. Good luck on the interview.

edit: Ah I just figured out the pruning algorithm that will solve it. And that's the answer too, I just gave it to you in the previous sentence if you read carefully. Obvious once you think of it, not until then. I doubt many people would figure it out without a hint. And with a hint only clever ones could get it. As a screening to send in resumes? Pretty useless. If you do get a response who's to say they didn't ask for hints on a message board or pay someone to solve it on rentacoder.

I had this one solved already, but thanks. See, think about it for 10 minutes and it's not hard.

I don't agree with that at all. Thinking for 10 minutes is not sufficient. There's two insights and neither are obvious until you get them. Assuming candidates will get them is like assuming quick sort will occur to them if they've never seen it before.

The minute you actually sat down and thought about it you got it, as did I, as would any of the better programmers I've worked with in my career. Walk halfway into an algorithm and it's clear. I wouldn't expect the average code schlepper to get this but that's the entire point. This ad suggests to me that's not what they're after.

Ended up being 5 lines of code in C.

(Cue: reactions from others that it's a one liner in Haskell, or that it's obviously simple and easy since the solution was so short.)

(The five lines didn't include the data, but a sixth very long line takes care of that if really felt to be part of the count.)