Amazon SWE 26NG 四轮面经：Dijkstra 配送最短路 + 滑动窗口 + Top K 订单 + Bar Raiser

Round 1：BQ + Graph

BQ

Tell me about a time you improved a process with data.

Coding：配送网络最短耗时

题目：给定 Amazon 仓库的配送站点网络，站点是节点，两点之间有双向配送通路以及对应的通行耗时。求从起点仓库到目标站点的最短配送耗时。

解题思路：Dijkstra 单源最短路径。维护优先队列，不断取出当前距离最小的节点，松弛更新邻居节点的距离。

import heapq

def shortest_delivery_time(n, roads, src, dst):
    """roads: [(u, v, cost)] 双向边，不可达返回 -1"""
    adj = [[] for _ in range(n)]
    for u, v, w in roads:
        adj[u].append((v, w))
        adj[v].append((u, w))
    dist = [float("inf")] * n
    dist[src] = 0
    pq = [(0, src)]
    while pq:
        d, u = heapq.heappop(pq)
        if u == dst:
            return d
        if d > dist[u]:
            continue                    # 过期的队列项
        for v, w in adj[u]:
            if d + w < dist[v]:
                dist[v] = d + w
                heapq.heappush(pq, (dist[v], v))
    return -1

时间 O((V + E) log V)。

面试中需要讨论：

负权边（Dijkstra 不适用，要换 Bellman-Ford）
不可达节点
节点数量很大时的性能优化边界

Round 2：项目 Deep Dive + BQ

针对简历上的两个项目深度盘问，重点探究：

遇到了什么困境
采取了什么对策
有什么收获

一旦提到具体数据，面试官会要求详细说明数据的获取途径和来源。

中间穿插 trade-off 相关的 BQ，考察如何在成本和延迟之间做取舍。

Round 3：BQ + Sliding Window

BQ

Outside your responsibility & Tough feedback

Coding：订单总额不超过阈值的最长子数组

题目：给定一段用户订单金额的时间序列数组，找一个连续子数组，满足子数组内订单总额不超过给定阈值，求这类子数组的最大长度。

解题思路：滑动窗口（双指针）。右指针不断向右扩大窗口，窗口总和超过阈值时移动左指针收缩，每一步更新合法窗口的最大长度。

def longest_within_budget(orders, threshold):
    """orders 为非负金额"""
    left = total = best = 0
    for right, x in enumerate(orders):
        total += x
        while total > threshold and left <= right:
            total -= orders[left]
            left += 1
        best = max(best, right - left + 1)
    return best

需要讨论：

数组存在负数怎么办？—— 窗口和不再单调，滑动窗口失效，可以改用前缀和 + 有序结构 / 单调栈。
空数组等边界 case。

Round 4：Bar Raiser

BQ

围绕 Ownership、Customer Obsession、Dive Deep 等 Amazon LP 展开。

Coding：Top K 订单

题目：Amazon 订单数据流，每条记录包含订单金额，实时维护金额最高的前 K 个订单。

解题思路：维护一个大小为 K 的最小堆，遍历所有订单：

堆未满，直接入堆。
堆满时，如果新元素大于堆顶，就弹出堆顶、新元素入堆。
最终堆内就是 Top K 订单。

import heapq

def top_k_orders(amounts, k):
    heap = []
    for x in amounts:
        if len(heap) < k:
            heapq.heappush(heap, x)
        elif k > 0 and x > heap[0]:
            heapq.heapreplace(heap, x)
    return sorted(heap, reverse=True)

讨论：海量数据流、内存受限的场景。

小结

这套面经的算法本身都不算特别偏，但明显强调 BQ + 场景化包装 + follow-up。尤其是 Round 2 和 Bar Raiser，会围绕项目数据、trade-off、Ownership 一直往下挖。