Amazon CN SDE 27NG 四轮 VO：GenAI BQ + 拓扑排序 + 最短子数组 + 二分查找

面试安排

轮次	内容
Round 1	纯 BQ（GenAI / 大模型主题）
Round 2	Coding：拓扑排序 Topological Sort
Round 3	Coding：最短子数组和 >= target（前缀和 + 滑动窗口 Follow-up）
Round 4	Coding：Binary Search 二分查找

Round 1：BQ

面试官是 Senior SDE，重点考察 Customer Obsession、Invent and Simplify、Bias for Action、Learn and Be Curious。题目全部用英文口述：

1. Tell me about a time you leveraged generative AI / GAI tools to accelerate your coding or project work. What risks did you identify when using AI-generated code, and how did you mitigate them?
   • 考察：会用 AI，但懂得校验、不盲目复制代码，体现责任感。
2. Describe a situation where you needed to learn a new AI/tooling technology quickly for a project. How did you approach learning it?
   • 考察：Learn and Be Curious
3. Tell me about a time when an AI-assisted solution you tried did NOT work as expected. How did you troubleshoot and adjust your plan?
4. Tell me about a time you proposed a simplification to a complex workflow using AI tools. What tradeoffs did you discuss with your team?
   • 考察：Invent and Simplify

面试提示：全部用 STAR 结构回答。中国区面试官喜欢听具体的项目细节，不要说空话。重点提到 AI 输出的幻觉、代码正确性、安全风险，这些都是加分点。

Round 2：拓扑排序（Medium）

题目（口述）

We have a list of product dependencies for an e-commerce release. Each dependency [A, B] means B must be released before A. Given the total number of products numProducts and a list of dependency pairs, return one valid release order of all products. If there exists a cycle in dependencies (circular dependency, impossible to release), return an empty array.

Example：numProducts = 4，dependencies = [[1,0], [2,0], [3,1], [3,2]]，输出 [0,1,2,3]。

Clarify

1. Are product IDs unique integers?
2. Can we have multiple valid answers? —— We can return any valid topological order.
3. What if there are zero dependencies? —— Return any order of all products.
4. What about duplicate edges in the input dependency list?

解法：Kahn 算法（BFS）

1. 构建邻接表 + 入度数组（in-degree）。
2. 用 BFS 实现 Kahn 算法。
3. 每次取出入度为 0 的节点加入结果，把它下游邻居的入度减一；邻居入度变为 0 就加入队列。
4. 最后判断结果长度是否等于产品总数，不相等说明存在环，返回空数组。

from collections import deque

def release_order(num_products, dependencies):
    graph = [[] for _ in range(num_products)]
    indeg = [0] * num_products
    for a, b in set(map(tuple, dependencies)):   # 去掉重复边
        graph[b].append(a)
        indeg[a] += 1
    q = deque(i for i in range(num_products) if indeg[i] == 0)
    order = []
    while q:
        u = q.popleft()
        order.append(u)
        for v in graph[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                q.append(v)
    return order if len(order) == num_products else []

Follow-up

1. What is the time & space complexity? —— O(V + E)，V 是节点数，E 是边数。
2. If we need to find all possible valid release orders, how to modify this solution? —— DFS 回溯。
3. What if the graph is extremely large and cannot load all edges into memory? How to handle it?

Round 3：最短子数组和 >= target

题目（口述）

Given an integer array nums and a positive integer target, find the minimal length of a contiguous subarray of which the sum is greater than or equal to target. If there is no such subarray, return 0.

Clarify（面试时主动问）

1. Can the array contain negative integers?
2. Does the subarray have to be contiguous? —— Yes.
3. What about an empty input array? —— Return 0.
4. What about a single element?

解题思路

• 数组包含负数：前缀和不再单调，二分无法直接使用，暴力解法复杂度较高。
• 全部为正数：前缀和单调递增，可以用二分优化到 O(n log n)。
  • Follow-up 1：All elements positive, optimize to O(n log n).
  • Follow-up 2：Can we solve it with a sliding window in O(1) space? —— 可以。正数数组用双指针滑动窗口，O(n) 时间，O(1) 空间。
• 边界：遍历结束还找不到满足条件的子数组就返回 0。

def min_subarray_len(target, nums):
    best, left, s = float("inf"), 0, 0
    for right, x in enumerate(nums):
        s += x
        while s >= target:
            best = min(best, right - left + 1)
            s -= nums[left]
            left += 1
    return 0 if best == float("inf") else best

面试重点：面试官非常看重你主动区分「数组含负数」和「全是正数」两种场景的解法差异。不要上来就写滑动窗口，因为有负数时滑动窗口会失效。有负数的版本可以用前缀和 + 单调队列做到 O(n)（LeetCode 862）。

Round 4：二分查找 —— 最小库存阈值

题目（口述）

We have a sorted list of daily inventory checkpoints (ascending sorted array). We want to find the first position where the inventory value >= threshold. Return the index of this first element. If all elements < threshold, return -1.

Example：inventory = [2,5,8,12,16,20]，threshold = 11，输出 index 3（value = 12）。

Clarify

1. Is the input array strictly sorted ascending?
2. Are there duplicate inventory values?
3. What if the threshold is smaller than all elements? —— Return index 0.
4. Empty array? —— Return -1.

解题思路

经典的左边界二分查找（lower bound）：不断收缩搜索区间，定位第一个 >= threshold 的元素下标。时间 O(log n)，空间 O(1)。

def first_at_least(inventory, threshold):
    lo, hi = 0, len(inventory)
    while lo < hi:
        mid = (lo + hi) // 2
        if inventory[mid] >= threshold:
            hi = mid
        else:
            lo = mid + 1
    return lo if lo < len(inventory) else -1

Follow-up

1. What if the array is sorted descending? How do you adjust the binary search condition?
2. What is the edge case when multiple equal elements exist?
3. If the array is very large and stored on disk (not fully loaded into memory), can binary search still work?