Graph Modeling

A graph is the structure for relationships. Users follow users, services depend on services, cities connect by routes, permissions inherit through groups, and recommendations move through shared behavior. The algorithm only becomes clear after the model is precise.

Vertices and Edges

A vertex is an entity. An edge is a relationship. Directed edges have a source and destination. Undirected edges are symmetric. Weighted edges carry cost such as distance, latency, risk, or price.

Scenario: Permission Inheritance

A user belongs to teams; teams inherit permissions from parent teams; projects grant access to teams. This is no longer a simple tree if a team can have multiple parents. A graph model plus visited tracking prevents repeated work and infinite loops.

Same Pattern in Java, Python, and JavaScript

Most graph code starts by transforming an edge list into an adjacency list so traversal can quickly find neighbors.

import java.util.*;

class GraphBuilder {
    static Map<String, List<String>> buildDirected(List<String[]> edges) {
        Map<String, List<String>> graph = new HashMap<>();
        for (String[] edge : edges) {
            graph.computeIfAbsent(edge[0], key -> new ArrayList<>()).add(edge[1]);
            graph.computeIfAbsent(edge[1], key -> new ArrayList<>()); // Keep destination visible.
        }
        return graph;
    }
}

Interview signalFrequently Asked Interview Questions

These are canonical interview patterns for this topic, phrased as concrete problem statements. They avoid vague theory questions and prepare you for the exact reasoning interviewers expect: invariant, edge cases, complexity, and trade-off.

• Given directed edges, build an adjacency list that preserves terminal nodes.
• Given a directed graph, start, and target, return whether a path exists.
• Given n nodes and undirected edges, return whether the graph is a valid tree.

Production practiceCompany-Style Practice Examples

These are not claimed as exact company-specific questions. They are the interview patterns repeatedly used by product companies to test whether you can move from brute force to a defensible implementation.

Solved modelInterview Question Solutions

import java.util.*;

class GraphBuilder {
    static Map<String, List<String>> buildDirected(List<String[]> edges) {
        Map<String, List<String>> graph = new HashMap<>();
        for (String[] edge : edges) {
            graph.computeIfAbsent(edge[0], key -> new ArrayList<>()).add(edge[1]);
            graph.computeIfAbsent(edge[1], key -> new ArrayList<>()); // Keep destination visible.
        }
        return graph;
    }
}

import java.util.*;
class PathExists { static boolean exists(Map<String,List<String>> g, String s, String t) { Set<String> seen = new HashSet<>(); return dfs(g, s, t, seen); } static boolean dfs(Map<String,List<String>> g, String node, String target, Set<String> seen) { if (node.equals(target)) return true; if (!seen.add(node)) return false; for (String next : g.getOrDefault(node, List.of())) if (dfs(g, next, target, seen)) return true; return false; } }

import java.util.*;
class ValidTree { static boolean valid(int n, int[][] edges) { if (edges.length != n - 1) return false; List<List<Integer>> g = new ArrayList<>(); for (int i = 0; i < n; i++) g.add(new ArrayList<>()); for (int[] e : edges) { g.get(e[0]).add(e[1]); g.get(e[1]).add(e[0]); } Set<Integer> seen = new HashSet<>(); Deque<Integer> stack = new ArrayDeque<>(); stack.push(0); seen.add(0); while (!stack.isEmpty()) for (int next : g.get(stack.pop())) if (seen.add(next)) stack.push(next); return seen.size() == n; } }

Solved modelWorked Interview Answer

Build a directed adjacency list from relationship edges. The adjacency list keeps traversal cheap by storing each node's outgoing neighbors. Include nodes with no outgoing edges so isolated or terminal vertices are not lost.

import java.util.*;

class GraphBuilder {
    static Map<String, List<String>> buildDirected(List<String[]> edges) {
        Map<String, List<String>> graph = new HashMap<>();
        for (String[] edge : edges) {
            graph.computeIfAbsent(edge[0], key -> new ArrayList<>()).add(edge[1]);
            graph.computeIfAbsent(edge[1], key -> new ArrayList<>()); // Keep destination visible.
        }
        return graph;
    }
}

Hands-on drillTry It Yourself

Failure patternsCommon Mistakes to Avoid

• Confusing vertex identity with display label.
• Forgetting nodes with no outgoing edges.
• Using tree traversal when nodes can have multiple parents.
• Ignoring direction of edges.
• Not defining what edge weight means.

Execution guardrailQuick-Start Checklist

• Define vertices.
• Define edge meaning.
• Choose directed or undirected.
• Choose weighted or unweighted.
• Build adjacency list.
• Add visited tracking before traversal.

Recall drillKnowledge Check

VocabularyKey Terms

Next practiceFurther Reading

• Practice graph valid tree, clone graph, and route existence.
• Compare adjacency lists with matrices.
• Review graph modeling before BFS and DFS.