Clarify and Solve Currency Conversion Queries with a Maximum-Amount Follow-up

# Clarify and Solve Currency Conversion Queries with a Maximum-Amount Follow-up You are given currency exchange rates and conversion queries. Each query supplies a source currency, a target currency, and a starting amount. Return the amount in the target currency, or `-1` when no conversion path exists. The follow-up asks for the maximum target amount obtainable and is expected to use backtracking. The report does not preserve several rules that determine whether that maximum is finite or even unique, so establish those rules before proposing an implementation. ### Clarifying Questions to Ask - Does a quoted rate create only the stated edge, or may its reciprocal also be used? - Are rates exact decimals, binary floating-point values, or rational numbers, and what rounding rule applies? - Is the base task guaranteed to have path-consistent rates, or which path should be chosen when two routes give different amounts? - For the maximum follow-up, may a route revisit a currency? If so, how should a profitable cycle be reported? - Is an empty route valid when source and target are equal? - Are parallel quotes possible, and are rates always positive? ### Part 1 — Answer conversion queries Model currencies and quoted conversions as a graph. Explain how to find a route for each query, multiply the rates along it, and return `-1` only after reachability has been exhausted under the agreed edge rules. #### What This Part Should Cover - A graph representation that matches directed or reciprocal quote semantics. - Per-query DFS or BFS with cycle prevention and a well-defined same-currency case. - A numeric representation and rounding policy appropriate to the supplied rates. - The additional contract needed if different reachable paths can produce different amounts. ### Part 2 — Find the maximum obtainable amount Extend the approach to compare all routes allowed by the interviewer. If routes must be simple, describe backtracking that removes a currency from the active path on return. If repeated conversions are allowed, explain how profitable cycles change the result and what sentinel or error the API should return for an unbounded maximum. #### What This Part Should Cover - Accumulating the product while exploring and retaining the best target value. - Path-local visitation rather than a global visited set when different routes must be compared. - Correct handling of unreachable targets, parallel edges, and source equal to target. - Complexity in terms of the number of routes explored, with memoization used only when its state is sufficient for the chosen cycle rules. ### What a Strong Answer Covers - Separates facts in the reported task from assumptions needed to make it executable. - Explains why integer-only arithmetic, reciprocal edges, and simple paths cannot be silently imposed. - Uses graph traversal for reachability and backtracking for the reported maximum-amount follow-up. - Identifies profitable-cycle behavior instead of returning an arbitrary finite value. - Gives concrete time and space bounds for the selected contract. ### Follow-up Questions 1. How would you detect that a profitable cycle is reachable from the source and can still reach the target? 2. What changes when thousands of queries reuse the same rate graph? 3. How would you make decimal results reproducible across programming languages?