[grogers]

Great post about how to attack solving a problem using DP. But this is not a good interview question.

It's a toy problem, not something you'll ever need to solve in real life. Maybe if you squint hard enough it's close to pathfinding algorithms, but be serious. I hate questions that aren't remotely relatable to something the candidate might experience. I get that interviews are short so you need tiny problems, but making them somewhat relevant will make comprehending the problem that much easier and give plenty of time for working on a solution.

There's also not much depth to it. Either they can get a naive solution, get the DP solution, or just can't solve it. Maybe I'm just not creative enough but the only follow up I can think of is the typical 'how to test' and this isn't even a good question for that. For me as an interviewer, it is better to start with an easy problem, and then later on additional complexity. For example dealing with concurrency, how to generalize the solution for other cases, etc. These follow ups don't even usually need full code written out so you can get much deeper since it's faster. Whereas if you start from a hard/tricky problem and have to keep explaining it and hinting at how to solve it, both candidate and interviewer feel bad and you haven't learned much.

Not that this is a particularly hard problem, it will fit within an interview slot if they are on top of things. But it's similar enough to questions I hate asking/getting (e.g. min of maxes of sliding windows) that I would definitely never ask it.