Goldman Sachs

14 DSA problems asked in Goldman Sachs coding interviews

1 Easy
8 Medium
5 Hard

14 problems

Binary Search
1
Median of Two Sorted Arrays
Hard

Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

Dynamic Programming
4
Minimum Path Sum
Medium

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. You can only move either down or right at any point in time.

Minimum Falling Path Sum
Medium

Given an n x n matrix, return the minimum sum of any falling path through the matrix. A falling path starts at any element in the first row and chooses the element in the next row that is either directly below or diagonally left/right.

Maximum Number of Events That Can Be Attended II
Hard

Given an array of events where events[i] = [startDay, endDay, value], and an integer k. You can attend at most k events. You cannot attend two events that overlap. Return the maximum sum of values that you can receive by attending events.

Make Array Strictly Increasing
Hard

Given two integer arrays arr1 and arr2, return the minimum number of operations to make arr1 strictly increasing. In one operation, you can replace any element in arr1 with any element from arr2. If impossible, return -1.

Graph
2
Number of Islands
Medium

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.

Cheapest Flights Within K Stops
Medium

There are n cities connected by some number of flights. You are given an array flights where flights[i] = [fromi, toi, pricei] indicates that there is a flight from city fromi to city toi with cost pricei. You are also given three integers src, dst, and k, return the cheapest price from src to dst with at most k stops. If there is no such route, return -1.

Greedy
1
Jump Game
Medium

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 at that position. Return true if you can reach the last index, or false otherwise.

Heap
1
Find Median from Data Stream
Hard

The median is the middle value in an ordered integer list. Implement the MedianFinder class.

Intervals
1
Merge Intervals
Medium

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

Linked List
1
Add Two Numbers
Medium

Given two non-empty linked lists representing two non-negative integers stored in reverse order, add them and return the sum as a linked list.

Sliding Window
2
Best Time to Buy and Sell Stock
Easy

You are given an array prices where prices[i] is the price of a given stock on the ith day. You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.

Minimum Size Subarray Sum
Medium

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 there is no such subarray, return 0.

Two Pointers
1
Trapping Rain Water
Hard

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.