SWE Interview preparation

https://leetcode.com/problems/delete-operation-for-two-strings/description/ Given two strings  word1  and  word2 , return  the minimum number of  steps  required to make   word1   and   word2   the same . In one  step , you can delete exactly one character in either string.   Example 1: Input: word1 = "sea", word2 = "eat" Output: 2 Explanation: You need one step to make "sea" to "ea" and another step to make "eat" to "ea". Example 2: Input: word1 = "leetcode", word2 = "etco" Output: 4   Constraints: 1 <= word1.length, word2.length <= 500 word1  and  word2  consist of only lowercase English letters. --- Time - O(M * N) Space - O(M * N) --- ---- ----

https://leetcode.com/problems/unique-binary-search-trees-ii/ Given an integer  n , generate all structurally unique  BST's  (binary search trees) that store values 1 ...  n . Example: Input: 3 Output: [   [1,null,3,2],   [3,2,null,1],   [3,1,null,null,2],   [2,1,3],   [1,null,2,null,3] ] Explanation: The above output corresponds to the 5 unique BST's shown below: 1 3 3 2 1 \ / / / \ \ 3 2 1 1 3 2 / / \ \ 2 1 2 3 --- Related problems 96-unique-binary-search-trees ---

https://www.lintcode.com/problem/the-maze/description https://leetcode.com/problems/the-maze There is a  ball  in a maze with empty spaces and walls. The ball can go through empty spaces by rolling  up ,  down ,  left  or  right , but it won't stop rolling until hitting a wall. When the ball stops, it could choose the next direction. Given the ball's  start position , the  destination  and the  maze , determine whether the ball could stop at the destination. The maze is represented by a binary 2D array. 1 means the wall and 0 means the empty space. You may assume that the borders of the maze are all walls. The start and destination coordinates are represented by row and column indexes. Example 1: Input 1: a maze represented by a 2D array 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 1 1 0 1 1 0 0 0 0 0 Input 2: start coordinate (rowStart, colStart) = (0, 4) Input 3: destination coordinate (rowDest, colDest) = (4, 4) Output: t...

https://leetcode.com/problems/triangle/ Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below. For example, given the following triangle [ [ 2 ], [ 3 ,4], [6, 5 ,7], [4, 1 ,8,3] ] The minimum path sum from top to bottom is  11  (i.e.,  2  +  3  +  5  +  1  = 11). Note: Bonus point if you are able to do this using only  O ( n ) extra space, where  n  is the total number of rows in the triangle. --- ---

https://leetcode.com/problems/minimum-falling-path-sum-ii/ Given a square grid of integers  arr , a  falling path with non-zero shifts  is a choice of exactly one element from each row of  arr , such that no two elements chosen in adjacent rows are in the same column. Return the minimum sum of a falling path with non-zero shifts. Example 1: Input: arr = [[1,2,3],[4,5,6],[7,8,9]] Output: 13 Explanation: The possible falling paths are: [1,5,9], [1,5,7], [1,6,7], [1,6,8], [2,4,8], [2,4,9], [2,6,7], [2,6,8], [3,4,8], [3,4,9], [3,5,7], [3,5,9] The falling path with the smallest sum is [1,5,7], so the answer is 13. Constraints: 1 <= arr.length == arr[i].length <= 200 -99 <= arr[i][j] <= 99 --- Time - O( n * n) Space - O(1) --- Related problems paint-house-ii ---

https://leetcode.com/problems/minimum-falling-path-sum/ Given a  square  array of integers  A , we want the  minimum  sum of a  falling path  through  A . A falling path starts at any element in the first row, and chooses one element from each row.  The next row's choice must be in a column that is different from the previous row's column by at most one. Example 1: Input: [[1,2,3],[4,5,6],[7,8,9]] Output: 12 Explanation: The possible falling paths are: [1,4,7], [1,4,8], [1,5,7], [1,5,8], [1,5,9] [2,4,7], [2,4,8], [2,5,7], [2,5,8], [2,5,9], [2,6,8], [2,6,9] [3,5,7], [3,5,8], [3,5,9], [3,6,8], [3,6,9] The falling path with the smallest sum is  [1,4,7] , so the answer is  12 . Note: 1 <= A.length == A[0].length <= 100 -100 <= A[i][j] <= 100 --- Time - O(n * n) Space - O(1) --- Related problems paint-house paint-house-ii ---

https://leetcode.com/problems/min-cost-climbing-stairs/ On a staircase, the  i -th step has some non-negative cost  cost[i]  assigned (0 indexed). Once you pay the cost, you can either climb one or two steps. You need to find minimum cost to reach the top of the floor, and you can either start from the step with index 0, or the step with index 1. Example 1: Input: cost = [10, 15, 20] Output: 15 Explanation: Cheapest is start on cost[1], pay that cost and go to the top. Example 2: Input: cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1] Output: 6 Explanation: Cheapest is start on cost[0], and only step on 1s, skipping cost[3]. Note: cost  will have a length in the range  [2, 1000] . Every  cost[i]  will be an integer in the range  [0, 999] . --- Intuition From last 2 steps cost to reach top is array element itself, since all number are positive, we will take respectively 2, 1 step to minimize the cost Cost 3rd last...

https://www.lintcode.com/problem/paint-house-ii/description https://leetcode.com/problems/paint-house-ii/ Description There are a row of  n  houses, each house can be painted with one of the  k  colors. The cost of painting each house with a certain color is different. You have to paint all the houses such that no two adjacent houses have the same color. The cost of painting each house with a certain color is represented by a  n  x  k  cost matrix. For example,  costs[0][0]  is the cost of painting house  0  with color  0 ;  costs[1][2]  is the cost of painting house  1  with color  2 , and so on... Find the minimum cost to paint all houses Example Example 1 Input: costs = [[14,2,11],[11,14,5],[14,3,10]] Output: 10 Explanation: The three house use color [1,2,1] for each house. The total cost is 10. Example 2 Input: costs = [[5]] Output: 5 Explanation: There is only one...

https://www.lintcode.com/problem/paint-house/description https://leetcode.com/problems/paint-house/ There are a row of  n  houses, each house can be painted with one of the three colors: red, blue or green. The cost of painting each house with a certain color is different. You have to paint all the houses such that  no two adjacent houses have the same color,  and you need to cost the least. Return the minimum cost. The cost of painting each house with a certain color is represented by a  n  x  3  cost matrix. For example,  costs[0][0]  is the cost of painting house  0  with color red;  costs[1][2]  is the cost of painting house  1  with color green, and so on... Find the minimum cost to paint all houses. All costs are positive integers. Example Example 1: Input: [[14,2,11],[11,14,5],[14,3,10]] Output: 10 Explanation: Paint house 0 into blue, paint house 1 into green, paint...

https://leetcode.com/problems/unique-paths-ii/ A robot is located at the top-left corner of a  m  x  n  grid (marked 'Start' in the diagram below). The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below). Now consider if some obstacles are added to the grids. How many unique paths would there be? An obstacle and empty space is marked as  1  and  0  respectively in the grid. Note:   m  and  n  will be at most 100. Example 1: Input: [   [0,0,0],   [0,1,0],   [0,0,0] ] Output: 2 Explanation: There is one obstacle in the middle of the 3x3 grid above. There are two ways to reach the bottom-right corner: 1. Right -> Right -> Down -> Down 2. Down -> Down -> Right -> Right --- Intuition Base case - If start or finish has obstacle, no path is possible, return 0 For f...