Good Read
Last active
February 22, 2020 05:04
-
-
Save binhp/fb1b8c9a9452e6dcca1f1700f3781a2e to your computer and use it in GitHub Desktop.
Awesome Articles For Developers
Passing the Google Interview. Every engineer’s dream.
After all, why wouldn’t you want to work at Google with the free food, cushy salary, and credentials that will make you set for life?
Ace the google interview
The “Google Interview” is a methodology of technical interviewing that has been widely used and popularized by the tech giant, Google. It serves as the ultimate test to determine whether you have the coding and algorithmic chops to develop software with the best.
It is a crucial measuring stick by which your technical prowess is assessed and arguably the most important determining factor in Google’s decision to go “hire” or “no hire”.
If you want to stack the deck in your favor when interviewing at Google you need to develop a strategy for attacking the most critical parts of what you will encounter. In this post, I’ll show you how.
As the style of interview that Google uses has been so widely emulated, this post will also help you interview at most other large tech companies. So sit back and let’s dig in.
In this post, you will learn:
What is the Google Interview?
How is the Google Interview different from other companies?
How to prepare for the Google Phone Interview and Google Onsite Interview
The most common Google Interview questions
Addition Google Interview resources
What exactly is the Google Interview? What should you expect when you walk into the room?
The Google Interview is not like many other interviews. If you’ve done coding interviews before, this will likely sound familiar, but if not, it’ll be pretty different than what you’re used to.
There are three key types of problems that you are likely to see in your Google interview:
Coding Interview Questions
Given: A coding challenge that relies on knowledge of data structures and algorithms.
Output: Ability to provide an efficient and optimized solution to the problem under the timing constraints of the interview.
System Design Questions
Given: A vague high-level problem that involves designing a complicated system. For example, the interviewer may want you to design Gmail.
Output: Ability to work with the interviewer to determine what the critical components of the system are and design a solution with scalability in mind.
General Analysis Questions
Given: A mathematical, design, or opinion-based question where the interviewer wants to investigate your thought process and how you would proceed as an employee.
Output: Provide a number of different solutions and be able to justify each one with a list of pros and cons. These can be a litmus test for telling the interviewer what you would be like to work with.
The majority of the Google interview consists of coding, and this is what the focus of this post specifically will be about. See this post for strategies on acing your system design interview.
Google isn’t shy about sharing their hiring practices. In fact they have a whole page dedicated to exactly that.
The interview process begins with at least one phone screen and, if successful, a series of onsite interviews. The Google phone screen and onsite portions are fairly typical across the board of technical interviewing, but the process at Google is unique in a couple specific details: The Google Phone Interview
For the phone screen, you are interviewed by at least one Google employee who provides you with a coding question. You share a Google document with the interviewer and use it to write code for the question asked by the interviewer.
Protip: Coding in Google Docs sucks, but if you update your preferences it can make your life 1000x better. Learn how to do that here.
This interview will focus on your ability to produce code without an IDE (integrated development environment). Typically, the question asked will be one that can be solved by a brute-force solution, and then progressively improved upon.
The phone interview is about 30-45 minutes. Assuming you did well, the Google recruiter will reach back out to you to give you the next steps if they decide to move along with you.
Don’t be disappointed if they ask to do a second phone interview. That’s totally normal if they don’t feel like they were able to adequately assess you the first time and doesn't have any bearing on your later interviews. The Google Onsite Interview
The Google onsite round involves speaking to a number of Googlers. Usually this will include four to six separate interviews, including one “lunch interview”.
Generally, you will be asked primarily coding interview questions and potentially one or two system design questions as well.
The more experience you have, the higher proportion of system design and topic-specific questions you can expect to be asked. Google rarely asks any system design questions to engineers with less than 5 years of experience.
Each interviewer collects feedback on how well you performed during the one-on-one interview with you. This feedback is collected by each interviewer independently as to eliminate cross-chatter and biases between your interviewers. If you felt as if you performed subpar in one of the interviews, that baggage stays there and does not follow you into the next interview. After the Interview
At the end of your interviews, all of the feedback is collected and a decision is made based on the feedback. You’re graded on a scale of 1-4 in a bunch of different categories including your coding experience, analytical ability, etc.
This feedback then gets sent to a hiring committee to decide on whether or not to make a “hire” or “no-hire” decision. Assuming things go well, you’ll move on to the more logistical side of things including discussing compensation and the like.
If not, you always have the option to re-apply in 6 months to a year. The idea here is that during this time, you can rally back and improve your skills and experience so that the next time, you’ll be in a better position to apply.
While it is not uncommon for eventual employees of Google to fail the onsite interviews, it can really suck after putting in so much time and effort. On top of that, having the wait half the year to apply again can be disorienting and throw your initial plans out the window.
Nothing in life is a guarantee, but stacking the deck in your favor and preparing the right material in the right way is something that is within your control. From here, I’ll show you exactly how to prepare for the Google interview.
In order to improve your chances of acing the Google interview, and to prevent you from having to spend another 6-months waiting to reapply, you should definitely stack the odds in your favor and prepare.
But how do you prepare effectively? There is no shortage of websites like HackerRank, LeetCode, ProjectEuler, TopCoder, etc. that serve as technical interviewing problem farms.
Sure, you could spend your time grinding through every single problem on LeetCode, but is the massive time investment really worth it? Is there a more efficient way you could be preparing?
Everyone has a finite amount of time and energy, and therefore using both resources as effectively as possible is an important factor in optimizing for both. Deliberate, consistent, and targeted practice is integral to successfully navigate the Google interview. Practice like you Play
Effective practice is realistic practice.
In the midst of an interview, you want to be focused and able to spend the majority of your mental energy on the problem given from the interviewer. You don’t want to be thrown off by extraneous factors such as not being used to writing code in a non-IDE environment.
Here is a list of factors that you should be mindful of when developing your practice regimen. Time Constraints
The phone interview is 30-45 minutes, and each of the one-on-one onsite interviews will be roughly 45 minutes to an hour each. In each of these scenarios, you will be presented with at least one question, which, in most cases, is a coding category question.
In order to effectively practice under time constraints, one strategy would be to select one specific problem.
For instance, selecting a problem from one of the book or video resources under the Additional Resources section of this post would be a good place to start. Then, start a timer and attempt to solve the problem without access to an IDE.
Following this practice for a few different categories of questions will give you some signal with respect to how you are faring with time constraints. Getting optimal solutions within the time interval of 30-45 minutes consistently for problems of varying difficulty is the ultimate goal. If you are struggling to hit this goal, use this as an opportunity to tighten up this area is something you will need to work on. Whiteboarding
For both the Google phone interview and the onsite, you will be expected to produce syntactically correct code in the absence of an IDE. Point blank, this part is really hard.
For the phone interview, it will be on a Google document, and for the onsite interview, it will be writing code on a whiteboard. Writing correct code on a whiteboard can be disorienting at first if you have never practiced it.
Without the aid of an editor or IDE, writing correct code can be difficult to do. Therefore, when practicing for the Google interview, it is critical to practice in the absence of any editor and under the time constraints that you would encounter in the interview.
After you’ve done the interview, it’s helpful to copy your code verbatim into an editor and try to run it. You may be surprised to find that the code you wrote on the whiteboard has a number of compilation errors.
In order to avoid this fate during the interview, it is crucial that you practice your solutions on paper.
You must also ensure that you are very familiar with the language you are using to interview with. While you can ask your interviewer for a library function to perform some task, this wastes time and reflects poorly on your preparation and domain knowledge. Pressure Constraints
When you are the one being interviewed, you are the center of attention and all eyes and ears are on you.
Being self-conscious or just feeling quite uncomfortable during your interview when you are expected to solve a challenging problem in a timed manner in an unorthodox way with someone staring at you can make just about anyone uncomfortable and diminish their performance.
One of the best ways to reduce performance anxiety is to practice using the above techniques of time pressure and whiteboarding, but to do so in front of a peer. You may be pursuing this goal of landing a job at Google in isolation, and therefore not have any peers in close proximity.
In this case, Pramp is a great way to cover this base. Pramp randomly matches you with a programming peer. You ask your peer a question and play the role of the interviewer for 30 minutes, and then the roles reverse and you play the part of the interviewee for 30 minutes.
Protip: With Pramp you also get the benefit of learning what it’s like to be an interviewer. That’s a good perspective to have. Testing and Edge Cases
When you develop a solution for a given problem, you’ll want to make sure that you cover extraneous cases that may be caused by unexpected inputs. This is a good habit to get into and it definitely gives you brownie points with the interviewer to show them that you are thinking about what could go wrong with your code.
In addition to isolating edge cases, you’ll want to propose solutions for what happens when those cases are encountered.
If you find yourself having solved a given coding problem within the time limit you have allotted for yourself, it’s a good idea to write a few unit tests and to really think about the edge cases you may have missed when coding up your initial solution.
Getting in the habit of thinking with tests that you would or should write allows you to predict a series of questions from the interviewer. If you practice this, it will become more automatic, and when you are asked during the interview, you won’t be thrown off guard. Practice Material is Key
Taking up a practice regimen that covers everything we’ve already talked about is great, but focusing on right material is key.
While you could blindly grind through LeetCode, your overall ability to succeed at the Google interview would not improve too much with each randomly selected question.
Instead, what if the questions you worked through were questions that were known to show up in the context of past Google interviews? Narrowing your focus down to this shorter list of categories and questions would be an ideal manner in which to focus your time and energy.
In the next section, we will look at the specific categories and questions that Google appears to favor.
As I mentioned in the previous section, “practice material is key”. Therefore, the types of questions that we spend our time practicing is important, especially if we are targeting a specific company.
With this in mind, we decided to gather some data regarding the types of questions that are typically asked in Google interviews.
We combed through the website Glassdoor to find specific examples of what people had experienced in their Google interview.
Glassdoor has a page dedicated to Google, and individuals who have interviewed at Google give a review on their experience. This often includes specifics as to what problems, or at least, what types of problems they were asked during their interview.
After parsing through a couple hundred interview experiences from Glassdoor for Google and obtained the following distribution of the types of problems that were generally encountered in a Google interview.
Google Interview Question breakdown
Excluding the “system design” category and sticking to the “coding” category of questions, the top three categories are:
- Graphs and Trees
- Arrays and String Processing
- Recursion and Dynamic Programming
Protip: Google generally only asks system design questions to candidates with at least 3-5 years of software engineering experience.
As these categories appear to be favored by Google, spending the bulk of your practice time on these topics would be a worthwhile endeavor. The next few sections provide some information as to how to focus on developing your skills in these specific categories. Graphs and trees
Note: This section will rely heavily on this Binary Tree YouTube playlist. A complete implementation of the binary tree code that we cover in this section can be found on on Github here.
Trees, and their more elaborate superset counterpart, graphs, are a common type of data structure that arise in the majority of problems we analyzed from Glassdoor.
Familiarity with designing, navigating, and manipulating such structures to solve problems is critically important to your probability of success.
One strategy for testing your own command of these types of structures is to start by first coding up your own implementation of a type of tree or graph.
For instance, let us say that we begin by deeply diving into binary trees. Assuming you understand the idea of a binary tree, you know that it consists of node objects.
Each node has a few attributes, namely a specific data field that consists of the content stored at that node in addition to a left and right pointer that refer to the respective left and right child, if any, of the node. Using Python, we can define a Node class as follows:
class Node(object):
def __init__(self, value):
self.value = value
self.left = None
self.right = None
We can also put together a BinaryTree class that will be constructed out of Node objects
class BinaryTree(object):
def __init__(self, root):
self.root = Node(root)
Once we have this basic structure in place, we can now construct a simple BinaryTree object:
# Set up binary tree:
tree = BinaryTree(1)
tree.root.left = Node(2)
tree.root.right = Node(3)
This binary tree is one where the root contains the value of 1, the left child contains the value 2, and the right child of the root contains the value 3.
Here is a good refresher on binary trees.
Now, once you have the rough scaffolding for a binary tree object, knowing how to traverse the structure is crucial to properly utilizing it.
Knowing the standard post-order, pre-order, and in-order traversal algorithms are the basic building blocks of how to navigate the tree.
Taking our understanding one step further, we want to see how deeply we truly understand the binary tree data structure. My suggestion here is to test your own skills in this regard by attempting to solve some binary tree problems.
For instance, one of the more gradual things you could try, assuming you’ve followed this far, is to attempt to implement a level-order traversal, that is, a traversal which prints out all of the nodes of the binary tree from top to bottom and left to right.
Try to solve this problem using the tactics that we described in the earlier part of this post, namely, where you enforce time and pressure constraints and solve the problem on paper or a whiteboard.
From there, you can attempt to build on your knowledge of the binary tree structure and how best to utilize it with other problems such as calculating the size of a binary tree and calculating the height of a binary tree.
This gradual process allows you to cumulatively build upon or refresh your knowledge of a given data structure. While this might be overkill for all data structures, taking a gradual and in-depth approach like this can be very helpful for developing a very breadth-heavy understanding of a given data structure and how to use it for certain problems. Arrays and strings
The category of arrays and strings are grouped together as one because processing a string can often be thought of as performing some type of array manipulation.
The array data structure, (or list if you’re using a language like Python) is a fundamental building block for just about any problem that you are going to receive in your Google interview.
Having a solid understanding of the basics of the array structure, including an understanding of the complexity analysis of storing, retrieving, etc. from an array is essential to know and quickly apply to the problem at hand.
Let us look at a problem from our free 50 Interview Questions Guide. Specifically, let’s look at problem 4 which is “find duplicates”. The question is:
Given an array of integers where each value 1 <= x <= len(array), write a function that finds all the duplicates in the array.
For example:
dups([1, 2, 3]) = []
dups([1, 2, 2]) = [2]
dups([3, 3, 3]) = [3]
dups([2, 1, 2, 1]) = [1, 2]
You can find more info on this problem here.
As we’ve previously written, it’s usually a good idea to start with a brute force solution to a problem. Sure, it won’t be the final solution, but it’s a solution that will solve the problem, which is surely optimal to not making progress on the problem while you are staring at the whiteboard blankly.
So what is the brute-force solution here? Well, you could process the array one element at a time, and in doing so, check the remaining elements to see if any of the other elements in the array are equal to the one you are processing.
For instance, something like this would provide the correct answer with that approach:
def dups(A):
dups = {}
for i in range(len(A)):
num = A[i]
for j in range(i+1, len(A)):
if num == A[j]:
dups[num] = num
return list(dups.keys())
What is the runtime of this code? Well, we have the outer loop going through the array and the inner loop going through the remaining elements as we progress through the array. This will yield an O(n2) algorithm.
Okay, so not great, but it’s a starting point. We can improve on this solution a bit by taking advantage of the built-in set() function that Python offers. Other languages will have a similar style of algorithm.
The gist of how this improved algorithm will work is that we can create a set object and iterate through out input list. If the element that we are iterating through is not in the set, add it to the set. Otherwise, continue processing the list.
This code for how to implement this is given as:
def dups(A):
s = set()
for i in A:
if i not in s:
s.add(i)
return list(s)
So we have taken our O(n2) algorithm and improved it to an O(n) algorithm. It also now takes O(n) space for storing the elements into our set. Can we improve this solution?
Well, we can improve on the space and reduce the space to constant.
If we sort our input array, we can then iterate through the array and check if the element we are processing differs from the next element in the array. If it does not, we have a duplicate and we can process that accordingly. If instead it is increasing, we continue processing the array.
The code for this would be something like:
def dups(A):
A = sorted(A)
s = set()
for i in range(len(A)-1):
if A[i] == A[i+1]:
s.add(A[i])
return list(s)
So we have improved our space to O(1), but incurred more of a hit on time, as sorting is going to dominate the time complexity with O(n log n).
Okay, so we have a few approaches here and they all have varying trade-offs with respect to time and space. One thing that we should perhaps do is look again at the question to see if there are any specific attributes of the question we can leverage to our advantage.
Looking again, we indeed see that we have a guaranteed precondition that guarantees that each value 1 <= x <= len(array). The idea or “trick” here is to think about how we can go about encoding that we have already seen a certain number without using any additional data structures and keeping our space complexity constant.
Using the fact that all of the numbers in the array range from 1 to the length of the array, we can encode those in the existing array data structure. So we will be making use of the space that has already been allocated to us from the input that we are given.
Let us take a look at a specific input example to see how our new and improved approach will work. Take the input to be the list [2, 1, 2, 1]. Just to reiterate, we know that every value in the array we are given is between 1 and the total length of the array we are provided.
One thing that will make this easier for us is to subtract one from the values of the list so that our condition becomes that each value in the array ranges from 0 <= x <= len(array) - 1 instead of 1 <= x <= len(array).
Another key observation is that given the guaranteed precondition, we know that every value in the array will be a positive integer.
As we traverse through this array then, we can encode whether or not we have seen a particular number by flipping the sign of the index that the value corresponds to from positive to negative. If we stumble on a value with a negative sign, we know that we’ve previously encountered this value before and will add that value to our duplicate set.
To solidify this concept, let us again turn to our example input of [2, 1, 2, 1]. Iterating through each of the elements of this list, we see that the first value we encounter is 2. We now want to encode the fact that we have encountered a 2 in our array. So we need to calculate the index by subtracting one from the value, giving:
index = 2 - 1 = 1
Then, we flip the index corresponding to index 1 to a negative, giving us a list that now looks like this:
[2, -1, 2, 1]
Moving along in our list, we happen upon a -1, which we take the absolute value of to get the original value and calculate the index as we did before
index = 1 - 1 = 0
Now, we go to the index 0 in the array and flip the sign of that value from positive to negative giving us
[-2, -1, 2, 1]
So this list tells us that we have seen a 1 since we flipped the value of index 0 and that we have seen a 2 since we negated the value of index 1. Let’s carry on with the algorithm, we hit a second 2 giving us the index calculate of
index = 2 - 1 = 1
We check the value held at index 1 in the array, but this value is negative, indicating that we have already seen this value in our array. In this case then, we add this duplicate value to our result set.
Analyzing the above approach, we have an algorithm that takes O(n) time and uses O(1) space. The final code listing for this solution is provided below:
def dups(A):
result_set = set()
for i in range(len(A)):
# Translate the value into an index (1 <= x <= len(A))
index = abs(A[i] - 1)
# If the value at that index is negative, then we've already seen
# that value so it's a duplicate. Otherwise, negate the value at
# that index so we know we've seen it.
if A[index] < 0:
result_set.add(abs(A[i]))
else:
A[index] = -A[index]
# Return the array to its original state.
for i in range(len(A)):
A[i] = abs(A[i])
return list(result_set)
Check out this post for more info on common string and array patterns.
Recursion and dynamic programming
Recursion and dynamic programming go hand-in-hand. In order to solve a given problem with the strategy of dynamic programming, this typically involves first finding a recursive solution to the problem, and then finding a way in which to store and consult previous computations to prevent future unnecessary calculations.
Mastering both of these topics surely then requires a solid understanding of recursion. Furthermore, just understanding the idea of recursion is not sufficient, but the ability to quickly apply recursive thinking to a problem in a swift manner is key.
It goes without saying that the previous mentioned categories of popular problems, namely the tree/graph and array/string processing problems often require the use of recursion as well.
For instance, being problems such as finding the upper cases letter in a string, calculating the length of a string, or counting the number of consonants in a string are all problems that could be categorized as “string problems”, but also have very concise recursive solutions.
The key to solving a problem that requires recursion is develop a strategy for how to recognize, analyze, and solve recursive problems. For this, we have a targeted course for precisely this purpose.
We’ve also talked a lot about how to tackle dynamic programming problems using the FAST Method.
There are resource materials involved in preparing for the Google interview that are beyond the scope of what can be contained in a blog post.
As a major chunk of what determines your success for the Google interview is centered on coding proficiency, we will mention a few of my favorite book and video resources.
Note: This section contains some affiliate links. We earn a small commission if you buy through our link. Books:
Cracking the Coding Interview
For practice material, Cracking the Coding Interview (CTCI) by Gayle Laakmann McDowell is one of the more popular resources. In addition to providing a good array of practice problems, the introduction of the book provides specific information on how Google hires.
It’s a brief few pages, but as Gayle previously has worked for and went through the Google interview process, her advice here is an important piece of information. For a deeper dive on how to extract the most out of CTCI for your interview, check out this video.
Elements of Programming Interviews
If you wish to supplement your book preparation material, this video mentions his top 5 books for preparing for the technical interview, with CTCI being among them.
Extracting content from that video specifically geared towards the Google interview, the book that is my overall favorite for technical interview preparation is Elements of Programming Interviews in Python (EPI) by Adnan Aziz, Tsung-Hsien Lee, and Amit Prakash.
One of the authors, Tsung-Hsien, is a current employee of Google, and it’s probably no coincidence that many of the problems found in this book had a high overlap with the problems that showed up in the Glassdoor data. CTCI is an excellent source of practice problems, but it is so excellent that the problems have declined in popularity for interviewers to ask due to their ubiquity.
For EPI, the solutions are incredibly concise, well-written, and guide your thought process gradually. As you read through one solution, you may be able to stop midway and solve it yourself without reading the entire thing.
This is great and simulates obtaining a hint from the interviewer if you're really stuck on a problem. While it's best to solve the problem without any explicit hints, it's good that the book has that option.
The solution code is also exceptionally Pythonic. I've found that when working through the problems in this text that even if I have the correct idea, looking at the concise way the authors solved the problem was a real inspiration to well-formed Python code.
If you decide that Python is not your strongest language to interview in, they also offer a Java and C++ versions of the book that may be better suited for you. The writing style and theme of these books is just as good.
Byte-by-Byte 50 Coding Interview Problems
We have compiled a large list of problems that serve as a great companion to the above two resources.You can download the free guide here.
If you are going through a particular problem and need some further guidance, this supplemental material can be incredibly helpful in understanding and solving the problem. Video Resources:
Depending on your timeline and learning stye, working through video content may be a preferable way in which to spend your time preparing for your Google interview. Assuming your gaps in knowledge are larger, there are no shortage of MOOCs offered through sites like Coursera and Udacity that focus on the fundamentals of computer science, data structures, algorithms, etc.
Assuming you have a solid foundation in data structures and algorithms, finding good video content on the specific type of problems you may encounter in a Google interview will most likely serve you better.
It’s also worth checking out our Youtube channel. We’ve compiled playlists of videos for certain problems in categories including dynamic programming, graphs, recursion, and arrays for starters. All of these videos can be found in our Coding Interview Question playlist.
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment