So. Having just messed up an interview at a large tech company by having trouble deriving an O(n) solution on the whiteboard, anyone got any good tips on how to take algorithms / data structures to the next level and look good at this sort of thing?
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.
Most of the things you're going to run into on a daily basis are going to follow the same pattern, and so you just get an intuitive sense of runtimes after a little while. At my first internship, whenever I wrote a new function, I would mentally take note of what the runtime complexity was, which served two purposes:
1) It got me into the habit of thinking about runtime complexities.
2) It forced me to think about why different operations have different runtimes, which made them easy to reason about in the vast majority of cases.
If you're having a hard time thinking about complexity analysis, the same process might work for you.
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.
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.
http://ocw.mit.edu/courses/electrical-engineering-and-comput...
"Introduction to Algorithms" (2005) but according to OCW more similar to what's now the more advanced "Design and Analysis of Algorithms".
Not sure how much it'll help you in deriving solutions, but good if you have an interest in actually learning the subject.