SWE Interview preparation

https://leetcode.com/problems/validate-binary-tree-nodes/ You have  n  binary tree nodes numbered from  0  to  n - 1  where node  i  has two children  leftChild[i]  and  rightChild[i] , return  true  if and only if  all  the given nodes form  exactly one  valid binary tree. If node  i  has no left child then  leftChild[i]  will equal  -1 , similarly for the right child. Note that the nodes have no values and that we only use the node numbers in this problem.   Example 1: Input: n = 4, leftChild = [1,-1,3,-1], rightChild = [2,-1,-1,-1] Output: true Example 2: Input: n = 4, leftChild = [1,-1,3,-1], rightChild = [2,3,-1,-1] Output: false Example 3: Input: n = 2, leftChild = [1,0], rightChild = [-1,-1] Output: false Example 4: Input: n = 6, leftChild = [1,-1,-1,4,-1,-1], rightChild = [2,-1,-1,5,-1,-1] Output: false   Constraints: 1 <= n <= 10^4 leftChild...

https://leetcode.com/problems/text-justification/ Given an array of words and a width  maxWidth , format the text such that each line has exactly  maxWidth  characters and is fully (left and right) justified. You should pack your words in a greedy approach; that is, pack as many words as you can in each line. Pad extra spaces  ' '  when necessary so that each line has exactly  maxWidth  characters. Extra spaces between words should be distributed as evenly as possible. If the number of spaces on a line do not divide evenly between words, the empty slots on the left will be assigned more spaces than the slots on the right. For the last line of text, it should be left justified and no  extra  space is inserted between words. Note: A word is defined as a character sequence consisting of non-space characters only. Each word's length is guaranteed to be greater than 0 and not exceed  maxWidth . The input array  words  cont...

https://leetcode.com/problems/count-and-say/ The count-and-say sequence is the sequence of integers with the first five terms as following: 1. 1 2. 11 3. 21 4. 1211 5. 111221 1  is read off as  "one 1"  or  11 . 11  is read off as  "two 1s"  or  21 . 21  is read off as  "one 2 , then  one 1"  or  1211 . Given an integer  n  where 1 ≤  n  ≤ 30, generate the  n th  term of the count-and-say sequence. You can do so recursively, in other words from the previous member read off the digits, counting the number of digits in groups of the same digit. Note: Each term of the sequence of integers will be represented as a string.   Example 1: Input: 1 Output: "1" Explanation: This is the base case. Example 2: Input: 4 Output: "1211" Explanation: For n = 3 the term was "21" in which we have two groups "2" and "1", "2" can be read as "12" which means frequency = 1 and val...

https://leetcode.com/problems/replace-the-substring-for-balanced-string/ You are given a string containing only 4 kinds of characters  'Q',   'W', 'E'  and  'R' . A string is said to be  balanced   if each of its characters appears  n/4  times where  n  is the length of the string. Return the minimum length of the substring that can be replaced with  any  other string of the same length to make the original string  s   balanced . Return 0 if the string is already  balanced .   Example 1: Input: s = "QWER" Output: 0 Explanation: s is already balanced. Example 2: Input: s = "QQWE" Output: 1 Explanation: We need to replace a 'Q' to 'R', so that "RQWE" (or "QRWE") is balanced. Example 3: Input: s = "QQQW" Output: 2 Explanation: We can replace the first "QQ" to "ER". Example 4: Input: s = "QQQQ" Output: 3 Explanation: We can replace the last 3 'Q' ...

https://leetcode.com/problems/remove-sub-folders-from-the-filesystem/ Given a list of folders, remove all sub-folders in those folders and return in  any order  the folders after removing. If a  folder[i]  is located within another  folder[j] , it is called a sub-folder of it. The format of a path is one or more concatenated strings of the form:  /  followed by one or more lowercase English letters. For example,  /leetcode  and  /leetcode/problems  are valid paths while an empty string and  /  are not.   Example 1: Input: folder = ["/a","/a/b","/c/d","/c/d/e","/c/f"] Output: ["/a","/c/d","/c/f"] Explanation: Folders "/a/b/" is a subfolder of "/a" and "/c/d/e" is inside of folder "/c/d" in our filesystem. Example 2: Input: folder = ["/a","/a/b/c","/a/b/d"] Output: ["/a"] Explanation: Folders "/a/b/c" and "/a/...

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/maximum-binary-tree/ Given an integer array with no duplicates. A maximum tree building on this array is defined as follow: The root is the maximum number in the array. The left subtree is the maximum tree constructed from left part subarray divided by the maximum number. The right subtree is the maximum tree constructed from right part subarray divided by the maximum number. Construct the maximum tree by the given array and output the root node of this tree. Example 1: Input: [3,2,1,6,0,5] Output: return the tree root node representing the following tree: 6 / \ 3 5 \ / 2 0 \ 1 Note: The size of the given array will be in the range [1,1000]. --- Recursion Time - O(N ^ 2) - worst case - sorted array, max elem is at end, O(N log N) - average case - balanced tree Space - O(N) - recursion stack - worst case, sorted array, N levels, O( log N) - average case ---

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

https://leetcode.com/problems/factorial-trailing-zeroes/ Given an integer  n , return the number of trailing zeroes in  n !. Example 1: Input: 3 Output: 0 Explanation:  3! = 6, no trailing zero. Example 2: Input: 5 Output: 1 Explanation:  5! = 120, one trailing zero. Note:  Your solution should be in logarithmic time complexity. --- Intuition - Count number of 5 factors in n Time - O( Log N base 5) ---

https://leetcode.com/problems/boundary-of-binary-tree https://github.com/openset/leetcode/tree/master/problems/boundary-of-binary-tree https://www.lintcode.com/problem/boundary-of-binary-tree/description Given a binary tree, return the values of its boundary in  anti-clockwise  direction starting from root. Boundary includes left boundary, leaves, and right boundary in order without duplicate  nodes .  (The values of the nodes may still be duplicates.) Left boundary  is defined as the path from root to the  left-most  node.  Right boundary  is defined as the path from root to the  right-most  node. If the root doesn't have left subtree or right subtree, then the root itself is left boundary or right boundary. Note this definition only applies to the input binary tree, and not applies to any subtrees. The  left-most  node is defined as a  leaf  node you could reach when you always firstly travel to the left subtre...

https://leetcode.com/problems/palindromic-substrings/ Given a string, your task is to count how many palindromic substrings in this string. The substrings with different start indexes or end indexes are counted as different substrings even they consist of same characters. Example 1: Input: "abc" Output: 3 Explanation: Three palindromic strings: "a", "b", "c". Example 2: Input: "aaa" Output: 6 Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa". Note: The input string length won't exceed 1000. ---