I agree with you. I put more the emphasis on the optimality of the solutions because that was the feedback from the recruiter. During the interviews, I made sure to talk through the problems indeed. That is a whole skill in itself.