Compute currency conversion via graph search
Overview
This question evaluates graph modeling and pathfinding with weighted edges, numerical reasoning about multiplicative rates and floating-point precision, and the ability to analyze algorithmic time and space complexity.
Given a list of currency pairs, e.g., [('USD','CAD'), ('CAD','EUR'), ...], and a parallel list of conversion ratios [1.1, 1.2, ...] where ratio r means 1 unit of the first currency converts to r units of the second, implement a function rate(src, dst) that returns the conversion ratio from src to dst, or -1 if no path exists. Specify your data structures, the search algorithm (e.g., build a directed graph and use DFS/BFS to find a path while multiplying edge weights), and analyze time and space complexity. Follow-up: if conversions are directional and not reciprocal, compute the best achievable rate from src to dst. Explain how to model this as a weighted directed graph and select an appropriate shortest-path algorithm (e.g., transform multiplicative weights with -log and use Dijkstra), and discuss handling cycles/arbitrage and floating-point precision.