Answer a large batch of variable-ratio queries from division equations

Quick Overview

Given division equations between named variables and their values, answer a large batch of ratio queries, returning -1.0 whenever a ratio cannot be determined. It tests chaining ratios through shared variables, handling unknown and disconnected variables, and reusing work across many queries, the scale follow-up raised in the interview.

Answer a large batch of variable-ratio queries from division equations

Company: Amazon

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

You are given a list of equations between variables. Equation `i` is `equations[i] = [a, b]` together with a real number `values[i]`, and it states that `a / b = values[i]`. Every variable is a string that stands for an unknown positive real number. For each query `[c, d]` in `queries`, return the value of `c / d` if it can be determined from the equations, or `-1.0` if it cannot. In the interview, the base problem came first. The follow-up asked what changes when the function is called millions of times a day. This version models that follow-up: one call receives one set of equations and a large batch of queries. ### Function Signature ```python def evaluate_ratios(equations: list[list[str]], values: list[float], queries: list[list[str]]) -> list[float]: ``` ### Rules - An equation `a / b = v` may be used in either direction: it also states that `b / a = 1 / v`. - A ratio `c / d` can be determined when `c` and `d` are linked through a chain of one or more equations; its value is the product of the ratios along the chain. When several chains link the same two variables, they all give the same value, because the equations never contradict each other. - If `c` or `d` does not appear in any equation, the answer is `-1.0`, even when `c == d`. - If `c == d` and that variable appears in at least one equation, the answer is `1.0`. - If both variables appear in equations but no chain links them, the answer is `-1.0`. - Return one answer per query, in the order of `queries`. - Every determinable ratio is positive, so `-1.0` never collides with a real answer. A determinable answer is accepted when its relative error from the exact ratio is at most `1e-5`. The value `-1.0` must be returned exactly. ### Constraints - `1 <= len(equations) == len(values) <= 100000` - `1 <= len(queries) <= 100000` - `len(equations[i]) == 2` and `len(queries[j]) == 2` - Every variable name has 1 to 5 characters, each a lowercase English letter or a digit. - In each equation, `a != b`. - `0.001 <= values[i] <= 1000.0` - The equations are consistent: no two chains between the same pair of variables imply different ratios. - For any two variables linked by a chain, the ratio between them lies between `1e-9` and `1e9`, so no product along a chain overflows or underflows. - Query variables may be names that appear in no equation. ### Examples **Example 1** ```text Input: equations = [["x", "y"], ["y", "z"]] values = [4.0, 2.5] queries = [["x", "z"], ["z", "x"], ["y", "x"], ["x", "w"], ["y", "y"], ["w", "w"]] Output: [10.0, 0.1, 0.25, -1.0, 1.0, -1.0] ``` `x / z = (x / y) * (y / z) = 4.0 * 2.5 = 10.0`, and `z / x` is its reciprocal. `y / x` uses the first equation in reverse. `w` appears in no equation, so both queries that use it return `-1.0`, including `w / w`. **Example 2** ```text Input: equations = [["p", "q"], ["r", "s"], ["t", "q"]] values = [0.5, 8.0, 0.25] queries = [["p", "t"], ["t", "p"], ["p", "s"], ["s", "r"]] Output: [2.0, 0.5, -1.0, 0.125] ``` `p / t = (p / q) * (q / t) = 0.5 * 4.0 = 2.0`, using the third equation in reverse. `p` and `s` both appear in equations, but no chain links the group `{p, q, t}` to the group `{r, s}`, so `p / s` is `-1.0`. `s / r` is the reciprocal of `8.0`. ### Small Equation Variant Implement `Solution.calcEquation(equations, values, queries)`, returning one double per query in query order. As above, a name is defined only if it appears in an equation. Return exactly `-1.0` for an unknown name or disconnected pair, including an unknown name divided by itself; a defined name divided by itself gives `1.0`. The input is consistent and query evaluation never divides by zero. Use these separate source bounds: - `1 <= len(equations) == len(values) <= 20` and `1 <= len(queries) <= 20`. - Each equation and query has exactly two names. - Names have `1` to `5` characters, each a lowercase English letter or digit. - `0.0 < values[i] <= 20.0`. There is no extra positive lower bound. - An equation may use the same name twice; consistency then requires its value to be `1.0`. The large-batch limits, its `a != b` constraint, its lower bound on equation values, and its bound on every connected ratio do not apply to this small variant. #### Numeric Clarification For this written small variant, `values` contains finite positive IEEE 754 binary64 numbers, and the mathematical factors are their exact represented values. Consistency is interpreted for those values. Each determinable **requested** ratio is promised to round to a finite, nonzero binary64 number. This promise does not bound reciprocal factors, intermediate ratios, or answers to unrequested queries. Return the nearest binary64 value of a determinable exact ratio, using ties-to-even rounding. The large variant's relative-error rule remains unchanged for that variant; it is not imposed on unrounded small-variant ratios that may lie in the subnormal range. This clarification supplies a numeric convention where the source does not specify one, without imposing the large variant's range restrictions. ```text Input: equations = [["a","b"],["b","c"]] values = [2.0,3.0] queries = [["a","c"],["b","a"],["a","e"],["a","a"],["x","x"]] Output: [6.0,0.5,-1.0,1.0,-1.0] Input: equations = [["a","b"],["b","c"],["bc","cd"]] values = [1.5,2.5,5.0] queries = [["a","c"],["c","b"],["bc","cd"],["cd","bc"]] Output: [3.75,0.4,5.0,0.2] Input: equations = [["a","b"]] values = [0.5] queries = [["a","b"],["b","a"],["a","c"],["x","y"]] Output: [0.5,2.0,-1.0,-1.0] ``` ### Clarifying Questions to Ask - Which variant's batch size and numeric guarantee apply? - Does a repeated query refer to the same equation snapshot, or can equations change between calls? - Does a requested result need the bounded variant's relative accuracy or the small variant's final binary64 rounding convention? ### What a Strong Answer Covers - Ordered answers, correct direction of each ratio, and the distinction between undefined and disconnected variables. - Reuse of work across the large query batch. - Defined self-queries and unknown self-queries under both variants. - Numeric safety under the selected variant's guarantees, including unrepresentable intermediate ratios in the small variant. - Time and space bounds that account for numeric representation and batch size. ### Follow-up Questions - If the equations stay fixed across many calls, what work can be reused and what must be invalidated when they change? - How would the contract need to change if a requested ratio could round to zero or infinity?

Overview: Given division equations between named variables and their values, answer a large batch of ratio queries, returning -1.0 whenever a ratio cannot be determined. It tests chaining ratios through shared variables, handling unknown and disconnected variables, and reusing work across many queries, the scale follow-up raised in the interview.

Community answers

Answer by mail2sudatra

vector calcEquation(vector>& equations, vector& values, vector>& queries) { unordered_map mp; vector > ratios; vector res; int idx = 0; for(auto it: equations) { if(mp.find(it[0]) == mp.end()) mp[it[0]] = idx++; if(mp.find(it[1]) == mp.end()) mp[it[1]] = idx++; } int n = mp.size(); ratios.resize(n, vector (n, -1.0)); for(int i = 0; i < n; i++) ratios[i][i] = 1.0; for(int i = 0; i < equations.size(); i++) { ratios[mp[equations[i][0]]][mp[equations[i][1]]] = values[i]; ratios[mp[equations[i][1]]][mp[equations[i][0]]] = 1.0 / values[i]; } for(int k = 0; k < n; k++) { for(int i = 0; i < n; i++) { for(int j = 0; j < n; j++) { if(ratios[i][k] != -1.0 && ratios[k][j] != -1.0 && ratios[i][j] == -1.0) ratios[i][j] = ratios[i][k] * ratios[k][j]; } } } for(auto it: queries) { if(mp.find(it[0]) == mp.end() || mp.find(it[1]) == mp.end()) res.push_back(-1.0); else res.push_back(ratios[mp[it[0]]][mp[it[1]]]); } return res; }

Answer by charles.kuncheria

/** @param {string[][]} equations @param {number[]} values @param {string[][]} queries @returns {number[]} */ function evaluateRatios(equations, values, queries) { // Each neighbor entry [b, ratio] stores the value of a / b. const adjMap = new Map(); for (let i = 0; i < equations.length; i++) { const [left, right] = equations[i]; if (!adjMap.has(left)) adjMap.set(left, []); if (!adjMap.has(right)) adjMap.set(right, []); adjMap.get(left).push([right, values[i]]); adjMap.get(right).push([left, 1 / values[i]]); } function findRatio(start, target) { // Check existence first: an unknown variable divided by itself is -1. if (!adjMap.has(start) || !adjMap.has(target)) return -1.0; if (start === target) return 1.0; // Each queue entry stores [current variable, start / current]. const queue = [[start, 1.0]]; let head = 0; const visited = new Set([start]); while (head < queue.length) { const [current, ratio] = queue[head++]; if (current === target) return ratio; for (const [neighbor, edgeRatio] of adjMap.get(current)) { if (visited.has(neighbor)) continue; visited.add(neighbor); // (start / current) * (current / neighbor) = start / neighbor. queue.push([neighbor, ratio * edgeRatio]); } } return -1.0; // Both variables exist, but no path connects them. } return queries.map(([left, right]) => findRatio(left, right)); }
Amazon logo
Amazon
mediumSoftware EngineerTechnical ScreenCoding & Algorithms
19
0

You are given a list of equations between variables. Equation i is equations[i] = [a, b] together with a real number values[i], and it states that a / b = values[i]. Every variable is a string that stands for an unknown positive real number.

For each query [c, d] in queries, return the value of c / d if it can be determined from the equations, or -1.0 if it cannot.

In the interview, the base problem came first. The follow-up asked what changes when the function is called millions of times a day. This version models that follow-up: one call receives one set of equations and a large batch of queries.

Function Signature

def evaluate_ratios(equations: list[list[str]], values: list[float], queries: list[list[str]]) -> list[float]:

Rules

  • An equation a / b = v may be used in either direction: it also states that b / a = 1 / v .
  • A ratio c / d can be determined when c and d are linked through a chain of one or more equations; its value is the product of the ratios along the chain. When several chains link the same two variables, they all give the same value, because the equations never contradict each other.
  • If c or d does not appear in any equation, the answer is -1.0 , even when c == d .
  • If c == d and that variable appears in at least one equation, the answer is 1.0 .
  • If both variables appear in equations but no chain links them, the answer is -1.0 .
  • Return one answer per query, in the order of queries .
  • Every determinable ratio is positive, so -1.0 never collides with a real answer. A determinable answer is accepted when its relative error from the exact ratio is at most 1e-5 . The value -1.0 must be returned exactly.

Constraints

  • 1 <= len(equations) == len(values) <= 100000
  • 1 <= len(queries) <= 100000
  • len(equations[i]) == 2 and len(queries[j]) == 2
  • Every variable name has 1 to 5 characters, each a lowercase English letter or a digit.
  • In each equation, a != b .
  • 0.001 <= values[i] <= 1000.0
  • The equations are consistent: no two chains between the same pair of variables imply different ratios.
  • For any two variables linked by a chain, the ratio between them lies between 1e-9 and 1e9 , so no product along a chain overflows or underflows.
  • Query variables may be names that appear in no equation.

Examples

Example 1

Input:  equations = [["x", "y"], ["y", "z"]]
        values    = [4.0, 2.5]
        queries   = [["x", "z"], ["z", "x"], ["y", "x"], ["x", "w"], ["y", "y"], ["w", "w"]]
Output: [10.0, 0.1, 0.25, -1.0, 1.0, -1.0]

x / z = (x / y) * (y / z) = 4.0 * 2.5 = 10.0, and z / x is its reciprocal. y / x uses the first equation in reverse. w appears in no equation, so both queries that use it return -1.0, including w / w.

Example 2

Input:  equations = [["p", "q"], ["r", "s"], ["t", "q"]]
        values    = [0.5, 8.0, 0.25]
        queries   = [["p", "t"], ["t", "p"], ["p", "s"], ["s", "r"]]
Output: [2.0, 0.5, -1.0, 0.125]

p / t = (p / q) * (q / t) = 0.5 * 4.0 = 2.0, using the third equation in reverse. p and s both appear in equations, but no chain links the group {p, q, t} to the group {r, s}, so p / s is -1.0. s / r is the reciprocal of 8.0.

Small Equation Variant

Implement Solution.calcEquation(equations, values, queries), returning one double per query in query order. As above, a name is defined only if it appears in an equation. Return exactly -1.0 for an unknown name or disconnected pair, including an unknown name divided by itself; a defined name divided by itself gives 1.0. The input is consistent and query evaluation never divides by zero.

Use these separate source bounds:

  • 1 <= len(equations) == len(values) <= 20 and 1 <= len(queries) <= 20 .
  • Each equation and query has exactly two names.
  • Names have 1 to 5 characters, each a lowercase English letter or digit.
  • 0.0 < values[i] <= 20.0 . There is no extra positive lower bound.
  • An equation may use the same name twice; consistency then requires its value to be 1.0 .

The large-batch limits, its a != b constraint, its lower bound on equation values, and its bound on every connected ratio do not apply to this small variant.

Numeric Clarification

For this written small variant, values contains finite positive IEEE 754 binary64 numbers, and the mathematical factors are their exact represented values. Consistency is interpreted for those values. Each determinable requested ratio is promised to round to a finite, nonzero binary64 number. This promise does not bound reciprocal factors, intermediate ratios, or answers to unrequested queries.

Return the nearest binary64 value of a determinable exact ratio, using ties-to-even rounding. The large variant's relative-error rule remains unchanged for that variant; it is not imposed on unrounded small-variant ratios that may lie in the subnormal range. This clarification supplies a numeric convention where the source does not specify one, without imposing the large variant's range restrictions.

Input:  equations = [["a","b"],["b","c"]]
        values = [2.0,3.0]
        queries = [["a","c"],["b","a"],["a","e"],["a","a"],["x","x"]]
Output: [6.0,0.5,-1.0,1.0,-1.0]

Input:  equations = [["a","b"],["b","c"],["bc","cd"]]
        values = [1.5,2.5,5.0]
        queries = [["a","c"],["c","b"],["bc","cd"],["cd","bc"]]
Output: [3.75,0.4,5.0,0.2]

Input:  equations = [["a","b"]]
        values = [0.5]
        queries = [["a","b"],["b","a"],["a","c"],["x","y"]]
Output: [0.5,2.0,-1.0,-1.0]

Clarifying Questions to Ask Guidance

  • Which variant's batch size and numeric guarantee apply?
  • Does a repeated query refer to the same equation snapshot, or can equations change between calls?
  • Does a requested result need the bounded variant's relative accuracy or the small variant's final binary64 rounding convention?

What a Strong Answer Covers Guidance

  • Ordered answers, correct direction of each ratio, and the distinction between undefined and disconnected variables.
  • Reuse of work across the large query batch.
  • Defined self-queries and unknown self-queries under both variants.
  • Numeric safety under the selected variant's guarantees, including unrepresentable intermediate ratios in the small variant.
  • Time and space bounds that account for numeric representation and batch size.

Follow-up Questions Guidance

  • If the equations stay fixed across many calls, what work can be reused and what must be invalidated when they change?
  • How would the contract need to change if a requested ratio could round to zero or infinity?