[wirelessest]

Having given a lot of complexity interviews, I value a candidate who says, "This is O(n^2) and it seems like there's a faster way, but I can't see it" over one who stumbles on the right solution.

If they had to tell you your solution was slow, and a linear solution exists it might not be your inability to find it that made you mess up the interview. Get good at recognizing inefficient computation first, then worry about making it more efficient. On the job you can always consult a coworker/google, but if you don't know to do that you're going to ship some slow code.