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

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.

Meeting Rooms

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

Longest Substring Without Repeating Characters

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

Merge Sorted Array

You are given two integer arrays nums1 and nums2, sorted in non-decreasing order, and two integers m and n, representing the number of elements in nums1 and num...

Alien Dictionary

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

Group Anagrams

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

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

Valid Parentheses

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

Longest Palindromic Substring

Given a string s, return the longest palindromic substring in s.

3Sum

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Merge Intervals

Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cove...

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.

Container With Most Water

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]).

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

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.

Merge k Sorted Lists

You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.

Maximum Subarray

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

Longest Common Prefix

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

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

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

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.

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

Climbing Stairs

You are climbing a staircase. It takes n steps to reach the top.

Generate Parentheses

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

Letter Combinations of a Phone Number

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.

Spiral Matrix

Given an m x n matrix, return all elements of the matrix in spiral order.

Search in Rotated Sorted Array

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

Palindrome Number

Given an integer x, return true if x is a palindrome, and false otherwise.

Roman to Integer

Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.

Merge Two Sorted Lists

You are given the heads of two sorted linked lists list1 and list2.

Reverse Integer

Given a signed 32-bit integer x, return x with its digits reversed. If reversing x causes the value to go outside the signed 32-bit integer range [-231, 231 - 1...

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

Delete Node in a BST

Given a root node reference of a BST and a key, delete the node with the given key in the BST. Return the root node reference (possibly updated) of the BST.

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.

Unique Length-3 Palindromic Subsequences

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

Rotate Image

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

Word Search

Given an m x n grid of characters board and a string word, return true if word exists in the grid.

Next Permutation

A permutation of an array of integers is an arrangement of its members into a sequence or linear order.

Remove Duplicates from Sorted Array

Given an integer array nums sorted in non-decreasing order, remove the duplicates in-place such that each unique element appears only once. The relative order o...

Largest Rectangle in Histogram

Given an array of integers heights representing the histogram's bar height where the width of each bar is 1, return the area of the largest rectangle in the his...

Find First and Last Position of Element in Sorted Array

Given an array of integers nums sorted in non-decreasing order, find the starting and ending position of a given target value.

Valid Sudoku

Determine if a 9 x 9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:

Design Underground System

An underground railway system is keeping track of customer travel times between different stations. They are using this data to calculate the average time it ta...

Detect Squares

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

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

Jump Game II

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

First Missing Positive

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

Subsets

Given an integer array nums of unique elements, return all possible subsets (the power set).

Set Matrix Zeroes

Given an m x n integer matrix matrix, if an element is 0, set its entire row and column to 0's.

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:

Pow(x, n)

Implement pow(x, n), which calculates x raised to the power n (i.e., xn).

Reverse Nodes in k-Group

Given the head of a linked list, reverse the nodes of the list k at a time, and return the modified list.

Unique Paths

There is a robot on an m x n grid. The robot is initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner...

Sort Colors

Given an array nums with n objects colored red, white, or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order...

Regular Expression Matching

Given an input string s and a pattern p, implement regular expression matching with support for '.' and '' where:

Search a 2D Matrix

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

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

Split Linked List in Parts

Given the head of a singly linked list and an integer k, split the linked list into k consecutive linked list parts.

Minimum Window Substring

Given two strings s and t of lengths m and n respectively, return the minimum window substring of s such that every character in t (including duplicates) is inc...

Remove Nth Node From End of List

Given the head of a linked list, remove the nth node from the end of the list and return its head.

Validate Binary Search Tree

Given the root of a binary tree, determine if it is a valid binary search tree (BST).

N-Queens

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.

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.

Zigzag Conversion

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better...

Combination Sum

Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum...

Remove Element

Given an integer array nums and an integer val, remove all occurrences of val in nums in-place. The order of the elements may be changed. Then return the number...

Integer to Roman

Seven different symbols represent Roman numerals with the following values:

Sqrt(x)

Given a non-negative integer x, return the square root of x rounded down to the nearest integer. The returned integer should be non-negative as well.

Plus One

You are given a large integer represented as an integer array digits, where each digits[i] is the ith digit of the integer. The digits are ordered from most sig...

Permutations

Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.

Search Insert Position

Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were ins...

Longest Valid Parentheses

Given a string containing just the characters '(' and ')', return the length of the longest valid (well-formed) parentheses substring.

String to Integer (atoi)

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

Reverse Linked List II

Given the head of a singly linked list and two integers left and right where left <= right, reverse the nodes of the list from position left to position right,...

Divide Two Integers

Given two integers dividend and divisor, divide two integers without using multiplication, division, and mod operator.

Swap Nodes in Pairs

Given a linked list, swap every two adjacent nodes and return its head. You must solve the problem without modifying the values in the list's nodes (i.e., only...

Edit Distance

Given two strings word1 and word2, return the minimum number of operations required to convert word1 to word2.

Add Binary

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

Simplify Path

You are given an absolute path for a Unix-style file system, which always begins with a slash '/'. Your task is to transform this absolute path into its simplif...

Decode Ways

You have intercepted a secret message encoded as a string of numbers. The message is decoded via the following mapping:

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.

Remove Duplicates from Sorted Array II

Given an integer array nums sorted in non-decreasing order, remove some duplicates in-place such that each unique element appears at most twice. The relative or...

Subsets II

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

Rotate List

Given the head of a linked list, rotate the list to the right by k places.

Combination Sum II

Given a collection of candidate numbers (candidates) and a target number (target), find all unique combinations in candidates where the candidate numbers sum to...

Same Tree

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

Length of Last Word

Given a string s consisting of words and spaces, return the length of the last word in the string.

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

Sudoku Solver

Write a program to solve a Sudoku puzzle by filling the empty cells.

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.

Wildcard Matching

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

Count and Say

The count-and-say sequence is a sequence of digit strings defined by the recursive formula:

Search in Rotated Sorted Array II

There is an integer array nums sorted in non-decreasing order (not necessarily with distinct values).

Remove Duplicates from Sorted List

Given the head of a sorted linked list, delete all duplicates such that each element appears only once. Return the linked list sorted as well.

Binary Tree Inorder Traversal

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

Multiply Strings

Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a 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...

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.

Unique Paths II

You are given an m x n integer array grid. There is a robot initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-r...

Unique Binary Search Trees II

Given an integer n, return all the structurally unique BST's (binary search trees), which has exactly n nodes of unique values from 1 to n. Return the answer in...

Partition List

Given the head of a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.

Permutation Sequence

The set [1, 2, 3, ..., n] contains a total of n! unique permutations.

Substring with Concatenation of All Words

You are given a string s and an array of strings words. All the strings of words are of the same length.

Combinations

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

Recover Binary Search Tree

You are given the root of a binary search tree (BST), where the values of exactly two nodes of the tree were swapped by mistake. Recover the tree without changi...

Permutations II

Given a collection of numbers, nums, that might contain duplicates, return all possible unique permutations in any order.

Interleaving String

Given strings s1, s2, and s3, find whether s3 is formed by an interleaving of s1 and s2.

Gray Code

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

Unique Binary Search Trees

Given an integer n, return the number of structurally unique BST's (binary search trees) which has exactly n nodes of unique values from 1 to n.

Restore IP Addresses

A valid IP address consists of exactly four integers separated by single dots. Each integer is between 0 and 255 (inclusive) and cannot have leading zeros.

Spiral Matrix II

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

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

Valid Number

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

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.

Scramble String

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