Crack the Backend

Problem Statement

You are given a list of equations equations[i] = [A_i, B_i] and values values[i] meaning A_i / B_i = values[i]. Then queries queries[j] = [C_j, D_j]: return C_j / D_j if it can be determined, otherwise -1.0. All variables are non-empty strings. Assume no division by zero and that each equation has a unique value.

Key Observations

Weighted Union Find: For each variable we store its root and a weight (value of variable/root). When we find, we path-compress and update weight so weight[x] = value(x) / value(root). When we union(a, b, val) where a/b = val, we link root(a) to root(b) with the appropriate ratio so that a/b = val is preserved. For a query c/d: if c and d are in the same set, return weight[c]/weight[d]; else -1.0.

Approach

High-level: Map<String,String> root; Map<String,Double> weight. find(x): path compress and set weight[x] = weight[parent]. union(a, b, v): ra=find(a), rb=find(b); if ra!=rb then parent[ra]=rb, weight[ra]=vweight[b]/weight[a]. Query: if same root return weight[a]/weight[b] else -1.

Steps: For each equation (a, b, v): ensure a,b in structures; union(a,b,v). For each query (c,d): if either unknown return -1; if find(c)!=find(d) return -1; return weight.get(c)/weight.get(d);

Implementation

Java

Map<String, String> root = new HashMap<>();
Map<String, Double> weight = new HashMap<>();
void union(String a, String b, double v) {
    String ra = find(a), rb = find(b);

    if (ra.equals(rb)) {
        return;
    }

    root.put(ra, rb);
    weight.put(ra, weight.get(b) / weight.get(a) * v);
}

String find(String x) {

    if (!root.containsKey(x)) { root.put(x, x); weight.put(x, 1.0); return x; }
    if (root.get(x).equals(x)) {
        return x;
    }

    String r = find(root.get(x));
    weight.put(x, weight.get(x) * weight.get(root.get(x)));
    root.put(x, r);
    return r;
}

public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {

    for (int i = 0; i < equations.size(); i++)
    union(equations.get(i).get(0), equations.get(i).get(1), values[i]);
    double[] res = new double[queries.size()];

    for (int i = 0; i < queries.size(); i++) {
        String a = queries.get(i).get(0), b = queries.get(i).get(1);

        if (!root.containsKey(a) || !root.containsKey(b) || !find(a).equals(find(b)))
        res[i] = -1.0;
        else
        res[i] = weight.get(a) / weight.get(b);
    }

    return res;
}

Test Cases

Example 1

Input

equations = [["a","b"]], values = [2.0], query ["b","a"]

Expected

0.5

Explanation

b/a = 1/2.

Complexity Analysis

Time: O(n α(n)) ≈ O(n).
Space: O(n).

Follow-ups

Path compression + rank for optimal UF.