SWE Interview preparation

https://leetcode.com/problems/sequence-reconstruction/ https://github.com/openset/leetcode/tree/master/problems/sequence-reconstruction https://www.lintcode.com/problem/sequence-reconstruction/description Check whether the original sequence  org  can be uniquely reconstructed from the sequences in  seqs . The  org  sequence is a permutation of the integers from 1 to n, with 1 ≤ n ≤ 10 4 . Reconstruction means building a shortest common supersequence of the sequences in  seqs  (i.e., a shortest sequence so that all sequences in  seqs  are subsequences of it). Determine whether there is only one sequence that can be reconstructed from  seqs  and it is the  org  sequence. Example 1: Input: org: [1,2,3], seqs: [[1,2],[1,3]] Output: false Explanation: [1,2,3] is not the only one sequence that can be reconstructed, because [1,3,2] is also a valid sequence that can be reconstructed. Example 2: Input: org: [1,2,3], seqs: [[1,...

329. Longest Increasing Path in a Matrix Given an integer matrix, find the length of the longest increasing path. From each cell, you can either move to four directions: left, right, up or down. You may NOT move diagonally or move outside of the boundary (i.e. wrap-around is not allowed). Example 1: Input: nums = [ [ 9 ,9,4], [ 6 ,6,8], [ 2 , 1 ,1] ] Output: 4 Explanation: The longest increasing path is [1, 2, 6, 9] . Example 2: Input: nums = [ [ 3 , 4 , 5 ], [3,2, 6 ], [2,2,1] ] Output: 4 Explanation: The longest increasing path is [3, 4, 5, 6] . Moving diagonally is not allowed. --- DFS --- --- Intuition If a neighboring cell is less than current cell, there is a potential path from neighbor to current. Number of neighbors smaller than current - number of potential paths coming into current ~ inDegree if inDegree of current is 0 => no neighbor is smaller than me at this time. So current cell is potential starting point Once...

https://leetcode.com/problems/reconstruct-itinerary/ Given a list of airline tickets represented by pairs of departure and arrival airports  [from, to] , reconstruct the itinerary in order. All of the tickets belong to a man who departs from  JFK . Thus, the itinerary must begin with  JFK . Note: If there are multiple valid itineraries, you should return the itinerary that has the smallest lexical order when read as a single string. For example, the itinerary  ["JFK", "LGA"]  has a smaller lexical order than  ["JFK", "LGB"] . All airports are represented by three capital letters (IATA code). You may assume all tickets form at least one valid itinerary. Example 1: Input: [["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]] Output: ["JFK", "MUC", "LHR", "SFO", "SJC"] Example 2: Input: [[...

https://leetcode.com/problems/find-eventual-safe-states/ In a directed graph, we start at some node and every turn, walk along a directed edge of the graph.  If we reach a node that is terminal (that is, it has no outgoing directed edges), we stop. Now, say our starting node is  eventually safe  if and only if we must eventually walk to a terminal node.  More specifically, there exists a natural number  K  so that for any choice of where to walk, we must have stopped at a terminal node in less than  K  steps. Which nodes are eventually safe?  Return them as an array in sorted order. The directed graph has  N  nodes with labels  0, 1, ..., N-1 , where  N  is the length of  graph .  The graph is given in the following form:  graph[i]  is a list of labels  j  such that  (i, j)  is a directed edge of the graph. Example: Input: graph = [[1,2],[2,3],[5],[0],[5],[],[]...

https://leetcode.com/problems/alien-dictionary/ https://www.lintcode.com/problem/alien-dictionary/description There is a new alien language which uses the latin alphabet. However, the order among letters are unknown to you. You receive a list of  non-empty  words from the dictionary, where  words are sorted lexicographically by the rules of this new language . Derive the order of letters in this language. Example 1: Input: [ "wrt", "wrf", "er", "ett", "rftt" ] Output: "wertf" Example 2: Input: [ "z", "x" ] Output: "zx" Example 3: Input: [ "z", "x", "z" ] Output: ""   Explanation: The order is invalid, so return "" . Note: You may assume all letters are in lowercase. You may assume that if a is a prefix of b, then a must appear before b in the given dictionary. If the order is invalid, return an...

https://leetcode.com/problems/course-schedule-ii/ There are a total of  n  courses you have to take, labeled from  0  to  n-1 . Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair:  [0,1] Given the total number of courses and a list of prerequisite  pairs , return the ordering of courses you should take to finish all courses. There may be multiple correct orders, you just need to return one of them. If it is impossible to finish all courses, return an empty array. Example 1: Input: 2, [[1,0]] Output: [0,1] Explanation:  There are a total of 2 courses to take. To take course 1 you should have finished   course 0. So the correct course order is [0,1] . Example 2: Input: 4, [[1,0],[2,0],[3,1],[3,2]] Output: [0,1,2,3] or [0,2,1,3] Explanation:  There are a total of 4 courses to take. To take course 3 you should have finished both ...

https://leetcode.com/problems/course-schedule/ There are a total of  n  courses you have to take, labeled from  0  to  n-1 . Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair:  [0,1] Given the total number of courses and a list of prerequisite  pairs , is it possible for you to finish all courses? Example 1: Input: 2, [[1,0]] Output: true Explanation:  There are a total of 2 courses to take.   To take course 1 you should have finished course 0. So it is possible. Example 2: Input: 2, [[1,0],[0,1]] Output: false Explanation:  There are a total of 2 courses to take.   To take course 1 you should have finished course 0, and to take course 0 you should   also have finished course 1. So it is impossible. Note: The input prerequisites is a graph represented by  a list of edges , not adjacency matr...