[AgentIcarus]

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?

[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.

[ShaneWilton]

Really, unless you're trying to find a tighter upper bound on something like matrix multiplication, it just comes down to practice.

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.

[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.

[cdr]

As far as analysis, I believe this is the course I followed awhile back on MIT OCW and found quite good:

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.

[apendleton]

Project Euler is great for practicing this sort of thing. With the early questions, you can solve them however and it's fine, but many of the later problems have an obvious quadratic (or worse) solution that ends up being too slow in practice to finish in a sane amount of time, and it forces you to come up with a better algorithm to actually solve the puzzle. As a bonus, once you solve it you get to see other people's solutions, which are often super clever.

[bcbrown]

Pick up the book Elements of Programming Interviews and practice.