Stripe OA 面试真题解析：Sending Terminal Hardware（图搜索与最短路径）

Sending Terminal Hardware (Part 1)

Stripe operates in many countries and sends out payment terminal hardware through different shipping methods based on routes between countries.

Your task is to write a program that determines the cost of shipping for available methods and routes.

An example input string looks like this:

inputString = "US:UK:FedEx:5, UK:US:UPS:4, UK:CA:FedEx:7, US:CA:DHL:10, UK:FR:DHL:2"

Each entry represents a source country, target country, shipping method, and a shipping cost. For instance, shipping via FedEx from the US to the UK costs $5 per unit.

Your program will read and parse that input string.

Write a function shippingCost(inputString, sourceCountry, targetCountry, method) that can look up the cost of shipping via a specified method from the source country to the target country from the input list.

For example:

shippingCost(inputString, "US", "UK", "FedEx") should return 5
shippingCost(inputString, "UK", "FR", "DHL") should return 2

Sending Terminal Hardware (Part 2)

Modify your program such that it can find shipping routes through at most one intermediate country. Any shipping methods are allowed.

Output the route, the method(s) taken, and the total cost.

For instance:

shippingRoute(inputString, "US", "FR") should return
{
  route: "US -> UK -> FR",
  method: "FedEx -> DHL",
  cost: 7
}

这道题分两部分：第一部分需要先解析输入字符串，把每条运输记录拆成“起点国家、终点国家、运输方式、费用”，然后在查询时根据源国家、目标国家和指定方式直接查找对应费用；第二部分则把问题升级为带路径选择的图搜索，要求在最多经过一个中转国家的前提下，找到可行路线并输出完整路径、所用方式和总成本。实现时通常会先用哈希表按起点和终点建立索引，第一问可做到 O(1) 或接近 O(1) 查询；第二问则需要枚举直达和一跳中转路径，比较总成本后返回结果。