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.

  1. Unique Email Addresses
  2. Odd Even Jump
  3. License Key Formatting
  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
  10. Read N Characters Given Read4 II – Call multiple times
  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

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

  1. Add Two Numbers
  2. Remove Nth Node From End of List
  3. Merge Two Sorted Lists
  4. Copy List with Random Pointer

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
  2. Word Ladder
  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
  8. Evaluate Division (Editor’s choice: Frequently asked in Google onsite interview.)
  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

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.

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.

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

Leave a Reply

Your email address will not be published. Required fields are marked *