Google Programming Interview Questions

Subscribe for free interview question feeds

Leave your Email to get the latest Google interview questions weekly.
We'll never share your email with anyone else.
No spam we promise.

Most Frequently Asked Google Programming Interview Questions
Letter Combinations of a Phone Number
Valid Parentheses
Generate Parentheses
Next Permutation
Pow(x, n)
Spiral Matrix
Merge Intervals
Clone Graph
Word Break
Min Stack
Find Peak Element
Missing Ranges
Fraction to Recurring Decimal
Binary Search Tree Iterator
Number of Islands
Implement Trie (Prefix Tree)
Summary Ranges
Kth Smallest Element in a BST
Power of Two
Search a 2D Matrix II
Strobogrammatic Number
Strobogrammatic Number II
Group Shifted Strings
Flatten 2D Vector
Meeting Rooms II
Binary Tree Paths
3Sum Smaller
Graph Valid Tree
Palindrome Permutation
Closest Binary Search Tree Value
Encode and Decode Strings
H-Index
Paint Fence
Perfect Squares
Wiggle Sort
Zigzag Iterator
Peeking Iterator
Walls and Gates
Unique Word Abbreviation
Game of Life
Flip Game
Flip Game II
Binary Tree Longest Consecutive Sequence
Best Time to Buy and Sell Stock with Cooldown
Minimum Height Trees
Super Ugly Number
Binary Tree Vertical Order Traversal
Maximum Product of Word Lengths
Generalized Abbreviation
Number of Connected Components in an Undirected Graph
Wiggle Sort II
Power of Three
Verify Preorder Serialization of a Binary Tree
Reconstruct Itinerary
Flatten Nested List Iterator
Reverse Vowels of a String
Moving Average from Data Stream
Design Tic-Tac-Toe
Android Unlock Patterns
Design Snake Game
Line Reflection
Count Numbers with Unique Digits
Logger Rate Limiter
Sort Transformed Array
Bomb Enemy
Design Hit Counter
Max Sum of Rectangle No Larger Than K
Largest Divisible Subset
Plus One Linked List
Range Addition
Find K Pairs with Smallest Sums
Guess Number Higher or Lower
Guess Number Higher or Lower II
Combination Sum IV
Kth Smallest Element in a Sorted Matrix
Design Phone Directory
Insert Delete GetRandom O(1)
Linked List Random Node
Longest Absolute File Path
Find the Difference
UTF-8 Validation
Decode String
Integer Replacement
Evaluate Division
Nth Digit
Binary Watch
Remove K Digits
Queue Reconstruction by Height
Valid Word Abbreviation
Longest Palindrome
Add Strings
Pacific Atlantic Water Flow
Sentence Screen Fitting
Maximum XOR of Two Numbers in an Array
Valid Word Square
Sequence Reconstruction
Number of Boomerangs
Find All Numbers Disappeared in an Array
Sort Characters By Frequency
Repeated Substring Pattern
Island Perimeter
Convex Polygon
Encode String with Shortest Length
Ones and Zeroes
Heaters
Magical String
License Key Formatting
Max Consecutive Ones
Predict the Winner
Max Consecutive Ones II
The Maze
Diagonal Traverse
Find Mode in Binary Search Tree
Next Greater Element II
The Maze II
Relative Ranks
Longest Uncommon Subsequence I
Longest Uncommon Subsequence II
Longest Word in Dictionary through Deleting
Beautiful Arrangement
Lonely Pixel I
Lonely Pixel II
Encode and Decode TinyURL
Reverse String II
01 Matrix
Diameter of Binary Tree
Output Contest Matches
Boundary of Binary Tree
Binary Tree Longest Consecutive Sequence II
Student Attendance Record I
Longest Line of Consecutive One in Matrix
Delete Operation for Two Strings
Add Bold Tag in String
Shopping Offers
Maximum Average Subarray I
Find Duplicate Subtrees
Find K Closest Elements
Split Array into Consecutive Subsequences
Non-decreasing Array
Beautiful Arrangement II
Repeated String Match
My Calendar II
Sentence Similarity II
Daily Temperatures
First Unique Character in a String
Shortest Completing Word
Largest Number At Least Twice of Others
Bold Words in String
Find Anagram Mappings
Rotated Digits
Escape The Ghosts
Domino and Tromino Tiling
Number of Matching Subsequences
Find Eventual Safe States
Soup Servings
Expressive Words
Largest Triangle Area
Largest Sum of Averages
Ambiguous Coordinates
Positions of Large Groups
Flipping an Image
Find And Replace in String
New 21 Game
Push Dominoes
Magic Squares In Grid
Keys and Rooms
Backspace String Compare
Maximize Distance to Closest Person
Peak Index in a Mountain Array
Exam Room
Median of Two Sorted Arrays
Regular Expression Matching
Merge k Sorted Lists
Trapping Rain Water
Wildcard Matching
Insert Interval
Longest Consecutive Sequence
Longest Substring with At Most Two Distinct Characters
LRU Cache
Word Break II
Word Search II
Shortest Palindrome
The Skyline Problem
Basic Calculator
Sliding Window Maximum
Alien Dictionary
Closest Binary Search Tree Value II
Expression Add Operators
Find Median from Data Stream
Serialize and Deserialize Binary Tree
Smallest Rectangle Enclosing Black Pixels
Number of Islands II
Range Sum Query 2D - Mutable
Count of Smaller Numbers After Self
Number of Atoms
My Calendar III
Cracking the Safe
Couples Holding Hands
Max Chunks To Make Sorted II
Minimize Max Distance to Gas Station
Swim in Rising Water
Transform to Chessboard
Reaching Points
Bricks Falling When Hit
Bus Routes
Race Car
Sum of Distances in Tree
Similar String Groups
Guess the Word
K-Similar Strings
Shortest Path Visiting All Nodes
Minimum Window Subsequence
Remove Duplicate Letters
Shortest Distance from All Buildings
Burst Balloons
Create Maximum Number
Count of Range Sum
Longest Increasing Path in a Matrix
Patching Array
Palindrome Pairs
Longest Substring with At Most K Distinct Characters
Word Squares
Russian Doll Envelopes
Rearrange String k Distance Apart
Perfect Rectangle
Trapping Rain Water II
Minimum Unique Word Abbreviation
LFU Cache
Optimal Account Balancing
Sliding Window Median
Smallest Good Base
Reverse Pairs
Freedom Trail
Word Abbreviation
Student Attendance Record II
Maximum Vacation Days
Median Employee Salary
Erect the Fence
Maximum Average Subarray II
Coin Path
Kth Smallest Number in Multiplication Table
24 Game
K Empty Slots
Redundant Connection II
Maximum Sum of 3 Non-Overlapping Subarrays
Reverse Image Search

Given a gallery of images, implement a class to support searching image...

Construct Word Using Dice

Given a word and N six-sided dice with char on each side, find out whether it's possible to construct the word by rolling the dices...

Pizza Shop

A pizza shop offers n pizzas along with m toppings. A customer plans to spend around x coins. The customer should order exactly one pizza, and may order zero, one or two toppings. Each topping may be ordered only once.
Given the lists of prices of available pizzas and toppings, what is the price closest to x of possible orders? Here, a price said closer to x when the difference from x is the smaller. Note the customer is allowed to make an order that costs more than x.

Fibonacci Base I

Given an int n, return all possible representations of n in Fibonacci base.
...

Recursive Islands and Lakes

Write a function to return the area of the largest island with inland lakes...

Tree Path

Given a binary tree and two nodes, return the path from one node to the other node...

Robot in Maze Problem - Collection

1. Google Robot in Maze Problem - Count Number of Ways in Matrix
1.2 Count Number of Ways with Obstacles in Matrix
1.3 Count Number of Ways Detour for North

Matrix Boundary

Given a matrix noted as 0 or 1, return the shortest distance to the boundary. The definition of boundary is the points which has at least one 0 neighbors...

Find Books By Genre

Implement a function to get the books of a given genre...

Min Points to Create a Line Chart

You task is to build a line chart for the server load change through time, given a sequence of load rate data. Each data point is a pair of numerics [int timestamp, double rate]. The timestamp starts from 0 and naturally increments by 1 per data point...

Dropping Balls

In a 2d array, a cell has either '/' or '\' as its value.
The matrix has N columns. N balls are dropped from the top of the matrix, one at each column...

Count Asterisks

Implement a function that finds the number of '*' in the input string, excluding the '*' between a pair of '|'...

Union Streams

Find the union set of two data streams and remove any duplicated elements.

Rotated Sliding Window

Given an array of integer of size N, select K numbers from the array...

Forest (Delete Nodes in a Binary Tree)

Delete a given list of nodes from a binary tree and return the roots of all remaining (sub)trees after the deletion...

Zero-filled Subarrays II

Given a 2d array with two rows, find out the number of non-empty subarrays filled with 0. A subarray may have either 1 or 2 rows...

IP Black List II

Build a function to check whether an IPv4 address is a bot in the black list. The robot ip black list is given as a list of strings. Each string has 3 dots and 4 segments of numbers between 0 and 255...

Disjointed Elements

Find out the disjointed elements of two arrays. The disjointed elements are those that remain after common elements of the arrays are removed...

Zero-filled Subarrays

Given an array of integer, find out the number of non-empty subarrays filled with 0.

Search Valid Parentheses

Given a matrix of parentheses, find if there exists a path from upper left corner to the bottom right corner that forms a valid parentheses.

Binary Search

Online Judege Demo. Currently support Python and Java.

Tree Diameter

Find the longest diameter of a tree. The diameter of a tree is defined as the number of edges on the longest path in the tree.

Pickup Coupon

Given an array of integers representing the value of coupons, return the minimum number of consecutive coupons to pick up to win the prize.

Fill 2D Array

Given a n*n  2D array. Fill the integer from 1 to n*n to this 2D array that makes the sum of each row, each column and the two diagonal equal. 

Cut Binary Search Tree

Given a BST, and an integer k, cut the BST vertically into two substrees A and B, where all nodes in A <= k and all nodes in B > k.

Contrain: for any node A and it’s parent B in the original BST. If after the cut they are both in the same subtree. B should still be the parent of A.

Minimum Number Of Decreasing Subsequence Partitions

Given an int array of length n. Split it into strictly decreasing subsequences. Return the minimum number of decreasing subsequences you can get by splitting the array.

Rose Garden

Given an array represents the bloom dates of a list of roses, return the earliest day that we can get n bouquets of roses...

Min Cost to Repair Edges (Minimum Spanning Tree II)

Amazon Online Assessment Question: Find the minimum cost to repair the edges so that all the nodes are once again accessible from each other.

Zombie in Matrix

[Google Onsite Question] Zombie in Matrix Problem

In a 2d array of integer, 2 denotes wall, 1 denotes zombie and 0 denotes human...

Min Deletions To Make Palindrome

Given a String, find the minimum number of deletions required to convert it into a palindrome.
...

Longest Common Subsequence

Given two two integer arrays, find the longest common subsequence.

eg: a =[1 5 2 6 3 7], b = [5 6 7 1 2 3]. return [1 2 3] or [5 6 7]

Bus Catch

Given a schedule of N buses departure time and the capacity of bus, find out the latest time you may arrive at the bus station to catch a bus...

Signal Coverage

Find out the minimum number of routers to cover the full range of array...

Error Alert

In an array of integer, array[i] denotes the error rate of server i. An alert gets triggered when for any one of the subarrays of size X, all error rates in the subarray appear greater than [threshold / X]...

Count Number in Sorted Array

Given a sorted array of integers and a target number, return the count of the target number...

Chatty Users

Given a chat log, find out the top K users who text the most words in total...

Word Break Combinations

Given a list of words L, find out all the combinations where any word W0 in list L can be made from concatenating other words [W1, W2, W3, ...] in L...

LRU Cache II

LRU Cache With TTL

Design and implement the Least Recently Used Cache with TTL(Time To Live)
Expalnation on the eviction stragedy since people have questions on the testcase:
1, after the record expires, it still remains in the cache.
2, when the cache reaches the capacity, it first evicts the expried records. If there are more than one expired records, evict the one with the minimum expire timestamp.

...

Fibonacci Base II

Given an integer n, return the representations in Fibonacci base for the integer from 1 to n.
...

Delete Islands

Given a binary grid where 0 represents water and 1 represents land. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. Delete all islands except their borders. A border is land adjacent to water. You may assume all four edges of the grid are surrounded by water

Marathon

There are n students [0, ..., n-1] participate in a marathon. You are given an int array standings where standings[i] = j means that student j finished just before student i. Return the students in the order in which they finished the marathon.

Secret Word

Given a secret word and encoding rules as follows: Each letter can be changed to a different letter. Different letters can not be changed to the same letter. For example, banana can be encoded to xyzyzy, but banana cannot become xyyyyy, because there is no way to decode it back. Also given an encoded string str, return true if and only if this string contains the specified secret word.

Guess Pin Code

Given 2 strings pin and guess. Write a function to provide a hint that indicates how digits in guess match the pin.

Min Swaps To Sort Array

Given an array return an integer indicating the minimum number of swap operations required to sort the array into ascending order.

String Conversion

Given two strings s and t, determine if you can convert s into t.

Count Trapezoids

Given an integer N which represents number of edges, where bases are always 2.Find how many trapezoid you can create with the integer N?

Chunked Palindrome

Normal palindrome is defined as a string that reads the same backwards as forwards, for example "abccba".

Run Length Encoded Strings II

Given a run-length encoded string s and a width of a board. Assume that the board is filled from left to right such that each line has exactly width chars. Return the run-length encoded string that represents the board rows from right to left without constructing the board.

Run Length Encoded Strings I

Given 2 run-length encoded strings s and t. Determine if they represent the same string.

Shortest Word Distance

Shortest Word Distance

Tree Game

Tree Game
Two people in a game, player scores by claiming nodes in binary tree, tree node class as shown above.
The player who eventually owns more nodes wins the game.
Player A and B each claims a node at first.
After the first round, a player will only be able to claim a node adjacent to any node owned by himself.
A tree node is adjacent to its parent, left right and right child.
A node owned cannot be re-claimed.
End game when all nodes are owned.
If player A gets the first claim at node N, find whether it is possible for player B to win.
If yes, find out which node player B should claim at his first move.

Maximum Block Volume

Given the left view and front view of the skyline of a block as two arrays, find the maximum total height of buildings in the block.

Design Text Editor

Build a text editor class with the following functions,

moveCursorLeft(),

moveCursorRight(),

insertCharacter(char) //insert the char right before cursor

backspace() //delete the char right before cursor

Set Matrix Zeroes II

Google On-site 2018 Winter

There are orbs on an NxM board ('O' denotes orb. 'X' denotes empty slot).

Whenever two orbs are in the same column or the same row, you get to erase one of them.

Try to erase as many orbs as possible.

Find the minimum number of orbs remained on board eventually.

Randomly select a number in an array

How to randomly select a number in an array?
array: [15, 2, 4, 5, 1, -2, 0]

Follow-up:
Given a second array freq where freq[i] represents the occurrence of the ith number in array, how to randomly select a number in array based on the frequency.

Extra requirement:
Could you complete the selection in a single-pass(go through each array only once)?

Cut Binary Tree

Give a binary tree, find if it's possible to cut the tree into two halves of equal sum. You can only cut one edge.

Design Compressed String Iterator

Design and implement a data structure for a compressed string iterator. It should support the following operations: next and hasNext. The given compressed string will be in the form of each letter followed by a positive integer representing the number of this letter existing in the original uncompressed string.

Unique Letter String

For example, UNIQ("LETTER") =  2.

Given a string S with only uppercases, calculate the sum of UNIQ(substring) over all non-empty substrings of S.

If there are two or more equal substrings at different positions in S, we consider them different. Since the answer can be very large, retrun the answer modulo 10 ^ 9 7.

Longest Arithmetic Progression

In the array {1, 6, 3, 5, 9, 7}, the longest arithmetic sequence is 1, 3, 5, and 7

Matrix Paths

Given the length and width of a matrix, get the number of paths from bottom-left to bottom right.

HTML Reverser

Implement a ring buffer

Find Missing Sequence

Give an array A of n integers where 1 <= a[i] <= K. Find out the length of the shortest sequence that can be constructed out of numbers 1, 2, .. k that is NOT a subsequence of A.

Flatten 2D Vector

Implement an iterator to flatten a 2d vector.

Boundary of Binary Tree

Given a binary tree, return the values of its boundary in anti-clockwise direction starting from root. Boundary includes left boundary, leaves, and right boundary in order without duplicate nodes.