Graph Algorithms for Technical Interviews

Introduction

• Instructor: Alvin from Structy
• Course Focus: Graph algorithms for technical interviews
• Goals: Learn patterns to solve about 80% of all graph problems in technical interviews

Course Structure

1. Visualization: Key to understanding graphs
2. Algorithm Tracing: Trace through different algorithms with animations
3. Prerequisites: Basic coding knowledge and some understanding of recursion
4. Pattern Practice: Apply identified patterns to solve classic interview problems
5. Language: Code implementations will be in JavaScript
6. Flexibility: Follow along in any language

Key Concepts

Graph Basics

• Definition: Collection of nodes and edges
  • Nodes = vertices (e.g., A, B, C)
  • Edges = connections between nodes (e.g., A-C)
• Types of Graphs: Directed and Undirected
  • Directed Graph: Edges have direction (one-way streets)
  • Undirected Graph: Edges have no direction (two-way streets)
• Terminology:
  • Neighbor nodes: Accessible nodes via edges
• Visualization: Draw nodes as circles and connections as lines with arrowheads
• Adjacency List: Common way to represent graphs programmatically
  • Key = node, Value = list of neighbor nodes

Graph Traversal

• Depth First Traversal (DFS): Uses a stack
  • Explore as far as possible along one branch before backtracking
  • Implementation:
    • Push starting node to stack
    • Loop while stack is not empty
    • Pop node from stack, mark as visited
    • Push unvisited neighbors to stack
• Breadth First Traversal (BFS): Uses a queue
  • Explore all neighbors at the present depth before moving on to nodes at the next depth level
  • Implementation:
    • Add starting node to queue
    • Loop while queue is not empty
    • Dequeue node, mark as visited
    • Enqueue unvisited neighbors

Detailed Examples

1. DFS Example: Traversal Order Matters
2. BFS Example: Equal Exploration of All Directions
3. Stack vs Queue: Key implementation difference between DFS & BFS

Practical Applications

Algorithm Implementations in JavaScript

• DFS (Iterative & Recursive): Print all nodes
  • Iterative uses an explicit stack (array with push/pop)
  • Recursive leverages the call stack
  • Example implementations with code snippets
• BFS: Print all nodes
  • Iterative uses a queue (array with push/shift)
  • Example implementation with code snippet

Graph Problems and Solutions

1. Has Path Problem: Determine if a path exists between two nodes

• Approach: Use DFS or BFS
  • Analysis: Time complexity = O(E), Space complexity = O(N)
  • Example implementation with recursive DFS and iterative BFS

2. Undirected Path Problem: Handle cycles in an undirected graph

• Approach: Convert edge list to adjacency list
  • Traversal: Use DFS/BFS with visited set to avoid cycles
  • Example implementation with code snippet

3. Connected Components Count: Count all connected components in a graph

• Approach: Use iterative traversal with DFS or BFS
  • Implementation: Example code with explanation

4. Largest Component: Find the largest component by size

• Approach: Track size of each traversal and compare
  • Example implementation with code snippet

5. Shortest Path: Find the shortest path between two nodes

• Preferred Approach: BFS for even exploration and shortest path guarantee
  • Example implementation with code snippet

Grid-Based Graph Problems

1. Island Count: Count the number of islands in a grid (connected regions of 'land')

• Approach: Use nested loop and DFS/BFS with visited set
  • Example implementation with code snippet

2. Minimum Island: Find the smallest island in a grid

• Approach: Similar to Island Count but tracking minimum size
  • Example implementation with code snippet

Conclusion

• Practice: Essential to master graph algorithms
• Transition: More problems and practice at Structy.net