Currency Conversion via Exchange Rate Graph Coding / DSA Interview
Given a list of direct exchange rates, find the effective conversion rate between any two currencies by multiplying rates along a path in a directed graph.
1. Problem Statement
You are building a currency exchange system. You receive a list of direct exchange rates, each described as (from_currency, to_currency, rate), meaning 1 unit of from_currency buys `rate` units of to_currency. Design and implement a system that: 1. Ingests the list of exchange rates. 2. Answers queries: given a source currency and a target currency, return the effective conversion rate (or indicate that conversion is not possible). Assume inverse rates are implied: if A→B = r, then B→A = 1/r. Start with any clarifying questions.
2. Live Coding Format
Work in the provided coding workspace while explaining your decisions to the live interviewer. Validation may use inline tests, examples, comments, or a verbal walkthrough.
3. Key Focus Areas
- 1Graph construction from rate pairs
- 2Implicit inverse edges (A→B at rate r implies B→A at rate 1/r)
- 3Path search: BFS or DFS with visited set
- 4Path product computation
- 5Disconnected currencies: no-path sentinel
- 6Cycle detection and numeric precision discussion
4. What Strong Candidates Should Demonstrate
- ✓Model exchange rates as a directed weighted graph with implicit inverse edges.
- ✓Find a conversion path using BFS or DFS and compute the path product.
- ✓Handle disconnected currencies (no path) and self-conversions.
- ✓Identify and discuss the numerical instability caused by chained floating-point products.
Want interactive feedback?
Practice this problem in the live coding workspace while the interviewer probes your clarification, implementation, trade-offs, and validation.
Start Interview