Q5 - Stripe Flight Routing & Cost Optimization Problem

Part 1: Direct Flight Cost Calculation (~10 minutes)

You are working on Stripe's international shipping infrastructure to optimize package delivery costs across different countries. You are given a string representing available flights between different locations formatted as follows:

Source:Destination:Airline:Cost,...

This indicates that a flight from Source to Destination via Airline costs Cost units. Multiple flights are separated by commas (,). Unlike currency conversion, flights are unidirectional, meaning if "UK:US:FedEx:4" is given, this only represents a flight from UK to US, not the reverse.

Your task is to implement a function that takes the input string, a source location, and a destination location. It should return the cost of the direct flight. If no direct flight exists, return -1.

Input:
input_str = "UK:US:FedEx:4,UK:FR:Jet1:2,US:UK:RyanAir:8,CA:UK:CanadaAir:8"
source = "UK"
destination = "US"

Output: 4

Explanation: Direct flight from UK to US via FedEx costs 4

Input:
input_str = "UK:US:FedEx:4,UK:FR:Jet1:2,US:UK:RyanAir:8,CA:UK:CanadaAir:8"
source = "US"
destination = "CA"

Output: -1

Explanation: No direct flight exists from US to CA

Solution - Part 1

The key insight is to build a direct mapping of source-destination pairs to their flight costs. For each given flight, we store the route as a tuple key with its associated cost.

Step-by-Step Approach

1. Parse the input string: Split the comma-separated flight data into individual flight records

2. Extract flight information: For each flight, parse the format Source:Destination:Airline:Cost

3. Build a lookup table: Create a hash map where the key is a (source, destination) pair and the value is the cost

4. Handle whitespace: Strip any extra whitespace from the parsed components to ensure clean data

5. Query the lookup table: Check if the requested route exists and return the cost, or -1 if not found

This approach transforms the problem into a simple hash table lookup, making retrieval very efficient.

# O(n) time | O(n) space
def get_flight_cost(input_str: str, source: str, destination: str) -> int:
    flights = input_str.split(",")
    flight_to_cost = {}
    
    # Build direct flight cost mapping
    for flight in flights:
        src, dst, airline, cost = flight.split(":")
        flight_to_cost[(src.strip(), dst.strip())] = int(cost.strip())
    
    # Return direct flight cost or -1 if not found
    return flight_to_cost.get((source, destination), -1)

Complexity Analysis

• Time Complexity: O(n), where n is the number of flights in the input string.
• Space Complexity: O(n) for storing the flight cost mapping.

Part 2: Finding Routes with Exactly One Stop (~15 minutes)

Now extend the solution to find flights with exactly one intermediate stop.

Input: 
input_str = "UK:FR:Jet1:2,FR:US:AmericanAir:6"
source = "UK"
destination = "US"

Output:
{
'route': 'UK -> FR -> US',
'method': 'Jet1 -> AmericanAir',
'cost': 8
}

Explanation:
UK -> FR: via Jet1 costs 2
FR -> US: via AmericanAir costs 6
Total cost: 2 + 6 = 8

Solution - Part 2

We iterate through all possible intermediate locations to find routes with exactly one stop. For each potential intermediate location, we check if both legs of the journey exist.

# O(n^2) time | O(n) space
def find_one_intermediary_route(input_str: str, source: str, destination: str) -> int:
    flights = input_str.split(",")
    flight_to_cost = {}
    
    # Build flight cost mapping
    for flight in flights:
        src, dest, airline, cost = flight.split(":")
        flight_to_cost[(src.strip(), dest.strip())] = int(cost.strip())
    
    # Check for direct flight first
    if (source, destination) in flight_to_cost:
        return flight_to_cost[(source, destination)]
    
    # Find cheapest one-hop route
    min_cost = float('inf')
    for (src, intermediate), cost1 in flight_to_cost.items():
        if src == source and (intermediate, destination) in flight_to_cost:
            cost2 = flight_to_cost[(intermediate, destination)]
            total_cost = cost1 + cost2
            min_cost = min(min_cost, total_cost)
    
    return min_cost if min_cost != float('inf') else -1

Complexity Analysis

• Time Complexity: O(n^2), in line with the implementation that iterates over flight mappings and checks potential one-hop combinations.
• Space Complexity: O(n) for storing the flight mappings.

Part 3: Finding Any Route Path (~25 minutes)

The final part requires finding any path from source to destination using Depth-First Search (DFS). The function should return the complete route, airlines used, and total cost.

Input:
input_str = "UK:FR:Jet1:2,FR:DE:Lufthansa:3,DE:US:Delta:5"
source = "UK"
destination = "US"

Output:
{
'route': 'UK -> FR -> DE -> US',
'method': 'Jet1 -> Lufthansa -> Delta',
'cost': 10
}

Explanation:
UK -> FR: via Jet1 costs 2
FR -> DE: via Lufthansa costs 3  
DE -> US: via Delta costs 5
Total cost: 2 + 3 + 5 = 10

Solution - Part 3

We use DFS to explore all possible paths from the source to the destination. The algorithm maintains the current path, airlines used, and accumulated cost, backtracking when necessary.

Key Implementation Details:

• Path Tracking: Maintain a list of locations in the current path
• Method Tracking: Keep track of airlines used for each leg
• Cost Accumulation: Sum up the costs as we traverse
• Backtracking: Properly revert all three states (path, methods, cost) when backtracking
• Visited Set: Prevent cycles by tracking visited locations

from collections import defaultdict

# O(V + E) time | O(V) space
def find_any_route(input_str: str, source: str, destination: str) -> dict:
    flights = input_str.split(",")
    graph = defaultdict(list)
    
    # Build adjacency list representation
    for flight in flights:
        src, dst, airline, cost = flight.split(":")
        cost_as_int = int(cost.strip())
        graph[src.strip()].append((dst.strip(), airline.strip(), cost_as_int))
    
    total_cost = 0
    path = []
    methods = []
    visited = set()
    
    def dfs(src, method=None, cost=0):
        nonlocal total_cost
        visited.add(src)
        path.append(src)
        if method: 
            methods.append(method)
        total_cost += cost
        
        if src == destination:
            return True
        
        for nbr_country, nbr_airline, nbr_cost in graph[src]:
            if nbr_country not in visited:
                if dfs(nbr_country, nbr_airline, nbr_cost):
                    return True
        
        # Backtrack: revert state
        visited.remove(src)
        path.pop()
        total_cost -= cost
        if methods:
            methods.pop()
        return False
    
    if not dfs(source):
        return {'route': 'No available route', 'method': '', 'cost': -1}
    
    return {
        'route': " -> ".join(path),
        'method': " -> ".join(methods),
        'cost': total_cost
    }

Complexity Analysis

• Time Complexity: O(V + E), where V is the number of locations and E is the number of flights. In the worst case, we might explore all possible paths.
• Space Complexity: O(V) for the recursion stack and visited set.

Final Notes

Alright, let's break down what you need to know about this Stripe flight routing question - we've been tracking this one and it's become their signature logistics optimization problem for backend roles. Here's the scoop:

1. The Logistics Angle: Stripe loves this question because it mirrors their real-world shipping and payment routing challenges. When processing international payments, they need to find optimal paths through banking networks, similar to finding flight routes. Don't get caught up in the airline theme: at its core, you are building a graph from the input and searching it for paths.

2. The Three-Part Escalation Trap: Classic Stripe format here. Part 1 is a warm-up (direct lookups), Part 2 adds constraints (exactly one hop), and Part 3 is the full graph traversal problem. Most candidates breeze through Parts 1 and 2 in 20 minutes, then struggle with the DFS implementation in Part 3. We believe most candidates who go on to get offers finish all three parts here, which makes this slightly more approachable than Stripe's famous currency conversion problem.

3. Cut Straight to the Core: The shipping and delivery-network story is real Stripe domain, but the skill they are grading sits underneath it: parse the input string into a graph, then run DFS to find paths. Build the adjacency list carefully, attaching the airline and cost to each edge, and Part 3 falls into place.

4. The Silent Treatment: Like all Stripe interviews, expect minimal guidance from your interviewer. They won't hint when you're on the right track or suggest optimizations. They're looking for independent problem-solving and clean implementation. Focus on getting correct solutions that pass their test cases rather than theoretical optimality.

5. The DFS Gotcha: Part 3 is where most people stumble. The key insight is maintaining three separate tracking mechanisms: the current path (for route output), the airlines used (for method output), and the total cost. Your backtracking must correctly revert all three states. We've seen countless candidates get the path tracking right but forget to pop from the methods array during backtracking.

Reality check: under the flight-routing story sits a graph traversal with extra bookkeeping, tracking the route, the airlines used, and the running cost all at once. Stripe leans on problems like this to see whether you can pull the algorithm out of a business spec and implement it cleanly, edge cases and all, the way their payment infrastructure has to every day.

The bottom line? Master your DFS implementation, practice careful state management during backtracking, and don't let the shipping theme distract you from the core graph algorithms. Get those right and this one falls into place fast, and three clean parts is the pace that earns the on-site.