Google Coding Interview Questions

Two Sum

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

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

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.

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.

Maximum Subarray

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

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.

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

Group Anagrams

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

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.

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.

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.

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.

Isomorphic Strings

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

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":

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.

Word Search II

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

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.

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

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

Second Highest Salary

Table: Employee

Fraction to Recurring Decimal

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

Basic Calculator II

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

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

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.

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.

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.

Combinations

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

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.

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:

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

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:

Minimum Depth of Binary Tree

Given a binary tree, find its minimum depth.

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.

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

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.

Gray Code

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

Valid Number

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

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:

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