How should I practice Maximum Currency Conversion with Arbitrage?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Google phone screen problems in FastPrep.

Is Maximum Currency Conversion with Arbitrage associated with Google?

FastPrep tags this as a Google phone screen coding practice problem when the problem catalog has that company and stage context.

Problem · Graph

Maximum Currency Conversion with Arbitrage

Learn this problem

● Hard

GoogleFULLTIMEPHONE SCREEN

See Google hiring insights

Problem statement

Each directed conversion edge i means that one unit of sources[i] converts to rates[i] units of targets[i]. Edges are directed; no reverse conversion exists unless it is listed.

Starting with amount units of source, return the maximum amount of target obtainable by applying edges any number of times.

Return -1.0 when target is unreachable from source.
Return -2.0 when a multiplicative-gain cycle is reachable from source and can still reach target, so the obtainable amount is unbounded.
Otherwise return the finite maximum amount. Using zero edges is allowed, so converting a currency to itself returns amount unless an applicable gain cycle makes it unbounded.

Function

maximumConversion(sources: String[], targets: String[], rates: double[], source: String, target: String, amount: double) → double

Examples

Example 1

sources = ["USD","CAD","USD","GBP"]targets = ["CAD","JPY","GBP","JPY"]rates = [1.3,100.0,0.8,150.0]source = "USD"target = "JPY"amount = 10.0return = 1300.0

The USD-CAD-JPY route multiplies by 130, producing 1300. The USD-GBP-JPY route multiplies by 120.

Example 2

sources = ["A","B","B"]targets = ["B","A","C"]rates = [2.0,0.6,1.0]source = "A"target = "C"amount = 1.0return = -2.0

The cycle A-B-A multiplies the amount by 1.2. It is reachable from A and can exit through B-C, so the target amount is unbounded.

Example 3

sources = ["A"]targets = ["B"]rates = [2.0]source = "B"target = "A"amount = 5.0return = -1.0

The only edge points from A to B, so A is unreachable from B.

Constraints

0 <= sources.length == targets.length == rates.length <= 5000
There are at most 300 distinct currency codes across the edges and query.
Each currency code contains 1 to 10 uppercase English letters.
0 < rates[i] <= 1000000 and 0 < amount <= 1000000000.
Any directed cycle's product is either at most 1 or differs from 1 by at least 10^-9.
Every finite answer is representable by a double.