這道題是 Stripe "Shipping Cost Calculation" 的後續擴充，難度從單純的雜湊表搜尋升級到了圖論（Graph）與路徑搜尋。
題目描述
在前一道題中，我們只需要計算兩點之間的直接運費。現在，業務場景變得更複雜：
我們需要找出從 Source Country 到 Target Country 的最佳運輸路徑，並且允許 最多經過一個中轉國家。
輸入要求
- Shipping Methods: 定義了國家之間的連通性、運輸方式（如 FedEx, DHL）和成本。
US -> UK: FedEx ($5), DHL ($7)UK -> FR: UPS ($4)US -> FR: FedEx ($15)
- Query: 起點
US，終點FR。
輸出要求
返回一個物件，包含：
route: 路徑字串 (e.g., "US -> UK -> FR")method: 運輸方式鏈 (e.g., "FedEx -> UPS")cost: 總成本
目標：找到成本最低的路徑。
oavoservice 解題思路分析
這本質上是一個帶約束的最短路徑問題（Constrained Shortest Path）。 約束條件是：跳數（Hops）<= 2（直接到達是 1 跳，經過一個中轉是 2 跳）。
1. 圖的建模
首先，將輸入轉化為鄰接表（Adjacency List）。
graph = {
"US": [ {"to": "UK", "method": "FedEx", "cost": 5}, ... ],
"UK": [ {"to": "FR", "method": "UPS", "cost": 4} ],
...
}
注意：兩個國家之間可能有多條邊（不同的運輸方式），我們需要保留成本最低的那條，或者在搜尋時遍歷所有邊。
2. 搜尋策略 (BFS vs DFS)
由於最大深度被限制為 2（起點->終點，或 起點->中轉->終點），我們不需要完整的 Dijkstra 演算法，簡單的遍歷即可。
演算法流程：
- Direct Path (0 中轉): 檢查
graph[source]中是否有直接到target的邊。記錄最低成本min_cost。 - 1-Hop Path (1 中轉):
- 遍歷
source的所有鄰居mid。 - 如果
mid不是target，再檢查graph[mid]中是否有到target的邊。 - 計算
cost(source->mid) + cost(mid->target)。 - 如果小於當前
min_cost，更新結果。
- 遍歷
3. 邊界條件
- 無路徑：如果無法到達，返回
null或空物件。 - 自環：起點等於終點？通常運費為 0。
- 多條同成本路徑：通常返回任意一條即可，或者按 method 字母序排列。
程式碼片段 (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
面試官會怎麼 Follow-up？
- 任意中轉次數：如果取消「最多一個中轉」的限制？（需升級為 Dijkstra 或 BFS）
- 禁運國家：如果某些國家在黑名單中不能經過？
- 最大成本限制：如果要求成本不能超過 $50？
oavoservice 的面試輔助服務涵蓋所有可能的 Follow-up 場景，我們幫你在面試中不僅做對題，還能展現出 senior 級別的思考深度。