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.