Interview advice

(0) Think out loud. The interviewers aren't looking for the right answer (and the questions often don't have one right answer; see (1) below), but for how you think and how you interact with others while solving problems. Thinking out loud also makes it easier for the interviewer to direct the discussion where they want, and to push you in the right direction if you're stuck.

(1) Talk about tradeoffs. Interviewers will probably ask about this explicitly (e.g. "what if writes are super expensive" or "what if your input is a petabyte"), but you get bonus points for explicitly pointing out the places where you're making some tradeoff, and where you might do it a different way if you had more knowledge about the specific application. Talking about tradeoffs is especially important for really broad design questions (e.g. "how would you design Google search?")

(2) Brush up on data structures and algorithms. I tell this to people because they tend to over-emphasize becoming super fluent in some language. You will write actual code at the interview, but errors in syntax aren't a big deal (unless you claimed to be a language expert on your resume). Being able to find a good algorithm is worth way more points. Thinking about this stuff also addresses (1), because you end up thinking things like "I could have constant time reads and log(n) writes, or log(n) reads and constant time writes ... which do I want?"

(3) Make sure you can code up a recursion (e.g. any problem with backtracking, or depth-first search of a tree). I was surprised how often it happens that a candidate can describe a recursive algorithm extremely clearly, but then falls apart when asked to code it up. Also make sure you use a hash table whenever possible (e.g. if you just need to detect collisions, or if you don't need to keep stuff sorted).

(4) Know that hash tables are in practice constant time insertion and lookup, and they're good for detecting duplicates of anything.