🔎 Browse questions

Can you solve this real interview question? 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. You may assume that each input would have exactly one solution, and you may not use the same element twice. You can return the answer in any order.   Example 1: Input: nums = [2,7,11,15], target = 9 Output: [0,1] Explanation: Because nums[0] + nums[1] == 9, we return [0, 1]. Example 2: Input: nums = [3,2,4], target = 6 Output: [1,2] Example 3: Input: nums = [3,3], target = 6 Output: [0,1]   Constraints: * 2 <= nums.length <= 104 * -109 <= nums[i] <= 109 * -109 <= target <= 109 * Only one valid answer exists.   Follow-up: Can you come up with an algorithm that is less than O(n2) time complexity?

Can you solve this real interview question? 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. 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. Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.   Example 1: Input: prices = [7,1,5,3,6,4] Output: 5 Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5. Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell. Example 2: Input: prices = [7,6,4,3,1] Output: 0 Explanation: In this case, no transactions are done and the max profit = 0.   Constraints: * 1 <= prices.length <= 105 * 0 <= prices[i] <= 104

Can you solve this real interview question? Contains Duplicate - 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.   Example 1: Input: nums = [1,2,3,1] Output: true Explanation: The element 1 occurs at the indices 0 and 3. Example 2: Input: nums = [1,2,3,4] Output: false Explanation: All elements are distinct. Example 3: Input: nums = [1,1,1,3,3,4,3,2,4,2] Output: true   Constraints: * 1 <= nums.length <= 105 * -109 <= nums[i] <= 109

Can you solve this real interview question? Maximum Subarray - Given an integer array nums, find the subarray with the largest sum, and return its sum.   Example 1: Input: nums = [-2,1,-3,4,-1,2,1,-5,4] Output: 6 Explanation: The subarray [4,-1,2,1] has the largest sum 6. Example 2: Input: nums = [1] Output: 1 Explanation: The subarray [1] has the largest sum 1. Example 3: Input: nums = [5,4,-1,7,8] Output: 23 Explanation: The subarray [5,4,-1,7,8] has the largest sum 23.   Constraints: * 1 <= nums.length <= 105 * -104 <= nums[i] <= 104   Follow up: If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

Can you solve this real interview question? Number of 1 Bits - Write a function that takes the binary representation of a positive integer and returns the number of set bits it has (also known as the Hamming weight [http://en.wikipedia.org/wiki/Hamming_weight]).   Example 1: Input: n = 11 Output: 3 Explanation: The input binary string 1011 has a total of three set bits. Example 2: Input: n = 128 Output: 1 Explanation: The input binary string 10000000 has a total of one set bit. Example 3: Input: n = 2147483645 Output: 30 Explanation: The input binary string 1111111111111111111111111111101 has a total of thirty set bits.   Constraints: * 1 <= n <= 231 - 1   Follow up: If this function is called many times, how would you optimize it?

Can you solve this real interview question? Counting Bits - 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.   Example 1: Input: n = 2 Output: [0,1,1] Explanation: 0 --> 0 1 --> 1 2 --> 10 Example 2: Input: n = 5 Output: [0,1,1,2,1,2] Explanation: 0 --> 0 1 --> 1 2 --> 10 3 --> 11 4 --> 100 5 --> 101   Constraints: * 0 <= n <= 105   Follow up: * It is very easy to come up with a solution with a runtime of O(n log n). Can you do it in linear time O(n) and possibly in a single pass? * Can you do it without using any built-in function (i.e., like __builtin_popcount in C++)?

Can you solve this real interview question? 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.   Example 1: Input: nums = [3,0,1] Output: 2 Explanation: n = 3 since there are 3 numbers, so all numbers are in the range [0,3]. 2 is the missing number in the range since it does not appear in nums. Example 2: Input: nums = [0,1] Output: 2 Explanation: n = 2 since there are 2 numbers, so all numbers are in the range [0,2]. 2 is the missing number in the range since it does not appear in nums. Example 3: Input: nums = [9,6,4,2,3,5,7,0,1] Output: 8 Explanation: n = 9 since there are 9 numbers, so all numbers are in the range [0,9]. 8 is the missing number in the range since it does not appear in nums.   Constraints: * n == nums.length * 1 <= n <= 104 * 0 <= nums[i] <= n * All the numbers of nums are unique.   Follow up: Could you implement a solution using only O(1) extra space complexity and O(n) runtime complexity?

Can you solve this real interview question? Reverse Bits - Reverse bits of a given 32 bits unsigned integer. Note: * Note that in some languages, such as Java, there is no unsigned integer type. In this case, both input and output will be given as a signed integer type. They should not affect your implementation, as the integer's internal binary representation is the same, whether it is signed or unsigned. * In Java, the compiler represents the signed integers using 2's complement notation [https://en.wikipedia.org/wiki/Two%27s_complement]. Therefore, in Example 2 above, the input represents the signed integer -3 and the output represents the signed integer -1073741825.   Example 1: Input: n = 00000010100101000001111010011100 Output: 964176192 (00111001011110000010100101000000) Explanation: The input binary string 00000010100101000001111010011100 represents the unsigned integer 43261596, so return 964176192 which its binary representation is 00111001011110000010100101000000. Example 2: Input: n = 11111111111111111111111111111101 Output: 3221225471 (10111111111111111111111111111111) Explanation: The input binary string 11111111111111111111111111111101 represents the unsigned integer 4294967293, so return 3221225471 which its binary representation is 10111111111111111111111111111111.   Constraints: * The input must be a binary string of length 32   Follow up: If this function is called many times, how would you optimize it?

Can you solve this real interview question? Climbing Stairs - 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?   Example 1: Input: n = 2 Output: 2 Explanation: There are two ways to climb to the top. 1. 1 step + 1 step 2. 2 steps Example 2: Input: n = 3 Output: 3 Explanation: There are three ways to climb to the top. 1. 1 step + 1 step + 1 step 2. 1 step + 2 steps 3. 2 steps + 1 step   Constraints: * 1 <= n <= 45

Can you solve this real interview question? Meeting Rooms - Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

Can you solve this real interview question? Reverse Linked List - Given the head of a singly linked list, reverse the list, and return the reversed list.   Example 1: [https://assets.leetcode.com/uploads/2021/02/19/rev1ex1.jpg] Input: head = [1,2,3,4,5] Output: [5,4,3,2,1] Example 2: [https://assets.leetcode.com/uploads/2021/02/19/rev1ex2.jpg] Input: head = [1,2] Output: [2,1] Example 3: Input: head = [] Output: []   Constraints: * The number of nodes in the list is the range [0, 5000]. * -5000 <= Node.val <= 5000   Follow up: A linked list can be reversed either iteratively or recursively. Could you implement both?

Can you solve this real interview question? Linked List Cycle - Given head, the head of a linked list, determine if the linked list has a cycle in it. There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail's next pointer is connected to. Note that pos is not passed as a parameter. Return true if there is a cycle in the linked list. Otherwise, return false.   Example 1: [https://assets.leetcode.com/uploads/2018/12/07/circularlinkedlist.png] Input: head = [3,2,0,-4], pos = 1 Output: true Explanation: There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed). Example 2: [https://assets.leetcode.com/uploads/2018/12/07/circularlinkedlist_test2.png] Input: head = [1,2], pos = 0 Output: true Explanation: There is a cycle in the linked list, where the tail connects to the 0th node. Example 3: [https://assets.leetcode.com/uploads/2018/12/07/circularlinkedlist_test3.png] Input: head = [1], pos = -1 Output: false Explanation: There is no cycle in the linked list.   Constraints: * The number of the nodes in the list is in the range [0, 104]. * -105 <= Node.val <= 105 * pos is -1 or a valid index in the linked-list.   Follow up: Can you solve it using O(1) (i.e. constant) memory?

Can you solve this real interview question? Merge Two Sorted Lists - 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. Return the head of the merged linked list.   Example 1: [https://assets.leetcode.com/uploads/2020/10/03/merge_ex1.jpg] Input: list1 = [1,2,4], list2 = [1,3,4] Output: [1,1,2,3,4,4] Example 2: Input: list1 = [], list2 = [] Output: [] Example 3: Input: list1 = [], list2 = [0] Output: [0]   Constraints: * The number of nodes in both lists is in the range [0, 50]. * -100 <= Node.val <= 100 * Both list1 and list2 are sorted in non-decreasing order.

Can you solve this real interview question? Valid Anagram - Given two strings s and t, return true if t is an anagram of s, and false otherwise.   Example 1: Input: s = "anagram", t = "nagaram" Output: true Example 2: Input: s = "rat", t = "car" Output: false   Constraints: * 1 <= s.length, t.length <= 5 * 104 * s and t consist of lowercase English letters.   Follow up: What if the inputs contain Unicode characters? How would you adapt your solution to such a case?

Can you solve this real interview question? Valid Parentheses - Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid. An input string is valid if: 1. Open brackets must be closed by the same type of brackets. 2. Open brackets must be closed in the correct order. 3. Every close bracket has a corresponding open bracket of the same type.   Example 1: Input: s = "()" Output: true Example 2: Input: s = "()[]{}" Output: true Example 3: Input: s = "(]" Output: false Example 4: Input: s = "([])" Output: true   Constraints: * 1 <= s.length <= 104 * s consists of parentheses only '()[]{}'.

Can you solve this real interview question? Valid Palindrome - 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. Alphanumeric characters include letters and numbers. Given a string s, return true if it is a palindrome, or false otherwise.   Example 1: Input: s = "A man, a plan, a canal: Panama" Output: true Explanation: "amanaplanacanalpanama" is a palindrome. Example 2: Input: s = "race a car" Output: false Explanation: "raceacar" is not a palindrome. Example 3: Input: s = " " Output: true Explanation: s is an empty string "" after removing non-alphanumeric characters. Since an empty string reads the same forward and backward, it is a palindrome.   Constraints: * 1 <= s.length <= 2 * 105 * s consists only of printable ASCII characters.

Can you solve this real interview question? Maximum Depth of Binary Tree - Given the root of a binary tree, return its maximum depth. A binary tree's maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.   Example 1: [https://assets.leetcode.com/uploads/2020/11/26/tmp-tree.jpg] Input: root = [3,9,20,null,null,15,7] Output: 3 Example 2: Input: root = [1,null,2] Output: 2   Constraints: * The number of nodes in the tree is in the range [0, 104]. * -100 <= Node.val <= 100

Can you solve this real interview question? Same Tree - Given the roots of two binary trees p and q, write a function to check if they are the same or not. Two binary trees are considered the same if they are structurally identical, and the nodes have the same value.   Example 1: [https://assets.leetcode.com/uploads/2020/12/20/ex1.jpg] Input: p = [1,2,3], q = [1,2,3] Output: true Example 2: [https://assets.leetcode.com/uploads/2020/12/20/ex2.jpg] Input: p = [1,2], q = [1,null,2] Output: false Example 3: [https://assets.leetcode.com/uploads/2020/12/20/ex3.jpg] Input: p = [1,2,1], q = [1,1,2] Output: false   Constraints: * The number of nodes in both trees is in the range [0, 100]. * -104 <= Node.val <= 104

Can you solve this real interview question? Invert Binary Tree - Given the root of a binary tree, invert the tree, and return its root.   Example 1: [https://assets.leetcode.com/uploads/2021/03/14/invert1-tree.jpg] Input: root = [4,2,7,1,3,6,9] Output: [4,7,2,9,6,3,1] Example 2: [https://assets.leetcode.com/uploads/2021/03/14/invert2-tree.jpg] Input: root = [2,1,3] Output: [2,3,1] Example 3: Input: root = [] Output: []   Constraints: * The number of nodes in the tree is in the range [0, 100]. * -100 <= Node.val <= 100

Can you solve this real interview question? Subtree of Another Tree - Given the roots of two binary trees root and subRoot, return true if there is a subtree of root with the same structure and node values of subRoot and false otherwise. A subtree of a binary tree tree is a tree that consists of a node in tree and all of this node's descendants. The tree tree could also be considered as a subtree of itself.   Example 1: [https://assets.leetcode.com/uploads/2021/04/28/subtree1-tree.jpg] Input: root = [3,4,5,1,2], subRoot = [4,1,2] Output: true Example 2: [https://assets.leetcode.com/uploads/2021/04/28/subtree2-tree.jpg] Input: root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2] Output: false   Constraints: * The number of nodes in the root tree is in the range [1, 2000]. * The number of nodes in the subRoot tree is in the range [1, 1000]. * -104 <= root.val <= 104 * -104 <= subRoot.val <= 104

Can you solve this real interview question? 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. According to the definition of LCA on Wikipedia [https://en.wikipedia.org/wiki/Lowest_common_ancestor]: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”   Example 1: [https://assets.leetcode.com/uploads/2018/12/14/binarysearchtree_improved.png] Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8 Output: 6 Explanation: The LCA of nodes 2 and 8 is 6. Example 2: [https://assets.leetcode.com/uploads/2018/12/14/binarysearchtree_improved.png] Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4 Output: 2 Explanation: The LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition. Example 3: Input: root = [2,1], p = 2, q = 1 Output: 2   Constraints: * The number of nodes in the tree is in the range [2, 105]. * -109 <= Node.val <= 109 * All Node.val are unique. * p != q * p and q will exist in the BST.

Can you solve this real interview question? Majority Element - 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.   Example 1: Input: nums = [3,2,3] Output: 3 Example 2: Input: nums = [2,2,1,1,1,2,2] Output: 2   Constraints: * n == nums.length * 1 <= n <= 5 * 104 * -109 <= nums[i] <= 109   Follow-up: Could you solve the problem in linear time and in O(1) space?

Can you solve this real interview question? Longest Palindrome - Given a string s which consists of lowercase or uppercase letters, return the length of the longest palindrome that can be built with those letters. Letters are case sensitive, for example, "Aa" is not considered a palindrome.   Example 1: Input: s = "abccccdd" Output: 7 Explanation: One longest palindrome that can be built is "dccaccd", whose length is 7. Example 2: Input: s = "a" Output: 1 Explanation: The longest palindrome that can be built is "a", whose length is 1.   Constraints: * 1 <= s.length <= 2000 * s consists of lowercase and/or uppercase English letters only.

Can you solve this real interview question? Binary Search - 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. You must write an algorithm with O(log n) runtime complexity.   Example 1: Input: nums = [-1,0,3,5,9,12], target = 9 Output: 4 Explanation: 9 exists in nums and its index is 4 Example 2: Input: nums = [-1,0,3,5,9,12], target = 2 Output: -1 Explanation: 2 does not exist in nums so return -1   Constraints: * 1 <= nums.length <= 104 * -104 < nums[i], target < 104 * All the integers in nums are unique. * nums is sorted in ascending order.

Can you solve this real interview question? First Bad Version - You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad. Suppose you have n versions [1, 2, ..., n] and you want to find out the first bad one, which causes all the following ones to be bad. You are given an API bool isBadVersion(version) which returns whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.   Example 1: Input: n = 5, bad = 4 Output: 4 Explanation: call isBadVersion(3) -> false call isBadVersion(5) -> true call isBadVersion(4) -> true Then 4 is the first bad version. Example 2: Input: n = 1, bad = 1 Output: 1   Constraints: * 1 <= bad <= n <= 231 - 1

Can you solve this real interview question? Flood Fill - You are given an image represented by an m x n grid of integers image, where image[i][j] represents the pixel value of the image. You are also given three integers sr, sc, and color. Your task is to perform a flood fill on the image starting from the pixel image[sr][sc]. To perform a flood fill: 1. Begin with the starting pixel and change its color to color. 2. Perform the same process for each pixel that is directly adjacent (pixels that share a side with the original pixel, either horizontally or vertically) and shares the same color as the starting pixel. 3. Keep repeating this process by checking neighboring pixels of the updated pixels and modifying their color if it matches the original color of the starting pixel. 4. The process stops when there are no more adjacent pixels of the original color to update. Return the modified image after performing the flood fill.   Example 1: Input: image = [[1,1,1],[1,1,0],[1,0,1]], sr = 1, sc = 1, color = 2 Output: [[2,2,2],[2,2,0],[2,0,1]] Explanation: [https://assets.leetcode.com/uploads/2021/06/01/flood1-grid.jpg] From the center of the image with position (sr, sc) = (1, 1) (i.e., the red pixel), all pixels connected by a path of the same color as the starting pixel (i.e., the blue pixels) are colored with the new color. Note the bottom corner is not colored 2, because it is not horizontally or vertically connected to the starting pixel. Example 2: Input: image = [[0,0,0],[0,0,0]], sr = 0, sc = 0, color = 0 Output: [[0,0,0],[0,0,0]] Explanation: The starting pixel is already colored with 0, which is the same as the target color. Therefore, no changes are made to the image.   Constraints: * m == image.length * n == image[i].length * 1 <= m, n <= 50 * 0 <= image[i][j], color < 216 * 0 <= sr < m * 0 <= sc < n

Can you solve this real interview question? 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. According to the definition of LCA on Wikipedia [https://en.wikipedia.org/wiki/Lowest_common_ancestor]: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”   Example 1: [https://assets.leetcode.com/uploads/2018/12/14/binarysearchtree_improved.png] Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8 Output: 6 Explanation: The LCA of nodes 2 and 8 is 6. Example 2: [https://assets.leetcode.com/uploads/2018/12/14/binarysearchtree_improved.png] Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4 Output: 2 Explanation: The LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition. Example 3: Input: root = [2,1], p = 2, q = 1 Output: 2   Constraints: * The number of nodes in the tree is in the range [2, 105]. * -109 <= Node.val <= 109 * All Node.val are unique. * p != q * p and q will exist in the BST.

Can you solve this real interview question? Invert Binary Tree - Given the root of a binary tree, invert the tree, and return its root.   Example 1: [https://assets.leetcode.com/uploads/2021/03/14/invert1-tree.jpg] Input: root = [4,2,7,1,3,6,9] Output: [4,7,2,9,6,3,1] Example 2: [https://assets.leetcode.com/uploads/2021/03/14/invert2-tree.jpg] Input: root = [2,1,3] Output: [2,3,1] Example 3: Input: root = [] Output: []   Constraints: * The number of nodes in the tree is in the range [0, 100]. * -100 <= Node.val <= 100

Can you solve this real interview question? Balanced Binary Tree - Given a binary tree, determine if it is height-balanced.   Example 1: [https://assets.leetcode.com/uploads/2020/10/06/balance_1.jpg] Input: root = [3,9,20,null,null,15,7] Output: true Example 2: [https://assets.leetcode.com/uploads/2020/10/06/balance_2.jpg] Input: root = [1,2,2,3,3,null,null,4,4] Output: false Example 3: Input: root = [] Output: true   Constraints: * The number of nodes in the tree is in the range [0, 5000]. * -104 <= Node.val <= 104

Can you solve this real interview question? Diameter of Binary Tree - Given the root of a binary tree, return the length of the diameter of the tree. The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root. The length of a path between two nodes is represented by the number of edges between them.   Example 1: [https://assets.leetcode.com/uploads/2021/03/06/diamtree.jpg] Input: root = [1,2,3,4,5] Output: 3 Explanation: 3 is the length of the path [4,2,1,3] or [5,2,1,3]. Example 2: Input: root = [1,2] Output: 1   Constraints: * The number of nodes in the tree is in the range [1, 104]. * -100 <= Node.val <= 100

Can you solve this real interview question? Ransom Note - Given two strings ransomNote and magazine, return true if ransomNote can be constructed by using the letters from magazine and false otherwise. Each letter in magazine can only be used once in ransomNote.   Example 1: Input: ransomNote = "a", magazine = "b" Output: false Example 2: Input: ransomNote = "aa", magazine = "ab" Output: false Example 3: Input: ransomNote = "aa", magazine = "aab" Output: true   Constraints: * 1 <= ransomNote.length, magazine.length <= 105 * ransomNote and magazine consist of lowercase English letters.

Can you solve this real interview question? Linked List Cycle - Given head, the head of a linked list, determine if the linked list has a cycle in it. There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail's next pointer is connected to. Note that pos is not passed as a parameter. Return true if there is a cycle in the linked list. Otherwise, return false.   Example 1: [https://assets.leetcode.com/uploads/2018/12/07/circularlinkedlist.png] Input: head = [3,2,0,-4], pos = 1 Output: true Explanation: There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed). Example 2: [https://assets.leetcode.com/uploads/2018/12/07/circularlinkedlist_test2.png] Input: head = [1,2], pos = 0 Output: true Explanation: There is a cycle in the linked list, where the tail connects to the 0th node. Example 3: [https://assets.leetcode.com/uploads/2018/12/07/circularlinkedlist_test3.png] Input: head = [1], pos = -1 Output: false Explanation: There is no cycle in the linked list.   Constraints: * The number of the nodes in the list is in the range [0, 104]. * -105 <= Node.val <= 105 * pos is -1 or a valid index in the linked-list.   Follow up: Can you solve it using O(1) (i.e. constant) memory?

Can you solve this real interview question? Reverse Linked List - Given the head of a singly linked list, reverse the list, and return the reversed list.   Example 1: [https://assets.leetcode.com/uploads/2021/02/19/rev1ex1.jpg] Input: head = [1,2,3,4,5] Output: [5,4,3,2,1] Example 2: [https://assets.leetcode.com/uploads/2021/02/19/rev1ex2.jpg] Input: head = [1,2] Output: [2,1] Example 3: Input: head = [] Output: []   Constraints: * The number of nodes in the list is the range [0, 5000]. * -5000 <= Node.val <= 5000   Follow up: A linked list can be reversed either iteratively or recursively. Could you implement both?

Can you solve this real interview question? Middle of the Linked List - 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.   Example 1: [https://assets.leetcode.com/uploads/2021/07/23/lc-midlist1.jpg] Input: head = [1,2,3,4,5] Output: [3,4,5] Explanation: The middle node of the list is node 3. Example 2: [https://assets.leetcode.com/uploads/2021/07/23/lc-midlist2.jpg] Input: head = [1,2,3,4,5,6] Output: [4,5,6] Explanation: Since the list has two middle nodes with values 3 and 4, we return the second one.   Constraints: * The number of nodes in the list is in the range [1, 100]. * 1 <= Node.val <= 100

Can you solve this real interview question? Implement Queue using Stacks - Implement a first in first out (FIFO) queue using only two stacks. The implemented queue should support all the functions of a normal queue (push, peek, pop, and empty). Implement the MyQueue class: * void push(int x) Pushes element x to the back of the queue. * int pop() Removes the element from the front of the queue and returns it. * int peek() Returns the element at the front of the queue. * boolean empty() Returns true if the queue is empty, false otherwise. Notes: * You must use only standard operations of a stack, which means only push to top, peek/pop from top, size, and is empty operations are valid. * Depending on your language, the stack may not be supported natively. You may simulate a stack using a list or deque (double-ended queue) as long as you use only a stack's standard operations.   Example 1: Input ["MyQueue", "push", "push", "peek", "pop", "empty"] [[], [1], [2], [], [], []] Output [null, null, null, 1, 1, false] Explanation MyQueue myQueue = new MyQueue(); myQueue.push(1); // queue is: [1] myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue) myQueue.peek(); // return 1 myQueue.pop(); // return 1, queue is [2] myQueue.empty(); // return false   Constraints: * 1 <= x <= 9 * At most 100 calls will be made to push, pop, peek, and empty. * All the calls to pop and peek are valid.   Follow-up: Can you implement the queue such that each operation is amortized [https://en.wikipedia.org/wiki/Amortized_analysis] O(1) time complexity? In other words, performing n operations will take overall O(n) time even if one of those operations may take longer.

Can you solve this real interview question? Min Stack - Design a stack that supports push, pop, top, and retrieving the minimum element in constant time. Implement the MinStack class: * MinStack() initializes the stack object. * void push(int val) pushes the element val onto the stack. * void pop() removes the element on the top of the stack. * int top() gets the top element of the stack. * int getMin() retrieves the minimum element in the stack. You must implement a solution with O(1) time complexity for each function.   Example 1: Input ["MinStack","push","push","push","getMin","pop","top","getMin"] [[],[-2],[0],[-3],[],[],[],[]] Output [null,null,null,null,-3,null,0,-2] Explanation MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.getMin(); // return -3 minStack.pop(); minStack.top(); // return 0 minStack.getMin(); // return -2   Constraints: * -231 <= val <= 231 - 1 * Methods pop, top and getMin operations will always be called on non-empty stacks. * At most 3 * 104 calls will be made to push, pop, top, and getMin.

Can you solve this real interview question? Add Binary - Given two binary strings a and b, return their sum as a binary string.   Example 1: Input: a = "11", b = "1" Output: "100" Example 2: Input: a = "1010", b = "1011" Output: "10101"   Constraints: * 1 <= a.length, b.length <= 104 * a and b consist only of '0' or '1' characters. * Each string does not contain leading zeros except for the zero itself.

Can you solve this real interview question? 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]. The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer. You must write an algorithm that runs in O(n) time and without using the division operation.   Example 1: Input: nums = [1,2,3,4] Output: [24,12,8,6] Example 2: Input: nums = [-1,1,0,-3,3] Output: [0,0,9,0,0]   Constraints: * 2 <= nums.length <= 105 * -30 <= nums[i] <= 30 * The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.   Follow up: Can you solve the problem in O(1) extra space complexity? (The output array does not count as extra space for space complexity analysis.)

Can you solve this real interview question? Maximum Product Subarray - Given an integer array nums, find a subarray that has the largest product, and return the product. The test cases are generated so that the answer will fit in a 32-bit integer.   Example 1: Input: nums = [2,3,-2,4] Output: 6 Explanation: [2,3] has the largest product 6. Example 2: Input: nums = [-2,0,-1] Output: 0 Explanation: The result cannot be 2, because [-2,-1] is not a subarray.   Constraints: * 1 <= nums.length <= 2 * 104 * -10 <= nums[i] <= 10 * The product of any subarray of nums is guaranteed to fit in a 32-bit integer.

Can you solve this real interview question? 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: * [4,5,6,7,0,1,2] if it was rotated 4 times. * [0,1,2,4,5,6,7] if it was rotated 7 times. Notice that rotating an array [a[0], a[1], a[2], ..., a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], ..., a[n-2]]. Given the sorted rotated array nums of unique elements, return the minimum element of this array. You must write an algorithm that runs in O(log n) time.   Example 1: Input: nums = [3,4,5,1,2] Output: 1 Explanation: The original array was [1,2,3,4,5] rotated 3 times. Example 2: Input: nums = [4,5,6,7,0,1,2] Output: 0 Explanation: The original array was [0,1,2,4,5,6,7] and it was rotated 4 times. Example 3: Input: nums = [11,13,15,17] Output: 11 Explanation: The original array was [11,13,15,17] and it was rotated 4 times.   Constraints: * n == nums.length * 1 <= n <= 5000 * -5000 <= nums[i] <= 5000 * All the integers of nums are unique. * nums is sorted and rotated between 1 and n times.

Can you solve this real interview question? Search in Rotated Sorted Array - There is an integer array nums sorted in ascending order (with distinct values). Prior to being passed to your function, nums is possibly rotated at an unknown pivot index k (1 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2]. 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. You must write an algorithm with O(log n) runtime complexity.   Example 1: Input: nums = [4,5,6,7,0,1,2], target = 0 Output: 4 Example 2: Input: nums = [4,5,6,7,0,1,2], target = 3 Output: -1 Example 3: Input: nums = [1], target = 0 Output: -1   Constraints: * 1 <= nums.length <= 5000 * -104 <= nums[i] <= 104 * All values of nums are unique. * nums is an ascending array that is possibly rotated. * -104 <= target <= 104

Can you solve this real interview question? 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. Notice that the solution set must not contain duplicate triplets.   Example 1: Input: nums = [-1,0,1,2,-1,-4] Output: [[-1,-1,2],[-1,0,1]] Explanation: nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0. nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0. nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0. The distinct triplets are [-1,0,1] and [-1,-1,2]. Notice that the order of the output and the order of the triplets does not matter. Example 2: Input: nums = [0,1,1] Output: [] Explanation: The only possible triplet does not sum up to 0. Example 3: Input: nums = [0,0,0] Output: [[0,0,0]] Explanation: The only possible triplet sums up to 0.   Constraints: * 3 <= nums.length <= 3000 * -105 <= nums[i] <= 105

Can you solve this real interview question? 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 two lines that together with the x-axis form a container, such that the container contains the most water. Return the maximum amount of water a container can store. Notice that you may not slant the container.   Example 1: [https://s3-lc-upload.s3.amazonaws.com/uploads/2018/07/17/question_11.jpg] Input: height = [1,8,6,2,5,4,8,3,7] Output: 49 Explanation: The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49. Example 2: Input: height = [1,1] Output: 1   Constraints: * n == height.length * 2 <= n <= 105 * 0 <= height[i] <= 104

Can you solve this real interview question? Sum of Two Integers - Given two integers a and b, return the sum of the two integers without using the operators + and -.   Example 1: Input: a = 1, b = 2 Output: 3 Example 2: Input: a = 2, b = 3 Output: 5   Constraints: * -1000 <= a, b <= 1000

Can you solve this real interview question? Coin Change - You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money. Return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1. You may assume that you have an infinite number of each kind of coin.   Example 1: Input: coins = [1,2,5], amount = 11 Output: 3 Explanation: 11 = 5 + 5 + 1 Example 2: Input: coins = [2], amount = 3 Output: -1 Example 3: Input: coins = [1], amount = 0 Output: 0   Constraints: * 1 <= coins.length <= 12 * 1 <= coins[i] <= 231 - 1 * 0 <= amount <= 104

Can you solve this real interview question? Longest Increasing Subsequence - Given an integer array nums, return the length of the longest strictly increasing subsequence.   Example 1: Input: nums = [10,9,2,5,3,7,101,18] Output: 4 Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4. Example 2: Input: nums = [0,1,0,3,2,3] Output: 4 Example 3: Input: nums = [7,7,7,7,7,7,7] Output: 1   Constraints: * 1 <= nums.length <= 2500 * -104 <= nums[i] <= 104   Follow up: Can you come up with an algorithm that runs in O(n log(n)) time complexity?

Can you solve this real interview question? Longest Common Subsequence - Given two strings text1 and text2, return the length of their longest common subsequence. If there is no common subsequence, return 0. A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters. * For example, "ace" is a subsequence of "abcde". A common subsequence of two strings is a subsequence that is common to both strings.   Example 1: Input: text1 = "abcde", text2 = "ace" Output: 3 Explanation: The longest common subsequence is "ace" and its length is 3. Example 2: Input: text1 = "abc", text2 = "abc" Output: 3 Explanation: The longest common subsequence is "abc" and its length is 3. Example 3: Input: text1 = "abc", text2 = "def" Output: 0 Explanation: There is no such common subsequence, so the result is 0.   Constraints: * 1 <= text1.length, text2.length <= 1000 * text1 and text2 consist of only lowercase English characters.

Can you solve this real interview question? Word Break - Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words. Note that the same word in the dictionary may be reused multiple times in the segmentation.   Example 1: Input: s = "leetcode", wordDict = ["leet","code"] Output: true Explanation: Return true because "leetcode" can be segmented as "leet code". Example 2: Input: s = "applepenapple", wordDict = ["apple","pen"] Output: true Explanation: Return true because "applepenapple" can be segmented as "apple pen apple". Note that you are allowed to reuse a dictionary word. Example 3: Input: s = "catsandog", wordDict = ["cats","dog","sand","and","cat"] Output: false   Constraints: * 1 <= s.length <= 300 * 1 <= wordDict.length <= 1000 * 1 <= wordDict[i].length <= 20 * s and wordDict[i] consist of only lowercase English letters. * All the strings of wordDict are unique.

Can you solve this real interview question? Combination Sum IV - Given an array of distinct integers nums and a target integer target, return the number of possible combinations that add up to target. The test cases are generated so that the answer can fit in a 32-bit integer.   Example 1: Input: nums = [1,2,3], target = 4 Output: 7 Explanation: The possible combination ways are: (1, 1, 1, 1) (1, 1, 2) (1, 2, 1) (1, 3) (2, 1, 1) (2, 2) (3, 1) Note that different sequences are counted as different combinations. Example 2: Input: nums = [9], target = 3 Output: 0   Constraints: * 1 <= nums.length <= 200 * 1 <= nums[i] <= 1000 * All the elements of nums are unique. * 1 <= target <= 1000   Follow up: What if negative numbers are allowed in the given array? How does it change the problem? What limitation we need to add to the question to allow negative numbers?

Can you solve this real interview question? 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 robbing each of them is that adjacent houses have security systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night. Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.   Example 1: Input: nums = [1,2,3,1] Output: 4 Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3). Total amount you can rob = 1 + 3 = 4. Example 2: Input: nums = [2,7,9,3,1] Output: 12 Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1). Total amount you can rob = 2 + 9 + 1 = 12.   Constraints: * 1 <= nums.length <= 100 * 0 <= nums[i] <= 400

Can you solve this real interview question? House Robber II - You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. All houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, adjacent houses have a security system connected, and it will automatically contact the police if two adjacent houses were broken into on the same night. Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.   Example 1: Input: nums = [2,3,2] Output: 3 Explanation: You cannot rob house 1 (money = 2) and then rob house 3 (money = 2), because they are adjacent houses. Example 2: Input: nums = [1,2,3,1] Output: 4 Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3). Total amount you can rob = 1 + 3 = 4. Example 3: Input: nums = [1,2,3] Output: 3   Constraints: * 1 <= nums.length <= 100 * 0 <= nums[i] <= 1000

Can you solve this real interview question? Decode Ways - You have intercepted a secret message encoded as a string of numbers. The message is decoded via the following mapping: "1" -> 'A' "2" -> 'B' ... "25" -> 'Y' "26" -> 'Z' However, while decoding the message, you realize that there are many different ways you can decode the message because some codes are contained in other codes ("2" and "5" vs "25"). For example, "11106" can be decoded into: * "AAJF" with the grouping (1, 1, 10, 6) * "KJF" with the grouping (11, 10, 6) * The grouping (1, 11, 06) is invalid because "06" is not a valid code (only "6" is valid). Note: there may be strings that are impossible to decode. Given a string s containing only digits, return the number of ways to decode it. If the entire string cannot be decoded in any valid way, return 0. The test cases are generated so that the answer fits in a 32-bit integer.   Example 1: Input: s = "12" Output: 2 Explanation: "12" could be decoded as "AB" (1 2) or "L" (12). Example 2: Input: s = "226" Output: 3 Explanation: "226" could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6). Example 3: Input: s = "06" Output: 0 Explanation: "06" cannot be mapped to "F" because of the leading zero ("6" is different from "06"). In this case, the string is not a valid encoding, so return 0.   Constraints: * 1 <= s.length <= 100 * s contains only digits and may contain leading zero(s).

Can you solve this real interview question? 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 (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. The test cases are generated so that the answer will be less than or equal to 2 * 109.   Example 1: [https://assets.leetcode.com/uploads/2018/10/22/robot_maze.png] Input: m = 3, n = 7 Output: 28 Example 2: Input: m = 3, n = 2 Output: 3 Explanation: From the top-left corner, there are a total of 3 ways to reach the bottom-right corner: 1. Right -> Down -> Down 2. Down -> Down -> Right 3. Down -> Right -> Down   Constraints: * 1 <= m, n <= 100

Can you solve this real interview question? 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 at that position. Return true if you can reach the last index, or false otherwise.   Example 1: Input: nums = [2,3,1,1,4] Output: true Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index. Example 2: Input: nums = [3,2,1,0,4] Output: false Explanation: You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index.   Constraints: * 1 <= nums.length <= 104 * 0 <= nums[i] <= 105

Can you solve this real interview question? Clone Graph - Given a reference of a node in a connected [https://en.wikipedia.org/wiki/Connectivity_(graph_theory)#Connected_graph] undirected graph. Return a deep copy [https://en.wikipedia.org/wiki/Object_copying#Deep_copy] (clone) of the graph. Each node in the graph contains a value (int) and a list (List[Node]) of its neighbors. class Node { public int val; public List<Node> neighbors; }   Test case format: For simplicity, each node's value is the same as the node's index (1-indexed). For example, the first node with val == 1, the second node with val == 2, and so on. The graph is represented in the test case using an adjacency list. An adjacency list is a collection of unordered lists used to represent a finite graph. Each list describes the set of neighbors of a node in the graph. The given node will always be the first node with val = 1. You must return the copy of the given node as a reference to the cloned graph.   Example 1: [https://assets.leetcode.com/uploads/2019/11/04/133_clone_graph_question.png] Input: adjList = [[2,4],[1,3],[2,4],[1,3]] Output: [[2,4],[1,3],[2,4],[1,3]] Explanation: There are 4 nodes in the graph. 1st node (val = 1)'s neighbors are 2nd node (val = 2) and 4th node (val = 4). 2nd node (val = 2)'s neighbors are 1st node (val = 1) and 3rd node (val = 3). 3rd node (val = 3)'s neighbors are 2nd node (val = 2) and 4th node (val = 4). 4th node (val = 4)'s neighbors are 1st node (val = 1) and 3rd node (val = 3). Example 2: [https://assets.leetcode.com/uploads/2020/01/07/graph.png] Input: adjList = [[]] Output: [[]] Explanation: Note that the input contains one empty list. The graph consists of only one node with val = 1 and it does not have any neighbors. Example 3: Input: adjList = [] Output: [] Explanation: This an empty graph, it does not have any nodes.   Constraints: * The number of nodes in the graph is in the range [0, 100]. * 1 <= Node.val <= 100 * Node.val is unique for each node. * There are no repeated edges and no self-loops in the graph. * The Graph is connected and all nodes can be visited starting from the given node.

Can you solve this real interview question? Course Schedule - 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. * For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1. Return true if you can finish all courses. Otherwise, return false.   Example 1: Input: numCourses = 2, prerequisites = [[1,0]] Output: true Explanation: There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible. Example 2: Input: numCourses = 2, prerequisites = [[1,0],[0,1]] Output: false Explanation: There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.   Constraints: * 1 <= numCourses <= 2000 * 0 <= prerequisites.length <= 5000 * prerequisites[i].length == 2 * 0 <= ai, bi < numCourses * All the pairs prerequisites[i] are unique.

Can you solve this real interview question? Pacific Atlantic Water Flow - There is an m x n rectangular island that borders both the Pacific Ocean and Atlantic Ocean. The Pacific Ocean touches the island's left and top edges, and the Atlantic Ocean touches the island's right and bottom edges. The island is partitioned into a grid of square cells. You are given an m x n integer matrix heights where heights[r][c] represents the height above sea level of the cell at coordinate (r, c). The island receives a lot of rain, and the rain water can flow to neighboring cells directly north, south, east, and west if the neighboring cell's height is less than or equal to the current cell's height. Water can flow from any cell adjacent to an ocean into the ocean. Return a 2D list of grid coordinates result where result[i] = [ri, ci] denotes that rain water can flow from cell (ri, ci) to both the Pacific and Atlantic oceans.   Example 1: [https://assets.leetcode.com/uploads/2021/06/08/waterflow-grid.jpg] Input: heights = [[1,2,2,3,5],[3,2,3,4,4],[2,4,5,3,1],[6,7,1,4,5],[5,1,1,2,4]] Output: [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]] Explanation: The following cells can flow to the Pacific and Atlantic oceans, as shown below: [0,4]: [0,4] -> Pacific Ocean   [0,4] -> Atlantic Ocean [1,3]: [1,3] -> [0,3] -> Pacific Ocean   [1,3] -> [1,4] -> Atlantic Ocean [1,4]: [1,4] -> [1,3] -> [0,3] -> Pacific Ocean   [1,4] -> Atlantic Ocean [2,2]: [2,2] -> [1,2] -> [0,2] -> Pacific Ocean   [2,2] -> [2,3] -> [2,4] -> Atlantic Ocean [3,0]: [3,0] -> Pacific Ocean   [3,0] -> [4,0] -> Atlantic Ocean [3,1]: [3,1] -> [3,0] -> Pacific Ocean   [3,1] -> [4,1] -> Atlantic Ocean [4,0]: [4,0] -> Pacific Ocean [4,0] -> Atlantic Ocean Note that there are other possible paths for these cells to flow to the Pacific and Atlantic oceans. Example 2: Input: heights = [[1]] Output: [[0,0]] Explanation: The water can flow from the only cell to the Pacific and Atlantic oceans.   Constraints: * m == heights.length * n == heights[r].length * 1 <= m, n <= 200 * 0 <= heights[r][c] <= 105

Can you solve this real interview question? 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. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.   Example 1: Input: grid = [ ["1","1","1","1","0"], ["1","1","0","1","0"], ["1","1","0","0","0"], ["0","0","0","0","0"] ] Output: 1 Example 2: Input: grid = [ ["1","1","0","0","0"], ["1","1","0","0","0"], ["0","0","1","0","0"], ["0","0","0","1","1"] ] Output: 3   Constraints: * m == grid.length * n == grid[i].length * 1 <= m, n <= 300 * grid[i][j] is '0' or '1'.

Can you solve this real interview question? Longest Consecutive Sequence - Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence. You must write an algorithm that runs in O(n) time.   Example 1: Input: nums = [100,4,200,1,3,2] Output: 4 Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4. Example 2: Input: nums = [0,3,7,2,5,8,4,6,0,1] Output: 9   Constraints: * 0 <= nums.length <= 105 * -109 <= nums[i] <= 109

Can you solve this real interview question? Graph Valid Tree - Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

Can you solve this real interview question? Number of Connected Components in an Undirected Graph - Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

Can you solve this real interview question? 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 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). Return intervals after the insertion. Note that you don't need to modify intervals in-place. You can make a new array and return it.   Example 1: Input: intervals = [[1,3],[6,9]], newInterval = [2,5] Output: [[1,5],[6,9]] Example 2: Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8] Output: [[1,2],[3,10],[12,16]] Explanation: Because the new interval [4,8] overlaps with [3,5],[6,7],[8,10].   Constraints: * 0 <= intervals.length <= 104 * intervals[i].length == 2 * 0 <= starti <= endi <= 105 * intervals is sorted by starti in ascending order. * newInterval.length == 2 * 0 <= start <= end <= 105

Can you solve this real interview question? 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 cover all the intervals in the input.   Example 1: Input: intervals = [[1,3],[2,6],[8,10],[15,18]] Output: [[1,6],[8,10],[15,18]] Explanation: Since intervals [1,3] and [2,6] overlap, merge them into [1,6]. Example 2: Input: intervals = [[1,4],[4,5]] Output: [[1,5]] Explanation: Intervals [1,4] and [4,5] are considered overlapping.   Constraints: * 1 <= intervals.length <= 104 * intervals[i].length == 2 * 0 <= starti <= endi <= 104

Can you solve this real interview question? Non-overlapping Intervals - Given an array of intervals intervals where intervals[i] = [starti, endi], return the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping. Note that intervals which only touch at a point are non-overlapping. For example, [1, 2] and [2, 3] are non-overlapping.   Example 1: Input: intervals = [[1,2],[2,3],[3,4],[1,3]] Output: 1 Explanation: [1,3] can be removed and the rest of the intervals are non-overlapping. Example 2: Input: intervals = [[1,2],[1,2],[1,2]] Output: 2 Explanation: You need to remove two [1,2] to make the rest of the intervals non-overlapping. Example 3: Input: intervals = [[1,2],[2,3]] Output: 0 Explanation: You don't need to remove any of the intervals since they're already non-overlapping.   Constraints: * 1 <= intervals.length <= 105 * intervals[i].length == 2 * -5 * 104 <= starti < endi <= 5 * 104

Can you solve this real interview question? Meeting Rooms II - Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

Can you solve this real interview question? 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.   Example 1: [https://assets.leetcode.com/uploads/2020/10/03/remove_ex1.jpg] Input: head = [1,2,3,4,5], n = 2 Output: [1,2,3,5] Example 2: Input: head = [1], n = 1 Output: [] Example 3: Input: head = [1,2], n = 1 Output: [1]   Constraints: * The number of nodes in the list is sz. * 1 <= sz <= 30 * 0 <= Node.val <= 100 * 1 <= n <= sz   Follow up: Could you do this in one pass?

Can you solve this real interview question? Reorder List - 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 → … You may not modify the values in the list's nodes. Only nodes themselves may be changed.   Example 1: [https://assets.leetcode.com/uploads/2021/03/04/reorder1linked-list.jpg] Input: head = [1,2,3,4] Output: [1,4,2,3] Example 2: [https://assets.leetcode.com/uploads/2021/03/09/reorder2-linked-list.jpg] Input: head = [1,2,3,4,5] Output: [1,5,2,4,3]   Constraints: * The number of nodes in the list is in the range [1, 5 * 104]. * 1 <= Node.val <= 1000

Can you solve this real interview question? 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. You must do it in place [https://en.wikipedia.org/wiki/In-place_algorithm].   Example 1: [https://assets.leetcode.com/uploads/2020/08/17/mat1.jpg] Input: matrix = [[1,1,1],[1,0,1],[1,1,1]] Output: [[1,0,1],[0,0,0],[1,0,1]] Example 2: [https://assets.leetcode.com/uploads/2020/08/17/mat2.jpg] Input: matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]] Output: [[0,0,0,0],[0,4,5,0],[0,3,1,0]]   Constraints: * m == matrix.length * n == matrix[0].length * 1 <= m, n <= 200 * -231 <= matrix[i][j] <= 231 - 1   Follow up: * A straightforward solution using O(mn) space is probably a bad idea. * A simple improvement uses O(m + n) space, but still not the best solution. * Could you devise a constant space solution?

Can you solve this real interview question? Spiral Matrix - Given an m x n matrix, return all elements of the matrix in spiral order.   Example 1: [https://assets.leetcode.com/uploads/2020/11/13/spiral1.jpg] Input: matrix = [[1,2,3],[4,5,6],[7,8,9]] Output: [1,2,3,6,9,8,7,4,5] Example 2: [https://assets.leetcode.com/uploads/2020/11/13/spiral.jpg] Input: matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]] Output: [1,2,3,4,8,12,11,10,9,5,6,7]   Constraints: * m == matrix.length * n == matrix[i].length * 1 <= m, n <= 10 * -100 <= matrix[i][j] <= 100

Can you solve this real interview question? Rotate Image - 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 [https://en.wikipedia.org/wiki/In-place_algorithm], which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.   Example 1: [https://assets.leetcode.com/uploads/2020/08/28/mat1.jpg] Input: matrix = [[1,2,3],[4,5,6],[7,8,9]] Output: [[7,4,1],[8,5,2],[9,6,3]] Example 2: [https://assets.leetcode.com/uploads/2020/08/28/mat2.jpg] Input: matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]] Output: [[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]   Constraints: * n == matrix.length == matrix[i].length * 1 <= n <= 20 * -1000 <= matrix[i][j] <= 1000

Can you solve this real interview question? Word Search - Given an m x n grid of characters board and a string word, return true if word exists in the grid. The word can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once.   Example 1: [https://assets.leetcode.com/uploads/2020/11/04/word2.jpg] Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED" Output: true Example 2: [https://assets.leetcode.com/uploads/2020/11/04/word-1.jpg] Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE" Output: true Example 3: [https://assets.leetcode.com/uploads/2020/10/15/word3.jpg] Input: board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB" Output: false   Constraints: * m == board.length * n = board[i].length * 1 <= m, n <= 6 * 1 <= word.length <= 15 * board and word consists of only lowercase and uppercase English letters.   Follow up: Could you use search pruning to make your solution faster with a larger board?

Can you solve this real interview question? Longest Substring Without Repeating Characters - Given a string s, find the length of the longest substring without repeating characters.   Example 1: Input: s = "abcabcbb" Output: 3 Explanation: The answer is "abc", with the length of 3. Example 2: Input: s = "bbbbb" Output: 1 Explanation: The answer is "b", with the length of 1. Example 3: Input: s = "pwwkew" Output: 3 Explanation: The answer is "wke", with the length of 3. Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.   Constraints: * 0 <= s.length <= 5 * 104 * s consists of English letters, digits, symbols and spaces.

Can you solve this real interview question? Longest Repeating Character Replacement - 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.   Example 1: Input: s = "ABAB", k = 2 Output: 4 Explanation: Replace the two 'A's with two 'B's or vice versa. Example 2: Input: s = "AABABBA", k = 1 Output: 4 Explanation: Replace the one 'A' in the middle with 'B' and form "AABBBBA". The substring "BBBB" has the longest repeating letters, which is 4. There may exists other ways to achieve this answer too.   Constraints: * 1 <= s.length <= 105 * s consists of only uppercase English letters. * 0 <= k <= s.length

Can you solve this real interview question? Group Anagrams - Given an array of strings strs, group the anagrams together. You can return the answer in any order.   Example 1: Input: strs = ["eat","tea","tan","ate","nat","bat"] Output: [["bat"],["nat","tan"],["ate","eat","tea"]] Explanation: * There is no string in strs that can be rearranged to form "bat". * The strings "nat" and "tan" are anagrams as they can be rearranged to form each other. * The strings "ate", "eat", and "tea" are anagrams as they can be rearranged to form each other. Example 2: Input: strs = [""] Output: [[""]] Example 3: Input: strs = ["a"] Output: [["a"]]   Constraints: * 1 <= strs.length <= 104 * 0 <= strs[i].length <= 100 * strs[i] consists of lowercase English letters.

Can you solve this real interview question? Longest Palindromic Substring - Given a string s, return the longest palindromic substring in s.   Example 1: Input: s = "babad" Output: "bab" Explanation: "aba" is also a valid answer. Example 2: Input: s = "cbbd" Output: "bb"   Constraints: * 1 <= s.length <= 1000 * s consist of only digits and English letters.

Can you solve this real interview question? Palindromic Substrings - Given a string s, return the number of palindromic substrings in it. A string is a palindrome when it reads the same backward as forward. A substring is a contiguous sequence of characters within the string.   Example 1: Input: s = "abc" Output: 3 Explanation: Three palindromic strings: "a", "b", "c". Example 2: Input: s = "aaa" Output: 6 Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".   Constraints: * 1 <= s.length <= 1000 * s consists of lowercase English letters.

Can you solve this real interview question? Encode and Decode Strings - Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

Can you solve this real interview question? Binary Tree Level Order Traversal - 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).   Example 1: [https://assets.leetcode.com/uploads/2021/02/19/tree1.jpg] Input: root = [3,9,20,null,null,15,7] Output: [[3],[9,20],[15,7]] Example 2: Input: root = [1] Output: [[1]] Example 3: Input: root = [] Output: []   Constraints: * The number of nodes in the tree is in the range [0, 2000]. * -1000 <= Node.val <= 1000

Can you solve this real interview question? Construct Binary Tree from Preorder and Inorder Traversal - Given two integer arrays preorder and inorder where preorder is the preorder traversal of a binary tree and inorder is the inorder traversal of the same tree, construct and return the binary tree.   Example 1: [https://assets.leetcode.com/uploads/2021/02/19/tree.jpg] Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7] Output: [3,9,20,null,null,15,7] Example 2: Input: preorder = [-1], inorder = [-1] Output: [-1]   Constraints: * 1 <= preorder.length <= 3000 * inorder.length == preorder.length * -3000 <= preorder[i], inorder[i] <= 3000 * preorder and inorder consist of unique values. * Each value of inorder also appears in preorder. * preorder is guaranteed to be the preorder traversal of the tree. * inorder is guaranteed to be the inorder traversal of the tree.

Can you solve this real interview question? Validate Binary Search Tree - Given the root of a binary tree, determine if it is a valid binary search tree (BST). A valid BST is defined as follows: * The left subtree of a node contains only nodes with keys less than the node's key. * The right subtree of a node contains only nodes with keys greater than the node's key. * Both the left and right subtrees must also be binary search trees.   Example 1: [https://assets.leetcode.com/uploads/2020/12/01/tree1.jpg] Input: root = [2,1,3] Output: true Example 2: [https://assets.leetcode.com/uploads/2020/12/01/tree2.jpg] Input: root = [5,1,4,null,null,3,6] Output: false Explanation: The root node's value is 5 but its right child's value is 4.   Constraints: * The number of nodes in the tree is in the range [1, 104]. * -231 <= Node.val <= 231 - 1

Can you solve this real interview question? 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.   Example 1: [https://assets.leetcode.com/uploads/2021/01/28/kthtree1.jpg] Input: root = [3,1,4,null,2], k = 1 Output: 1 Example 2: [https://assets.leetcode.com/uploads/2021/01/28/kthtree2.jpg] Input: root = [5,3,6,2,4,null,null,1], k = 3 Output: 3   Constraints: * The number of nodes in the tree is n. * 1 <= k <= n <= 104 * 0 <= Node.val <= 104   Follow up: If the BST is modified often (i.e., we can do insert and delete operations) and you need to find the kth smallest frequently, how would you optimize?

Can you solve this real interview question? Implement Trie (Prefix Tree) - A trie [https://en.wikipedia.org/wiki/Trie] (pronounced as "try") or prefix tree is a tree data structure used to efficiently store and retrieve keys in a dataset of strings. There are various applications of this data structure, such as autocomplete and spellchecker. Implement the Trie class: * Trie() Initializes the trie object. * void insert(String word) Inserts the string word into the trie. * boolean search(String word) Returns true if the string word is in the trie (i.e., was inserted before), and false otherwise. * boolean startsWith(String prefix) Returns true if there is a previously inserted string word that has the prefix prefix, and false otherwise.   Example 1: Input ["Trie", "insert", "search", "search", "startsWith", "insert", "search"] [[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]] Output [null, null, true, false, true, null, true] Explanation Trie trie = new Trie(); trie.insert("apple"); trie.search("apple"); // return True trie.search("app"); // return False trie.startsWith("app"); // return True trie.insert("app"); trie.search("app"); // return True   Constraints: * 1 <= word.length, prefix.length <= 2000 * word and prefix consist only of lowercase English letters. * At most 3 * 104 calls in total will be made to insert, search, and startsWith.

Can you solve this real interview question? 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. Implement the WordDictionary class: * WordDictionary() Initializes the object. * void addWord(word) Adds word to the data structure, it can be matched later. * bool search(word) Returns true if there is any string in the data structure that matches word or false otherwise. word may contain dots '.' where dots can be matched with any letter.   Example: Input ["WordDictionary","addWord","addWord","addWord","search","search","search","search"] [[],["bad"],["dad"],["mad"],["pad"],["bad"],[".ad"],["b.."]] Output [null,null,null,null,false,true,true,true] Explanation WordDictionary wordDictionary = new WordDictionary(); wordDictionary.addWord("bad"); wordDictionary.addWord("dad"); wordDictionary.addWord("mad"); wordDictionary.search("pad"); // return False wordDictionary.search("bad"); // return True wordDictionary.search(".ad"); // return True wordDictionary.search("b.."); // return True   Constraints: * 1 <= word.length <= 25 * word in addWord consists of lowercase English letters. * word in search consist of '.' or lowercase English letters. * There will be at most 2 dots in word for search queries. * At most 104 calls will be made to addWord and search.

Can you solve this real interview question? 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.   Example 1: Input: nums = [1,1,1,2,2,3], k = 2 Output: [1,2] Example 2: Input: nums = [1], k = 1 Output: [1]   Constraints: * 1 <= nums.length <= 105 * -104 <= nums[i] <= 104 * k is in the range [1, the number of unique elements in the array]. * It is guaranteed that the answer is unique.   Follow up: Your algorithm's time complexity must be better than O(n log n), where n is the array's size.

Can you solve this real interview question? 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. Notice that the solution set must not contain duplicate triplets.   Example 1: Input: nums = [-1,0,1,2,-1,-4] Output: [[-1,-1,2],[-1,0,1]] Explanation: nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0. nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0. nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0. The distinct triplets are [-1,0,1] and [-1,-1,2]. Notice that the order of the output and the order of the triplets does not matter. Example 2: Input: nums = [0,1,1] Output: [] Explanation: The only possible triplet does not sum up to 0. Example 3: Input: nums = [0,0,0] Output: [[0,0,0]] Explanation: The only possible triplet sums up to 0.   Constraints: * 3 <= nums.length <= 3000 * -105 <= nums[i] <= 105

Can you solve this real interview question? Sort Colors - Given an array nums with n objects colored red, white, or blue, sort them in-place [https://en.wikipedia.org/wiki/In-place_algorithm] so that objects of the same color are adjacent, with the colors in the order red, white, and blue. We will use the integers 0, 1, and 2 to represent the color red, white, and blue, respectively. You must solve this problem without using the library's sort function.   Example 1: Input: nums = [2,0,2,1,1,0] Output: [0,0,1,1,2,2] Example 2: Input: nums = [2,0,1] Output: [0,1,2]   Constraints: * n == nums.length * 1 <= n <= 300 * nums[i] is either 0, 1, or 2.   Follow up: Could you come up with a one-pass algorithm using only constant extra space?

Can you solve this real interview question? String to Integer (atoi) - Implement the myAtoi(string s) function, which converts a string to a 32-bit signed integer. The algorithm for myAtoi(string s) is as follows: 1. Whitespace: Ignore any leading whitespace (" "). 2. Signedness: Determine the sign by checking if the next character is '-' or '+', assuming positivity is neither present. 3. Conversion: Read the integer by skipping leading zeros until a non-digit character is encountered or the end of the string is reached. If no digits were read, then the result is 0. 4. Rounding: If the integer is out of the 32-bit signed integer range [-231, 231 - 1], then round the integer to remain in the range. Specifically, integers less than -231 should be rounded to -231, and integers greater than 231 - 1 should be rounded to 231 - 1. Return the integer as the final result.   Example 1: Input: s = "42" Output: 42 Explanation: The underlined characters are what is read in and the caret is the current reader position. Step 1: "42" (no characters read because there is no leading whitespace) ^ Step 2: "42" (no characters read because there is neither a '-' nor '+') ^ Step 3: "42" ("42" is read in) ^ Example 2: Input: s = " -042" Output: -42 Explanation: Step 1: " -042" (leading whitespace is read and ignored) ^ Step 2: " -042" ('-' is read, so the result should be negative) ^ Step 3: " -042" ("042" is read in, leading zeros ignored in the result) ^ Example 3: Input: s = "1337c0d3" Output: 1337 Explanation: Step 1: "1337c0d3" (no characters read because there is no leading whitespace) ^ Step 2: "1337c0d3" (no characters read because there is neither a '-' nor '+') ^ Step 3: "1337c0d3" ("1337" is read in; reading stops because the next character is a non-digit) ^ Example 4: Input: s = "0-1" Output: 0 Explanation: Step 1: "0-1" (no characters read because there is no leading whitespace) ^ Step 2: "0-1" (no characters read because there is neither a '-' nor '+') ^ Step 3: "0-1" ("0" is read in; reading stops because the next character is a non-digit) ^ Example 5: Input: s = "words and 987" Output: 0 Explanation: Reading stops at the first non-digit character 'w'.   Constraints: * 0 <= s.length <= 200 * s consists of English letters (lower-case and upper-case), digits (0-9), ' ', '+', '-', and '.'.

Can you solve this real interview question? Find All Anagrams in a String - Given two strings s and p, return an array of all the start indices of p's anagrams in s. You may return the answer in any order.   Example 1: Input: s = "cbaebabacd", p = "abc" Output: [0,6] Explanation: The substring with start index = 0 is "cba", which is an anagram of "abc". The substring with start index = 6 is "bac", which is an anagram of "abc". Example 2: Input: s = "abab", p = "ab" Output: [0,1,2] Explanation: The substring with start index = 0 is "ab", which is an anagram of "ab". The substring with start index = 1 is "ba", which is an anagram of "ab". The substring with start index = 2 is "ab", which is an anagram of "ab".   Constraints: * 1 <= s.length, p.length <= 3 * 104 * s and p consist of lowercase English letters.

Can you solve this real interview question? Time Based Key-Value Store - Design a time-based key-value data structure that can store multiple values for the same key at different time stamps and retrieve the key's value at a certain timestamp. Implement the TimeMap class: * TimeMap() Initializes the object of the data structure. * void set(String key, String value, int timestamp) Stores the key key with the value value at the given time timestamp. * String get(String key, int timestamp) Returns a value such that set was called previously, with timestamp_prev <= timestamp. If there are multiple such values, it returns the value associated with the largest timestamp_prev. If there are no values, it returns "".   Example 1: Input ["TimeMap", "set", "get", "get", "set", "get", "get"] [[], ["foo", "bar", 1], ["foo", 1], ["foo", 3], ["foo", "bar2", 4], ["foo", 4], ["foo", 5]] Output [null, null, "bar", "bar", null, "bar2", "bar2"] Explanation TimeMap timeMap = new TimeMap(); timeMap.set("foo", "bar", 1); // store the key "foo" and value "bar" along with timestamp = 1. timeMap.get("foo", 1); // return "bar" timeMap.get("foo", 3); // return "bar", since there is no value corresponding to foo at timestamp 3 and timestamp 2, then the only value is at timestamp 1 is "bar". timeMap.set("foo", "bar2", 4); // store the key "foo" and value "bar2" along with timestamp = 4. timeMap.get("foo", 4); // return "bar2" timeMap.get("foo", 5); // return "bar2"   Constraints: * 1 <= key.length, value.length <= 100 * key and value consist of lowercase English letters and digits. * 1 <= timestamp <= 107 * All the timestamps timestamp of set are strictly increasing. * At most 2 * 105 calls will be made to set and get.

Can you solve this real interview question? 01 Matrix - Given an m x n binary matrix mat, return the distance of the nearest 0 for each cell. The distance between two adjacent cells is 1.   Example 1: [https://assets.leetcode.com/uploads/2021/04/24/01-1-grid.jpg] Input: mat = [[0,0,0],[0,1,0],[0,0,0]] Output: [[0,0,0],[0,1,0],[0,0,0]] Example 2: [https://assets.leetcode.com/uploads/2021/04/24/01-2-grid.jpg] Input: mat = [[0,0,0],[0,1,0],[1,1,1]] Output: [[0,0,0],[0,1,0],[1,2,1]]   Constraints: * m == mat.length * n == mat[i].length * 1 <= m, n <= 104 * 1 <= m * n <= 104 * mat[i][j] is either 0 or 1. * There is at least one 0 in mat.

Can you solve this real interview question? Rotting Oranges - You are given an m x n grid where each cell can have one of three values: * 0 representing an empty cell, * 1 representing a fresh orange, or * 2 representing a rotten orange. Every minute, any fresh orange that is 4-directionally adjacent to a rotten orange becomes rotten. Return the minimum number of minutes that must elapse until no cell has a fresh orange. If this is impossible, return -1.   Example 1: [https://assets.leetcode.com/uploads/2019/02/16/oranges.png] Input: grid = [[2,1,1],[1,1,0],[0,1,1]] Output: 4 Example 2: Input: grid = [[2,1,1],[0,1,1],[1,0,1]] Output: -1 Explanation: The orange in the bottom left corner (row 2, column 0) is never rotten, because rotting only happens 4-directionally. Example 3: Input: grid = [[0,2]] Output: 0 Explanation: Since there are already no fresh oranges at minute 0, the answer is just 0.   Constraints: * m == grid.length * n == grid[i].length * 1 <= m, n <= 10 * grid[i][j] is 0, 1, or 2.

Can you solve this real interview question? Accounts Merge - Given a list of accounts where each element accounts[i] is a list of strings, where the first element accounts[i][0] is a name, and the rest of the elements are emails representing emails of the account. Now, we would like to merge these accounts. Two accounts definitely belong to the same person if there is some common email to both accounts. Note that even if two accounts have the same name, they may belong to different people as people could have the same name. A person can have any number of accounts initially, but all of their accounts definitely have the same name. After merging the accounts, return the accounts in the following format: the first element of each account is the name, and the rest of the elements are emails in sorted order. The accounts themselves can be returned in any order.   Example 1: Input: accounts = [["John","johnsmith@mail.com","john_newyork@mail.com"],["John","johnsmith@mail.com","john00@mail.com"],["Mary","mary@mail.com"],["John","johnnybravo@mail.com"]] Output: [["John","john00@mail.com","john_newyork@mail.com","johnsmith@mail.com"],["Mary","mary@mail.com"],["John","johnnybravo@mail.com"]] Explanation: The first and second John's are the same person as they have the common email "johnsmith@mail.com". The third John and Mary are different people as none of their email addresses are used by other accounts. We could return these lists in any order, for example the answer [['Mary', 'mary@mail.com'], ['John', 'johnnybravo@mail.com'], ['John', 'john00@mail.com', 'john_newyork@mail.com', 'johnsmith@mail.com']] would still be accepted. Example 2: Input: accounts = [["Gabe","Gabe0@m.co","Gabe3@m.co","Gabe1@m.co"],["Kevin","Kevin3@m.co","Kevin5@m.co","Kevin0@m.co"],["Ethan","Ethan5@m.co","Ethan4@m.co","Ethan0@m.co"],["Hanzo","Hanzo3@m.co","Hanzo1@m.co","Hanzo0@m.co"],["Fern","Fern5@m.co","Fern1@m.co","Fern0@m.co"]] Output: [["Ethan","Ethan0@m.co","Ethan4@m.co","Ethan5@m.co"],["Gabe","Gabe0@m.co","Gabe1@m.co","Gabe3@m.co"],["Hanzo","Hanzo0@m.co","Hanzo1@m.co","Hanzo3@m.co"],["Kevin","Kevin0@m.co","Kevin3@m.co","Kevin5@m.co"],["Fern","Fern0@m.co","Fern1@m.co","Fern5@m.co"]]   Constraints: * 1 <= accounts.length <= 1000 * 2 <= accounts[i].length <= 10 * 1 <= accounts[i][j].length <= 30 * accounts[i][0] consists of English letters. * accounts[i][j] (for j > 0) is a valid email.

Can you solve this real interview question? Minimum Height Trees - A tree is an undirected graph in which any two vertices are connected by exactly one path. In other words, any connected graph without simple cycles is a tree. Given a tree of n nodes labelled from 0 to n - 1, and an array of n - 1 edges where edges[i] = [ai, bi] indicates that there is an undirected edge between the two nodes ai and bi in the tree, you can choose any node of the tree as the root. When you select a node x as the root, the result tree has height h. Among all possible rooted trees, those with minimum height (i.e. min(h))  are called minimum height trees (MHTs). Return a list of all MHTs' root labels. You can return the answer in any order. The height of a rooted tree is the number of edges on the longest downward path between the root and a leaf.   Example 1: [https://assets.leetcode.com/uploads/2020/09/01/e1.jpg] Input: n = 4, edges = [[1,0],[1,2],[1,3]] Output: [1] Explanation: As shown, the height of the tree is 1 when the root is the node with label 1 which is the only MHT. Example 2: [https://assets.leetcode.com/uploads/2020/09/01/e2.jpg] Input: n = 6, edges = [[3,0],[3,1],[3,2],[3,4],[5,4]] Output: [3,4]   Constraints: * 1 <= n <= 2 * 104 * edges.length == n - 1 * 0 <= ai, bi < n * ai != bi * All the pairs (ai, bi) are distinct. * The given input is guaranteed to be a tree and there will be no repeated edges.

Can you solve this real interview question? Lowest Common Ancestor of a Binary Tree - Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree. According to the definition of LCA on Wikipedia [https://en.wikipedia.org/wiki/Lowest_common_ancestor]: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”   Example 1: [https://assets.leetcode.com/uploads/2018/12/14/binarytree.png] Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1 Output: 3 Explanation: The LCA of nodes 5 and 1 is 3. Example 2: [https://assets.leetcode.com/uploads/2018/12/14/binarytree.png] Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4 Output: 5 Explanation: The LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition. Example 3: Input: root = [1,2], p = 1, q = 2 Output: 1   Constraints: * The number of nodes in the tree is in the range [2, 105]. * -109 <= Node.val <= 109 * All Node.val are unique. * p != q * p and q will exist in the tree.

Can you solve this real interview question? 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.   Example 1: [https://assets.leetcode.com/uploads/2021/02/14/tree.jpg] Input: root = [1,2,3,null,5,null,4] Output: [1,3,4] Example 2: Input: root = [1,null,3] Output: [1,3] Example 3: Input: root = [] Output: []   Constraints: * The number of nodes in the tree is in the range [0, 100]. * -100 <= Node.val <= 100

Can you solve this real interview question? Permutations - Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order.   Example 1: Input: nums = [1,2,3] Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]] Example 2: Input: nums = [0,1] Output: [[0,1],[1,0]] Example 3: Input: nums = [1] Output: [[1]]   Constraints: * 1 <= nums.length <= 6 * -10 <= nums[i] <= 10 * All the integers of nums are unique.

Can you solve this real interview question? Subsets - Given an integer array nums of unique elements, return all possible subsets (the power set). The solution set must not contain duplicate subsets. Return the solution in any order.   Example 1: Input: nums = [1,2,3] Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]] Example 2: Input: nums = [0] Output: [[],[0]]   Constraints: * 1 <= nums.length <= 10 * -10 <= nums[i] <= 10 * All the numbers of nums are unique.

Can you solve this real interview question? 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. A mapping of digits to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters. [https://assets.leetcode.com/uploads/2022/03/15/1200px-telephone-keypad2svg.png]   Example 1: Input: digits = "23" Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"] Example 2: Input: digits = "" Output: [] Example 3: Input: digits = "2" Output: ["a","b","c"]   Constraints: * 0 <= digits.length <= 4 * digits[i] is a digit in the range ['2', '9'].

Can you solve this real interview question? LRU Cache - Design a data structure that follows the constraints of a Least Recently Used (LRU) cache [https://en.wikipedia.org/wiki/Cache_replacement_policies#LRU]. Implement the LRUCache class: * LRUCache(int capacity) Initialize the LRU cache with positive size capacity. * int get(int key) Return the value of the key if the key exists, otherwise return -1. * void put(int key, int value) Update the value of the key if the key exists. Otherwise, add the key-value pair to the cache. If the number of keys exceeds the capacity from this operation, evict the least recently used key. The functions get and put must each run in O(1) average time complexity.   Example 1: Input ["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"] [[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]] Output [null, null, null, 1, null, -1, null, -1, 3, 4] Explanation LRUCache lRUCache = new LRUCache(2); lRUCache.put(1, 1); // cache is {1=1} lRUCache.put(2, 2); // cache is {1=1, 2=2} lRUCache.get(1); // return 1 lRUCache.put(3, 3); // LRU key was 2, evicts key 2, cache is {1=1, 3=3} lRUCache.get(2); // returns -1 (not found) lRUCache.put(4, 4); // LRU key was 1, evicts key 1, cache is {4=4, 3=3} lRUCache.get(1); // return -1 (not found) lRUCache.get(3); // return 3 lRUCache.get(4); // return 4   Constraints: * 1 <= capacity <= 3000 * 0 <= key <= 104 * 0 <= value <= 105 * At most 2 * 105 calls will be made to get and put.

Can you solve this real interview question? Evaluate Reverse Polish Notation - You are given an array of strings tokens that represents an arithmetic expression in a Reverse Polish Notation [http://en.wikipedia.org/wiki/Reverse_Polish_notation]. Evaluate the expression. Return an integer that represents the value of the expression. Note that: * The valid operators are '+', '-', '*', and '/'. * Each operand may be an integer or another expression. * The division between two integers always truncates toward zero. * There will not be any division by zero. * The input represents a valid arithmetic expression in a reverse polish notation. * The answer and all the intermediate calculations can be represented in a 32-bit integer.   Example 1: Input: tokens = ["2","1","+","3","*"] Output: 9 Explanation: ((2 + 1) * 3) = 9 Example 2: Input: tokens = ["4","13","5","/","+"] Output: 6 Explanation: (4 + (13 / 5)) = 6 Example 3: Input: tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"] Output: 22 Explanation: ((10 * (6 / ((9 + 3) * -11))) + 17) + 5 = ((10 * (6 / (12 * -11))) + 17) + 5 = ((10 * (6 / -132)) + 17) + 5 = ((10 * 0) + 17) + 5 = (0 + 17) + 5 = 17 + 5 = 22   Constraints: * 1 <= tokens.length <= 104 * tokens[i] is either an operator: "+", "-", "*", or "/", or an integer in the range [-200, 200].

Can you solve this real interview question? K Closest Points to Origin - 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 on the X-Y plane is the Euclidean distance (i.e., √(x1 - x2)2 + (y1 - y2)2). You may return the answer in any order. The answer is guaranteed to be unique (except for the order that it is in).   Example 1: [https://assets.leetcode.com/uploads/2021/03/03/closestplane1.jpg] Input: points = [[1,3],[-2,2]], k = 1 Output: [[-2,2]] Explanation: The distance between (1, 3) and the origin is sqrt(10). The distance between (-2, 2) and the origin is sqrt(8). Since sqrt(8) < sqrt(10), (-2, 2) is closer to the origin. We only want the closest k = 1 points from the origin, so the answer is just [[-2,2]]. Example 2: Input: points = [[3,3],[5,-1],[-2,4]], k = 2 Output: [[3,3],[-2,4]] Explanation: The answer [[-2,4],[3,3]] would also be accepted.   Constraints: * 1 <= k <= points.length <= 104 * -104 <= xi, yi <= 104

Can you solve this real interview question? Task Scheduler - You are given an array of CPU tasks, each labeled with a letter from A to Z, and a number n. Each CPU interval can be idle or allow the completion of one task. Tasks can be completed in any order, but there's a constraint: there has to be a gap of at least n intervals between two tasks with the same label. Return the minimum number of CPU intervals required to complete all tasks.   Example 1: Input: tasks = ["A","A","A","B","B","B"], n = 2 Output: 8 Explanation: A possible sequence is: A -> B -> idle -> A -> B -> idle -> A -> B. After completing task A, you must wait two intervals before doing A again. The same applies to task B. In the 3rd interval, neither A nor B can be done, so you idle. By the 4th interval, you can do A again as 2 intervals have passed. Example 2: Input: tasks = ["A","C","A","B","D","B"], n = 1 Output: 6 Explanation: A possible sequence is: A -> B -> C -> D -> A -> B. With a cooling interval of 1, you can repeat a task after just one other task. Example 3: Input: tasks = ["A","A","A", "B","B","B"], n = 3 Output: 10 Explanation: A possible sequence is: A -> B -> idle -> idle -> A -> B -> idle -> idle -> A -> B. There are only two types of tasks, A and B, which need to be separated by 3 intervals. This leads to idling twice between repetitions of these tasks.   Constraints: * 1 <= tasks.length <= 104 * tasks[i] is an uppercase English letter. * 0 <= n <= 100

Can you solve this real interview question? Word Break - Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words. Note that the same word in the dictionary may be reused multiple times in the segmentation.   Example 1: Input: s = "leetcode", wordDict = ["leet","code"] Output: true Explanation: Return true because "leetcode" can be segmented as "leet code". Example 2: Input: s = "applepenapple", wordDict = ["apple","pen"] Output: true Explanation: Return true because "applepenapple" can be segmented as "apple pen apple". Note that you are allowed to reuse a dictionary word. Example 3: Input: s = "catsandog", wordDict = ["cats","dog","sand","and","cat"] Output: false   Constraints: * 1 <= s.length <= 300 * 1 <= wordDict.length <= 1000 * 1 <= wordDict[i].length <= 20 * s and wordDict[i] consist of only lowercase English letters. * All the strings of wordDict are unique.

Can you solve this real interview question? Partition Equal Subset Sum - 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 or false otherwise.   Example 1: Input: nums = [1,5,11,5] Output: true Explanation: The array can be partitioned as [1, 5, 5] and [11]. Example 2: Input: nums = [1,2,3,5] Output: false Explanation: The array cannot be partitioned into equal sum subsets.   Constraints: * 1 <= nums.length <= 200 * 1 <= nums[i] <= 100

Can you solve this real interview question? Alien Dictionary - Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

Can you solve this real interview question? Merge k Sorted Lists - 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.   Example 1: Input: lists = [[1,4,5],[1,3,4],[2,6]] Output: [1,1,2,3,4,4,5,6] Explanation: The linked-lists are: [ 1->4->5, 1->3->4, 2->6 ] merging them into one sorted list: 1->1->2->3->4->4->5->6 Example 2: Input: lists = [] Output: [] Example 3: Input: lists = [[]] Output: []   Constraints: * k == lists.length * 0 <= k <= 104 * 0 <= lists[i].length <= 500 * -104 <= lists[i][j] <= 104 * lists[i] is sorted in ascending order. * The sum of lists[i].length will not exceed 104.

Can you solve this real interview question? 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 included in the window. If there is no such substring, return the empty string "". The testcases will be generated such that the answer is unique.   Example 1: Input: s = "ADOBECODEBANC", t = "ABC" Output: "BANC" Explanation: The minimum window substring "BANC" includes 'A', 'B', and 'C' from string t. Example 2: Input: s = "a", t = "a" Output: "a" Explanation: The entire string s is the minimum window. Example 3: Input: s = "a", t = "aa" Output: "" Explanation: Both 'a's from t must be included in the window. Since the largest window of s only has one 'a', return empty string.   Constraints: * m == s.length * n == t.length * 1 <= m, n <= 105 * s and t consist of uppercase and lowercase English letters.   Follow up: Could you find an algorithm that runs in O(m + n) time?

Can you solve this real interview question? Binary Tree Maximum Path Sum - 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 of a path 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.   Example 1: [https://assets.leetcode.com/uploads/2020/10/13/exx1.jpg] Input: root = [1,2,3] Output: 6 Explanation: The optimal path is 2 -> 1 -> 3 with a path sum of 2 + 1 + 3 = 6. Example 2: [https://assets.leetcode.com/uploads/2020/10/13/exx2.jpg] Input: root = [-10,9,20,null,null,15,7] Output: 42 Explanation: The optimal path is 15 -> 20 -> 7 with a path sum of 15 + 20 + 7 = 42.   Constraints: * The number of nodes in the tree is in the range [1, 3 * 104]. * -1000 <= Node.val <= 1000

Can you solve this real interview question? Serialize and Deserialize Binary Tree - Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment. Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure. Clarification: The input/output format is the same as how LeetCode serializes a binary tree [https://support.leetcode.com/hc/en-us/articles/32442719377939-How-to-create-test-cases-on-LeetCode#h_01J5EGREAW3NAEJ14XC07GRW1A]. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.   Example 1: [https://assets.leetcode.com/uploads/2020/09/15/serdeser.jpg] Input: root = [1,2,3,null,null,4,5] Output: [1,2,3,null,null,4,5] Example 2: Input: root = [] Output: []   Constraints: * The number of nodes in the tree is in the range [0, 104]. * -1000 <= Node.val <= 1000