Chapter 2 Build a Solid Foundation - The Complete Guide to Google Interview Preparation

Chapter 2 Build a Solid Foundation - The Complete Guide to Google Interview Preparation This is the second chapter for our The Complete Guide to Google Interview Preparation  series. If you pay attention to a lot of job requirements, you usually see things like “have a solid computer science foundation”. What does that actually mean? Apparently, it doesnt mean you have a computer science degree, nor does it mean you have written a lot of code. in reality, a solid computer science foundation means having a clear understanding of basic knowledge. In this chapter, Id like to delve into this topic and give you practical tips on how to build a solid foundation. I would say this is the entry point to Google interview preparation, but at the same time, its the most important step. The Shortest Path A lot of people are asking for “shortcut” for Google interview preparation. If there exists a shortcut, I would say its to focus on the computer science foundation. The tip here is to play the long game. The most common mistake is to practice coding questions before having a clear understanding of basic knowledge. These folks might have a “better” performance in the short term, however, they will come back to re-visit the basic knowledge sooner or later. This is because without fully understanding the basic data structures and algorithms, its almost impossible to come up with the right idea and write bug-free code. If you really want to be fast in preparation, spending enough effort on basic things will save you tons of time in the long run. I would strongly suggest people do not work on interview problems before you are confident with your foundation. What Do You Mean By Solid Foundation? Sometimes, people are asking me what do you really mean by solid computer science foundation? I can write code and I know bubble sort, does it mean Im good? For coding interviews, foundation mostly means clear understanding of basic data structures and algorithms. Ill explain this step by step in this post. But try to answer the following questions: How to do a search in a graph? What are the pros and cons of each approach? How to decide which one to use? For a list of objects, you can use linked list, array, stack, queue and other data structures. How would you decide which one to use? What is the biggest advantage/disadvantage? Whats the difference between dynamic programming and recursion? How do you compare a recursive solution and its iterative version? If I want to improve my solution from O(n^2) time complexity to O(nlogn), what algorithms come to your mind? How about O(n)? These are just some sample questions in my mind and if you cant answer all of them immediately, youd better re-visit your algorithm books. Lets decompose the computer science foundation step by step. Definition First and foremost, you should be clear about the definition of each basic data structure and algorithm. Most people have no trouble to explain what linked list is, but therere more about it. First, some concepts are a bit confusing. For example, a lot of candidates dont fully understand the difference between dynamic programming and recursion. Another example is stack vs heap and how they are used in memory. This post wont give you the specific answer, but if you just do a quick Google search, youll find all of them. Second, you should also be able to implement them. The best example is quick sort. The algorithm is not really easy in terms of implementation, but it could be very helpful. If you want to implement find the k-th largest number in an array, youll end up writing the same piece of code. BFS/DFS are also similar and a lot of interview questions are about writing BFS/DFS in essence (e.g. traverse a tree by level). Pros Cons The biggest trouble in an interview is that the candidate didnt know which data structure/algorithm to use. The root cause is that they never thought about pros cons about each data structure/algorithm. The idea is that all those basic data structures/algorithms are like your weapons, if you want to be able to use the right one at right time, you should be extremely familiar with their specialities. Fortunately, most resources and books group similar tools in the same big chapter. For example, linked list, array, stack, and queue are in a collection. BFS and DFS are in another collection. Lets take BFS and DFS as an example. In a tree structure, DFS will try to reach the deepest leaf, going back, and find another leaf. So a stack is used and it can be implemented both recursively (easier to write) and iteratively. The benefit is that when you want to check if a node is reachable or want to find a path from A to B, DFS is the best choice. Similarly, BFS traverse horizontally and a heap is used. If you want to find the length of the shortest path or traverse by level, you should use BFS. So the homework is for every single data structure/algorithm, you should ask yourself: what are the advantages/disadvantages? When will I use it? Complexity This is what a lot of people ignored. As an interview, for every coding question I asked, I will definitely ask about time and space complexity. By the same token, when reviewing data structures/algorithms, you should be clear about complexity. In fact, you should also do this for every question you have practiced. If you are super familiar with this, it can be extremely helpful when you try to figure out which algorithm to use. For example, the most common scenario is that your solution is slow and the interviewer asks you to optimize it. Suppose you have a O(n^2) approach, to make it faster, we can think in this way: Generally, to improve the speed, we can either choose a better data structure/algorithm or use more memory. If we want to make it O(nlogn), there are several available tools: binary search, sort, BST and so on. Maybe you should try to sort the array first and see if you can take advantage of this. To use more memory, hash is one option. Also, DP is a good way to optimize recursion. If you think in this way, your life will be much easier since you have fewer options to select. Summary There are a lot of resources about this topic like The Technical Interview Cheat Sheet and Big-O cheat sheet. Also the book Introduction to Algorithms is also recommended, though some sections are optional. As an interviewer, I will never pass a candidate who is confused about basic concepts. To me, its like the candidate is not sure what he is doing. On the contrary, even if someone doesnt solve the problem completely, he may still have a chance if everything is clear in his mind. I would recommend people go over all basic data structures/algorithms one by one. Understand the concept, figure out pros cons, and implement by yourself. Dont rush to practice coding questions before you are done in this step. By the way, if you want to have guidance from experienced interviewers, you can check Gainlo that allows you to have mock interview with engineers from Google, Facebook etc..