Stripe Interview Question: Shipping Route with One Intermediate Country

This question is an extension of Stripe's "Shipping Cost Calculation", escalating from simple Hash Map lookups to Graph Theory and Pathfinding.

Problem Description

In the previous problem, we only calculated direct shipping costs between two points. Now, the business scenario becomes more complex: We need to find the best shipping route from a Source Country to a Target Country, allowing for at most one intermediate country.

Input Requirements

1. Shipping Methods: Defines connectivity, methods (e.g., FedEx, DHL), and costs between countries.
   • US -> UK: FedEx ($5), DHL ($7)
   • UK -> FR: UPS ($4)
   • US -> FR: FedEx ($15)
2. Query: Start US, End FR.

Output Requirements

Return an object containing:

• route: Path string (e.g., "US -> UK -> FR")
• method: Chain of shipping methods (e.g., "FedEx -> UPS")
• cost: Total cost

Goal: Find the path with the minimum cost.

oavoservice Solution Analysis

This is essentially a Constrained Shortest Path problem. The constraint is: Hops <= 2 (Direct is 1 hop, via intermediate is 2 hops).

1. Graph Modeling

First, convert the input into an Adjacency List.

graph = {
    "US": [ {"to": "UK", "method": "FedEx", "cost": 5}, ... ],
    "UK": [ {"to": "FR", "method": "UPS", "cost": 4} ],
    ...
}

Note: There might be multiple edges (methods) between two countries. We should either keep the cheapest one or iterate through all of them during search.

2. Search Strategy (BFS vs DFS)

Since the maximum depth is limited to 2 (Source->Target, or Source->Mid->Target), we don't need a full Dijkstra algorithm. A simple traversal is sufficient.

Algorithm Flow:

1. Direct Path (0 Intermediate): Check if there is a direct edge from graph[source] to target. Record min_cost.
2. 1-Hop Path (1 Intermediate):
   • Iterate through all neighbors mid of source.
   • If mid is not target, check graph[mid] for edges to target.
   • Calculate cost(source->mid) + cost(mid->target).
   • If less than current min_cost, update result.

3. Edge Cases

• No Path: Return null or empty object if unreachable.
• Self-loop: Source equals Target? Cost is usually 0.
• Ties: Return any valid path, or sort lexicographically by method name.

Code Snippet (Python)

def find_best_route(source, target, graph):
    best_route = None
    min_cost = float('inf')

    # 1. Check Direct Paths
    if source in graph:
        for edge in graph[source]:
            if edge['to'] == target:
                if edge['cost'] < min_cost:
                    min_cost = edge['cost']
                    best_route = {
                        "route": f"{source} -> {target}",
                        "method": edge['method'],
                        "cost": min_cost
                    }

    # 2. Check 1-Intermediate Paths
    if source in graph:
        for edge1 in graph[source]:
            mid = edge1['to']
            if mid == target: continue # Skip direct

            if mid in graph:
                for edge2 in graph[mid]:
                    if edge2['to'] == target:
                        total_cost = edge1['cost'] + edge2['cost']
                        if total_cost < min_cost:
                            min_cost = total_cost
                            best_route = {
                                "route": f"{source} -> {mid} -> {target}",
                                "method": f"{edge1['method']} -> {edge2['method']}",
                                "cost": min_cost
                            }
    
    return best_route

Common Follow-ups

• Any Number of Hops: What if the "at most one" restriction is removed? (Upgrade to Dijkstra or BFS)
• Forbidden Countries: What if certain countries are on a blacklist?
• Max Cost Constraint: What if the cost cannot exceed $50?

oavoservice's interview support covers all possible follow-up scenarios, helping you not only solve the problem but also demonstrate senior-level depth.

Learn about VO Support

联系方式

Email: [email protected] Telegram: @OAVOProxy