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/critical-connections-in-a-network/ There are  n  servers numbered from  0  to  n-1  connected by undirected server-to-server  connections  forming a network where  connections[i] = [a, b]  represents a connection between servers  a  and  b . Any server can reach any other server directly or indirectly through the network. A  critical connection  is a connection that, if removed, will make some server unable to reach some other server. Return all critical connections in the network in any order. Example 1: Input: n = 4, connections = [[0,1],[1,2],[2,0],[1,3]] Output: [[1,3]] Explanation: [[3,1]] is also accepted. Constraints: 1 <= n <= 10^5 n-1 <= connections.length <= 10^5 connections[i][0] != connections[i][1] There are no repeated connections. ---

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/text-justification/ Given an array of words and a width  maxWidth , format the text such that each line has exactly  maxWidth  characters and is fully (left and right) justified. You should pack your words in a greedy approach; that is, pack as many words as you can in each line. Pad extra spaces  ' '  when necessary so that each line has exactly  maxWidth  characters. Extra spaces between words should be distributed as evenly as possible. If the number of spaces on a line do not divide evenly between words, the empty slots on the left will be assigned more spaces than the slots on the right. For the last line of text, it should be left justified and no  extra  space is inserted between words. Note: A word is defined as a character sequence consisting of non-space characters only. Each word's length is guaranteed to be greater than 0 and not exceed  maxWidth . The input array  words  cont...

https://leetcode.com/problems/rearrange-string-k-distance-apart/ https://github.com/openset/leetcode/tree/master/problems/rearrange-string-k-distance-apart Given a non-empty string  s  and an integer  k , rearrange the string such that the same characters are at least distance  k  from each other. All input strings are given in lowercase letters. If it is not possible to rearrange the string, return an empty string  "" . Example 1: Input: s = "aabbcc" , k = 3 Output: "abcabc" Explanation: The same letters are at least distance 3 from each other. Example 2: Input: s = "aaabc" , k = 3 Output: "" Explanation: It is not possible to rearrange the string. Example 3: Input: s = "aaadbbcc" , k = 2 Output: "abacabcd" Explanation: The same letters are at least distance 2 from each other. --- Related problems 621-task-scheduler ---

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/split-array-largest-sum/ Given an array which consists of non-negative integers and an integer  m , you can split the array into  m  non-empty continuous subarrays. Write an algorithm to minimize the largest sum among these  m  subarrays. Note: If  n  is the length of array, assume the following constraints are satisfied: 1 ≤  n  ≤ 1000 1 ≤  m  ≤ min(50,  n ) Examples: Input: nums = [7,2,5,10,8] m = 2 Output: 18 Explanation: There are four ways to split nums into two subarrays. The best way is to split it into [7,2,5] and [10,8] , where the largest sum among the two subarrays is only 18. --- Related problems 774-minimize-max-distance-to-gas-station 875-koko-eating-bananas 1011-capacity-to-ship-packages-within-d-days ---

https://leetcode.com/problems/serialize-and-deserialize-n-ary-tree/ https://github.com/openset/leetcode/tree/master/problems/serialize-and-deserialize-n-ary-tree https://www.lintcode.com/problem/serialize-and-deserialize-n-ary-tree/description Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment. Design an algorithm to serialize and deserialize an N-ary tree. An N-ary tree is a rooted tree in which each node has no more than N children. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that an N-ary tree can be serialized to a string and this string can be deserialized to the original tree structure. For example, you may serialize the following  3-ary  tree     as  [1 [3[5 6] 2 4]] . You do n...

https://leetcode.com/problems/first-missing-positive/ Given an unsorted integer array, find the smallest missing positive integer. Example 1: Input: [1,2,0] Output: 3 Example 2: Input: [3,4,-1,1] Output: 2 Example 3: Input: [7,8,9,11,12] Output: 1 Note: Your algorithm should run in  O ( n ) time and uses constant extra space. ---

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 ...