What memorized algorithm does this test for? As far as I know there is no algorithm to do this, and this interview tests for algorithm design rather than memorization.
1. having seen the specific class of problem before and knowing, as you're writing that solution, to stop and switch to the class of solution you've seen before that would solve the problem more efficiently, or
2. finishing the obvious, poorly performing solution and then optimizing it like an real engineer would do. The problem is that there's not going to be enough time for this to occur in the interview session. The act of writing out the poorly performing solution will consume the entire session.
Therefore, the only way someone would have passed your interview question would have been if they had seen this class of problem before.
If someone fails to design anything more sophisticated than number 1 despite my guidance, or takes an unreasonable amount of time to implement it, that’s a signal.
Also, let’s keep in mind a hiring recommendation isn’t a judgment of a person’a abilities as an engineer, it’s a judgement of how badly we should be trying to hire them relative to other candidates. My LNH is a statement that the candidate is solid but not stellar enough to extend an offer to. If our hiring pool were restricted or we needed to hire more people my assessment would be accordingly softened.