SWE Interview preparation

 https://leetcode.com/problems/inorder-successor-in-bst-ii/description/ Given a  node  in a binary search tree, return  the in-order successor of that node in the BST . If that node has no in-order successor, return  null . The successor of a  node  is the node with the smallest key greater than  node.val . You will have direct access to the node but not to the root of the tree. Each node will have a reference to its parent node. Below is the definition for  Node : class Node { public int val; public Node left; public Node right; public Node parent; }   Example 1: Input: tree = [2,1,3], node = 1 Output: 2 Explanation: 1's in-order successor node is 2. Note that both the node and the return value is of Node type. Example 2: Input: tree = [5,3,6,2,4,null,null,1], node = 6 Output: null Explanation: There is no in-order successor of the current node, so the answer is null.   Constraints: The number of nodes in the ...

https://leetcode.com/problems/smallest-range-covering-elements-from-k-lists/ You have  k  lists of sorted integers in ascending order. Find the  smallest  range that includes at least one number from each of the  k  lists. We define the range [a,b] is smaller than range [c,d] if  b-a < d-c  or  a < c  if  b-a == d-c .   Example 1: Input: [[4,10,15,24,26], [0,9,12,20], [5,18,22,30]] Output: [20,24] Explanation: List 1: [4, 10, 15, 24,26], 24 is in range [20,24]. List 2: [0, 9, 12, 20], 20 is in range [20,24]. List 3: [5, 18, 22, 30], 22 is in range [20,24].   Note: The given list may contain duplicates, so ascending order means >= here. 1 <=  k  <= 3500 -10 5  <=  value of elements  <= 10 5 . --- Related problems 23-merge-k-sorted-lists ---

https://leetcode.com/problems/binary-search-tree-to-greater-sum-tree/ Given the root of a binary  search  tree with distinct values, modify it so that every  node  has a new value equal to the sum of the values of the original tree that are greater than or equal to  node.val . As a reminder, a  binary search tree  is a tree that satisfies these constraints: 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: Input: [4,1,6,0,2,5,7,null,null,null,3,null,null,null,8] Output: [30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]   Constraints: The number of nodes in the tree is between  1  and  100 . Each node will have value between  0  and  100 . The given tree is a binary search tree. Note:...

https://leetcode.com/problems/closest-binary-search-tree-value-ii/ https://github.com/openset/leetcode/tree/master/problems/closest-binary-search-tree-value-ii https://www.lintcode.com/problem/closest-binary-search-tree-value-ii/description Given a non-empty binary search tree and a target value, find  k  values in the BST that are closest to the target. Note: Given target value is a floating point. You may assume  k  is always valid, that is:  k  ≤ total nodes. You are guaranteed to have only one unique set of  k  values in the BST that are closest to the target. Example: Input: root = [4,2,5,1,3], target = 3.714286, and k = 2 4 / \ 2 5 / \ 1 3 Output: [4,3] Follow up: Assume that the BST is balanced, could you solve it in less than  O ( n ) runtime (where  n  = total nodes)? --- Related problems 270-closest-binary-search-tree-value --- ---

https://leetcode.com/problems/valid-parenthesis-string/ Given a string containing only three types of characters: '(', ')' and '*', write a function to check whether this string is valid. We define the validity of a string by these rules: Any left parenthesis  '('  must have a corresponding right parenthesis  ')' . Any right parenthesis  ')'  must have a corresponding left parenthesis  '(' . Left parenthesis  '('  must go before the corresponding right parenthesis  ')' . '*'  could be treated as a single right parenthesis  ')'  or a single left parenthesis  '('  or an empty string. An empty string is also valid. Example 1: Input: "()" Output: True Example 2: Input: "(*)" Output: True Example 3: Input: "(*))" Output: True Note: The string size will be in the range [1, 100]. --- Related problems 32-longest-valid-parentheses ---

https://leetcode.com/problems/symmetric-tree/ Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center). For example, this binary tree  [1,2,2,3,4,4,3]  is symmetric: 1 / \ 2 2 / \ / \ 3 4 4 3 But the following  [1,2,2,null,3,null,3]  is not: 1 / \ 2 2 \ \ 3 3 Follow up:  Solve it both recursively and iteratively --- Iterative - level order - queue based Offer 2 nodes, and remove 2 nodes at a time Offer nulls as well, don't filter them out Offer mirror nodes together n1.left, n2.right n1.right, n2.left -- Time - O(n) Space - O(n) ---

https://leetcode.com/problems/subsets-ii/ Given a collection of integers that might contain duplicates,  nums , return all possible subsets (the power set). Note:  The solution set must not contain duplicate subsets. Example: Input: [1,2,2] Output: [ [2], [1], [1,2,2], [2,2], [1,2], [] ] --- Intuition --- Related problems 78-subsets 46-permutations 47-permutations-ii 39-combination-sum 40-combination-sum-ii ---

https://leetcode.com/problems/binary-tree-level-order-traversal/ Given a binary tree, return the  level order  traversal of its nodes' values. (ie, from left to right, level by level). For example: Given binary tree  [3,9,20,null,null,15,7] , 3 / \ 9 20 / \ 15 7 return its level order traversal as: [ [3], [9,20], [15,7] ] ---- Intuition Level order requires access to all nodes which are 1 level away from parent. Essentially one edge away from parent - very similar to BFS in a graph We need to return all nodes L to R in the order they are encountered when traversing a level. Queue is appropriate data structure as it has FIFO behavior Implementation is a standard BFS traversal using queue ---- Time - O(n) Space - O(log(n))

https://leetcode.com/problems/n-ary-tree-postorder-traversal/ Given an n-ary tree, return the  postorder  traversal of its nodes' values. Nary-Tree input serialization is represented in their level order traversal, each group of children is separated by the null value (See examples). Follow up: Recursive solution is trivial, could you do it iteratively? Example 1: Input: root = [1,null,3,2,4,null,5,6] Output: [5,6,3,2,4,1] Example 2: Input: root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14] Output: [2,6,14,11,7,3,12,8,4,13,9,10,5,1] Constraints: The height of the n-ary tree is less than or equal to  1000 The total number of nodes is between  [0, 10^4] ----- Intuition Post order definition => Process the children first, and parent node after.  In recursive calls, we call into the child functions, and process the current node after called functions return. ...

https://leetcode.com/problems/n-ary-tree-preorder-traversal/ Given an n-ary tree, return the  preorder  traversal of its nodes' values. Nary-Tree input serialization is represented in their level order traversal, each group of children is separated by the null value (See examples). Follow up: Recursive solution is trivial, could you do it iteratively? Example 1: Input: root = [1,null,3,2,4,null,5,6] Output: [1,3,5,6,2,4] Example 2: Input: root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14] Output: [1,2,3,6,7,11,14,4,8,12,5,9,13,10] Constraints: The height of the n-ary tree is less than or equal to  1000 The total number of nodes is between  [0, 10^4] ---- Intuition Recursive solution is trivial, just focus on iterative solution In recursion we process the node as soon as we reach it, and then recurse on its children. We can extend the same idea here - Process no...