Topological Sort - How to Succeed in Algorithms Interview


Topological Sort - How to Succeed in Algorithms Interview

How to Succeed in Algorithms Interview Series


Topological Sort

When to use

  • order, sort
  • boundary: input degree: 0

Examples

  • LeetCode 329 - Longest Increasing Path in a Matrix
    • dfs + cache: O(mn)
    • Topological Sort: BFS
      • matrix to graph, only need indegrees[][]; no need to create graph map
      public int longestIncreasingPath(int[][] matrix) {
      int m = matrix.length; n = matrix[0].length;
      int[][] indegree = new int[m][n];
      Queue<int[]> q = new LinkedList();
      for (int row = 0; row < m; row++) {
          for (int col = 0; col < n; col++) {
              for(int i = 0; i < 4; i++) {
                  int nextRow = row + dirs[i][0];
                  int nextCol = col + dirs[i][1];
                  if (nextRow >= 0 && nextRow < m && nextCol >= 0 && nextCol < n &&
                      matrix[row][col] > matrix[nextRow][nextCol]) {
                      indegree[row][col]++;
                  }
              }
              if (indegree[row][col] == 0) q.offer(new int[]{row, col});
          }
      }
      int len = 0;
      while (!q.isEmpty()) {
          int size = q.size();
          while (size-- > 0) { // consume all nodes in cur layer and add next layer into queue
              int[] coord = q.poll();
              int row = coord[0], col = coord[1];
              for(int i = 0; i < 4; i++) {
                  int nextRow = row + dirs[i][0];
                  int nextCol = col + dirs[i][1];
                  if (nextRow >= 0 && nextRow < m && nextCol >= 0 && nextCol < n &&
                      matrix[row][col] < matrix[nextRow][nextCol]) {
                      if (--indegree[nextRow][nextCol] == 0)     // remove edge
                          q.offer(new int[]{nextRow, nextCol});  // add as next level node
                  }
              }
          }
          len++; // at the end of each layer, increase the length
      }
      return len;
      }
  • LeetCode 207- Course Schedule
  • LeetCode 210 - Course Schedule II
  • LeetCode 269 - Alien Dictionary
  • Find Itinerary from a given list of tickets
  • Detect Cycle in a Directed Graph
  • LeetCode 802 - Find Eventual Safe States
    • Topological sort
    • dfs: color[i] = 0 means node i is not visited; color[i] = 1 means node i is visiting; color[i] = 2 means node i has been already visited
      • when color[i] = 1 and it is visited again; then detect cycle
    • reverse graph
  • Preference list - Airbnb

Labels

adsense (5) Algorithm (69) Algorithm Series (35) Android (7) ANT (6) bat (8) Big Data (7) Blogger (14) Bugs (6) Cache (5) Chrome (19) Code Example (29) Code Quality (7) Coding Skills (5) Database (7) Debug (16) Design (5) Dev Tips (63) Eclipse (32) Git (5) Google (33) Guava (7) How to (9) Http Client (8) IDE (7) Interview (88) J2EE (13) J2SE (49) Java (186) JavaScript (27) JSON (7) Learning code (9) Lesson Learned (6) Linux (26) Lucene-Solr (112) Mac (10) Maven (8) Network (9) Nutch2 (18) Performance (9) PowerShell (11) Problem Solving (11) Programmer Skills (6) regex (5) Scala (6) Security (9) Soft Skills (38) Spring (22) System Design (11) Testing (7) Text Mining (14) Tips (17) Tools (24) Troubleshooting (29) UIMA (9) Web Development (19) Windows (21) xml (5)