# Get Well Prepared for Google Interview

Total 85 questions.

## Introduction

Google tech interviews are notoriously difficult and quite challenging. To get a phone screen, you will need to submit your resume to their online application system or via an internal referral from a Googler.

Assuming you passed their resume screen, a recruiter will reach out to you. Usually there will be two phone screens, and if you do well, you’ll be invited to onsite interviews.

Since Google operates at a large scale, be prepared to answer lots of follow up questions on how to scale the algorithm you wrote for multiple machines. Some examples are: Number of Islands and Intersection of Two Arrays II.

## Interview Process

You may receive an online assessment link as your first step of interview process. The assessment will expire within 7 days and contains two coding questions to be completed within an hour. Below are some Online Assessment questions for you to practice.

Near the end of this chapter we provide more details of the different stages of a Google interview.

2. Odd Even Jump
4. Fruit Into Baskets (Online Assessment Question)

## Arrays and Strings

String manipulation problems are in the same category as arrays, because internally, a string is represented as an array of characters. Array problems usually do not require knowledge of advanced data structures, so just basic data structures such as Hash Tables and basic techniques like Two Pointers should suffice.

Google likes to test your ability to think at large scale by asking variation of problems represented in a data stream model. For example, instead of giving you an integer array, you are given a stream of integers and all integers are too large to fit in memory. A great example of such problem, which can be represented in a data stream model, is the Longest Substring with At Most K Distinct Characters.

1. Longest Substring Without Repeating Characters
2. Container With Most Water
3. 3Sum
4. Next Permutation
5. Multiply Strings
6. Rotate Image
7. Jump Game
8. Plus One
9. Minimum Window Substring
11. Longest Substring with At Most Two Distinct Characters
12. Missing Ranges
13. Next Closest Time
14. Expressive Words
15. Find And Replace in String
16. Maximize Distance to Closest Person
17. Valid Parentheses
18. Merge k Sorted Lists
19. Trapping Rain Water
20. Kth Largest Element in an Array
21. Meeting Rooms II
22. Backspace String Compare (Editor’s choice: Frequently asked in a Google phone interview.)
23. Minimum Cost to Hire K Workers
24. K Closest Points to Origin

According to our user survey data, Linked List problems are not asked frequently at Google. Perhaps, most linked list problems are not that complex and it is harder to ask follow up and complexity analysis questions

Nonetheless, we strongly recommend you to still practice classic Linked List interview questions such as: Linked List CycleIntersection of Two Linked Lists, and Copy List with Random Pointers. These problems are really fun and they teach you how to think outside of the box.

Of course, Merge k Sorted Lists is one of our all-time favorite interview questions, and Google seems to love this question as well. Make sure you understand how to analyze the time complexity! This is a common follow up question for this problem.

## Trees and Graphs

Tree is just a special case of graph. To understand the difference between trees and graphs, you can work on Graph Valid Tree.

Graphs are generally breath-first search or depth-first search. The same applies to Trees, but trees never contain cycles.

Graphs are generally more complex than trees. Similarly, trees are generally more complex than linear data structures, such as arrays or linked lists.

Prepping your knowledge in Graphs is essential for Google interviews as you would most likely encounter a tree or a graph question. A great way to brush up your skills in this area is to implement a tree or graph by coding it from scratch in the Playground.

1. Binary Tree Maximum Path Sum
3. Number of Islands
4. Course Schedule II
5. Count Complete Tree Nodes (Editor’s choice: Frequently asked in Google phone interview.)
6. Longest Increasing Path in a Matrix
7. Decode String
9. Diameter of Binary Tree
10. Cracking the Safe
11. Robot Room Cleaner (Editor’s choice: Frequently asked in a Google onsite interview.)
12. Most Stones
13. Removed with Same Row or Column (Editor’s choice: Frequently asked in a Google onsite interview.)
14. Flip Equivalent Binary Trees

## Recursion

Recursion usually involves some kind of backtracking to enumerate all possibilities.

Note that Recursion is a more general purpose algorithm. Depth-First search is a specific form of backtracking related to searching tree data structures. Therefore we categorize those problems in “Trees and Graphs”, even though they involve recursion.

For a great introduction of how backtracking works, please check out LeetCode’s Recursion II card. A great example is “Word Search II” (aka the Boggle solver), which uses a data structure to optimize the search.

## Sorting and Searching

Similar to “Arrays and Strings”, interval related problems can be asked in the context of data stream.

## Dynamic Programming

It can be tricky to identify the subproblems and connect them, which is essential in solving Dynamic Programming problems. Dynamic programming is not that scary as you might think, and you can improve your dynamic programming skills by practicing a lot of these problems.

According to our user survey, one of the most frequently asked Dynamic Programming Google interview questions is Split Array Largest Sum.

## Others

• Reverse Integer
• Candy
• Isomorphic Strings
• Strobogrammatic Number
• Bulls and Cows
• Range Sum Query 2D – Mutable
• My Calendar II
• Jewels and Stones
• Swap Adjacent in LR String
• Guess the Word (Editor’s choice: Frequently asked in a Google onsite interview.)
• Minimum Area Rectangle