> Now, the obvious thing is N-squared and clearly terrible, but let's do it anyway and see if we can get some insight and improve it..."

By "let's do i anyway" do you mean to implement it? That's a terrible strat. You should not be touching the keyboard until you have an optimized or at least final design. If coding up the naive algorithm gives you some "insight" that you don't expect to have seen by thinking through the problem beforehand, you need to invest more in logical thinking.

This applies to both interviews and to your normal work.