Evaluate Division
On this page
Problem statement
You know some exchange rates and must answer conversion queries. Each rate
(a, b, r)means one unit of currencyabuysrunits ofb(r > 0), and all rates are consistent with each other. For each query(x, y), return how many units ofyone unit ofxbuys, or-1.0if it can't be worked out from the known rates. A currency that appears in no rate is unknown, even when the query is(x, x).
This is LeetCode 399, Evaluate Division, where the rates are written as divisions a / b = r. Interviewers often ask it as currency conversion or unit conversion (meters, feet, inches), which is the same graph problem.
Example

rates: USD -> EUR 0.8, EUR -> GBP 0.5, USD -> JPY 150
queries: GBP -> JPY -> 375.0 # 2 * 1.25 * 150
EUR -> USD -> 1.25 # 1 / 0.8
USD -> GBP -> 0.4 # 0.8 * 0.5
USD -> CAD -> -1.0 # CAD is unknown
EUR -> EUR -> 1.0
CAD -> CAD -> -1.0 # unknown, even to itself
Constraints (assumed)
- Up to 10⁴ rates and 10⁴ queries.
- Currency names are strings; rates are positive floats.
- The rates never contradict each other.
What this question tests
- Turning a word problem into a weighted graph, including the reverse edge.
- A clean BFS or DFS that carries a running product.
- Spotting that many queries on a fixed graph can share one precomputation.
Questions to ask first
- Are the rates consistent? If two paths could give different answers, the problem changes. (Here: consistent.)
- What should a query on an unknown currency return? (Here:
-1.0, even for(x, x).) - How many queries compared with rates? Many queries favor precomputing.
- Can rates be zero or negative? (Here: no, so the reverse
1 / ris always defined.)
Try it yourself first
You have the full problem. Sketch your answer, then sign up free to read the complete walkthrough.
- The complete design, flow by flow, with pictures
- Deep dives into the hard parts
- What mid, senior and staff candidates are expected to say
- Full company question lists
Free forever. No card needed.