Agree. When I'm interviewing I'm trying to evaluate if the candidate will be able to do a real job. In the real world you're coming up with answers to a novel problem. There's no way to know what the complexity of the optimal solution is (unless you can prove it, which doesn't happen outside of a classroom).