The O(n) Club: Evaluate Division – Connect the Dots, Multiply the Drama

The O(n) Club: Evaluate Division – Connect the Dots, Multiply the Drama

⚡ TL;DR

Take some equations like a / b = 2.0, make a directed, weighted graph. Each query is a scavenger hunt: can you chain-multiply weights from start to end? If not, hand back a -1 and pour some coffee.

// Classic DFS for division - in Java
double dfs(String curr, String target, Set<String> visited) {
    if (!graph.containsKey(curr) || !graph.containsKey(target)) return -1.0;
    if (curr.equals(target)) return 1.0;
    visited.add(curr);
    for (Pair n : graph.get(curr)) {
        if (visited.contains(n.key)) continue;
        double prod = dfs(n.key, target, visited);
        if (prod != -1.0) return n.value * prod;
    }
    return -1.0;
}

🧠 How Devs Usually Mess This Up

Look, nothing says “fresh grad” like trying to use Dijkstra because the word “graph” appeared. This problem doesn’t care about shortest paths or minimum anything. The main mistakes: only setting a → b and forgetting b → a (seriously, would you want a unicycle with half a wheel?), believing one true path exists (reality: cycles happen), or merrily answering with junk when the variable wasn’t even in any equation. Bonus whoops: treating it like a currency desk but using Monopoly money.

🔍 What’s Actually Going On

You’re basically the world’s most underpaid currency exchanger. The equations are exchange rates; the queries are customers wanting to convert fantasy money like a to c. The graph is your currency network: each node is a variable, edges are routes with “multiply by this” signs plastered on them. Need a / c? Start at a, walk the graph, multiply rates on the path – any path – and if you can’t get there, hand the customer a solid -1 and a coupon for real math lessons.

🛠️ PseudoCode

• Build a graph:
  For each equation, add both directions: a → b with value, b → a with 1/value.
  

  // E.g.: a/b = 2.0
  addEdge(a, b, 2.0); addEdge(b, a, 0.5);

• Check queries:
  If either var doesn’t exist, or no path, return -1.
  

  if (!graph.containsKey(start) || !graph.containsKey(end)) return -1.0;

• If start == end:
  Return 1.0. (Self-awareness bonus.)
• DFS it:
  Walk from start to end. If already visited, skip (avoid cycles). Multiply weights along the way. If you hit a dead end, try another neighbor.
  

  for (Pair neighbor : graph.get(curr)) {
      if (!visited.contains(neighbor.key)) {
          double res = dfs(neighbor.key, end, visited);
          if (res != -1.0) return neighbor.value * res;
      }
  }

• No path? Return -1:
  The graph giveth, and sometimes it taketh away.

💻 The Code

import java.util.*;
 class EvaluateDivision {
    Map<String, List<Pair>> graph = new HashMap<>();
    static class Pair {
        String key; double value;
        Pair(String k, double v) { key = k; value = v; }
    }
    public double[] calcEquation(List<List<String>> eq, double[] vals, List<List<String>> queries) {
        for (int i = 0; i < eq.size(); i++) {
            String a = eq.get(i).get(0), b = eq.get(i).get(1);
            double v = vals[i];
            graph.putIfAbsent(a, new ArrayList<>());
            graph.putIfAbsent(b, new ArrayList<>());
            graph.get(a).add(new Pair(b, v));
            graph.get(b).add(new Pair(a, 1.0 / v));
        }
        double[] out = new double[queries.size()];
        for (int i = 0; i < queries.size(); i++) {
            String start = queries.get(i).get(0), end = queries.get(i).get(1);
            Set<String> visited = new HashSet<>();
            out[i] = dfs(start, end, visited);
        }
        return out;
    }
    double dfs(String curr, String target, Set<String> visited) {
        if (!graph.containsKey(curr) || !graph.containsKey(target)) return -1.0;
        if (curr.equals(target)) return 1.0;
        visited.add(curr);
        for (Pair n : graph.get(curr)) {
            if (!visited.contains(n.key)) {
                double p = dfs(n.key, target, visited);
                if (p != -1.0) return n.value * p;
            }
        }
        return -1.0;
    }
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Missing the reverse edge: Like coffee without caffeine – it just won’t work.
• Querying mystery variables: Variables not in any equation? -1, not a stack trace.
• Cycles: No biggie, DFS with visited set keeps you from getting lost in time.
• Space: Okay, adjacency lists per node, standard stuff. Not a memory apocalypse.
• Time: Each query could, in worst cases, scan the whole graph. Usually, it’s snappy unless your friend supplies you a city-sized test case.
• Self-loops (a/a): That’s always 1. Unless you’re feeling philosophical. The program isn’t.

🧠 Interviewer Brain-Tattoo

“If the path exists, multiply your way home. If not, take the L and return -1. And never forget: every equation is just another excuse for a graph!”