SWE Interview preparation

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/nested-list-weight-sum-ii/ https://www.lintcode.com/problem/nested-list-weight-sum-ii/description Given a nested list of integers, return the sum of all integers in the list weighted by their depth. Each element is either an integer, or a list -- whose elements may also be integers or other lists. Different from the  previous question  where weight is increasing from root to leaf, now the weight is defined from bottom up. i.e., the leaf level integers have weight 1, and the root level integers have the largest weight. Example 1: Input: [[1,1],2,[1,1]] Output: 8 Explanation: F our 1's at depth 1, one 2 at depth 2. Example 2: Input: [1,[4,[6]]] Output: 17 Explanation: O ne 1 at depth 3, one 4 at depth 2, and one 6 at depth 1; 1*3 + 4*2 + 6*1 = 17. --- Related problems 339-nested-list-weight-sum 341-flatten-nested-list-iterator ---

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/kth-smallest-element-in-a-sorted-matrix/ Given a  n  x  n  matrix where each of the rows and columns are sorted in ascending order, find the kth smallest element in the matrix. Note that it is the kth smallest element in the sorted order, not the kth distinct element. Example: matrix = [ [ 1, 5, 9], [10, 11, 13], [12, 13, 15] ], k = 8, return 13. Note: You may assume k is always valid, 1 ≤ k ≤ n 2 ---- Intuition 0, 0 is first candidate Next two candidates are 0, 1 and 1, 0 With two numbers, its easy to directly compare. This boundary of search will expand over time, and we need access to lowest number from candidates We can use min priority queue to get us the lowest number from candidates Put both 0, 1 and 1,0 into Priotity Queue k-- Take min from top and then add its neighbors 1, 1 is neighbor for both 0, 1 and 1,0 To prevent double counting, we apply a check Add r, c + 1 -- always Add r + 1, c...

Source https://www.lintcode.com/problem/binary-tree-upside-down/description https://leetcode.com/problems/binary-tree-upside-down/ Description Given a binary tree where all the right nodes are either leaf nodes with a sibling (a left node that shares the same parent node) or empty, flip it upside down and turn it into a tree where the original right nodes turned into left leaf nodes. Return the new root. Example Example1 Input: {1,2,3,4,5} Output: {4,5,2,#,#,3,1} Explanation: The input is 1 / \ 2 3 / \ 4 5 and the output is 4 / \ 5 2 / \ 3 1 Example2 Input: {1,2,3,4} Output: {4,#,2,3,1} Explanation: The input is 1 / \ 2 3 / 4 and the output is 4 \ 2 / \ 3 1 ---