SWE Interview preparation

https://leetcode.com/problems/number-of-connected-components-in-an-undirected-graph/description/ You have a graph of  n  nodes. You are given an integer  n  and an array  edges  where  edges[i] = [a i , b i ]  indicates that there is an edge between  a i  and  b i  in the graph. Return  the number of connected components in the graph .   Example 1: Input: n = 5, edges = [[0,1],[1,2],[3,4]] Output: 2 Example 2: Input: n = 5, edges = [[0,1],[1,2],[2,3],[3,4]] Output: 1   Constraints: 1 <= n <= 2000 1 <= edges.length <= 5000 edges[i].length == 2 0 <= a i <= b i < n a i != b i There are no repeated edges. ---- Related problems https://sweip.blogspot.com/2020/05/200-number-of-islands.html --- Time - O(V + E) Space - O(V + E) --- ---

 https://leetcode.com/problems/ones-and-zeroes/description/ You are given an array of binary strings  strs  and two integers  m  and  n . Return  the size of the largest subset of  strs  such that there are  at most   m   0 's and  n   1 's in the subset . A set  x  is a  subset  of a set  y  if all elements of  x  are also elements of  y .   Example 1: Input: strs = ["10","0001","111001","1","0"], m = 5, n = 3 Output: 4 Explanation: The largest subset with at most 5 0's and 3 1's is {"10", "0001", "1", "0"}, so the answer is 4. Other valid but smaller subsets include {"0001", "1"} and {"10", "1", "0"}. {"111001"} is an invalid subset because it contains 4 1's, greater than the maximum of 3. Example 2: Input: strs = ["10","0","1"], m = 1, n = 1 Output: 2 Explanation: The largest subs...

https://github.com/openset/leetcode/tree/master/problems/find-leaves-of-binary-tree https://leetcode.com/problems/find-leaves-of-binary-tree/ https://www.lintcode.com/problem/find-leaves-of-binary-tree/description Given a binary tree, collect a tree's nodes as if you were doing this: Collect and remove all leaves, repeat until the tree is empty.   Example: Input: [1,2,3,4,5]     1 / \ 2 3 / \ 4 5 Output: [[4,5,3],[2],[1]]   Explanation: 1. Removing the leaves  [4,5,3]  would result in this tree: 1 / 2   2. Now removing the leaf  [2]  would result in this tree: 1   3. Now removing the leaf  [1]  would result in the empty tree: [] ----- Intuition Need info from both left, and right child to determine if current node is leaf node Post Order DFS Consider looking up the tree from below where the level is...

https://leetcode.com/problems/interleaving-string/ Given  s1 ,  s2 ,  s3 , find whether  s3  is formed by the interleaving of  s1  and  s2 . Example 1: Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac" Output: true Example 2: Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbbaccc" Output: false

https://leetcode.com/problems/binary-tree-tilt/ Given a binary tree, return the tilt of the  whole tree . The tilt of a  tree node  is defined as the  absolute difference  between the sum of all left subtree node values and the sum of all right subtree node values. Null node has tilt 0. The tilt of the  whole tree  is defined as the sum of all nodes' tilt. Example: Input: 1 / \ 2 3 Output: 1 Explanation: Tilt of node 2 : 0 Tilt of node 3 : 0 Tilt of node 1 : |2-3| = 1 Tilt of binary tree : 0 + 0 + 1 = 1 Note: The sum of node values in any subtree won't exceed the range of 32-bit integer. All the tilt values won't exceed the range of 32-bit integer. --- Intuition We need info from left, right child to compute answer for current node Post Order DFS seems appropriate Increment the ans by Math.abs(dfs(node.left) - dfs(node.right)) return sum of all includes - left + right + self for parent to process in post order --- Time ...

https://leetcode.com/problems/convert-bst-to-greater-tree/ Given a Binary Search Tree (BST), convert it to a Greater Tree such that every key of the original BST is changed to the original key plus sum of all keys greater than the original key in BST. Example: Input: The root of a Binary Search Tree like this: 5 / \ 2 13 Output: The root of a Greater Tree like this: 18 / \ 20 13 Note:  This question is the same as 1038:  https://leetcode.com/problems/binary-search-tree-to-greater-sum-tree/ --- Related problems 1038-binary-search-tree-to-greater-sum --- Time - O(N) Space - O(N) --

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