> It's pretty disheartening to write a simple and obviously correct implementation only to have the interviewer express their disappointment that you didn't use a particular optimization.

I almost always preface whiteboard coding sessions with "I'm going to write some dumb, slow code and then we can make it faster if you want. Sound OK?" I've never had anyone disagree with this, but if they tell you they want you to go straight to the clever solution, hey, now you know what they're looking for.