Apple

136 DSA problems asked in Apple coding interviews

49 Easy
73 Medium
14 Hard
​

136 problems

Arrays & Hashing
16
Two Sum
Easy

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

Contains Duplicate
Easy

Given an integer array nums, return true if any value appears at least twice in the array, and return false if every element is distinct.

Group Anagrams
Medium

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

Top K Frequent
Medium

Given an integer array nums and an integer k, return the k most frequent elements.

Product Except Self
Medium

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

Valid Sudoku
Medium

Determine if a 9x9 Sudoku board is valid.

Find the Duplicate Number
Medium

Given an array of n + 1 integers where each integer is in the range [1, n], find the one repeated number without modifying the array and using only O(1) space.

Rotate Array
Medium

Given an integer array nums, rotate the array to the right by k steps, where k is non-negative. Do it in-place with O(1) extra space.

Pascal's Triangle
Easy

Given an integer numRows, return the first numRows of Pascal's triangle. In Pascal's triangle, each number is the sum of the two numbers directly above it.

Majority Element
Easy

Given an array nums of size n, return the majority element. The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.

Move Zeroes
Easy

Given an integer array nums, move all 0's to the end of it while maintaining the relative order of the non-zero elements. Note that you must do this in-place without making a copy of the array.

Missing Number
Easy

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.

Merge Sorted Array
Easy

Merge nums2 into nums1 as one sorted array. nums1 has enough space (size m + n) to hold additional elements from nums2.

Plus One
Easy

Given a large integer represented as an integer array digits, increment the large integer by one and return the resulting array of digits.

Find All Numbers Disappeared in an Array
Easy

Given an array nums of n integers where nums[i] is in the range [1, n], return an array of all the integers in the range [1, n] that do not appear in nums. You must write an algorithm that runs in O(n) time and uses only constant extra space.

Largest Number
Medium

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

Backtracking
6
Permutations
Medium

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

Letter Combinations of a Phone Number
Medium

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.

Restore IP Addresses
Medium

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. Given a string s containing only digits, return all possible valid IP addresses that can be formed by inserting dots into s.

N-Queens
Hard

Place n queens on an n x n chessboard such that no two queens attack each other. Return all distinct solutions.

Combinations
Medium

Given two integers n and k, return all possible combinations of k numbers chosen from the range [1, n]. You may return the answer in any order.

Sudoku Solver
Hard

Write a program to solve a Sudoku puzzle by filling the empty cells. A sudoku solution must satisfy all of the following rules: Each of the digits 1-9 must occur exactly once in each row, column, and 3x3 sub-box.

Binary Search
7
Binary Search
Easy

Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1.

Search a 2D Matrix
Medium

Write an efficient algorithm that searches for a value target in an m x n integer matrix matrix.

Search in Rotated Sorted Array
Medium

Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.

Search a 2D Matrix II
Medium

Write an efficient algorithm that searches for a value target in an m x n integer matrix matrix. This matrix has the following properties: Integers in each row are sorted in ascending from left to right. Integers in each column are sorted in ascending from top to bottom.

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

Sqrt(x)
Easy

Given a non-negative integer x, return the square root of x rounded down to the nearest integer.

Search Insert Position
Easy

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be inserted.

Bit Manipulation
6
Single Number
Easy

Given a non-empty array of integers nums, every element appears twice except for one. Find that single one. You must implement a solution with linear runtime complexity and use only constant extra space.

Reverse Bits
Easy

Reverse bits of a given 32-bit unsigned integer.

Number of 1 Bits
Easy

Write a function that takes the binary representation of an unsigned integer and returns the number of 1 bits it has (also known as the Hamming weight).

Power of Two
Easy

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

Counting Bits
Easy

Given an integer n, return an array ans of length n + 1 such that for each i (0 <= i <= n), ans[i] is the number of 1's in the binary representation of i.

Sum of Two Integers
Medium

Given two integers a and b, return the sum of the two integers without using the operators + and -. Use bitwise operations instead.

Design
2
LRU Cache
Medium

Design a data structure that follows the constraints of a Least Recently Used (LRU) cache. Implement the LRUCache class with get(key) returning the value or -1 if not found, and put(key, value) to insert or update. When capacity is exceeded, evict the least recently used key.

LFU Cache
Hard

Design and implement a data structure for a Least Frequently Used (LFU) cache. Implement get and put operations with O(1) time complexity.

Dynamic Programming
12
Climbing Stairs
Easy

You are climbing a staircase. It takes n steps to reach the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Maximum Product Subarray
Medium

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

Unique Paths
Medium

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 (i.e., grid[m - 1][n - 1]). The robot can only move either down or right at any point in time. Given the two integers m and n, return the number of possible unique paths that the robot can take to reach the bottom-right corner.

Min Cost Climbing Stairs
Easy

You are given an integer array cost where cost[i] is the cost of ith step on a staircase. Once you pay the cost, you can either climb one or two steps. You can either start from the step with index 0, or the step with index 1. Return the minimum cost to reach the top of the floor.

Edit Distance
Hard

Given two strings word1 and word2, return the minimum number of operations required to convert word1 to word2. Operations: insert, delete, or replace a character.

Longest Palindromic Substring
Medium

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

Partition Equal Subset Sum
Medium

Given an integer array nums, return true if you can partition the array into two subsets such that the sum of the elements in both subsets is equal.

Maximal Square
Medium

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.

Triangle
Medium

Given a triangle array, return the minimum path sum from top to bottom. For each step, you may move to an adjacent number of the row below. More formally, if you are on index i on the current row, you may move to either index i or index i + 1 on the next row.

Longest Palindromic Subsequence
Medium

Given a string s, find the longest palindromic subsequence's length in s. A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.

Regular Expression Matching
Hard

Given an input string s and a pattern p, implement regular expression matching with support for '.' and '*' where: '.' Matches any single character. '*' Matches zero or more of the preceding element. The matching should cover the entire input string (not partial).

Maximum Profit in Job Scheduling
Hard

We have n jobs, where every job is scheduled to be done from startTime[i] to endTime[i], obtaining a profit of profit[i]. Return the maximum profit you can take such that there are no two jobs with overlapping time ranges.

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

Course Schedule
Medium

There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai. Return true if you can finish all courses. Otherwise, return false.

Pacific Atlantic Water Flow
Medium

Return a list of grid coordinates where water can flow to both the Pacific and Atlantic oceans.

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.

Rotting Oranges
Medium

You are given an m x n grid where each cell can have one of three values: 0 (empty), 1 (fresh orange), or 2 (rotten orange). Every minute, any fresh orange that is 4-directionally adjacent to a rotten orange becomes rotten. Return the minimum number of minutes until no cell has a fresh orange. If impossible, return -1.

Course Schedule II
Medium

There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai. Return the ordering of courses you should take to finish all courses. If there are many valid answers, return any of them. If it is impossible to finish all courses, return an empty array.

Accounts Merge
Medium

Given a list of accounts where each account contains a name and emails, merge accounts belonging to the same person (accounts that share at least one common email).

Min Cost to Connect All Points
Medium

You are given an array points representing integer coordinates of some points on a 2D-plane, where points[i] = [xi, yi]. The cost of connecting two points [xi, yi] and [xj, yj] is the manhattan distance between them: |xi - xj| + |yi - yj|. Return the minimum cost to make all points connected.

Number of Provinces
Medium

There are n cities. Some of them are connected, while some are not. If city a is connected directly with city b, and city b is connected directly with city c, then city a is connected indirectly with city c. A province is a group of directly or indirectly connected cities and no other cities outside of the group. Return the total number of provinces.

Path With Minimum Effort
Medium

You are a hiker preparing for an upcoming hike. You are given heights, a 2D array of size rows x columns, where heights[row][col] represents the height of cell (row, col). You are situated in the top-left cell, (0, 0), and you hope to travel to the bottom-right cell, (rows-1, columns-1). The effort required to travel from one cell to an adjacent cell is the absolute difference of their heights. Return the minimum effort required to travel from the top-left cell to the bottom-right cell.

Greedy
5
Maximum Subarray
Medium

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

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.

Jump Game II
Medium

You are given a 0-indexed array of integers nums of length n. You are initially positioned at nums[0]. Each element nums[i] represents the maximum length of a forward jump from index i. Return the minimum number of jumps to reach nums[n - 1].

Best Time to Buy and Sell Stock II
Medium

Find the maximum profit from buying and selling stock with unlimited transactions. You may hold at most one share at a time.

Candy
Hard

There are n children standing in a line. Each child is assigned a rating value given in the integer array ratings. You are giving candies to these children subjected to the following requirements: Each child must have at least one candy. Children with a higher rating get more candies than their neighbors. Return the minimum number of candies you need to have to distribute the candies to the children.

Heap
7
Find Median from Data Stream
Hard

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

Reorganize String
Medium

Given a string s, rearrange the characters of s so that any two adjacent characters are not the same. Return any possible rearrangement of s or return "" if not possible.

Task Scheduler
Medium

Given a characters array tasks, representing the tasks a CPU needs to do, where each letter represents a different task. Tasks could be done in any order. Each task is done in one unit of time. For each unit of time, the CPU could complete either one task or just be idle. However, there is a non-negative integer n that represents the cooldown period between two same tasks (the same letter in the array), that is that there must be at least n units of time between any two same tasks.

Kth Largest Element in a Stream
Easy

Design a class to find the kth largest element in a stream. Note that it is the kth largest element in the sorted order, not the kth distinct element.

K Closest Points to Origin
Medium

Given an array of points where points[i] = [xi, yi] represents a point on the X-Y plane and an integer k, return the k closest points to the origin (0, 0). The distance between two points is the Euclidean distance. You may return the answer in any order.

Kth Largest Element in an Array
Medium

Given an integer array nums and an integer k, return the kth largest element in the array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

Design Twitter
Medium

Design a simplified version of Twitter where users can post tweets, follow/unfollow another user, and see the 10 most recent tweets in their news feed. Implement the Twitter class with postTweet, getNewsFeed, follow, and unfollow methods.

Intervals
3
Meeting Rooms II
Medium

Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],...] (si < ei), find the minimum number of conference rooms required.

Insert Interval
Medium

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 intervals is sorted in ascending order by starti. You are also given an interval newInterval = [start, end] that represents the start and end of another interval. Insert newInterval into intervals such that intervals is still sorted in ascending order by starti and intervals still does not have any overlapping intervals (merge overlapping intervals if necessary).

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
14
Reverse Linked List
Easy

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

Linked List Cycle
Easy

Given head, the head of a linked list, determine if the linked list has a cycle in it. A cycle exists if there is some node that can be reached again by continuously following the next pointer.

Reorder List
Medium

You are given the head of a singly linked-list. The list can be represented as: L0 → L1 → … → Ln - 1 → Ln. Reorder the list to be on the following form: L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …

Merge Two Sorted Lists
Easy

You are given the heads of two sorted linked lists list1 and list2. Merge the two lists into one sorted list. The list should be made by splicing together the nodes of the first two lists.

Merge K Sorted Lists
Hard

You are given an array of k linked-lists lists, each linked-list is sorted in ascending order. Merge all the linked-lists into one sorted linked-list and return it.

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.

Copy List with Random Pointer
Medium

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. Construct a deep copy of the list.

Palindrome Linked List
Easy

Given the head of a singly linked list, return true if it is a palindrome or false otherwise.

Swap Nodes in Pairs
Medium

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

Remove Linked List Elements
Easy

Given the head of a linked list and an integer val, remove all the nodes of the linked list that has Node.val == val, and return the new head.

Linked List Cycle II
Medium

Given the head of a linked list, return the node where the cycle begins. If there is no cycle, return null.

Middle of the Linked List
Easy

Given the head of a singly linked list, return the middle node of the linked list. If there are two middle nodes, return the second middle node.

Intersection of Two Linked Lists
Easy

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 all, return null.

Rotate List
Medium

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

Math
5
Happy Number
Easy

Write an algorithm to determine if a number n is happy. A happy number is a number defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits, and repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1.

Count Primes
Medium

Given an integer n, return the number of prime numbers that are strictly less than n.

Reverse Integer
Medium

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, return 0.

Palindrome Number
Easy

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

Multiply Strings
Medium

Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a string. You must not use any built-in BigInteger library or convert the inputs to integer directly.

Matrix
3
Rotate Image
Medium

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

Spiral Matrix
Medium

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

Spiral Matrix II
Medium

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

Sliding Window
4
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.

Longest Substring Without Repeating Characters
Medium

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

Longest Repeating Character Replacement
Medium

You are given a string s and an integer k. You can choose any character of the string and change it to any other uppercase English character. You can perform this operation at most k times. Return the length of the longest substring containing the same letter you can get after performing the above operations.

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.

Stack
4
Valid Parentheses
Easy

Given a string s containing just the characters "(", ")", "{", "}", "[" and "]", determine if the input string is valid. An input string is valid if: Open brackets must be closed by the same type of brackets. Open brackets must be closed in the correct order.

Evaluate Reverse Polish Notation
Medium

Evaluate the value of an arithmetic expression in Reverse Polish Notation. Valid operators are +, -, *, and /. Each operand may be an integer or another expression. Note that division between two integers should truncate toward zero.

Min Stack
Medium

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

Decode String
Medium

Given an encoded string, return its decoded string. The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times.

Strings
3
Longest Common Prefix
Easy

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

Roman to Integer
Easy

Given a roman numeral, convert it to an integer.

Length of Last Word
Easy

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

Trees
19
Maximum Depth of Binary Tree
Easy

Given the root of a binary tree, return its maximum depth.

Invert Binary Tree
Easy

Given the root of a binary tree, invert the tree, and return its root.

Same Tree
Easy

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

Lowest Common Ancestor of a Binary Tree
Medium

Find the lowest common ancestor (LCA) of two nodes in a binary tree. The LCA is the lowest node that has both p and q as descendants.

Binary Tree Level Order Traversal
Medium

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

Serialize and Deserialize Binary Tree
Hard

Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work.

Binary Tree Maximum Path Sum
Hard

A path in a binary tree is a sequence of nodes where each pair of adjacent nodes in the sequence has an edge connecting them. A node can only appear in the sequence at most once. Note that the path does not need to pass through the root. The path sum is the sum of the node's values in the path. Given the root of a binary tree, return the maximum path sum of any non-empty path.

Binary Tree Right Side View
Medium

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.

Diameter of Binary Tree
Easy

Given the root of a binary tree, return the length of the diameter of the tree.

Balanced Binary Tree
Easy

Given a binary tree, determine if it is height-balanced. A height-balanced binary tree is a binary tree in which the depth of the two subtrees of every node never differs by more than one.

Symmetric Tree
Easy

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

Path Sum
Easy

Given the root of a binary tree and an integer targetSum, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals targetSum.

Flatten Binary Tree to Linked List
Medium

Given the root of a binary tree, flatten the tree into a "linked list": The "linked list" should use the same TreeNode class where the right child pointer points to the next node in the list and the left child pointer is always null. The "linked list" should be in the same order as a pre-order traversal of the binary tree.

Populating Next Right Pointers
Medium

You are given a perfect binary tree where all leaves are on the same level, and every parent has two children. Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.

Minimum Depth of Binary Tree
Easy

Given a binary tree, find its minimum depth. The minimum depth is the number of nodes along the shortest path from the root node down to the nearest leaf node.

Binary Tree Paths
Easy

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

Sum of Left Leaves
Easy

Given the root of a binary tree, return the sum of all left leaves. A leaf is a node with no children. A left leaf is a leaf that is the left child of another node.

Convert Sorted Array to Binary Search Tree
Easy

Given an integer array nums where the elements are sorted in ascending order, convert it to a height-balanced binary search tree.

Recover Binary Search Tree
Medium

Two nodes of a BST are swapped by mistake. Recover the tree without changing its structure.

Trie
1
Concatenated Words
Hard

Given an array of strings words (without duplicates), return all the concatenated words in the given list. A concatenated word is a string that is comprised entirely of at least two shorter words in the given array.

Two Pointers
9
Valid Palindrome
Easy

A phrase is a palindrome if, after converting all uppercase letters into lowercase letters and removing all non-alphanumeric characters, it reads the same forward and backward.

Two Sum II - Input Array Is Sorted
Medium

Find two numbers that add up to a specific target number in a sorted array. Return 1-based indices.

3Sum
Medium

Find all unique triplets in the array which gives the sum of zero.

Container With Most Water
Medium

Find two lines that together with the x-axis form a container, such that the container contains the most water.

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.

Reverse String
Easy

Write a function that reverses a string. The input string is given as an array of characters s. You must do this by modifying the input array in-place with O(1) extra memory.

Remove Duplicates from Sorted Array
Easy

Given an integer array nums sorted in non-decreasing order, remove the duplicates in-place such that each unique element appears only once. Return the number of unique elements.

Sort Colors
Medium

Given an array with n objects colored red, white, or blue (represented by 0, 1, and 2), sort them in-place so that objects of the same color are adjacent (Dutch National Flag problem).

Squares of a Sorted Array
Easy

Given an integer array nums sorted in non-decreasing order, return an array of the squares of each number sorted in non-decreasing order.