Goldman Sachs Coding Interview Questions

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.

First Unique Character in a String

Given a string s, find the first non-repeating character in it and return its index. If it does not exist, return -1.

Fraction to Recurring Decimal

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

Best Time to Buy and Sell Stock

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

Number of Islands

Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands.

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.

String Compression

Given an array of characters chars, compress it using the following algorithm:

LRU Cache

Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.

Two Sum

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

Group Anagrams

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

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

Find Minimum in Rotated Sorted Array

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

Decode Ways

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

Longest Substring Without Repeating Characters

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

Search in Rotated Sorted Array

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

Minimize the Maximum of Two Arrays

We have two arrays arr1 and arr2 which are initially empty. You need to add positive integers to them such that they satisfy all the following conditions:

Best Time to Buy and Sell Stock II

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

Kth Largest Element in an Array

Given an integer array nums and an integer k, return the kth largest element in the array.

Valid Arrangement of Pairs

You are given a 0-indexed 2D integer array pairs where pairs[i] = [starti, endi]. An arrangement of pairs is valid if for every index i where 1 <= i < pairs.len...

Maximum Subarray

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

Construct Smallest Number From DI String

You are given a 0-indexed string pattern of length n consisting of the characters 'I' meaning increasing and 'D' meaning decreasing.

Power of Three

Given an integer n, return true if it is a power of three. Otherwise, return false.

Longest Increasing Subsequence

Given an integer array nums, return the length of the longest strictly increasing subsequence.

Longest Palindromic Substring

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

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

Valid Parentheses

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

Minimum Cost Homecoming of a Robot in a Grid

There is an m x n grid, where (0, 0) is the top-left cell and (m - 1, n - 1) is the bottom-right cell. You are given an integer array startPos where startPos =...

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

Count Palindromic Subsequences

Given a string of digits s, return the number of palindromic subsequences of s having length 5. Since the answer may be very large, return it modulo 109 + 7.

Range Product Queries of Powers

Given a positive integer n, there exists a 0-indexed array called powers, composed of the minimum number of powers of 2 that sum to n. The array is sorted in no...

Successful Pairs of Spells and Potions

You are given two positive integer arrays spells and potions, of length n and m respectively, where spells[i] represents the strength of the ith spell and potio...

Sliding Window Maximum

You are given an array of integers nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see...

Keep Multiplying Found Values by Two

You are given an array of integers nums. You are also given an integer original which is the first number that needs to be searched for in nums.

Determine if Two Events Have Conflict

You are given two arrays of strings that represent two inclusive events that happened on the same day, event1 and event2, where:

Count Number of Texts

Alice is texting Bob using her phone. The mapping of digits to letters is shown in the figure below.

Find All Good Indices

You are given a 0-indexed integer array nums of size n and a positive integer k.

String to Integer (atoi)

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

Search a 2D Matrix

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

Product of Array Except Self

Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].

House Robber

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from rob...

Subarray Sum Equals K

Given an array of integers nums and an integer k, return the total number of subarrays whose sum equals to k.

Pow(x, n)

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

Next Permutation

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

Word Search

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

Linked List Cycle

Given head, the head of a linked list, determine if the linked list has a cycle in it.

Pascal's Triangle

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

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.

Minimum Size Subarray Sum

Given an array of positive integers nums and a positive integer target, return the minimal length of a subarray whose sum is greater than or equal to target. If...

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.

Find Peak Element

A peak element is an element that is strictly greater than its neighbors.

Insert Delete GetRandom O(1)

Implement the RandomizedSet class:

Climbing Stairs

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

Minimum Number of Arrows to Burst Balloons

There are some spherical balloons taped onto a flat wall that represents the XY-plane. The balloons are represented as a 2D integer array points where points[i]...

Top K Frequent Elements

Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.

Maximum Product Subarray

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

Gas Station

There are n gas stations along a circular route, where the amount of gas at the ith station is gas[i].

Count Number of Pairs With Absolute Difference K

Given an integer array nums and an integer k, return the number of pairs (i, j) where i < j such that |nums[i] - nums[j]| == k.

First Missing Positive

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

Merge Two Sorted Lists

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

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.

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.

Decode String

Given an encoded string, return its decoded string.

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

Maximal Square

Given an m x n binary matrix filled with 0's and 1's, find the largest square containing only 1's and return its area.

Next Greater Element I

The next greater element of some element x in an array is the first greater element that is to the right of x in the same array.

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.

Candy

There are n children standing in a line. Each child is assigned a rating value given in the integer array ratings.

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

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

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.

Roman to Integer

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

Spiral Matrix

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

Maximum XOR of Two Numbers in an Array

Given an integer array nums, return the maximum result of nums[i] XOR nums[j], where 0 <= i <= j < n.

Pascal's Triangle II

Given an integer rowIndex, return the rowIndexth (0-indexed) row of the Pascal's triangle.

Rotate Array

Given an integer array nums, rotate the array to the right by k steps, where k is non-negative.

Find the Duplicate Number

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

Reorder List

You are given the head of a singly linked-list. The list can be represented as:

Permutations

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

Next Greater Element III

Given a positive integer n, find the smallest integer which has exactly the same digits existing in the integer n and is greater in value than n. If no such pos...

Integer to Roman

Seven different symbols represent Roman numerals with the following values:

Amount of Time for Binary Tree to Be Infected

You are given the root of a binary tree with unique values, and an integer start. At minute 0, an infection starts from the node with value start.

Permutation in String

Given two strings s1 and s2, return true if s2 contains a permutation of s1, or false otherwise.

Intersection of Two Linked Lists

Given the heads of two singly linked-lists headA and headB, return the node at which the two lists intersect. If the two linked lists have no intersection at al...

Fraction Addition and Subtraction

Given a string expression representing an expression of fraction addition and subtraction, return the calculation result in string format.

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.

Valid Anagram

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

Rotate Image

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

Reverse String

Write a function that reverses a string. The input string is given as an array of characters s.

Largest Number

Given a list of non-negative integers nums, arrange them such that they form the largest number and return it.

Remove Duplicate Letters

Given a string s, remove duplicate letters so that every letter appears once and only once. You must make sure your result is the smallest in lexicographical or...

Jump Game II

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

Query Kth Smallest Trimmed Number

You are given a 0-indexed array of strings nums, where each string is of equal length and consists of only digits.

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

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:

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

Interleaving String

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

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

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