Goldman Sachs 2026 SWE Summer UK OA 终极复盘：两道真题最优解、Python 模板与 7 天上岸策略

这份面经看似只有两题，但非常典型：一题考数学建模与公式化简，一题考数据结构与执行顺序建模。 如果你正在准备海外大厂 OA，这两题的解题方式可以直接复用到 Amazon、MSFT、Stripe 等同类型题目。

目录

• 题目背景与考点定位
• 题 1：网格中所有 a×a 子方阵总数
• 题 2：CPU 反向执行下的饥饿时间
• 2026 上岸案例：从 OA 卡题到拿到 Offer
• 高频失分点与面试官追问
• 7 天冲刺计划（可直接执行）
• 立即预约 1v1 复盘（CTA）
• 面试救急

题目背景与考点定位

原始输入来自 GS 2026 SWE Summer UK OA 面经，核心能力点非常明确：

• 题 1：把“枚举”升级为“闭式公式”，从 O(min(r,c)) 压到 O(1)。
• 题 2：把“时间顺序描述”转成“索引关系”，再用树状数组做快速查询。

如果你只会暴力写法，通常会在大数据下超时；如果你能写出下面这版，你在 OA 里会非常稳。

题 1：网格中所有 a×a 子方阵总数

题意重述

给定 rows x columns 网格，对每个 a（1 <= a <= min(rows, columns)），统计可选 a x a 正方形数量并求和。

单个 a 的数量是：

(rows - a + 1) * (columns - a + 1)

总和为：

[ \sum_{a=1}^{m}(rows-a+1)(columns-a+1), \quad m=\min(rows,columns) ]

最优解思路

将求和展开后用等差、平方和公式化简，可得 O(1) 计算式：

[ m(rows+1)(columns+1) -(rows+columns+2)\frac{m(m+1)}{2} +\frac{m(m+1)(2m+1)}{6} ]

Python 参考实现

from typing import List, Tuple

def count_square_subgrids(rows: int, cols: int) -> int:
    m = min(rows, cols)
    return (
        m * (rows + 1) * (cols + 1)
        - (rows + cols + 2) * m * (m + 1) // 2
        + m * (m + 1) * (2 * m + 1) // 6
    )

def solve_queries(queries: List[Tuple[int, int]]) -> List[int]:
    return [count_square_subgrids(r, c) for r, c in queries]

复杂度

• 时间复杂度：每个 query O(1)
• 空间复杂度：O(1)（不计输出）

题 2：CPU 反向执行下的饥饿时间

题意重述

有 n 个进程，优先级数组 priorities。CPU 执行顺序是从 n-1 到 0。 对进程 i，若在它之前执行了更低优先级进程，则它产生饥饿。 饥饿时长 = “最早开始执行的低优先级进程时间” 到 “进程 i 执行时间”。

建模关键

进程 i 执行时间是 n - 1 - i。 “最早执行”的先后对应“索引更大”。 因此我们要找：

j = max { j > i | priorities[j] < priorities[i] }

若不存在则饥饿时长为 0，否则：

starvation[i] = j - i

问题转化为：对每个位置 i，在右侧找“值更小的元素中的最大索引”。

最优解：坐标压缩 + 树状数组（维护前缀最大索引）

from typing import List

class FenwickMax:
    def __init__(self, n: int):
        self.n = n
        self.bit = [-1] * (n + 1)

    def update(self, i: int, val: int) -> None:
        while i <= self.n:
            if val > self.bit[i]:
                self.bit[i] = val
            i += i & -i

    def query(self, i: int) -> int:
        ans = -1
        while i > 0:
            if self.bit[i] > ans:
                ans = self.bit[i]
            i -= i & -i
        return ans

def starvation_times(priorities: List[int]) -> List[int]:
    n = len(priorities)
    vals = sorted(set(priorities))
    rank = {v: idx + 1 for idx, v in enumerate(vals)}

    bit = FenwickMax(len(vals))
    ans = [0] * n

    for i in range(n - 1, -1, -1):
        r = rank[priorities[i]]
        j = bit.query(r - 1)  # 右侧优先级更低的最大索引
        ans[i] = 0 if j == -1 else j - i
        bit.update(r, i)

    return ans

复杂度

• 时间复杂度：O(n log n)
• 空间复杂度：O(n)

2026 上岸案例：从 OA 卡题到拿到 Offer

候选人：L 同学，华南某 211，后端方向，目标英国岗位。 时间线（2026 年）：

• 01月12日：参加我们的一对一 OA 诊断，首轮模拟正确率 58%。
• 01月16日：完成“公式化计数 + 反向执行建模”专项训练。
• 01月21日：第二次模拟达到 92%，两题都在时限内 AC。
• 01月27日：收到 GS UK Summer 面试邀请。
• 02月14日：拿到 SWE Summer 2026 offer。

关键提升不是“刷更多题”，而是建立了两套稳定框架： 枚举题 -> 公式化，流程描述 -> 索引关系 -> 数据结构。 这也是大厂 OA 最看重的工程化解题能力。

高频失分点与面试官追问

• 把题 1 写成三重循环或双重枚举，数据一大直接超时。
• 题 1 忘记 a 的上界是 min(rows, cols)。
• 题 2 把“最早执行”误解成“最小索引”，方向写反。
• 题 2 只找“最近更小”而不是“右侧最大索引的更小值”。
• 没有处理“无更小值”时返回 0 的边界。

面试官常追问：

• 如果 priorities 值域很小，能不能把 O(n log n) 优化为 O(n)？
• 如果执行时间不是 1，而是 durations[i]，如何改造模型？
• 如何证明你找到的是“最早导致饥饿”的进程？

7 天冲刺计划（可直接执行）

• Day 1：只练“计数题公式化”，做 8 题并总结模板。
• Day 2：只练“反向执行/时间线建模”，做 6 题。
• Day 3：树状数组专题，完成 10 道“前缀查询 + 点更新”。
• Day 4：把本篇两题手写 3 遍，要求无 IDE 自动补全。
• Day 5：90 分钟 OA 模拟 2 套，严格计时。
• Day 6：复盘错题，整理“触发条件 -> 对应数据结构”清单。
• Day 7：全真模拟 + 英文解释训练（可口述 5 分钟解法）。

立即预约 1v1 复盘（CTA）

你如果也在冲刺 GS / Amazon / MSFT 的 2026 校招 OA，可以直接约一次专项复盘。 我们会给你可落地的结果：题型映射、代码模板、时间分配和提分路径。

立即预约：OA 1v1 诊断

面试救急

面试临近、题还做不稳？ 面试救急 通道可在 24 小时内安排资深工程师，提供：

• 45 分钟高频题极速梳理
• 30 分钟手撕代码限时纠错
• 15 分钟英文讲题与追问模拟

名额按周开放，先到先排。