I've only interviewed twice at Google for engineering so take this with a grain of salt.

Here are some things I would depriotize: ● Sorting: ○ Know how to sort. Don't do bubble-sort. ○ You should know the details of at least one nlog(n) sorting algorithm, preferably two (say, quicksort and merge sort). > I don't know anyone who has had to write a sort in an interview. Obviously you should know big O notation and also how they work, but practicing the implementation seems like a waste of time. In fact in my onsite, I used the .sort() method mentioned it was O(nlog(n)) and moved on to the rest of the problem. It was a minute part of the solution.

● Hash Tables: ○ Be prepared to explain how they work, and be able to implement one using only arrays in your favorite language, in about the space of one interview. > Again, while you should know how to use Hash Tables, I really don't think they would ask you to implement one.

● Trees and Graphs: * You should be familiar with at least one flavor of balanced binary tree, whether it's a red/black tree, a splay tree or an AVL tree, and you should know how it's implemented. > I actually still don't know how to build a balanced tree. It's never come up on any Big N interview I've had. The rest of this section is really important though, tree problems are extremely common in interviews.

○ If you get a chance, study up on fancier algorithms, such as Dijkstra and A (for graphs). > I dont know Dijkstra and I don't think it comes up that often. I have no idea what A is.

● Other data structures: ○ You should study up on as many other data structures and algorithms as possible. > I think if you know trees, tries, arrays, linked lists, and hash tables you will do fine. I only had one interview which had a different data structure (rope data structure) and the only reason he asked me the question was because I had never used it before. It was an intro question and if I said I knew it he wouldn't have given it to me. So I think if they give you another data structure, they are gonna assume you don't know it and will give you an intro question.

● Operating Systems, Systems Programming and Concurrency: ○ Know about processes, threads, and concurrency issues. Know about locks, mutexes, semaphores and monitors, and how they work. Know about deadlock and livelock and how to avoid them. > I don't know anything in this area (besides real basics on processes, threads, and locks). Never had a question here. I wouldn't study unless you are interviewing at team where this is relevant.

○ Know what resources a processes needs, a thread needs, how context switching works, and how it's initiated by the operating system and underlying hardware. ○ Know a little about scheduling. The world is rapidly moving towards multi-core, so know the fundamentals of "modern" concurrency constructs. > Again I don't know anything about OSes. I am not a CS major and never had a question in this area.do

● Data Structure Analysis and Discrete Math: ○ Some interviewers ask basic discrete math questions. This is more prevalent at Google than at other companies because we are surrounded by counting problems, probability problems, and other Discrete Math 101 situations. ○ Spend some time before the interview on the essentials of combinatorics and probability. You should be familiar with n-choose-k problems and their ilk – the more the better. > Also don't think this is that important. You should know how n choose k works (because that is needed for measuring complexity), but I definitely wouldn't spend my time on discrete math.

Thanks for replying. This is helpful stuff.

Did you pass either of those 2 Google interviews? And/or get offers from other similar companies?

> I only had one interview which had a different data structure (rope data structure) and the only reason he asked me the question was because I had never used it before. It was an intro question and if I said I knew it he wouldn't have given it to me. So I think if they give you another data structure, they are gonna assume you don't know it and will give you an intro question.

Can you explain that a little more?

Specifically: “they are gonna assume you don't know it and will give you an intro question.”

I failed the first time and passed the 2nd. I'm interviewing now so waiting to see if I get other offers.

To explain, one of the interviewers walked in and asked "have you heard of the rope data structure?"

I said "no" because I hadn't and he was like "great because otherwise I would give you another question". He then asked me to build 2 key functions for the data structure. I didn't need to study it beforehand, and if I did he would have gave me another question.

I think if they give you an uncommon data structure the expectation is that you have prior knowledge of it. This question was the favorite part of my interview loop (we chatted a bit about how google uses rope data structures)

Thanks for elaborating!

Was this part of the interview challenging? Seems to me like a surprise data structure coming up in an interview could be a bad thing (in terms of doing well).

Edit: What have your other interview experiences been like? Similar to Google, or would different/more preparation be required?

Also, what level are you at/interviewing for at these companies?