Evaluate Division
A game market lists exchange rates. equations[i] = [a, b] says one a is worth values[i] of b, so a / b = values[i]; no rate contradicts another. A query [c, d] asks how many d one c is worth, which is c / d. Chain rates together when you must, in either direction. Answer -1.0 when the rates do not settle a question: a name that appears in no equation, or two names that no chain of equations joins. A name over itself is 1.0 if it appears in some equation and -1.0 if it does not. Return one answer per query, in order. An equation may be repeated, and may pair a name with itself. Limits: 1 <= equations.length <= 1000, values.length == equations.length, 1 <= queries.length <= 1000, every name is 1 to 5 lowercase letters or digits, 0.05 <= values[i] <= 20.0, and every answer is -1.0 or lies between 0.001 and 1000. An answer within 1e-6 of the true one is accepted. Example: equations = [["gem","coin"],["coin","token"]], values = [4.0, 2.5] queries = [["gem","token"],["token","gem"],["gem","ruby"],["ruby","ruby"],["gem","gem"]] => [10.0, 0.1, -1.0, -1.0, 1.0]
You're given ratios between pairs of things, like one gem being worth four coins, and asked about ratios nobody wrote down. Interviewers love it because it hides a graph in plain sight: once names are nodes, every answer is a product along a path. The classic traps are the reverse direction and the name that never showed up, since dividing something by itself is only 1.0 when it exists. Expect up to 1,000 equations and 1,000 queries, with names of at most 5 characters.
Examples
You write
calc_equation(equations: List[List[str]], values: List[float], queries: List[List[str]])
Example 1
- Input
- equations = [["gem","coin"],["coin","token"]], values = [4.0,2.5], queries = [["gem","token"],["token","gem"],["coin","gem"],["gem","ruby"],["ruby","ruby"],["gem","gem"]]
- returns
- [10.0,0.1,0.25,-1.0,-1.0,1.0]
Example 2
- Input
- equations = [["a","b"]], values = [2.0], queries = [["a","z"],["z","a"],["z","y"]]
- returns
- [-1.0,-1.0,-1.0]
Save this for your laptop
The editor and Run need a bigger screen. The link opens Evaluate Division ready to code. It is free, and the editor needs no account.
The pattern behind it
Graphs
I reach for it when
- The input is edges, prerequisites or connections.
- You need cycles, an ordering or connected groups.
Say this before you type. Say whether the edges are directed, and which of the three jobs you are doing.
All 32 Graphs problemsBFS & DFS
I reach for it when
- You walk a grid, a graph or a tree and visit each cell once.
- The word shortest appears and every step costs the same.
Say this before you type. Say why breadth or depth fits, and exactly when a cell counts as visited.
All 52 BFS & DFS problems
Meet Coco
Coco is an AI study partner, not a person. She listens while you explain your code, asks what a line does and never hands you the fix. Sign in free to type with Coco, up to a daily limit, and to talk with her for one hour. After that, talking comes with the $79 pack. Anyone can open the editor and run their code.