SWE Interview preparation

https://leetcode.com/problems/connecting-cities-with-minimum-cost/ https://github.com/openset/leetcode/tree/master/problems/connecting-cities-with-minimum-cost There are  N  cities numbered from 1 to  N . You are given  connections , where each  connections[i] = [city1, city2, cost]  represents the cost to connect  city1  and  city2  together.  (A  connection  is bidirectional: connecting  city1  and  city2  is the same as connecting  city2  and  city1 .) Return the minimum cost so that for every pair of cities, there exists a path of connections (possibly of length 1) that connects those two cities together.  The cost is the sum of the connection costs used. If the task is impossible, return -1.   Example 1: Input: N = 3, connections = [[1,2,5],[1,3,6],[2,3,1]] Output: 6 Explanation: Choosing any 2 edges will connect all cities so we choose the minimum 2. Example 2: Input...

https://www.lintcode.com/problem/graph-valid-tree/description https://leetcode.com/problems/graph-valid-tree/ Given  n  nodes labeled from  0  to  n-1  and a list of undirected edges (each edge is a pair of nodes), write a function to check whether these edges make up a valid tree. Example 1: Input: n = 5 , and edges = [[0,1], [0,2], [0,3], [1,4]] Output: true Example 2: Input: n = 5, and edges = [[0,1], [1,2], [2,3], [1,3], [1,4]] Output: false Note : you can assume that no duplicate edges will appear in  edges . Since all edges are undirected,  [0,1]  is the same as  [1,0]  and thus will not appear together in  edges . --- Intuition Union Find Check number of nodes - 1 = number of edges -- tree definition Union - check if parents of two nodes are the same -- cannot happen with path compression Find - use path compression --- BFS Start with node 0 Use Set instead of Q for BFS - we need to detec...

https://leetcode.com/problems/redundant-connection/ In this problem, a tree is an  undirected  graph that is connected and has no cycles. The given input is a graph that started as a tree with N nodes (with distinct values 1, 2, ..., N), with one additional edge added. The added edge has two different vertices chosen from 1 to N, and was not an edge that already existed. The resulting graph is given as a 2D-array of  edges . Each element of  edges  is a pair  [u, v]  with  u < v , that represents an  undirected  edge connecting nodes  u  and  v . Return an edge that can be removed so that the resulting graph is a tree of N nodes. If there are multiple answers, return the answer that occurs last in the given 2D-array. The answer edge  [u, v]  should be in the same format, with  u < v . Example 1: Input: [[1,2], [1,3], [2,3]] Output: [2,3] Explanation: The given undirected graph will be l...

https://leetcode.com/problems/surrounded-regions/ Given a 2D board containing  'X'  and  'O'  ( the letter O ), capture all regions surrounded by  'X' . A region is captured by flipping all  'O' s into  'X' s in that surrounded region. Example: X X X X X O O X X X O X X O X X After running your function, the board should be: X X X X X X X X X X X X X O X X Explanation: Surrounded regions shouldn’t be on the border, which means that any  'O'  on the border of the board are not flipped to  'X' . Any  'O'  that is not on the border and it is not connected to an  'O'  on the border will be flipped to  'X' . Two cells are connected if they are adjacent cells connected horizontally or vertically. --- Intuition Identify O's at borders, save them and connected neighbors. In the end, restore the saved O's and mark remaining O's as X DFS, and BFS both work DFS is faster Note - N...