OpenAI OA Coding 面试复盘｜状态压缩 DP、矩阵模拟与区间 DP 四题

这套 OpenAI OA 用 CoderPad 平台，限时两小时，一共四道 Coding 题：四类商店路径计数、风向推动矩阵、图像镜像与模糊，以及两人从牌堆两端取牌。整体看下来，两道 DP 最费思考，两道模拟题的分则容易丢在移动顺序、边界判断和结果矩阵的更新时机上。下面按题目拆开讲思路和最容易写错的地方。

第一题：经过四类商店的路径计数

题目描述

给定商店类型数组 shops 和道路列表 roads，每个商店属于 0 到 3 中的一类。统计沿道路连续经过商店的路径数量，要求四种类型各出现一次，且不能重复经过同一类型。题目问的是路径数量，不是最短距离。

解题思路

先按道路连接关系建立邻接表，用四位二进制记录已经经过的商店类型。dp[mask][v] 表示以 v 结尾、已访问类型为 mask 的路径数量，初始时每个商店都能作为起点。沿道路转移到下一家商店时，只有目标商店的类型尚未出现才更新状态，最后汇总 mask 为 15 的计数。

def count_type_paths(shops, roads):
    n = len(shops)
    graph = [[] for _ in range(n)]
    for u, v in roads:
        graph[u].append(v)
        graph[v].append(u)

    full = (1 << 4) - 1
    dp = [[0] * n for _ in range(1 << 4)]
    for v in range(n):
        dp[1 << shops[v]][v] = 1

    for mask in range(1, 1 << 4):
        for v in range(n):
            if dp[mask][v] == 0:
                continue
            for w in graph[v]:
                bit = 1 << shops[w]
                if mask & bit:
                    continue
                dp[mask | bit][w] += dp[mask][v]

    return sum(dp[full])

商店类型只有四种，mask 只有 16 个取值，状态空间很小；时间复杂度 O(16·(n+m))，额外空间 O(16·n)。最容易漏的是起点初始化：每个商店都要先把自己这一类型放进 mask，否则会少算从任意节点出发的路径。

第二题：风向推动矩阵元素

题目描述

给定一个二维矩阵，每个位置表示该格的树叶数量，以及由 U、D、R、L 组成的风向字符串。每次风把所有仍在矩阵内的树叶向对应方向移动一格，移出边界的树叶丢弃。按顺序执行全部操作后，返回剩余树叶的总数。

解题思路

把 U、D、R、L 映射成上下左右四个坐标偏移。每次操作新建一个全零矩阵，遍历当前矩阵，把仍在边界内的元素搬到新位置，越界的直接舍弃，再用新矩阵执行下一次操作。已经移出的元素不会因为后续反向风而恢复，所以不能只算四个方向的净位移。

def remaining_leaves(grid, winds):
    dirs = {'U': (-1, 0), 'D': (1, 0), 'L': (0, -1), 'R': (0, 1)}
    rows, cols = len(grid), len(grid[0])
    cur = [row[:] for row in grid]
    for w in winds:
        dr, dc = dirs[w]
        nxt = [[0] * cols for _ in range(rows)]
        for r in range(rows):
            for c in range(cols):
                if cur[r][c] == 0:
                    continue
                nr, nc = r + dr, c + dc
                if 0 <= nr < rows and 0 <= nc < cols:
                    nxt[nr][nc] += cur[r][c]
        cur = nxt
    return sum(sum(row) for row in cur)

每一步都是全体元素同方向平移，越界即丢弃。时间复杂度 O(L·R·C)，L 为风向长度，R、C 为矩阵尺寸。这里最容易漏的是每次都要用上一轮的新矩阵继续算，不能反复基于最初的矩阵累加。

第三题：图像镜像与邻域模糊

题目描述

给一个像素值在 0 到 255 之间的二维图像矩阵，根据指定滤镜执行左右镜像或模糊。镜像以竖直轴为对称轴；模糊时取原图中周围八个方向的有效邻居，计算平均值并四舍五入，不包含当前像素，没有邻居时保留原值。

解题思路

镜像时逐行反转，每个像素从列 c 移到 width - 1 - c。模糊时新建结果矩阵，逐个像素枚举八个方向，只累加原图中未越界的邻居，再按实际邻居数求平均并四舍五入。不能边计算边覆盖原图，否则后续像素会读到已经修改的值。

def mirror(image):
    return [row[::-1] for row in image]


def blur(image):
    rows, cols = len(image), len(image[0])
    result = [[0] * cols for _ in range(rows)]
    for r in range(rows):
        for c in range(cols):
            total, count = 0, 0
            for dr in (-1, 0, 1):
                for dc in (-1, 0, 1):
                    if dr == 0 and dc == 0:
                        continue
                    nr, nc = r + dr, c + dc
                    if 0 <= nr < rows and 0 <= nc < cols:
                        total += image[nr][nc]
                        count += 1
            result[r][c] = round(total / count) if count else image[r][c]
    return result

模糊必须在原图上读、在结果矩阵上写。边角像素按实际邻居数求平均，单像素图像没有邻居，保留原值即可。

第四题：两端取牌的最优得分

题目描述

桌上有偶数张牌，每张牌的分值都是正整数。两名玩家轮流从剩余牌的最左端或最右端取一张，取到的分值加入自己的总分。双方都知道整副牌的顺序，并采用最优策略，要求返回先手玩家的最终得分。

解题思路

用 dp[l][r] 表示面对区间 [l, r] 时，当前玩家能比对手多拿的最大分数。取左端后分差为 cards[l] - dp[l+1][r]，取右端后为 cards[r] - dp[l][r-1]，取两者较大值。从短区间算到长区间，最后用「牌面总和加最终分差，再除以 2」得到先手得分。

def first_player_score(cards):
    n = len(cards)
    dp = [[0] * n for _ in range(n)]
    for length in range(1, n + 1):
        for l in range(n - length + 1):
            r = l + length - 1
            if length == 1:
                dp[l][r] = cards[l]
            else:
                take_left = cards[l] - dp[l + 1][r]
                take_right = cards[r] - dp[l][r - 1]
                dp[l][r] = max(take_left, take_right)
    return (sum(cards) + dp[0][n - 1]) // 2

当前拿哪一端，会决定对手接下来能拿到什么，所以每次贪心选两端较大值并不成立；区间 DP 会同时计算对手的最优回应。时间复杂度 O(n²)，空间可压缩到 O(n)。

备考建议

两道 DP 建议先手推小样例再写代码：第一题确认 mask 的初始化与转移条件，第四题确认区间长度递增的循环顺序。两道模拟题建议先写正确版本，再补「越界丢弃」「结果矩阵与原始矩阵分离」这类边界测试，不要一上来追求最简写法。

时间上，四题里 DP 通常更花思考，模拟题则要留出检查细节的时间。每写完一题，跑一组正常样例和一组极端样例再进入下一题。

FAQ

状态压缩 DP 的 mask 为什么只用四位？

因为题目要求四种类型各出现一次，四位二进制恰好能记录每种类型是否已经出现，总共只有 16 个状态。相比记录每个节点是否访问过，状态数从指数级降到常数级。

风向模拟能只算四个方向的净位移吗？

不能。树叶中途越界就被丢弃，即使后面的风向把位置移回来，丢失的树叶也不会恢复，所以必须逐步模拟每一步。

模糊计算需要包含当前像素吗？

不包含。只统计周围八个方向中未越界的邻居，边角像素按实际邻居数求平均，单像素图像保留原值。

取牌时每次选两端较大的牌可以吗？

不可以。当前拿哪一端，会决定对手接下来能拿到什么；区间 DP 会同时计算对手的最优回应，贪心只看眼前两步并不成立。

参考来源

OpenAI OA 四道 Coding 题的候选人分享与平台记录 OpenAI Software Engineer 面试流程与 CoderPad 测评说明 OpenAI Software Engineer 面试问题与准备要点

联系 VOPathway

如果你希望把这套方法用于自己的 OA 或 VO 准备，可以把目标岗位、当前阶段、面试时间和主要难点发给 VOPathway，我们会据此安排针对性的练习与复盘。

• 微信：Coding0201
• 邮箱：[email protected]
• Telegram：@OAVOProxy
• WhatsApp：+86 178 6396 8105

可提供 OA辅助、OA辅导、VO辅助与 VO辅导。文章用于训练参考，不代表相关公司的官方流程；实际安排请以候选人收到的通知为准。