Google Coding Interview Questions

Two Sum

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

Meeting Rooms II

Given an array of meeting time intervals intervals where intervals[i] = [starti, endi], return the minimum number of conference rooms required.

Alien Dictionary

There is a new alien language that uses the English alphabet. However, the order of the letters is unknown to you.

Encode and Decode Strings

Design an algorithm to encode a list of strings to a single string. The encoded string is then decoded back to the original list of strings.

Detect Squares

You are given a stream of points on the X-Y plane. Design a data structure that:

Number of Good Paths

There is a tree of n nodes labeled from 0 to n - 1, rooted at node 0. You are given a 0-indexed integer array vals of length n where vals[i] denotes the value o...

Minimum Interval to Include Each Query

You are given a 2D integer array intervals, where intervals[i] = [lefti, righti] describes the ith interval starting at lefti and ending at righti (inclusive)....

Meeting Rooms

Given an array of meeting time intervals where intervals[i] = [starti, endi], determine if a person could attend all meetings.

Graph Valid Tree

You have a graph of n nodes labeled from 0 to n - 1. You are given an integer n and a list of edges where edges[i] = [ai, bi] indicates that there is an undirec...

Add Two Numbers

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a sing...

Number of Connected Components in an Undirected Graph

You have a graph of n nodes. You are given an integer n and an array edges where edges[i] = [ai, bi] indicates that there is an edge between ai and bi in the gr...

Design Add and Search Words Data Structure

Design a data structure that supports adding new words and finding if a string matches any previously added string.

Hand of Straights

Alice has some number of cards and she wants to rearrange the cards into groups so that each group is of size groupSize, and consists of groupSize consecutive c...

Naming a Company

You are given an array of strings ideas that represents a list of names to be used in the process of naming a company. The process of naming a company is as fol...

Trapping Rain Water

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

Median of Two Sorted Arrays

Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.

Longest Substring Without Repeating Characters

Given a string s, find the length of the longest substring without duplicate characters.

Longest Common Prefix

Write a function to find the longest common prefix string amongst an array of strings.

Time Needed to Inform All Employees

A company has n employees with a unique ID for each employee from 0 to n - 1. The head of the company is the one with headID.

Valid Parentheses

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

Longest Consecutive Sequence

Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.

Remove Max Number of Edges to Keep Graph Fully Traversable

Alice and Bob have an undirected graph of n nodes and three types of edges:

Push Dominoes

There are n dominoes in a line, and we place each domino vertically upright. In the beginning, we simultaneously push some of the dominoes either to the left or...

Merge Triplets to Form Target Triplet

A triplet is an array of three integers. You are given a 2D integer array triplets, where triplets[i] = [ai, bi, ci] describes the ith triplet. You are also giv...

Maximum Subarray

Given an integer array nums, find the subarray with the largest sum, and return its sum.

Grid Game

You are given a 0-indexed 2D array grid of size 2 x n, where grid[r][c] represents the number of points at position (r, c) on the matrix. Two robots are playing...

Unique Length-3 Palindromic Subsequences

Given a string s, return the number of unique palindromes of length three that are a subsequence of s.

Find Eventual Safe States

There is a directed graph of n nodes with each node labeled from 0 to n - 1. The graph is represented by a 0-indexed 2D integer array graph where graph[i] is an...

Rotate Image

You are given an n x n 2D matrix representing an image, rotate the image by 90 degrees (clockwise).

Search in Rotated Sorted Array

There is an integer array nums sorted in ascending order (with distinct values).

Reverse Linked List

Given the head of a singly linked list, reverse the list, and return the reversed list.

4Sum

Given an array nums of n integers, return an array of all the unique quadruplets [nums[a], nums[b], nums[c], nums[d]] such that:

Jump Game

You are given an integer array nums. You are initially positioned at the array's first index, and each element in the array represents your maximum jump length...

Single Number

Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.

Pascal's Triangle

Given an integer numRows, return the first numRows of Pascal's triangle.

Group Anagrams

Given an array of strings strs, group the anagrams together. You can return the answer in any order.

Find Median from Data Stream

The median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value, and the median is the mean of the two midd...

Find the Index of the First Occurrence in a String

Given two strings needle and haystack, return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

Maximal Rectangle

Given a rows x cols binary matrix filled with 0's and 1's, find the largest rectangle containing only 1's and return its area.

Valid Anagram

Given two strings s and t, return true if t is an anagram of s, and false otherwise.

First Missing Positive

Given an unsorted integer array nums. Return the smallest positive integer that is not present in nums.

Jump Game II

You are given a 0-indexed array of integers nums of length n. You are initially positioned at index 0.

Add Binary

Given two binary strings a and b, return their sum as a binary string.

Text Justification

Given an array of strings words and a width maxWidth, format the text such that each line has exactly maxWidth characters and is fully (left and right) justifie...

Insert Interval

You are given an array of non-overlapping intervals intervals where intervals[i] = [starti, endi] represent the start and the end of the ith interval and interv...

Maximum Product Subarray

Given an integer array nums, find a subarray that has the largest product, and return the product.

String to Integer (atoi)

Implement the myAtoi(string s) function, which converts a string to a 32-bit signed integer.

Same Tree

Given the roots of two binary trees p and q, write a function to check if they are the same or not.

Search a 2D Matrix

You are given an m x n integer matrix matrix with the following two properties:

Wildcard Matching

Given an input string (s) and a pattern (p), implement wildcard pattern matching with support for '?' and '' where:

Find the Duplicate Number

Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive.

Isomorphic Strings

Given two strings s and t, determine if they are isomorphic.

3Sum Closest

Given an integer array nums of length n and an integer target, find three integers at distinct indices in nums such that the sum is closest to target.

Missing Number

Given an array nums containing n distinct numbers in the range [0, n], return the only number in the range that is missing from the array.

Contains Duplicate II

Given an integer array nums and an integer k, return true if there are two distinct indices i and j in the array such that nums[i] == nums[j] and abs(i - j) <=...

Symmetric Tree

Given the root of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center).

Minimum Path Sum

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right, which minimizes the sum of all numbers along its path.

Kth Smallest Element in a BST

Given the root of a binary search tree, and an integer k, return the kth smallest value (1-indexed) of all the values of the nodes in the tree.

Copy List with Random Pointer

A linked list of length n is given such that each node contains an additional random pointer, which could point to any node in the list, or null.

Clone Graph

Given a reference of a node in a connected undirected graph.

Integer to Roman

Seven different symbols represent Roman numerals with the following values:

Shortest Palindrome

You are given a string s. You can convert s to a palindrome by adding characters in front of it.

Flatten Binary Tree to Linked List

Given the root of a binary tree, flatten the tree into a "linked list":

Word Search II

Given an m x n board of characters and a list of strings words, return all words on the board.

Subsets II

Given an integer array nums that may contain duplicates, return all possible subsets (the power set).

Binary Tree Right Side View

Given the root of a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.

Best Time to Buy and Sell Stock with Cooldown

You are given an array prices where prices[i] is the price of a given stock on the ith day.

The Skyline Problem

A city's skyline is the outer contour of the silhouette formed by all the buildings in that city when viewed from a distance. Given the locations and heights of...

Implement Stack using Queues

Implement a last-in-first-out (LIFO) stack using only two queues. The implemented stack should support all the functions of a normal stack (push, top, pop, and...

Second Highest Salary

Table: Employee

Basic Calculator II

Given a string s which represents an expression, evaluate this expression and return its value.

Fraction to Recurring Decimal

Given two integers representing the numerator and denominator of a fraction, return the fraction in string format.

Number of Digit One

Given an integer n, count the total number of digit 1 appearing in all non-negative integers less than or equal to n.

Game of Life

According to Wikipedia's article: "The Game of Life, also known simply as Life, is a cellular automaton devised by the British mathematician John Horton Conway...

Walls and Gates

You are given an m x n grid rooms initialized with these three possible values:

Binary Tree Paths

Given the root of a binary tree, return all root-to-leaf paths in any order.

Best Time to Buy and Sell Stock IV

You are given an integer array prices where prices[i] is the price of a given stock on the ith day, and an integer k.

Wiggle Sort

Given an integer array nums, reorder it such that nums[0] <= nums[1] >= nums[2] <= nums[3]....

Combinations

Given two integers n and k, return all possible combinations of k numbers chosen from the range [1, n].

Lowest Common Ancestor of a Binary Search Tree

Given a binary search tree (BST), find the lowest common ancestor (LCA) node of two given nodes in the BST.

Binary Tree Postorder Traversal

Given the root of a binary tree, return the postorder traversal of its nodes' values.

Department Top Three Salaries

Table: Employee

Spiral Matrix II

Given a positive integer n, generate an n x n matrix filled with elements from 1 to n2 in spiral order.

Peeking Iterator

Design an iterator that supports the peek operation on an existing iterator in addition to the hasNext and the next operations.

Remove Duplicates from Sorted List II

Given the head of a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list. Return the linked li...

Factorial Trailing Zeroes

Given an integer n, return the number of trailing zeroes in n!.

Insertion Sort List

Given the head of a singly linked list, sort the list using insertion sort, and return the sorted list's head.

Scramble String

We can scramble a string s to get a string t using the following algorithm:

Populating Next Right Pointers in Each Node

You are given a perfect binary tree where all leaves are on the same level, and every parent has two children. The binary tree has the following definition:

N-Queens II

The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other.

Minimum Depth of Binary Tree

Given a binary tree, find its minimum depth.

Word Pattern

Given a pattern and a string s, find if s follows the same pattern.

Bitwise AND of Numbers Range

Given two integers left and right that represent the range [left, right], return the bitwise AND of all numbers in this range, inclusive.

Rank Scores

Table: Scores

Find Minimum in Rotated Sorted Array II

Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,4,4,5,6,7] might become:

Valid Number

Given a string s, return whether s is a valid number.

Gray Code

An n-bit gray code sequence is a sequence of 2n integers where:

Remove Invalid Parentheses

Given a string s that contains parentheses and letters, remove the minimum number of invalid parentheses to make the input string valid.

Range Sum Query - Mutable

Given an integer array nums, handle multiple queries of the following types:

Binary Tree Level Order Traversal II

Given the root of a binary tree, return the bottom-up level order traversal of its nodes' values. (i.e., from left to right, level by level from leaf to root).

Paint House

There is a row of n houses, where each house can be painted one of three colors: red, blue, or green. The cost of painting each house with a certain color is di...