Implement a Graph (Adjacency Matrix)
Design a graph data structure using an Adjacency Matrix. Implement methods for adding edges and checking if a path exists between two nodes.
Why Interviewers Ask This
Interviewers at Airbnb ask this to evaluate your ability to select appropriate data structures for specific constraints. They want to see if you understand the trade-offs between space and time complexity, specifically how an adjacency matrix handles dense graphs versus sparse ones. This tests your foundational knowledge of graph algorithms and your capacity to implement robust, error-free code under pressure.
How to Answer This Question
1. Clarify requirements immediately: Ask about node count limits and whether the graph is directed or weighted, as Airbnb values clarity in ambiguous scenarios.
2. Define the structure: Propose a 2D array where indices represent nodes and values represent edge weights or existence flags. Mention O(1) lookup benefits.
3. Discuss complexity trade-offs: Explicitly state that while checking edges is O(1), space usage is O(V^2), making it unsuitable for very large, sparse networks like global flight routes but ideal for smaller social clusters.
4. Implement core methods: Walk through adding an edge by updating two matrix cells (for undirected) or one (directed). For path finding, suggest Breadth-First Search (BFS) using a queue and a visited set.
5. Validate with examples: Trace a small example manually to show how the matrix updates and how BFS traverses neighbors row by row until the target is found.
Key Points to Cover
- Explicitly discussing the O(V^2) space complexity trade-off compared to adjacency lists
- Demonstrating understanding of directed vs. undirected graph updates in the matrix
- Selecting BFS as the optimal traversal algorithm for path existence checks
- Clarifying assumptions about node counts before writing code
- Handling edge cases like self-loops or disconnected components
Sample Answer
To design a graph using an adjacency matrix, I would start by initializing a 2D integer array of size V x V, where V is the number of vertices. Each cell [i][j] will store the weight of the edge from node i to j; if no e…
Common Mistakes to Avoid
- Failing to mention that adjacency matrices are inefficient for sparse graphs with few edges
- Implementing DFS instead of BFS without explaining why, potentially missing the shortest path logic
- Neglecting to handle the symmetric update for undirected graphs when adding edges
- Not defining what value represents 'no edge' (e.g., -1, 0, or infinity) leading to logical errors
Sound confident on this question in 5 minutes
Answer once and get a 30-second AI critique of your structure, content, and delivery. First attempt is free — no signup needed.