SWE Interview preparation

 https://leetcode.com/problems/shortest-path-in-a-grid-with-obstacles-elimination/ You are given an  m x n  integer matrix  grid  where each cell is either  0  (empty) or  1  (obstacle). You can move up, down, left, or right from and to an empty cell in  one step . Return  the minimum number of  steps  to walk from the upper left corner  (0, 0)  to the lower right corner  (m - 1, n - 1)  given that you can eliminate  at most   k  obstacles . If it is not possible to find such walk return  -1 .   Example 1: Input: grid = [[0,0,0],[1,1,0],[0,0,0],[0,1,1],[0,0,0]], k = 1 Output: 6 Explanation: The shortest path without eliminating any obstacle is 10. The shortest path with one obstacle elimination at position (3,2) is 6. Such path is (0,0) -> (0,1) -> (0,2) -> (1,2) -> (2,2) -> (3,2) -> (4,2). Example 2: Input: grid = [[0,1,1],[1,1,1],[1,0,0]], k = 1 Output:...

https://leetcode.com/problems/open-the-lock/ You have a lock in front of you with 4 circular wheels. Each wheel has 10 slots:  '0', '1', '2', '3', '4', '5', '6', '7', '8', '9' . The wheels can rotate freely and wrap around: for example we can turn  '9'  to be  '0' , or  '0'  to be  '9' . Each move consists of turning one wheel one slot. The lock initially starts at  '0000' , a string representing the state of the 4 wheels. You are given a list of  deadends  dead ends, meaning if the lock displays any of these codes, the wheels of the lock will stop turning and you will be unable to open it. Given a  target  representing the value of the wheels that will unlock the lock, return the minimum total number of turns required to open the lock, or -1 if it is impossible. Example 1: Input: deadends = ["0201","0101","0102","1212",...

https://leetcode.com/problems/maximum-level-sum-of-a-binary-tree/ Given the  root  of a binary tree, the level of its root is  1 , the level of its children is  2 , and so on. Return the  smallest  level  X  such that the sum of all the values of nodes at level  X  is  maximal .   Example 1: Input: [1,7,0,7,-8,null,null] Output: 2 Explanation: Level 1 sum = 1. Level 2 sum = 7 + 0 = 7. Level 3 sum = 7 + -8 = -1. So we return the level with the maximum sum which is level 2.   Note: The number of nodes in the given tree is between  1  and  10^4 . -10^5 <= node.val <= 10^5

https://leetcode.com/problems/stickers-to-spell-word/ We are given N different types of stickers. Each sticker has a lowercase English word on it. You would like to spell out the given  target  string by cutting individual letters from your collection of stickers and rearranging them. You can use each sticker more than once if you want, and you have infinite quantities of each sticker. What is the minimum number of stickers that you need to spell out the  target ? If the task is impossible, return -1. Example 1: Input: ["with", "example", "science"], "thehat" Output: 3 Explanation: We can use 2 "with" stickers, and 1 "example" sticker. After cutting and rearrange the letters of those stickers, we can form the target "thehat". Also, this is the minimum number of stickers necessary to form the target string. Example 2: Input: ["notice", "possible"], "basicbasic" Output: -1 Explanation: We ...

https://leetcode.com/problems/game-of-life/ According to the  Wikipedia's article : "The  Game of Life , also known simply as  Life , is a cellular automaton devised by the British mathematician John Horton Conway in 1970." Given a  board  with  m  by  n  cells, each cell has an initial state  live  (1) or  dead  (0). Each cell interacts with its  eight neighbors  (horizontal, vertical, diagonal) using the following four rules (taken from the above Wikipedia article): Any live cell with fewer than two live neighbors dies, as if caused by under-population. Any live cell with two or three live neighbors lives on to the next generation. Any live cell with more than three live neighbors dies, as if by over-population.. Any dead cell with exactly three live neighbors becomes a live cell, as if by reproduction. Write a function to compute the next state (after one update) of the board given its current state.  The...

https://leetcode.com/problems/path-sum-iii/ You are given a binary tree in which each node contains an integer value. Find the number of paths that sum to a given value. The path does not need to start or end at the root or a leaf, but it must go downwards (traveling only from parent nodes to child nodes). The tree has no more than 1,000 nodes and the values are in the range -1,000,000 to 1,000,000. Example: root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8 10 / \ 5 -3 / \ \ 3 2 11 / \ \ 3 -2 1 Return 3. The paths that sum to 8 are: 1. 5 -> 3 2. 5 -> 2 -> 1 3. -3 -> 11 --- Related problems 112-path-sum 113-path-sum-ii --- ---

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/minimum-time-to-collect-all-apples-in-a-tree/ Given an undirected tree consisting of  n  vertices numbered from 0 to  n-1 , which has some apples in their vertices. You spend 1 second to walk over one edge of the tree.  Return the minimum time in seconds you have to spend in order to collect all apples in the tree starting at  vertex 0  and coming back to this vertex. The edges of the undirected tree are given in the array  edges , where  edges[i] = [from i , to i ]  means that exists an edge connecting the vertices  from i  and  to i . Additionally, there is a boolean array  hasApple , where  hasApple[i] = true  means that vertex  i  has an apple, otherwise, it does not have any apple.   Example 1: Input: n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], hasApple = [false,false,true,false,true,true,false] Output: 8 Explanation: Th...