## Problem You are given directed currency conversions `[from, to, rate]`. Converting an amount across a path multiplies it by every edge rate. Return the largest conversion factor obtainable from `source` to `target`. The input guarantees there is no profitable cycle that is reachable from `source` and can still reach `target`; therefore the optimum is finite. ### Function Contract Implement `bestConversionRate(conversions, source, target)`. - Return `0.0` if `target` is unreachable. - Return `1.0` if `source == target`. - Parallel directed conversions may appear. ### Constraints & Assumptions - At most `500` distinct currencies and `10,000` conversions. - Every rate is finite and strictly positive. - Intermediate and final factors fit in a finite double. - Answers within `1e-9` relative or absolute error are accepted. ### Clarifying Questions to Ask - Are conversions directed? Yes; a reverse conversion exists only if explicitly listed. - Can rates exceed one? Yes. - Can cycles occur? Yes, but no source-to-target-relevant cycle has a product greater than one. - Is the objective based on a fixed input amount? The maximizing path is the same for any positive amount, so return the factor. ```hint Relax products Initialize the source factor to one and repeatedly relax `best[to]` with `best[from] * rate`. ``` ```hint Know when a max-heap is safe A Dijkstra-style finalization works when all rates are at most one. With rates above one, use a Bellman-Ford-style relaxation under the no-profitable-cycle guarantee. ``` ### Example ```text conversions = [ ["USD", "EUR", 0.9], ["EUR", "JPY", 160.0], ["USD", "JPY", 140.0] ] source = "USD" target = "JPY" output = 144.0 ``` The two-edge route has factor `0.9 * 160 = 144`, which beats the direct factor `140`. ### Evaluation Focus - Preserves direction and multiplies rates correctly. - Does not incorrectly finalize a node when later edges may increase its factor. - Stops early when an entire relaxation pass makes no change. - Handles unreachable currencies, parallel edges, and cycles with product at most one. ### Extensions to Discuss 1. How would logarithms turn products into additive edge weights? 2. How would you detect and report an unbounded profitable cycle? 3. Which algorithm is preferable when every rate is in `(0, 1]`?