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.

- Unique Email Addresses
- Odd Even Jump
- License Key Formatting
- 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.

- Longest Substring Without Repeating Characters
- Container With Most Water
- 3Sum
- Next Permutation
- Multiply Strings
- Rotate Image
- Jump Game
- Plus One
- Minimum Window Substring
- Read N Characters Given Read4 II – Call multiple times
- Longest Substring with At Most Two Distinct Characters
- Missing Ranges
- Next Closest Time
- Expressive Words
- Find And Replace in String
- Maximize Distance to Closest Person
- Valid Parentheses
- Merge k Sorted Lists
- Trapping Rain Water
- Kth Largest Element in an Array
- Meeting Rooms II
- Backspace String Compare (Editor’s choice: Frequently asked in a Google phone interview.)
- Minimum Cost to Hire K Workers
- K Closest Points to Origin

## Linked Lists

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 Cycle, Intersection 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.

- Binary Tree Maximum Path Sum
- Word Ladder
- Number of Islands
- Course Schedule II
- Count Complete Tree Nodes (Editor’s choice: Frequently asked in Google phone interview.)
- Longest Increasing Path in a Matrix
- Decode String
- Evaluate Division (Editor’s choice: Frequently asked in Google onsite interview.)
- Diameter of Binary Tree
- Cracking the Safe
- Robot Room Cleaner (Editor’s choice: Frequently asked in a Google onsite interview.)
- Most Stones
- Removed with Same Row or Column (Editor’s choice: Frequently asked in a Google onsite interview.)
- 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.

- Word Squares
- Strobogrammatic Number II
- Word Search II
- Android Unlock Patterns
- Letter Combinations of a Phone Number
- Generate Parentheses

## Sorting and Searching

Interval related problems are quite often asked at Google interviews.

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

- Median of Two Sorted Arrays
- Find First and Last Position of Element in Sorted Array
- Merge Intervals
- Insert Interval
- Valid Anagram
- Count of Smaller Numbers After Self
- Peak Index in a Mountain Array

## 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.

- Longest Palindromic Substring
- Maximum Subarray
- Best Time to Buy and Sell Stock
- Maximum Product Subarray
- Coin Change
- Split Array Largest Sum (Editor’s choice: Frequently asked in a Google phone interview.)

## Design

- LRU Cache
- Min Stack
- Serialize and Deserialize Binary Tree
- Logger Rate Limiter
- Insert Delete GetRandom O(1)
- Design Search Autocomplete System

## 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