How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a hard difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Instacart.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Instacart during technical interviews.

Evaluate query ratios from equations | Instacart Coding Question

Evaluate query ratios from equations

Company: Instacart

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Technical Screen

You are given equations of the form `A / B = value` where `A` and `B` are variable names (strings) and `value` is a positive real number. You also receive queries of the form `X / Y = ?`. For each query, return the computed ratio if it can be derived from the known equations; otherwise return `-1.0`. **Input** - `equations`: list of pairs `[Ai, Bi]` - `values`: list of doubles where `values[i]` corresponds to `Ai / Bi` - `queries`: list of pairs `[Xj, Yj]` **Output** - Array of doubles where each element is the answer for the corresponding query. **Notes / Constraints** - Variables not appearing in any equation make related queries impossible. - You may assume there are no contradictions. - Aim for a graph + DFS/BFS solution. **Example** - `equations = [["a","b"],["b","c"]]`, `values = [2.0, 3.0]` - `queries = [["a","c"],["c","a"],["a","e"],["a","a"],["x","x"]]` - Output: `[6.0, 1/6, -1.0, 1.0, -1.0]`

Quick Answer: This question evaluates a candidate's skill in modeling variable ratios as relational structures, reasoning about transitive numeric relationships, and handling disconnected variables and edge cases.

You are given equations of the form `A / B = value` where `A` and `B` are variable names (strings) and `value` is a positive real number, plus a parallel `values` array. You also receive `queries` of the form `X / Y = ?`. For each query, return the computed ratio if it can be derived by chaining the known equations; otherwise return `-1.0`. **Input** - `equations`: list of pairs `[Ai, Bi]` - `values`: list of doubles where `values[i]` is `Ai / Bi` - `queries`: list of pairs `[Xj, Yj]` **Output** - Array of doubles, one answer per query. **Rules** - A query over a variable that never appears in any equation is impossible -> `-1.0` (this includes `["x","x"]` when `x` is unknown). - `X / X = 1.0` only when `X` appears in some equation. - No contradictions are present in the input. **Approach**: model variables as nodes and each equation as two weighted directed edges (`A->B` with weight `value`, `B->A` with weight `1/value`). Each query is then a path search (DFS/BFS) multiplying edge weights from `X` to `Y`.

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
1 <= Xj.length, Yj.length <= 5
Ai, Bi, Xj, Yj consist of lowercase English letters and digits
No contradictions exist among the equations

Examples

Input: ([["a","b"],["b","c"]], [2.0, 3.0], [["a","c"],["c","a"],["a","e"],["a","a"],["x","x"]])

Expected Output: [6.0, 0.16666666666666666, -1.0, 1.0, -1.0]

Explanation: a/b=2, b/c=3 so a/c=6. c/a=1/6. 'e' is unknown -> -1.0. a/a=1 (a is known). 'x' is unknown so x/x -> -1.0.

Input: ([["a","b"],["b","c"],["bc","cd"]], [1.5, 2.5, 5.0], [["a","c"],["c","b"],["bc","cd"],["cd","bc"]])

Expected Output: [3.75, 0.4, 5.0, 0.2]

Explanation: Two disconnected components. a/c = 1.5*2.5 = 3.75; c/b = 1/2.5 = 0.4. The {bc,cd} component is separate: bc/cd = 5.0, cd/bc = 0.2.

Input: ([["x1","x2"],["x2","x3"],["x3","x4"],["x4","x5"]], [3.0, 4.0, 5.0, 6.0], [["x1","x5"],["x5","x2"],["x2","x4"],["x2","x2"],["x9","x9"]])

Expected Output: [360.0, 0.008333333333333333, 20.0, 1.0, -1.0]

Explanation: Long chain. x1/x5 = 3*4*5*6 = 360. x5/x2 = 1/(4*5*6) = 0.008333... x2/x4 = 4*5 = 20. x2/x2 = 1. x9 is unknown -> -1.0.

Input: ([], [], [["a","a"],["a","b"]])

Expected Output: [-1.0, -1.0]

Explanation: Edge case: no equations at all. Every variable is unknown, so even a/a returns -1.0.

Input: ([["a","b"]], [0.5], [["a","b"],["b","a"],["a","a"],["b","b"]])

Expected Output: [0.5, 2.0, 1.0, 1.0]

Explanation: Single fractional equation. a/b = 0.5, b/a = 1/0.5 = 2.0, and both self-queries a/a and b/b are 1.0 since both are known.

Hints

Build a graph: each variable is a node. For equation A / B = v, add a directed edge A -> B with weight v and B -> A with weight 1/v.
A query X / Y is the product of edge weights along any path from X to Y. Use DFS or BFS, multiplying weights as you traverse.
Track visited nodes to avoid cycles. If either X or Y never appeared in an equation, immediately return -1.0 (this also handles X / X where X is unknown).
When X == Y and X is a known variable, the answer is 1.0 without any traversal.

Quick Overview

This question evaluates a candidate's skill in modeling variable ratios as relational structures, reasoning about transitive numeric relationships, and handling disconnected variables and edge cases.