‹ DS&A interview · Socratic
DSA · Graph · #67

Evaluate Division

Module 43 · difficulty 3/5·⏱ 30:00starts on first keystroke

You are given `equations` (an array of variable pairs `[A, B]`) and `values` (a parallel array of numbers) such that `A / B == values[i]`. Given a list of `queries` `[C, D]`, return an array where the i-th element is the answer to `C / D`. If a single answer cannot be determined (an involved variable is unknown, or the two variables are not connected), the answer is `-1.0`. Variables are strings of lowercase letters and represent positive real numbers. No equation contradicts another, and division by zero does not occur. Implement `calcEquation(equations, values, queries)` returning an array of numbers.

Examples
  • equations = [["a","b"],["b","c"]], values = [2.0,3.0], queries = [["a","c"],["b","a"],["a","e"],["a","a"],["x","x"]] → [6.0,0.5,-1.0,1.0,-1.0] — a/c = (a/b)*(b/c) = 2*3 = 6. a/e: e is unknown -> -1. x/x: x never appears -> -1.
  • equations = [["a","b"],["b","c"],["bc","cd"]], values = [1.5,2.5,5.0], queries = [["a","c"],["c","b"],["bc","cd"],["cd","bc"]] → [3.75,0.4,5.0,0.2] — a/c = 1.5*2.5 = 3.75; c/b = 1/2.5 = 0.4; cd/bc = 1/5 = 0.2.
  • equations = [["a","b"]], values = [0.5], queries = [["a","b"],["b","a"],["a","c"],["x","y"]] → [0.5,2.0,-1.0,-1.0] — Disconnected or unknown variables yield -1.0.
Constraints
  • · 1 <= equations.length <= 20
  • · equations[i].length == 2
  • · 1 <= Ai.length, Bi.length <= 5
  • · values.length == equations.length
  • · 0.0 < values[i] <= 20.0
  • · 1 <= queries.length <= 20
  • · queries[i].length == 2
  • · Variables consist of lowercase English letters
Session phases
A · Clarify
B · Approach
C · Complexity
D · Edges
E · Code
F · Tradeoff
G · Score
Phase A — Clarify
Ask questions about input bounds, types, and edge constraints.
Ask the coach clarifying questions about the problem.
When you've covered this phase, advance to the next.