SWE Interview preparation

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/word-ladder-ii/ Given two words ( beginWord  and  endWord ), and a dictionary's word list, find all shortest transformation sequence(s) from  beginWord  to  endWord , such that: Only one letter can be changed at a time Each transformed word must exist in the word list. Note that  beginWord  is  not  a transformed word. Note: Return an empty list if there is no such transformation sequence. All words have the same length. All words contain only lowercase alphabetic characters. You may assume no duplicates in the word list. You may assume  beginWord  and  endWord  are non-empty and are not the same. Example 1: Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"] Output: [ ["hit","hot","dot","dog","cog"],   ["hit","hot","lot","log...

https://leetcode.com/problems/generate-parentheses/ Given  n  pairs of parentheses, write a function to generate all combinations of well-formed parentheses. For example, given  n  = 3, a solution set is: [ "((()))", "(()())", "(())()", "()(())", "()()()" ] --

https://leetcode.com/problems/subtree-of-another-tree/ Given two non-empty binary trees  s  and  t , check whether tree  t  has exactly the same structure and node values with a subtree of  s . A subtree of  s  is a tree consists of a node in  s  and all of this node's descendants. The tree  s  could also be considered as a subtree of itself. Example 1: Given tree s: 3 / \ 4 5 / \ 1 2 Given tree t: 4 / \ 1 2 Return  true , because t has the same structure and node values with a subtree of s. Example 2: Given tree s: 3 / \ 4 5 / \ 1 2 / 0 Given tree t: 4 / \ 1 2 Return  false . --- Intuition Related problems same binary tree valid-palindrome-ii First check if trees are equal, if they are not check if left subtree of source or right subtree of source are equal to target. 

https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/ Given a binary tree, return the  zigzag level order  traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between). For example: Given binary tree  [3,9,20,null,null,15,7] , 3 / \ 9 20 / \ 15 7 return its zigzag level order traversal as: [ [3], [20,9], [15,7] ]

https://leetcode.com/problems/binary-tree-maximum-path-sum/ Given a  non-empty  binary tree, find the maximum path sum. For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain  at least one node  and does not need to go through the root. Example 1: Input: [1,2,3] 1 / \ 2 3 Output: 6 Example 2: Input: [-10,9,20,null,null,15,7]   -10    / \   9   20     /  \     15   7 Output: 42 --- Intuition Consider binary tree with 3 nodes => 1 root + 2 children There are four ways to compute path sum Node alone i.e., no children Node + left child Node + right child Node + left child + right child (*) The answer for this tree is max of the above 4 sums 2, 3 are essentially root + max child The choices reduce to Node alone i.e., no children...