SWE Interview preparation

https://leetcode.com/problems/shuffle-the-array/ Given the array  nums  consisting of  2n  elements in the form  [x 1 ,x 2 ,...,x n ,y 1 ,y 2 ,...,y n ] . Return the array in the form   [x 1 ,y 1 ,x 2 ,y 2 ,...,x n ,y n ] .   Example 1: Input: nums = [2,5,1,3,4,7], n = 3 Output: [2,3,5,4,1,7] Explanation: Since x 1 =2, x 2 =5, x 3 =1, y 1 =3, y 2 =4, y 3 =7 then the answer is [2,3,5,4,1,7]. Example 2: Input: nums = [1,2,3,4,4,3,2,1], n = 4 Output: [1,4,2,3,3,2,4,1] Example 3: Input: nums = [1,1,2,2], n = 2 Output: [1,2,1,2]   Constraints: 1 <= n <= 500 nums.length == 2n 1 <= nums[i] <= 10^3 Accepted 11,047 Submissions 11,992 ---  Time - O(N) Space - O(N) ---

https://leetcode.com/problems/max-dot-product-of-two-subsequences/ Given two arrays  nums1  and  nums2 . Return the maximum dot product between  non-empty  subsequences of nums1 and nums2 with the same length. A subsequence of a array is a new array which is formed from the original array by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie,  [2,3,5]  is a subsequence of  [1,2,3,4,5]  while  [1,5,3]  is not).   Example 1: Input: nums1 = [2,1,-2,5], nums2 = [3,0,-6] Output: 18 Explanation: Take subsequence [2,-2] from nums1 and subsequence [3,-6] from nums2. Their dot product is (2*3 + (-2)*(-6)) = 18. Example 2: Input: nums1 = [3,-2], nums2 = [2,-6,7] Output: 21 Explanation: Take subsequence [3] from nums1 and subsequence [7] from nums2. Their dot product is (3*7) = 21. Example 3: Input: nums1 = [-1,-1], nums2 = [1,1] Output: -1 Explanation: Tak...

https://leetcode.com/problems/count-good-nodes-in-binary-tree/ Given a binary tree  root , a node  X  in the tree is named  good  if in the path from root to  X  there are no nodes with a value  greater than  X. Return the number of  good  nodes in the binary tree.   Example 1: Input: root = [3,1,4,3,null,1,5] Output: 4 Explanation: Nodes in blue are good . Root Node (3) is always a good node. Node 4 -> (3,4) is the maximum value in the path starting from the root. Node 5 -> (3,4,5) is the maximum value in the path Node 3 -> (3,1,3) is the maximum value in the path. Example 2: Input: root = [3,3,null,4,2] Output: 3 Explanation: Node 2 -> (3, 3, 2) is not good, because "3" is higher than it. Example 3: Input: root = [1] Output: 1 Explanation: Root is considered as good .   Constraints: The number of nodes in the binary tree is in the range  [1, 10^5] . Each node's value is between  [-10^4, 10^...

https://leetcode.com/problems/pseudo-palindromic-paths-in-a-binary-tree/ Given a binary tree where node values are digits from 1 to 9. A path in the binary tree is said to be  pseudo-palindromic  if at least one permutation of the node values in the path is a palindrome. Return the number of  pseudo-palindromic  paths going from the root node to leaf nodes.   Example 1: Input: root = [2,3,1,3,1,null,1] Output: 2 Explanation: The figure above represents the given binary tree. There are three paths going from the root node to leaf nodes: the red path [2,3,3], the green path [2,1,1], and the path [2,3,1]. Among these paths only red path and green path are pseudo-palindromic paths since the red path [2,3,3] can be rearranged in [3,2,3] (palindrome) and the green path [2,1,1] can be rearranged in [1,2,1] (palindrome). Example 2: Input: root = [2,1,1,1,3,null,null,null,null,null,1] Output: 1 Explanation: The figure above represents the given binary tree. There...

https://leetcode.com/problems/minimum-time-to-collect-all-apples-in-a-tree/ Given an undirected tree consisting of  n  vertices numbered from 0 to  n-1 , which has some apples in their vertices. You spend 1 second to walk over one edge of the tree.  Return the minimum time in seconds you have to spend in order to collect all apples in the tree starting at  vertex 0  and coming back to this vertex. The edges of the undirected tree are given in the array  edges , where  edges[i] = [from i , to i ]  means that exists an edge connecting the vertices  from i  and  to i . Additionally, there is a boolean array  hasApple , where  hasApple[i] = true  means that vertex  i  has an apple, otherwise, it does not have any apple.   Example 1: Input: n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], hasApple = [false,false,true,false,true,true,false] Output: 8 Explanation: Th...

https://leetcode.com/problems/build-an-array-with-stack-operations/ Given an array  target  and an integer  n . In each iteration, you will read a number from   list = {1,2,3..., n} . Build the  target  array using the following operations: Push : Read a new element from the beginning  list , and push it in the array. Pop : delete the last element of the array. If the target array is already built, stop reading more elements. You are guaranteed that the target array is strictly increasing, only containing numbers between 1 to  n  inclusive. Return the operations to build the target array. You are guaranteed that the answer is unique.   Example 1: Input: target = [1,3], n = 3 Output: ["Push","Push","Pop","Push"] Explanation: Read number 1 and automatically push in the array -> [1] Read number 2 and automatically push in the array then Pop it -> [1] Read number 3 and automatically push in the array -...

https://leetcode.com/problems/diagonal-traverse-ii/ Given a list of lists of integers,  nums , return all elements of  nums  in diagonal order as shown in the below images. Example 1: Input: nums = [[1,2,3],[4,5,6],[7,8,9]] Output: [1,4,2,7,5,3,8,6,9] Example 2: Input: nums = [[1,2,3,4,5],[6,7],[8],[9,10,11],[12,13,14,15,16]] Output: [1,6,2,8,7,3,9,4,12,10,5,13,11,14,15,16] Example 3: Input: nums = [[1,2,3],[4],[5,6,7],[8],[9,10,11]] Output: [1,4,2,5,3,8,6,9,7,10,11] Example 4: Input: nums = [[1,2,3,4,5,6]] Output: [1,2,3,4,5,6] Constraints: 1 <= nums.length <= 10^5 1 <= nums[i].length <= 10^5 1 <= nums[i][j] <= 10^9 There at most  10^5  elements in  nums . --- Intuition Elements on same diagonal share same r + c Save the size of each row to compute output size Add to output in reverse from each list, since the addition is in reverse direction --- Time - O(R * C) Space - O(R * C) --- Related problems 49...

https://leetcode.com/problems/longest-continuous-subarray-with-absolute-diff-less-than-or-equal-to-limit/ Given an array of integers  nums  and an integer  limit , return the size of the longest continuous subarray such that the absolute difference between any two elements is less than or equal to  limit . In case there is no subarray satisfying the given condition return 0. Example 1: Input: nums = [8,2,4,7], limit = 4 Output: 2 Explanation: All subarrays are: [8] with maximum absolute diff |8-8| = 0 <= 4. [8,2] with maximum absolute diff |8-2| = 6 > 4. [8,2,4] with maximum absolute diff |8-2| = 6 > 4. [8,2,4,7] with maximum absolute diff |8-2| = 6 > 4. [2] with maximum absolute diff |2-2| = 0 <= 4. [2,4] with maximum absolute diff |2-4| = 2 <= 4. [2,4,7] with maximum absolute diff |2-7| = 5 > 4. [4] with maximum absolute diff |4-4| = 0 <= 4. [4,7] with maximum absolute diff |4-7| = 3 <= 4. [7] with maximum absolute diff...

https://leetcode.com/contest/weekly-contest-187/problems/destination-city/ You are given the array  paths , where  paths[i] = [cityA i , cityB i ]  means there exists a direct path going from  cityA i  to  cityB i .  Return the destination city, that is, the city without any path outgoing to another city. It is guaranteed that the graph of paths forms a line without any loop, therefore, there will be exactly one destination city. Example 1: Input: paths = [["London","New York"],["New York","Lima"],["Lima","Sao Paulo"]] Output: "Sao Paulo" Explanation: Starting at "London" city you will reach "Sao Paulo" city which is the destination city. Your trip consist of: "London" -> "New York" -> "Lima" -> "Sao Paulo". Example 2: Input: paths = [["B","C"],["D","B"],["C","A"]] Output...

https://leetcode.com/problems/count-number-of-teams/ There are  n  soldiers standing in a line. Each soldier is assigned a  unique   rating  value. You have to form a team of 3 soldiers amongst them under the following rules: Choose 3 soldiers with index ( i ,  j ,  k ) with rating ( rating[i] ,  rating[j] ,  rating[k] ). A team is valid if:  ( rating[i] < rating[j] < rating[k] ) or ( rating[i] > rating[j] > rating[k] ) where ( 0 <= i < j < k < n ). Return the number of teams you can form given the conditions. (soldiers can be part of multiple teams). Example 1: Input: rating = [2,5,3,4,1] Output: 3 Explanation: We can form three teams given the conditions. (2,3,4), (5,4,1), (5,3,1). Example 2: Input: rating = [2,1,3] Output: 0 Explanation: We can't form any team given the conditions. Example 3: Input: rating = [1,2,3,4] Output: 4 Constraints: n =...