The problem is that the candidate has been assured that they will be asked 'leet' code questions where solving the problem isn't enough, they will also be asked about O notation and how the code can be optimized and whether to use memoization or recursion. This is what the books will tell you, this is what YouTube will tell you, this is what 'helpful' recruiters will tell you.
And IME this is what most interviewers have been taught. They've got a list of sample questions, they've been told that if they give the knapsack problem and the interviewee doesn't immediately call out 'dynamic programming' than the interviewee is a pass.
If you only want to see working code than you are the exception rather than the rule.
I will ask all of those questions. But I don't expect perfect answers. You should at least know what big O is. I would really like it if you can tell an O(n^2) algorithm from a linear one. (That is often really important in real-world code). I would like you to consider different ways you can optimize the code.
I don't expect you to quickly crank out a novel optimal algorithm. But I like to see that you can think about how to solve problems programmatically. I would like to see you can identify differences in different algorithms and what tradeoffs there are. Considering different approaches that may be faster also shows that you didn't just memorize an algorithm from somewhere but that too took time to actual understand the problem and build a mental model in your head.
I have given people great reviews when they couldn't come up with a working algorthim because the clearly knew how to think like a programmer and considered all of the important things.
As an electrical engineer who has basically always worked as an embedded programmer, I don't know what big O is. But, I'm probably not applying for your open positions.
It definitely depends on the domain. In embedded programming you can often know that your n is small for your algorithms. If you are making a desktop app or web service it is very important to prepare for people using your service in unexpected ways and a super linear algorithm can result in terrible performance or downtime if not managed correctly.
They only want to see somebody who can get working code and a glimpse of their thought process. But from 100s of mediocre examples, the better coder will have a "better thought process."
Same goes for dating. Of course people will swear up and down they "only consider personality." Turns out, they've met 10 other people with a better personality than you.
Just because they're "only looking for x" doesn't mean they'll accept anybody that clears the bar.
The ultimate read between the lines though is that "oh I'm only looking for xyz, nothing superhuman" in a process where you have 10,000 competitors and applicants will still require high performance on your part. It's just a nicety, a meaningless phrase.
And IME this is what most interviewers have been taught. They've got a list of sample questions, they've been told that if they give the knapsack problem and the interviewee doesn't immediately call out 'dynamic programming' than the interviewee is a pass.
If you only want to see working code than you are the exception rather than the rule.