DEV Community

Dev Cookies
Dev Cookies

Posted on

📌 Day 20: The Graph Pattern (Amazon Interview Series)

Graphs represent relationships (networks, dependencies, maps, hierarchies).
Amazon frequently tests graph problems because they reveal:

  • Problem decomposition skills
  • Traversal mastery (BFS/DFS)
  • Ability to detect cycles / dependencies
  • Optimization on connected data

🔑 Core Graph Techniques

  1. BFS (Breadth-First Search) → shortest path in unweighted graphs.
  2. DFS (Depth-First Search) → connectivity, path existence, cycle detection.
  3. Topological Sort (Kahn’s Algorithm / DFS) → ordering with dependencies.
  4. Union-Find (Disjoint Set) → connected components, cycle detection in undirected graphs.

📝 Problem 1: Rotten Oranges (BFS)

👉 Amazon-style phrasing:
You are given a grid of 0 (empty), 1 (fresh orange), 2 (rotten orange). Every minute, rotten oranges infect adjacent fresh ones. Return minimum minutes to rot all oranges, or -1 if impossible.

Java Solution 

import java.util.*;

public class RottenOranges {
    public int orangesRotting(int[][] grid) {
        int rows = grid.length, cols = grid[0].length;
        Queue<int[]> queue = new LinkedList<>();
        int fresh = 0, minutes = 0;

        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (grid[i][j] == 2) queue.offer(new int[]{i, j});
                if (grid[i][j] == 1) fresh++;
            }
        }

        int[][] directions = {{1,0},{-1,0},{0,1},{0,-1}};
        while (!queue.isEmpty() && fresh > 0) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int[] cell = queue.poll();
                for (int[] d : directions) {
                    int x = cell[0] + d[0], y = cell[1] + d[1];
                    if (x>=0 && y>=0 && x<rows && y<cols && grid[x][y]==1) {
                        grid[x][y] = 2;
                        fresh--;
                        queue.offer(new int[]{x, y});
                    }
                }
            }
            minutes++;
        }
        return fresh == 0 ? minutes : -1;
    }

    public static void main(String[] args) {
        RottenOranges ro = new RottenOranges();
        int[][] grid = {{2,1,1},{1,1,0},{0,1,1}};
        System.out.println(ro.orangesRotting(grid)); // 4
    }
}
Enter fullscreen mode Exit fullscreen mode

✅ Key Insight: BFS level-order traversal = time progression.

📝 Problem 2: Course Schedule (Topological Sort)

👉 Amazon-style phrasing:
You are given n courses and prerequisites [a,b] meaning b → a. Return whether it is possible to finish all courses.

Java Solution 

import java.util.*;

public class CourseSchedule {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) graph.add(new ArrayList<>());

        int[] indegree = new int[numCourses];
        for (int[] pre : prerequisites) {
            graph.get(pre[1]).add(pre[0]);
            indegree[pre[0]]++;
        }

        Queue<Integer> q = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) if (indegree[i] == 0) q.offer(i);

        int count = 0;
        while (!q.isEmpty()) {
            int course = q.poll();
            count++;
            for (int next : graph.get(course)) {
                if (--indegree[next] == 0) q.offer(next);
            }
        }
        return count == numCourses;
    }

    public static void main(String[] args) {
        CourseSchedule cs = new CourseSchedule();
        int[][] prereq = {{1,0},{2,1},{3,2}};
        System.out.println(cs.canFinish(4, prereq)); // true
    }
}
Enter fullscreen mode Exit fullscreen mode

✅ Key Insight: Use Kahn’s Algorithm to check if a valid ordering exists.

📝 Problem 3: Number of Connected Components (Union-Find)

👉 Amazon-style phrasing:
Given n nodes labeled 0...n-1 and a list of undirected edges, return the number of connected components.

Java Solution 

public class ConnectedComponents {
    public int countComponents(int n, int[][] edges) {
        int[] parent = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;

        for (int[] edge : edges) {
            int root1 = find(parent, edge[0]);
            int root2 = find(parent, edge[1]);
            if (root1 != root2) {
                parent[root1] = root2;
                n--;
            }
        }
        return n;
    }

    private int find(int[] parent, int x) {
        if (parent[x] != x) parent[x] = find(parent, parent[x]);
        return parent[x];
    }

    public static void main(String[] args) {
        ConnectedComponents cc = new ConnectedComponents();
        int[][] edges = {{0,1},{1,2},{3,4}};
        System.out.println(cc.countComponents(5, edges)); // 2
    }
}
Enter fullscreen mode Exit fullscreen mode

✅ Key Insight: Union-Find reduces graph problems to set merging.

📝 Problem 4: Word Ladder (BFS on Word Graph)

👉 Amazon-style phrasing:
Given beginWord, endWord, and a word list, find the shortest transformation sequence where only one letter can change at a time.

Java Solution (Sketch) 

// BFS layer expansion with dictionary HashSet
Enter fullscreen mode Exit fullscreen mode

(Amazon almost always asks for BFS-based solution here.)

🎯 Amazon Variations of Graph Problems

  • Clone Graph → DFS/BFS with HashMap.
  • Is Graph Bipartite? → BFS coloring.
  • Alien Dictionary → Topological Sort on characters.
  • Network Delay Time → Dijkstra (weighted BFS).
  • Minimum Spanning Tree → Kruskal (Union-Find).

🏆 Key Takeaways

  • BFS → shortest path, level-order simulation.
  • DFS → connectivity, cycle detection.
  • Topological Sort → scheduling with dependencies.
  • Union-Find → efficient cycle/connection checks.

📅 Next in the series (Day 21):
👉 Heap / Priority Queue Pattern – scheduling, top-k, streaming problems.

Top comments (0)