Q1 - Stripe Currency Conversion Problem (~3 Parts)

Part 1: Direct Currency Conversion (~10 minutes)

You are given a string representing currency exchange rates formatted as follows:

Currency1:Currency2:Rate,...

This indicates that 1 unit of Currency1 equals Rate units of Currency2. Multiple exchange rates are separated by commas (,). Exchange rates are bidirectional—meaning if "USD:CAD:1.3" is given, then:

• 1 USD = 1.3 CAD
• 1 CAD = 1 / 1.3 USD

Your task is to implement a function that takes the input string, a source currency (from_currency), a target currency (to_currency), and an amount of the source currency. It should return the converted amount rounded to exactly two decimal places. If a direct conversion rate doesn't exist, return -1.

Input:
input_str = "USD:CAD:1.3,EUR:USD:1.1,GBP:EUR:1.15"
from_currency = "USD"
to_currency = "CAD"
amount = 100.0

Output: 130.0

Explanation: 1 USD = 1.3 CAD, so 100 USD = 130 CAD

Input:
input_str = "USD:CAD:1.3,EUR:USD:1.1"
from_currency = "USD"
to_currency = "GBP"
amount = 100.0

Output: -1

Explanation: No direct conversion exists between USD and GBP

Solution - Part 1

The key insight is to build a bidirectional mapping of currency pairs to their exchange rates. For each given rate, we store both directions: the original rate and its reciprocal.

from collections import defaultdict

def convert_currency(input_str: str, from_currency: str, to_currency: str, amount: float) -> float:
    currency_exchanges = input_str.split(",")
    graph = {}
    
    # Build bidirectional exchange rate mapping
    for exchange in currency_exchanges:
        curr_1, curr_2, rate = exchange.split(":")
        rate_float = float(rate.strip())
        
        # Store both directions
        graph[(curr_1.strip(), curr_2.strip())] = rate_float
        graph[(curr_2.strip(), curr_1.strip())] = 1.0 / rate_float

    # Check if direct conversion exists
    if (from_currency, to_currency) not in graph:
        return -1

    return round(amount * graph[(from_currency, to_currency)], 2)

Complexity Analysis

• Time Complexity: O(n), where n is the number of currency exchange pairs.
• Space Complexity: O(n) for storing the bidirectional graph.

Part 2: Finding Any Conversion Path (~20 minutes)

Now we extend the solution to support multi-hop conversions where intermediate currencies might be needed. The function should return a dictionary containing the conversion route, effective rate, and final converted amount.

Input: 
input_str = "USD:CAD:1.3,AUD:CAD:0.74"
from_currency = "USD"
to_currency = "AUD"
amount = 100.0

Output:
{
'route': 'USD -> CAD -> AUD',
'rate': 1.76,
'converted_value': 176.0
}

Explanation:
USD -> CAD: multiply by 1.3
CAD -> AUD: multiply by 1/0.74 ≈ 1.35
Total rate: 1.3 x 1.35 ≈ 1.76

Solution - Part 2

We use Depth-First Search (DFS) to explore all possible paths from the source currency to the target currency. The algorithm maintains the current path and accumulated rate, backtracking when necessary.

from collections import defaultdict

def find_conversion_path(input_str: str, from_currency: str, to_currency: str, amount: float) -> dict:
    currency_exchanges = input_str.split(",")
    graph = defaultdict(list)
    
    # Build adjacency list representation
    for exchange in currency_exchanges:
        curr_1, curr_2, rate = exchange.strip().split(":")
        rate_float = float(rate)
        graph[curr_1].append((curr_2, rate_float))
        graph[curr_2].append((curr_1, 1.0 / rate_float))

    currency_path = []
    rate = 1
    visited = set()
    
    def dfs(src_currency, ex_rate=1.0) -> bool:
        nonlocal rate
        visited.add(src_currency)
        currency_path.append(src_currency)
        rate *= ex_rate

        if src_currency == to_currency:
            return True

        for nbr_currency, nbr_rate in graph[src_currency]:
            if nbr_currency not in visited:
                if dfs(nbr_currency, nbr_rate):
                    return True

        # Backtrack: revert state
        visited.remove(src_currency)
        currency_path.pop()
        rate /= ex_rate
        return False

    if not dfs(from_currency):
        return {'route': 'No available conversion', 'rate': -1, 'converted_value': -1}

    return {
        'route': " -> ".join(currency_path),
        'rate': round(rate, 2),
        'converted_value': round(amount * rate, 2)
    }

Complexity Analysis

• Time Complexity: O(V + E), where V is the number of currencies and E is the number of exchange pairs.
• Space Complexity: O(V) for the recursion stack and visited set.

Part 3: Shortest Conversion Path (~25 minutes)

The final part optimizes the solution to find the shortest conversion path using Breadth-First Search (BFS), which guarantees the minimum number of currency hops.

Think of this like finding the shortest route on a subway map. You want to get from Station A to Station Z with the fewest transfers possible. There might be multiple routes:

• Route 1: A → B → C → D → Z (4 transfers)
• Route 2: A → X → Z (2 transfers) ← Shortest!

Similarly with currencies, you want the path with fewest conversion steps to minimize fees and reduce compounding errors.

Input: 
input_str = "USD:EUR:0.85,EUR:GBP:0.87,USD:CAD:1.3,CAD:GBP:0.58,USD:JPY:110,JPY:GBP:0.0065"
from_currency = "USD"
to_currency = "GBP"
amount = 100.0

Available Paths:

Path 1: USD → EUR → GBP (2 hops, rate ≈ 0.74)
Path 2: USD → CAD → GBP (2 hops, rate ≈ 0.75)
Path 3: USD → JPY → GBP (2 hops, rate ≈ 0.72)

BFS Output (shortest in terms of hops):
{
'route': 'USD -> EUR -> GBP',
'rate': 0.74,
'converted_value': 74.0
}

Explanation: All paths have 2 hops, but BFS finds the first valid shortest path.

Input:
input_str = "USD:EUR:0.85,EUR:GBP:0.87,USD:CAD:1.3,CAD:AUD:1.1,AUD:NZD:1.05,NZD:GBP:0.5"
from_currency = "USD"
to_currency = "GBP"
amount = 100.0

Available Paths:
Path 1: USD → EUR → GBP (2 hops)
Path 2: USD → CAD → AUD → NZD → GBP (4 hops)

BFS Output (guaranteed shortest):
{
'route': 'USD -> EUR -> GBP',
'rate': 0.74,
'converted_value': 74.0
}

Explanation: BFS explores level by level, finding 2-hop path before longer ones.

Solution - Part 3

We use BFS to explore currencies level by level, ensuring we find the path with the minimum number of intermediate conversions. We track the parent and accumulated rate for each discovered currency to reconstruct the optimal path.

Key Insight: BFS explores all 1-hop paths first, then all 2-hop paths, then 3-hop paths, etc. This guarantees the first path found to the destination is the shortest possible.

from collections import defaultdict, deque

def find_shortest_conversion_path(input_str: str, from_currency: str, to_currency: str, amount: float) -> dict:
    exchanges = input_str.split(",")
    graph = defaultdict(list)
    
    # Build adjacency list representation
    for group in exchanges:
        curr_1, curr_2, rate = group.split(":")
        rate_float = float(rate.strip())
        graph[curr_1.strip()].append((curr_2.strip(), rate_float))
        graph[curr_2.strip()].append((curr_1.strip(), 1.0 / rate_float))

    # BFS to find shortest path
    queue = deque([(from_currency, 1.0)])
    discovered_from = {from_currency: (None, 1.0)}
    
    while queue:
        currency, rate = queue.popleft()
        
        if currency == to_currency:
            break
            
        for nbr_currency, nbr_rate in graph[currency]:
            if nbr_currency not in discovered_from:
                discovered_from[nbr_currency] = (currency, rate * nbr_rate)
                queue.append((nbr_currency, rate * nbr_rate))

    # Check if path exists
    if to_currency not in discovered_from:
        return {'route': 'No available conversion', 'rate': -1, 'converted_value': -1}

    # Reconstruct path
    path = []
    currency = to_currency
    while currency:
        path.append(currency)
        currency = discovered_from[currency][0]

    return {
        'route': ' -> '.join(reversed(path)),
        'rate': round(discovered_from[to_currency][1], 2),
        'converted_value': round(discovered_from[to_currency][1] * amount, 2)
    }

Complexity Analysis

• Time Complexity: O(V + E), where V is the number of currencies and E is the number of exchange pairs. BFS visits each currency at most once and explores each exchange rate at most once.
• Space Complexity: O(V) for the queue, discovered currencies map, and path reconstruction. In the worst case, we might need to store information for all currencies.

Final Notes

Alright, let's talk real talk about this Stripe question - we've been tracking this one and it's become their go-to for testing candidates on graph algorithms and financial systems thinking. Here's what you need to know (very important for Stripe interviews):

1. The Three-Part Trap: Look, Stripe loves this format because it weeds people out fast. Part 1 seems easy (direct conversion), Part 2 gets you thinking (pathfinding), but Part 3 is where they separate the wheat from the chaff. We've seen candidates nail Parts 1 and 2 in 30 minutes, feel confident, then completely bomb Part 3 and get rejected. But here's the kicker - if you can push through and solve all three parts, you're basically guaranteed to move forward. It's like their litmus test.

2. The Novel-Length Problem Descriptions: Stripe purposely dumps these massive walls of text on you - it's not an accident. They want to see if you can cut through the fluff about "global payments infrastructure" and "seamless currency conversion" to get to the actual algorithmic meat.

3. You're On Your Own: Here's something most people don't realize - Stripe interviewers are notorious for being hands-off during the coding portion. Don't expect them to be your coding buddy or give you hints when you're stuck. They'll literally be checking their emails or reviewing other candidates while you're working. They only care about one thing: does your code work and pass all their test cases? That's it. No partial credit for "good effort" or "right approach but small bug." It's binary - working solution or not.

The bottom line? Stripe loves to claim their interviews aren't just "LeetCode grinding," but let's be honest - this is classic graph traversal (DFS/BFS) wrapped in fancy financial jargon and buried under paragraphs of payment processing fluff. Strip away all the currency conversion storytelling, and you're left with the same algorithmic patterns you'd find in any standard coding interview.