[taeric]

It seems the holy grail is almost always linear. Especially in interviews. Main thing to look for is if you find yourself doing something you have already done before.

Above that, just know the general idea behind different data structures. HashTables and binary trees will probably have you covered. More data structures can't hurt, though. Tries, BTrees, etc.

Though, I can't think of a single time I have used some of the more advanced items. Linear searches with sentinal values being my personal favorite optimization that I will likely never directly code.

[AgentIcarus]

That's a really good point, thanks taeric.

Anything less than O(n) obviously means not needing to look at every element of the input, i.e. it's already sorted or similar. For most other interview problems that seems like a reasonable lower bound in the absence of more detailed analysis. I guess the recruiter's advice to go practice on TopCoder wasn't just copy-paste.