Skip to content

Prepare For Coder Interview – Denny

  • Basic
  • Medium
  • Hard
  • Architect
  • Life

Review: Graph Problems

Posted on January 22, 2018July 26, 2020 by braindenny

Graph related questions mainly focus on depth first search and breath first search.



Basic Abstractions

Name Summary
bfs and dfs relationship LeetCode: Word Ladder II
Common graph representations Adjacent matrix, adjacent list, hashmap of hashmaps
From BFS to Bidirectional BFS Half of the time. LeetCode: Word Ladder
3 cases: state is invalid/visited/unexamined LeetCode: Word Ladder
Bridge in graph Bridge is an edge, when removed, will disconnect the graph
Duplicate edge  
Cycle in undirected graphs  
Cycle in DAG LeetCode: Redundant Connection II
For matrix graph problems: rectangle vs square  

Top 10 Graph Algorithm

Num Problem Summary
1 Dijkstra’s algorithm Greedy. Shortest path for two nodes in a weighted grap. See #dijkstra
2 Bellman-Ford algorithm Shortest path for two nodes in a weighted graph + negative edges. See #floyd
3 Floyd-Warshall algorithm Find shortest paths in a weighted graph
4 Kruskal’s algorithm Union find + Greedy. Minimum Spanning Tree(MST).
5 Prim’s algorithm Greedy + Heap. Minimum Spanning Tree(MST).
6 Tarjan’s algorithm Cut node
7   Cut edge
8 Topological Sort Node dependencies
9 #bipartite Whether graph is a bipartite graph

Top Questions

Num Problem Summary
1 Graph Connectivity: Count islands in a 2D matrix LeetCode: Number of Islands, LeetCode: Island Perimeter
2 Get the size of the largest island LeetCode: Max Area of Island
3 Cycle detection in a directed graph LeetCode: Redundant Connection II
4 Detect all cycles in a directed graph LeetCode: Find Eventual Safe States
5 Whether a graph is a tree LeetCode: Graph Valid Tree
6 Update a specific region LeetCode: Flood Fill
7 Graph trasversal from boarders Leetcode: Surrounded Regions
8 Number of Distinct Islands LeetCode: Number of Distinct Islands
9 Mark levels LeetCode: 01 Matrix
10 Diameter of a tree in graph theory LeetCode: Tree Diameter
11 Duplicate edges LeetCode: Reconstruct Itinerary
12 Find a certain node in a graph LeetCode: Find the Celebrity
13 Graph with next steps by a trie Leetcode: Word Search II
14 Coloring graph LeetCode: Minesweeper
15 Find a certain path from source to destination in a graph LeetCode: Path With Maximum Minimum Value
16 Find the shortest distance from point1 to point2 LeetCode: Word Ladder, LeetCode: Sliding Puzzle
17 Find shortest distance in a weighted graph LeetCode: Find the City With the Smallest Number of Neighbors
18 Find all minimum paths from point1 to point2 LeetCode: Word Ladder II
19 All Paths from Source Lead to Destination LeetCode: All Paths from Source Lead to Destination
20 Node connectivity problem for a sparse 2D matrix LeetCode: Escape a Large Maze
21 Bricks Falling When Hit LeetCode: Bricks Falling When Hit
22 Bridges in a connected graph – Tarjan’s algorithm LeetCode: Critical Connections in a Network
23 Valid & Invalid moves LeetCode: Alphabet Board Path
24 Move in different directions: 4 directions, 8 directions LeetCode: Queens That Can Attack the King
25 String Transforms Into Another String LeetCode: String Transforms Into Another String
26 Candidates are (i, j, r), instead of (i, j) LeetCode: Shortest Path in a Grid with Obstacles Elimination
27 Clone Graph Leetcode: Clone Graph
28 Array problem with hidden graph LeetCode: Number of Squareful Arrays
29 Is Graph Bipartite LeetCode: Is Graph Bipartite
30 Search an infinite graph LeetCode: Escape a Large Maze
31 BFS with BFS LeetCode: Minimum Moves to Move a Box to Their Target Location

Post Views: 7
Posted in ReviewTagged #graph, review

Post navigation

Review: Heap Problems
Review: Dynamic Programming Problems

Leave a Reply Cancel reply

Your email address will not be published.

Tags

#array #backtracking #bfs #binarytree #bitmanipulation #blog #classic #codetemplate #combination #dfs #dynamicprogramming #game #graph #greedy #heap #inspiring #interval #linkedlist #manydetails #math #palindrome #recursive #slidingwindow #stack #string #subarray #trie #twopointer #twosum binarysearch editdistance hashmap intervaldp knapsack monotone oodesign presum rectangle redo review rotatelist series sql treetraversal unionfind

Recent Posts

  • a
  • a
  • a
  • a
  • a

Recent Comments

    Archives

    Categories

    • Amusing
    • Basic
    • Easy
    • Hard
    • Life
    • Medium
    • Resource
    • Review
    • Series
    • Uncategorized
    Proudly powered by WordPress | Theme: petals by Aurorum.