Compute currency conversion via graph search

Q: Compute currency conversion via graph search

This is a Coding & Algorithms interview question from Uber for Machine Learning Engineer roles. View the full question and solution on PracHub.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

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.

Compute currency conversion via graph search

Comments (0)