SWE Interview preparation

https://leetcode.com/problems/making-a-large-island/ In a 2D grid of  0 s and  1 s, we change at most one  0  to a  1 . After, what is the size of the largest island? (An island is a 4-directionally connected group of  1 s). Example 1: Input: [[1, 0], [0, 1]] Output: 3 Explanation: Change one 0 to 1 and connect two 1s, then we get an island with area = 3. Example 2: Input: [[1, 1], [1, 0]] Output: 4 Explanation: Change the 0 to 1 and make the island bigger, only one island with area = 4. Example 3: Input: [[1, 1], [1, 1]] Output: 4 Explanation: Can't change any 0 to 1, only one island with area = 4.   Notes: 1 <= grid.length = grid[0].length <= 50 . 0 <= grid[i][j] <= 1 . ---

https://leetcode.com/problems/evaluate-division/ Equations are given in the format  A / B = k , where  A  and  B  are variables represented as strings, and  k  is a real number (floating point number). Given some queries, return the answers. If the answer does not exist, return  -1.0 . Example: Given  a / b = 2.0, b / c = 3.0. queries are:  a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ? . return  [6.0, 0.5, -1.0, 1.0, -1.0 ]. The input is:  vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries  , where  equations.size() == values.size() , and the values are positive. This represents the equations. Return  vector<double> . According to the example above: equations = [ ["a", "b"], ["b", "c"] ], values = [2.0, 3.0], queries = [ ["a", "c"], ["b", "a"], ["a", "e"], ["a", "a"], [...

https://leetcode.com/problems/decode-ways/ A message containing letters from  A-Z  is being encoded to numbers using the following mapping: 'A' -> 1 'B' -> 2 ... 'Z' -> 26 Given a  non-empty  string containing only digits, determine the total number of ways to decode it. Example 1: Input: "12" Output: 2 Explanation:  It could be decoded as "AB" (1 2) or "L" (12). Example 2: Input: "226" Output: 3 Explanation:  It could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6). --- Time - O(2 ^ N) - 2 branching at each recursive call - pure DFS Time - O(N) - each index is visited only once - memoized ---

https://leetcode.com/problems/target-sum/ You are given a list of non-negative integers, a1, a2, ..., an, and a target, S. Now you have 2 symbols  +  and  - . For each integer, you should choose one from  +  and  -  as its new symbol. Find out how many ways to assign symbols to make sum of integers equal to target S. Example 1: Input: nums is [1, 1, 1, 1, 1], S is 3. Output: 5 Explanation: -1+1+1+1+1 = 3 +1-1+1+1+1 = 3 +1+1-1+1+1 = 3 +1+1+1-1+1 = 3 +1+1+1+1-1 = 3 There are 5 ways to assign symbols to make the sum of nums be target 3. Note: The length of the given array is positive and will not exceed 20. The sum of elements in the given array will not exceed 1000. Your output answer is guaranteed to be fitted in a 32-bit integer. ----- Intuition Number of ways => DFS At each array index, we have two choices, + , - Terminate recursion when index == A.length * -- Can be memoized ---

https://leetcode.com/problems/similar-string-groups/ Two strings  X  and  Y  are similar if we can swap two letters (in different positions) of  X , so that it equals  Y . Also two strings  X  and  Y  are similar if they are equal. For example,  "tars"  and  "rats"  are similar (swapping at positions  0  and  2 ), and  "rats"  and  "arts"  are similar, but  "star"  is not similar to  "tars" ,  "rats" , or  "arts" . Together, these form two connected groups by similarity:  {"tars", "rats", "arts"}  and  {"star"} .  Notice that  "tars"  and  "arts"  are in the same group even though they are not similar.  Formally, each group is such that a word is in the group if and only if it is similar to at least one other word in the group. We are given a list  A  of strings.  Every string in  A ...

https://leetcode.com/problems/unique-paths-iii/ On a 2-dimensional  grid , there are 4 types of squares: 1  represents the starting square.  There is exactly one starting square. 2  represents the ending square.  There is exactly one ending square. 0  represents empty squares we can walk over. -1  represents obstacles that we cannot walk over. Return the number of 4-directional walks from the starting square to the ending square, that  walk over every non-obstacle square exactly once . Example 1: Input: [[1,0,0,0],[0,0,0,0],[0,0,2,-1]] Output: 2 Explanation: We have the following two paths: 1. (0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,2) 2. (0,0),(1,0),(2,0),(2,1),(1,1),(0,1),(0,2),(0,3),(1,3),(1,2),(2,2) Example 2: Input: [[1,0,0,0],[0,0,0,0],[0,0,0,2]] Output: 4 Explanation: We have the following four paths: 1. (0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,2),(2,3) 2. (...

https://leetcode.com/problems/n-queens-ii/ The  n -queens puzzle is the problem of placing  n  queens on an  n × n  chessboard such that no two queens attack each other. Given an integer  n , return the number of distinct solutions to the  n -queens puzzle. Example: Input: 4 Output: 2 Explanation: There are two distinct solutions to the 4-queens puzzle as shown below. [  [".Q..",  // Solution 1   "...Q",   "Q...",   "..Q."],  ["..Q.",  // Solution 2   "Q...",   "...Q",   ".Q.."] ] --- Related problems 51-n-queens ---

https://leetcode.com/problems/n-queens/ The  n -queens puzzle is the problem of placing  n  queens on an  n × n  chessboard such that no two queens attack each other. Given an integer  n , return all distinct solutions to the  n -queens puzzle. Each solution contains a distinct board configuration of the  n -queens' placement, where  'Q'  and  '.'  both indicate a queen and an empty space respectively. Example: Input: 4 Output: [ [".Q..", // Solution 1 "...Q", "Q...", "..Q."], ["..Q.", // Solution 2 "Q...", "...Q", ".Q.."] ] Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above. --- Related problems 52-n-queens-ii ---

https://leetcode.com/problems/permutations-ii/ Given a collection of numbers that might contain duplicates, return all possible unique permutations. Example: Input: [1,1,2] Output: [ [1,1,2], [1,2,1], [2,1,1] ] --- Related problems 46-permutations 78-subsets 90-subsets-ii 39-combination-sum 40-combination-sum-ii ---

https://leetcode.com/problems/subsets/ Given a set of  distinct  integers,  nums , return all possible subsets (the power set). Note:  The solution set must not contain duplicate subsets. Example: Input: nums = [1,2,3] Output: [ [3],   [1],   [2],   [1,2,3],   [1,3],   [2,3],   [1,2],   [] ] --- Intuition Generate all combinations, save combination at each stage --- Related problems 90-subsets-ii 46-permutations 47-permutations-ii 39-combination-sum 40-combination-sum-ii ---

https://leetcode.com/problems/letter-combinations-of-a-phone-number/ Given a string containing digits from  2-9  inclusive, return all possible letter combinations that the number could represent. A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters. Example: Input: "23" Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]. Note: Although the above answer is in lexicographical order, your answer could be in any order you want. ---- Intuition Traverse the digits string Take 1 digit at a time Get the characters for that digit For each char, recurse on second digit.. and so on.. We can keep a prefix and add current char there This will require backtracking once we come back from next digit StringBuilder has deleteCharAt method or use String, that will create a new object on each re...

https://leetcode.com/problems/combination-sum-ii/ Given a collection of candidate numbers ( candidates ) and a target number ( target ), find all unique combinations in  candidates  where the candidate numbers sums to  target . Each number in  candidates  may only be used  once  in the combination. Note: All numbers (including  target ) will be positive integers. The solution set must not contain duplicate combinations. Example 1: Input: candidates =  [10,1,2,7,6,1,5] , target =  8 , A solution set is: [ [1, 7], [1, 2, 5], [2, 6], [1, 1, 6] ] Example 2: Input: candidates = [2,5,2,1,2], target = 5, A solution set is: [   [1,2,2],   [5] ] --- Related problems 39-combination-sum 46-permutations 47-permutations-ii 78-subsets 90-subsets-ii ---

https://leetcode.com/problems/combination-sum/ Given a  set  of candidate numbers ( candidates )  (without duplicates)  and a target number ( target ), find all unique combinations in  candidates  where the candidate numbers sums to  target . The  same  repeated number may be chosen from  candidates  unlimited number of times. Note: All numbers (including  target ) will be positive integers. The solution set must not contain duplicate combinations. Example 1: Input: candidates = [2,3,6,7], target = 7 , A solution set is: [ [7], [2,2,3] ] Example 2: Input: candidates = [2,3,5] , target = 8, A solution set is: [   [2,2,2,2],   [2,3,3],   [3,5] ] --- Related problems 40-combination-sum-ii 46-permutations 47-permutations-ii 78-subsets 90-subsets-ii ---

https://leetcode.com/problems/combinations/ Given two integers  n  and  k , return all possible combinations of  k  numbers out of 1 ...  n . Example: Input:  n = 4, k = 2 Output: [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ] --- Related problems 39-combination-sum 40-combination-sum-ii 46-permutations 47-permutations-ii 784-letter-case-permutation ---