Capital One SWE OA 面试复盘｜70 分钟 CodeSignal 的图搜索和单调栈如何安排

Capital One 的 Full Stack / Backend SWE OA 里，70 分钟的 CodeSignal 节奏很紧。前半段要尽快拿到稳定分，后半段更考验图搜索、边界拆解和代码收尾。四题结构下，后两题往往决定最后的完成度。

第一题：带状态的图搜索

题目描述

这一题围绕图上的可达性与最短路径展开。节点之间的连接关系先要建出来，再从起点扩展，直到找到满足条件的目标节点。题目会给出多组连接和查询，不能为每个查询都重新扫描整张图。

解题思路

优先把边表转成邻接表。无权图直接用 BFS，队列里保存节点与当前步数； visited 必须在入队时写入，避免同一个节点被多条边反复推进队列。若查询很多，把固定图保留下来，每次只重置访问数组。图里存在方向时，反向边不能顺手补上。准备时可以先做一轮多源 BFS，再练一次“路径中带一个开关状态”的写法，能把状态转移说清楚比只报出 BFS 更有用。 复杂度 ：单次查询时间 O(V + E)，空间 O(V)。

第二题：直方图里的最大矩形

题目描述

另一道高分辨题把一串高度视为直方图，要求找出连续柱子组成的最大矩形面积。直接枚举左右边界会在数据变大后超时。

解题思路

单调递增栈是核心。遍历高度时，栈里保留尚未确定右边界的下标；遇到更矮的柱子，就持续弹栈，弹出的高度以当前下标作为右边界、以新栈顶之后作为左边界。遍历结束后补一个高度为 0 的哨兵，最后一批柱子才能结算。写代码时优先把宽度公式写出来： width = i - stack[-1] - 1 。这题最容易丢的是相同高度的处理和末尾清栈。 复杂度 ：每个下标只进出栈一次，时间 O(n)，空间 O(n)。

70 分钟如何分配

开场先读完全部题目，用两三分钟标出自己最稳的一题。第一道完成后立刻跑自定义边界：空输入、单节点、自环、重复边；第二道至少验算单柱、递增柱和递减柱。剩余时间不要把可运行代码大改成“更漂亮”的版本，先保住通过的测试，再补命名和异常分支。

FAQ

Capital One OA 要优先刷哪些题？

优先把 BFS、图建模、单调栈、矩阵遍历和字符串解析串起来练。CodeSignal 的限时环境里，能快速写出可运行版本比背题单更重要。

OA 里提交前最后检查什么？

检查索引是否越界、队列或栈是否在正确时机更新、返回值是否覆盖空数组和单元素。图题再看一次有向边与无向边的判断。

参考来源

Capital One CodeSignal OA 讨论 候选人的 Full Stack CodeSignal 记录 Capital One SWE 候选人流程记录

联系 VOPathway

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

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

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