Graph Real-Life Problems

What is this?

The trickiest part of many problems isn't the algorithm — it's noticing there's a graph hiding inside in the first place. "What's the exchange rate from dollars to pounds?" doesn't sound like a graph until you realize currencies are dots and exchange rates are the connecting lines. This chapter trains the single most valuable reflex: look at a messy real-world question, name what the dots are and what the lines mean, and watch a familiar graph technique suddenly fit.

💡 Fun fact: currency markets really are graphs, and a profitable loop in them has a name — arbitrage. If converting dollars to euros to yen and back to dollars leaves you with more than you started, you've found a "negative cycle," and high-frequency trading firms hunt for these loops with the very same graph algorithms taught in this chapter.

🔓 The problem in this chapter is free. Sign in with Google or Microsoft to start solving.

The one-line idea: a surprising number of "real" problems — currency conversion, service dependencies, social circles, package installs — are secretly graph problems the moment you name what the nodes are and what the edges mean. The hard part is almost never the algorithm; it's the modeling step that turns a messy domain into nodes, edges, and a known graph routine.

1. The skill this chapter teaches

You already know the graph algorithms — traversal, shortest path, union-find, topological sort, cycle detection. This chapter is about the step before them: recognizing a graph hiding inside a problem that doesn't mention graphs at all. An interviewer rarely says "build a graph." They say "given exchange rates, answer cross-rate queries" or "given who-follows-whom, count the communities." Your job is to translate.

The translation is mechanical once you trust it: pick the entities (nodes), pick the relationships (edges), decide direction and weight, and a standard algorithm drops in.

⚠️ The beginner trap is jumping straight to code on the literal data shape (a list of equations, a matrix of follows) and missing that it's a graph. Name the nodes and edges first — the algorithm usually becomes obvious right after.

2. What "modeling a real problem as a graph" really means

Every modeling exercise is the same substitution. You have entities and relationships; you rename them:

Once the rename is done, the question "what is a/c?" becomes "product of weights along a path a → c", "how many friend circles?" becomes "number of connected components", and "valid build order?" becomes "topological sort." Same five algorithms, dressed in different clothes.

3. Where you'll actually meet this

Graph modeling is a daily reflex in production systems, not just interviews:

• Distributed systems. A microservice dependency graph (who calls whom) drives deploy ordering, blast-radius analysis, and cycle detection (a dependency loop is a deadlock waiting to happen). Conversion services for units or currencies resolve unseen ratios by path product.
• Finance. Currencies are nodes, quoted rates are weighted edges; cross-rates are path products and arbitrage is a profitable cycle. Credit exposures between institutions form a contagion graph.
• Networking. Routers are nodes, links (with latency/bandwidth) are weighted edges; routing is shortest path.
• Build systems & package managers. Packages are nodes, "depends-on" are directed edges; install order is a topological sort, and a cycle is a hard error.
• Social & recommendation. Users and follows/friendships form graphs; communities are connected components or clusters.

If a problem talks about relationships, connections, dependencies, conversions, or networks, reach for a graph.

4. The modeling toolkit

A five-question checklist turns any relationship problem into a solved one:

1. What are the nodes? The atomic entities — variables, currencies, services, people, tasks.
2. What are the edges? The pairwise relationships — equations, rates, follows, dependencies.
3. Directed or undirected? Asymmetric relationship (a follows b, a/b) → directed. Symmetric (friendship, road) → undirected. Tip: a "reverse" often still exists with a transformed weight — a/b = k implies b/a = 1/k.
4. Weighted or unweighted? Is there a number on the edge (rate, cost, latency)? Weighted. Just connectivity? Unweighted.
5. Which algorithm does the question map to?
   • reachability / components / "is it connected" → DFS/BFS / Union-Find
   • "best / cheapest / shortest" → shortest path (BFS, Dijkstra)
   • "valid ordering / dependencies" → topological sort
   • "product/sum along a path", "cross-rate" → weighted traversal
   • "is there a loop / arbitrage / deadlock" → cycle detection

5. A 30-second worked example (model a conversion)

"USD/EUR = 0.9, EUR/GBP = 0.85. What is USD/GBP?" — model it, don't algebra it:

Nodes named, edges weighted and reversible, query becomes a path product — and a plain DFS answers it. That rename-then-traverse reflex is the entire chapter in one move.

6. Problems in this chapter

▶ Evaluate Division

Given equations a/b = k and queries c/d, return each ratio or -1. Model: variables are nodes; each equation is a bidirectional weighted edge (a → b is k, b → a is 1/k); a query is the product of weights along a path. Unknown variable or no path ⇒ -1.
Pattern: weighted graph traversal (path product). Target: per-query O(V+E) DFS; or O(V³) Floyd–Warshall precompute / weighted Union-Find when queries ≫ variables, then O(1) per query.

7. Common pitfalls 🚫

• Forgetting the reverse edge / reciprocal weight. a/b = k is useless one-way — you must also add b → a with 1/k, or cm/km and every reverse query silently fails.
• Missing nodes treated as reachable. If a query names a variable that never appeared in any equation, the answer is -1. Check membership before searching.
• Confusing disconnected with unknown. Both return -1, but for different reasons (no path vs. not a node) — and your code must handle each.
• Wrong direction. Modeling an asymmetric relationship (follows, depends-on, division) as undirected quietly corrupts answers.
• Picking the wrong algorithm for the query load. One query? Just DFS. Thousands of queries on a handful of variables? Precompute all pairs once.

8. Key takeaways

1. Model first, algorithm second. Name the nodes and edges; the standard routine almost always reveals itself afterward.
2. Direction and weight are decisions, not afterthoughts. Asymmetric → directed; numeric relationship → weighted; and watch for a reverse edge with a transformed weight.
3. Map the question to a known tool: components/reachability → DFS-BFS/Union-Find, cheapest → shortest path, ordering → topo sort, path product → weighted traversal, loops → cycle detection.
4. -1 (or "no answer") has two causes — unknown entity and disconnected entity — and both must be handled.
5. Why interviewers love this family: it tests the translation skill that real engineering runs on — seeing the graph inside conversion services, dependency managers, FX desks, and social platforms — far more than it tests memorized algorithms.