AI 编程面试题：示例与练习

即使知道算法名称，面对新问题时，你仍可能不知道如何着手。这些练习题把具体输入与解法选择、复杂度界限及应当口头说明的边界情况联系起来。

• Two Sum：返回两个不同的索引，其对应值之和等于目标值。对于 [3, 3] 和目标值 6，答案需要使用两个位置。扫描时使用哈希表保存此前见过的值，在存入当前值之前检查其补数。这样可以避免重复使用同一个索引。预期时间复杂度为 O(n)，额外空间复杂度为 O(n)。请说明不存在数对时应返回什么。
• 寻找不含重复字符的最长子串。对于 'abba'，长度为 2。记录每个字符最后出现的位置，并维护一个没有重复字符的窗口。当旧字符的出现位置位于当前窗口之外时，左边界绝不能向后移动。使用哈希表查询时，预期时间复杂度为 O(n)。请说明如何界定一个字符。
• 合并相互重叠的闭区间。对于 [1, 3]、[3, 5] 和 [8, 10]，返回 [1, 5] 和 [8, 10]。先按起点排序，再扩展当前区间或开始一个新区间。排序使时间复杂度为 O(n log n)。共享端点的闭区间会重叠；请确认这是否符合题目的定义。
• 反转无环单向链表。更改当前节点的 next 指针前，先保存下一个节点。迭代解法的时间复杂度为 O(n)，额外空间复杂度为 O(1)。依次推演空链表、单节点链表和双节点链表。说明每次迭代后，链表的哪一部分已经反转。
• 逐层返回二叉树的值。使用队列，并在开始处理下一层前，先处理当前层的节点数量。时间复杂度为 O(n)；辅助队列的空间复杂度为 O(w)，其中 w 是最大层宽度，不包括返回的输出。测试空树，以及每层都只有一个子节点的树。
• 根据先修课程判断能否完成所有课程。将先修关系建模为有向图，并使用拓扑排序。如果处理的顶点少于 V 个，则仍存在有向环。时间复杂度为 O(V + E)。测试不连通的分量、孤立课程和自依赖。
• 求凑出指定金额所需的最少硬币数。假设面额为正整数且每种硬币可以无限使用。对于 [1, 3, 4] 和金额 6，优先选择最大硬币需要三枚；3 + 3 只需两枚。将动态规划状态定义为凑出每个金额所需的最少硬币数，并以金额为零时需要零枚硬币作为初始状态。目标金额为 A、面额种类数为 c 时，标准方法的时间复杂度为 O(Ac)，空间复杂度为 O(A)。请明确处理无法凑出的金额。

如需按职位和主题整理的相关练习，请浏览面试题库。

请看这道题：统计和等于目标值的非空连续子数组数量，允许出现负数。对于 [1, -1, 1] 和目标值 1，答案是 3：可以是任意一个单元素 [1] 子数组，也可以是整个数组。

先从基准方法开始：选择每个起始位置，然后在维护累计和的同时不断扩展结束位置。这需要 O(n²) 时间和 O(1) 额外空间。常见的收缩窗口方法在这里并不可靠，因为负数会破坏“扩展窗口会增大其总和”这一假设。

更快的方法使用前缀和与频次表。如果当前前缀和为 s，那么此前每个等于 s - target 的前缀都对应一个和满足要求的子数组。初始化频次表时，将前缀和为零的出现次数设为一，表示数组开始前的空前缀。

• 处理顺序：将当前值加到前缀和中，统计匹配的早期前缀，然后记录当前前缀。若先记录当前前缀，当目标值为零时便会错误地计入一个空子数组。
• 不变量：记录当前前缀之前，频次表包含所有在当前位置之前结束的前缀及其出现次数。
• 复杂度：每个元素执行固定次数的映射操作。假设哈希操作的预期时间为常数，预期时间复杂度为 O(n)，额外空间复杂度为 O(n)。
• 检查：空数组返回 0。对于 [0, 0] 和目标值 0，返回 3。使用固定位宽整数类型时，需要考虑累计和与答案计数的溢出问题。

一个实用的后续问题是，任务要求返回数量还是实际的子数组。返回每个匹配的子数组会产生输出成本：当目标值为零时，一个全零数组有 n(n + 1)/2 个匹配的非空子数组。

先自行尝试，再请求帮助，并且只要求能让你继续完成题目的最小程度干预。以下提示词可以把与 AI 的对话转化为可验证的练习。

• 请求一个提示：给我一个关于应存储哪些信息的提示。暂时不要提供代码，也不要说出完整算法的名称。
• 质疑推理：这是我的循环不变量。请找出一个会使我的实现违反它的输入，或说明每次更新为何都能维持它。请自行检查回答；模型表示赞同并不能证明解法正确。
• 审查复杂度：统计此实现中切片、排序、容器操作和递归调用所执行的工作量。熟悉的算法名称并不能确定实际代码的复杂度。
• 生成测试：请针对空输入、重复值、边界值和无解情况提出测试用例，并说明每个用例的预期答案。将这些答案用作测试判定依据前，请先独立推导。
• 更改一个约束：如果输入已经排序、不可修改或以数据流形式到达，解法应如何改变？重写代码前，先说明新的权衡。

例如，一名正在准备云服务商高级职位的后端工程师解决了先修关系图问题后，请 AI 练习伙伴提供一个包含环的不连通图。随后，她在不查看提示的情况下推演队列，并解释已处理顶点的数量为何能揭示该环。

阅读完整解法后，将其关闭，再凭记忆重建算法、不变量和测试。能够复现代码，不如能够解释代码为何有效并根据变化后的约束调整解法来得有用。

如需练习在对话中讲解推理过程，请访问模拟面试页面。

SubcueAI 提供两种实时辅助界面。其旗舰原生应用适用于 macOS 和 Windows，可捕获系统音频和你的麦克风，并在本地浮动叠加层中显示辅助内容。它支持桌面会议客户端，包括 Zoom 和 Microsoft Teams。

浏览器扩展程序也通过 Chromium 浏览器（包括 Chrome 和 Edge）的侧边面板提供实时辅助。它只捕获会议标签页的音频，适用于 Google Meet 等浏览器标签页中的通话。它通过该标签页听取面试官的声音，绝不会捕获你的麦克风，也不会转录候选人的发言。Firefox 版本仅用于模拟练习。

这两种界面都不会向通话中添加会议机器人，也不会向会议页面注入内容脚本。对于编程题，需要区分口头上下文和书面上下文：仅捕获音频无法获得只显示在编辑器中的题目描述或代码。请依据确切的题目、约束和实现检查所有建议。

使用实时辅助前，请确认面试规则。SubcueAI 并非在所有情况下都无法被检测。屏幕共享、录屏、受监考的测评和公司管理的设备均不在隐藏保证范围内。共享或录制的屏幕可能暴露叠加层或侧边面板，设备或监考控制措施也可能监测活动。

有关可用界面的设置指南，请参阅SubcueAI 教程。