Convert between currencies: A Sample Coding Interview Solution

The coding question

You get exchange rates as a string like 'USD:CAD:DHL:5,USD:GBP:FEDX:10' (from, to, method, rate). Parse it, then convert an amount from one currency to another. Then handle pairs with no direct rate by chaining through other currencies.

Ask a few questions first

Ask	What we'll assume
Is the format always four parts per rate?	Yes: from, to, method, rate, split by colons, with rates split by commas. Raise an error on anything else, or a rate that isn't a positive number.
Do rates work both ways?	Yes. If USD to CAD is 5, then CAD to USD is 1 / 5, using the same method.
What if two methods link the same pair?	Use the one that gives you more money, and return which method it was.
What should convert return?	The converted amount rounded to 2 places, plus the method used. For a chain, the list of methods. None if there's no way to get there.
In part 2, does the chain need to be the best rate?	Any chain is fine for now. Fewest hops is a nice default. Best rate is a follow-up.

A couple of examples

Input	Output
parse_rates('USD:CAD:DHL:5,USD:GBP:FEDX:10')	[('USD', 'CAD', 'DHL', 5.0), ('USD', 'GBP', 'FEDX', 10.0)]
Rates: 'USD:CAD:DHL:5,USD:GBP:FEDX:10,USD:CAD:UPS:4,GBP:EUR:DHL:2'. convert_direct(10, 'USD', 'CAD') and convert_direct(100, 'GBP', 'USD')	(50.0, 'DHL') and (10.0, 'FEDX')
Same rates. convert_direct(10, 'CAD', 'GBP'), then convert(10, 'CAD', 'GBP')	None, then (25.0, ['UPS', 'FEDX'])
Same rates. convert(1, 'CAD', 'EUR') and convert(5, 'USD', 'JPY')	(5.0, ['UPS', 'FEDX', 'DHL']) and None

Start with brute force

For part 2, try every chain of rates from the starting currency, recursively, and stop when you reach the target. Without remembering where you've been, you'll loop forever (USD to CAD to USD...). Even with that fixed, listing every possible chain blows up.

Cost: Exponential in the number of currencies in the worst case.

A better way

Parse the string once into a graph. Currencies are nodes, and each rate is an edge in both directions. Store it as a dictionary of dictionaries, so graph['USD']['CAD'] is a list of (rate, method) options. Part 1 is then a plain hash map lookup.

For part 2, run a breadth-first search from the source currency. When you reach a new currency, its rate is the rate to where you came from times that edge's rate, and its route is the methods so far plus this one. Each currency is visited once, and you stop as soon as you reach the target.

Watch the reverse edges. CAD to USD by DHL is 1 / 5 = 0.2, but by UPS it's 1 / 4 = 0.25, so going backwards the best method is the one with the lower forward rate.

Split the string on commas, then each piece on colons. Check there are four parts and a positive rate.
Build the graph, adding each rate and its reverse with the same method.
convert_direct: if there's an edge, take the best (rate, method) option and multiply.
convert: BFS from the source, keeping found[currency] = (rate from the source, methods used).
When you reach the target, return the amount and the methods. If the queue empties, return None.

The code

solution.pypython

from collections import defaultdict, deque


def parse_rates(text):
    # "USD:CAD:DHL:5,USD:GBP:FEDX:10" -> [(from, to, method, rate), ...]
    rates = []
    for chunk in text.split(","):
        chunk = chunk.strip()
        if not chunk:
            continue
        parts = [part.strip() for part in chunk.split(":")]
        if len(parts) != 4:
            raise ValueError("bad rate: " + chunk)
        src, dst, method, rate = parts
        rate = float(rate)
        if rate <= 0:
            raise ValueError("rate must be positive: " + chunk)
        rates.append((src, dst, method, rate))
    return rates


class Converter:
    def __init__(self, text):
        # graph[a][b] is a list of (rate, method). The reverse uses 1 / rate.
        self.graph = defaultdict(lambda: defaultdict(list))
        for src, dst, method, rate in parse_rates(text):
            self.graph[src][dst].append((rate, method))
            self.graph[dst][src].append((1 / rate, method))

    def best_edge(self, src, dst):
        # Several methods can link the same pair. Take the best rate.
        return max(self.graph[src][dst])

    # Part 1: direct rates only.
    def convert_direct(self, amount, src, dst):
        if src == dst:
            return round(amount, 2), None
        if dst not in self.graph.get(src, {}):
            return None
        rate, method = self.best_edge(src, dst)
        return round(amount * rate, 2), method

    # Part 2: chain through other currencies when there's no direct rate.
    def convert(self, amount, src, dst):
        if src == dst:
            return round(amount, 2), []
        # BFS from src. found[c] = (rate from src to c, methods used on the way)
        found = {src: (1.0, [])}
        queue = deque([src])
        while queue:
            current = queue.popleft()
            rate_so_far, route = found[current]
            for nxt in self.graph.get(current, {}):
                if nxt in found:
                    continue
                rate, method = self.best_edge(current, nxt)
                found[nxt] = (rate_so_far * rate, route + [method])
                if nxt == dst:
                    total, methods = found[nxt]
                    return round(amount * total, 2), methods
                queue.append(nxt)
        return None

	Cost	Why
Parse and build	O(R)	One pass over the R rates in the string
convert_direct	O(M)	Picking the best of the M methods for that pair, usually 1 or 2
convert	O(C + R)	BFS visits each currency and each rate at most once
Space	O(C + R)	The graph, plus the BFS queue and routes

Test it

Walk through one of the examples out loud, then check the cases that tend to break things:

Two methods for the same pair: USD to CAD uses DHL at 5, not UPS at 4.
Going backwards picks the other one: CAD to USD uses UPS, since 1 / 4 beats 1 / 5.
No path, like USD to JPY, returns None.
Converting a currency to itself returns the amount, even if it's not in the string.
Blank pieces, like a trailing comma, are skipped.
'USD:CAD:5' (three parts) or a rate of 0 raises an error while parsing.

Common mistakes

Splitting on ':' and indexing without checking there are four parts, so bad input crashes with an index error far from the cause.
Only storing rates in the direction given, so GBP to USD finds nothing.
Keeping one rate per pair and letting the second method overwrite the first.
Not tracking visited currencies, so the search loops forever.
Using floats for real money without mentioning it. Say you'd use Decimal.

Follow-up questions

How do you find the best rate, not just any chain?

You want the path with the biggest product. Take -log of each rate and it becomes a shortest path problem. Some weights are negative, so use Bellman-Ford.

What if a loop of trades makes money?

That's arbitrage, and in the -log graph it's a negative cycle. Bellman-Ford finds those too, so you can report them.

What if each method also has a fee?

Store the fee on the edge and apply it at each hop. A fixed fee means the best route depends on the amount, so you can't precompute one rate per pair any more.

How the time adds up

Minutes	What you're doing
0–5	Ask about the format and what to return
5–10	Examples, and plan the graph
10–20	Part 1: parsing and direct conversion
20–35	Part 2: BFS through other currencies
35–45	Test the examples and edge cases
45–60	Follow-ups: best rate and arbitrage

Key concepts used here

We wrote this sample solution ourselves. Practice Loop is independent and isn't affiliated with or endorsed by Stripe.