[Mystrl]

Oh hey that's the question I got for my recent amazon onsite (slightly different constraints). I couldn't find the exact question online and I thought it was a "fair" medium question. IMO this is a pretty good question there's a really easy suboptimal solution so people don't get completely stuck, the optimizations are pretty straightforward and there's a lot of room to demonstrate you can write clean code.

*Fair meaning there's no crazy tricks to it or any obscure algorithms just applying DSA fundamentals.

[jmd42]

Right - I think it's fair to expect somebody to come up with some kind of approach to solving this, even if they've never encountered the problem or drilled Leetcode before. At least to be able to conceptualize the problem and make a decent attempt.

I wouldn't expect more than brute force. But being able to reason about this, having some working familiarity with graphs etc, is not an unfair bar.