Graphs
Nodes joined by edges, with no single shape.
3 subjects · 9 topics · 1 area · 3 cheatsheets
Subjects covering this category
3 subjects- Subject · Intermediate to Advanced
Tracing, implementing and proving the cost of the classic searching, sorting and graph algorithms, and designing new ones with divide and conquer, backtracking, greedy choice and dynamic programming, in Python, Java and TypeScript.
- Searching and Simple Sorting
- Efficient Sorting
- Design Strategies
- Subject · Beginner to Advanced
Choosing a data structure by the cost of its operations, and implementing arrays, linked lists, stacks, queues, hash tables, trees, heaps, tries and graphs in Python, Java and TypeScript.
- Measuring Cost
- Sequences and Lookup
- Recursion and Trees
- Subject · Intermediate to Advanced
Recognising which of the common problem-solving patterns an unseen coding problem needs, and solving it in Python, Java or TypeScript within the time an interview allows.
- Approach
- Array and Number Patterns
- Linked List Patterns
Cheatsheets
3 cheatsheets- Cheatsheet · Algorithms
Traversal, ordering, shortest paths, spanning trees and connectivity on one page: which algorithm a graph question needs and what it costs.
- Cheatsheet · Data Structures
Every data structure in the subject on one page: what each one is for, what its operations cost, and how to choose.
- Cheatsheet · Coding Interview Patterns
Fourteen coding interview patterns on one page: the property that points to each, what it costs, when it fails, and its loop in Python.
Graph Algorithms
7 topics- Algorithms
Shortest paths in weighted graphs, in algorithms: Dijkstra's algorithm, Bellman-Ford and Floyd-Warshall, and how weights and pairs choose between them.
Intermediate to Advanced11 cards · 6 qnot started
- Algorithms
Breadth-first and depth-first search in algorithms, and what they find: components, cycles, bipartite graphs and unweighted shortest paths.
Intermediate to Advanced10 cards · 6 qnot started
- Algorithms
Minimum spanning trees in algorithms: the cut property, Kruskal's algorithm with union-find, Prim's algorithm with a heap, and why neither gives shortest paths.
Intermediate to Advanced9 cards · 4 qnot started
- Algorithms
Ordering tasks so every dependency comes first, in algorithms: Kahn's algorithm, depth-first finishing times, and how each one finds a cycle.
Intermediate to Advanced8 cards · 4 qnot started
- Coding Interview Patterns
Grid traversal: treating a grid of cells as a graph for breadth-first and depth-first search, flood fills and searches from many starting cells.
Intermediate to Advanced8 cards · 4 qnot started
- Coding Interview Patterns
Graph modelling: finding the vertices and edges hidden in a problem's wording, then solving it with a search, a topological sort or union-find.
Intermediate to Advanced8 cards · 4 qnot started
- Algorithms
Graph connectivity in algorithms: strongly connected components with Kosaraju's two passes, bridges and articulation points from low values, and choosing the tool.
Intermediate to Advanced7 cards · 3 qnot started
In Graphs itself
2 topics- Data Structures
Graph representations: storing vertices and edges as an adjacency list or an adjacency matrix, and choosing between them by how many edges there are.
Beginner to Intermediate8 cards · 4 qnot started
- Data Structures
Union-find in data structures: tracking which items share a group with a parent array, merging groups, and counting components and detecting cycles in a graph.
Intermediate to Advanced7 cards · 3 qnot started