软件工程师面试问题

回答框架: 查找差值

暴力解法会检查每一对数字，时间复杂度为 O(n²)。更好的方法是用哈希表记录数字及其下标。遍历数组时，对当前数字 x，所需的另一个数是 target - x。如果这个差值已在哈希表中，就返回当前下标和表中记录的下标；否则将 x 及其下标存入表中，继续遍历。 正确性的关键在于，处理下标 i 时，哈希表中恰好只有此前下标对应的数。因此，如果某个有效数对的第二个数位于 i，就会立即找到它；同时也不会重复使用同一个元素。 每个数字只需查找和插入各一次，时间复杂度为 O(n)；哈希表占用 O(n) 空间。注意重复值、负数、零，以及题目允许不存在解时应如何处理。

回答框架: 记录最近出现位置的滑动窗口

使用始终只包含不同字符的滑动窗口。维护左指针，以及记录每个字符最近一次出现下标的哈希表。右指针从左到右遍历字符串。如果当前字符在现有窗口中出现过，就把左指针移到上次出现位置的下一位。随后更新该字符的下标，并记录最大窗口长度。 重要的是左指针只能向右移动。如果字符上次出现的位置已在窗口左侧，就不应缩小窗口。因此更新方式是 left = max(left, lastSeen[char] + 1)。 每个字符只处理一次，左指针也只向前移动，时间复杂度为 O(n)；空间复杂度为 O(k)，其中 k 是字符集大小。边界情况包括空字符串、全不重复、全重复，以及编程语言对 Unicode 字符与字节的处理差异。

回答框架: 构造规范化键

字母异位词由相同的字符组成。为每个单词构造一个规范化键，再用哈希表按键分组。最直接的做法是将单词中的字符排序；例如 “eat”“tea” 和 “ate” 排序后都得到 “aet”。 字符串较短时，逐词排序简单可靠。如果字符集固定为小写英文字母且字符串较长，则可用包含 26 个字符计数的元组作为键，省去每个单词 O(k log k) 的排序。 设字符串数量为 n，平均长度为 k，则排序法的时间复杂度为 O(n × k log k)；固定字母表计数法可达到 O(n × k)。输出和键共需 O(n × k) 空间。还要考虑空字符串、重复项、大小写规则及非英文字符。

回答框架: 三个指针：前驱、当前、后继

使用三个指针。previous 初始为 null，current 指向头节点。对每个节点，先保存 next = current.next，再将 current.next 指向 previous，随后把 previous 移至 current、current 移至 next。当 current 为 null 时，previous 就是新的头节点。 不变量是：previous 指向已反转部分，current 指向尚未反转的第一个节点。必须先保存 next 再修改 current.next，否则会丢失链表的剩余部分。 时间复杂度为 O(n)，额外空间复杂度为 O(1)。要考虑空链表、单节点链表，并确认原头节点最终成为 next 为 null 的尾节点。

回答框架: 取值范围约束

常见错误是只检查每个节点是否大于左子节点且小于右子节点。这还不够，因为整棵子树都必须满足祖先节点施加的范围约束。 采用带上下界的深度优先搜索。对每个节点验证 lower < node.value < upper。递归到左子节点时，沿用下界，并以当前节点的值作为上界；递归到右子节点时，以当前值作为下界，并沿用上界。任何节点超出范围，就返回 false。 每个节点只访问一次，时间复杂度为 O(n)；递归栈占用 O(h) 空间，其中 h 是树高。要考虑重复值、整数上下限、空树及退化成链的树。若允许重复值，应先澄清它们能位于哪一侧。

回答框架: 按距离分层的广度优先搜索

把每个可通行的格子视为图节点，上下左右每次移动视为一条等权边。由于每一步的代价相同，广度优先搜索能找到最短路径。从起点出发，将其以距离 0 放入队列并标记为已访问。每次取出一个格子，检查边界内、未访问且不是障碍物的相邻格子。首次到达终点时，距离就是最短距离。 正确性来自广度优先搜索按距离递增的顺序处理节点。某个格子一旦被访问，之后再到达它就不可能获得更短的无权路径。 每个格子最多访问一次，因此时间复杂度为 O(行数 × 列数)；队列与已访问集合也需 O(行数 × 列数) 空间。边界情况包括起点或终点被阻挡、起终点相同、无路径，以及是否允许斜向移动。

回答框架: 从原节点到克隆节点的映射

用哈希表记录每个原节点对应的克隆节点。在深度优先或广度优先遍历中，遇到原节点时，若它尚未被克隆，就先创建克隆节点。随后递归或迭代地克隆各个邻居，并将克隆后的邻居加入当前克隆节点的邻接列表。 这个映射有两个作用：防止遇到环时无限循环，并保留共享引用，使克隆图与原图具有相同拓扑。 设图有 V 个节点、E 条边，则时间复杂度为 O(V + E)；映射和遍历栈或队列占用 O(V) 空间，不计输出图本身。边界情况包括空输入、自环、题目是否要求从起点以外克隆不连通分量，以及重复的邻居记录。

回答框架: 按金额自底向上动态规划

定义 dp[a] 为凑出金额 a 所需的最少硬币数。初始化 dp[0] = 0，其他位置设为无穷大。对 1 到目标金额的每个数，尝试所有面额。若 a - coin 非负，则更新 dp[a] = min(dp[a], dp[a - coin] + 1)。最后，如果 dp[target] 仍为无穷大，就返回 -1。 这个状态转移成立，是因为最优解中的最后一枚硬币必定属于给定面额。若它的面值为 c，则剩余金额 target - c 也必须用最少硬币凑出。 时间复杂度为 O(金额 × 面额种数)，空间复杂度为 O(金额)。要考虑目标金额为 0、无法凑出、面额 1、重复面额和目标金额较大的情况。

回答框架: 按结尾位置动态规划，再用二分查找优化

一个清晰的动态规划解法是：定义 dp[i] 为以下标 i 结尾的最长递增子序列长度。对每个 i，检查此前的每个 j。若 nums[j] < nums[i]，则 nums[i] 可以接在以下标 j 结尾的子序列之后，于是 dp[i] = max(dp[i], dp[j] + 1)。答案为 max(dp)。这一解法用时 O(n²)，空间 O(n)。 优化到 O(n log n) 的方法维护数组 tails，其中 tails[length - 1] 是长度为 length 的递增子序列可能达到的最小结尾值。对每个数字，通过二分查找定位第一个大于等于它的结尾值并替换。tails 的长度就是最长递增子序列的长度。 如果面试时间有限，先给出 O(n²) 的动态规划，再讨论优化方案，也是合理的。注意重复值、完全递减的数组、空输入，以及题目是否要求严格递增。

回答框架: 只构造有效前缀

用两个计数回溯：已使用的左括号数 open 和右括号数 close。若 open < n，就可以加一个左括号；若 close < open，就可以加一个右括号。第二个条件确保每个前缀都有效，因此无需先生成无效字符串再筛除。 当当前字符串长度达到 2n 时，将它加入结果。这样只会探索有效前缀，并尽早剪去不可能的状态。 有效输出的数量是第 n 个卡特兰数，因此运行时间主要取决于输出规模。空间复杂度包括 O(n) 的递归深度和结果本身。还要根据题意处理 n = 0 或 n = 1 的情况。

回答框架: 需求 → API → ID 生成 → 存储 → 重定向链路 → 扩展

需求：用户提交长网址，获得短网址；访问短网址时应迅速重定向。可选功能包括自定义别名、有效期、访问分析、垃圾内容检测及用户账户。 核心 API 包括 createShortUrl(longUrl, optionalAlias, expiration) 和 redirect(shortCode)。数据模型可包含 shortCode、longUrl、userId、createdAt、expiresAt、status，以及按需添加的分析元数据。 生成 ID 时，可以把自增 ID 编码为 base62、生成随机 base62 代码并检查冲突，或采用分布式 ID。自增方案简单，但不加混淆就会暴露业务量；随机 ID 易于分布式生成，但需要处理冲突。在中等规模下，随机 base62 代码配合数据库唯一约束是可行方案。 读取链路最重要。重定向应尽量快速：先从缓存查找 shortCode，未命中再访问数据库，验证有效期和状态，然后返回 HTTP 301 或 302。如果访问分析或目标地址可能变化，使用 302；若是永久重定向且希望浏览器更积极地缓存，则使用 301。 扩展时，可将热门短码放入 Redis 或边缘缓存，必要时按 shortCode 分片，通过队列异步记录分析数据，对创建请求限流，并检查垃圾或恶意网址。监控重定向延迟、缓存命中率、错误率、滥用报告及数据库负载。

回答框架: 用户 → 帖子 → 分发 → 排序 → 读取 → 一致性

先明确是哪类信息流：社交关注动态、推荐内容，还是两者混合。这里假设用户发布帖子后，关注者按相关性或发布时间查看内容。 核心对象包括用户、关注关系、帖子、媒体资源、信息流条目、点赞与评论，以及排序特征。API 可包括 createPost、getFeed、followUser、unfollowUser 和 interactWithPost。 常见的生成方式有两种。写入时分发：发布帖子后，把它推送到关注者的信息流存储中，读取快，但拥有大量关注者的用户发布时写入开销高。读取时分发：用户请求信息流时，再从其关注对象那里汇集帖子，写入轻，但读取较慢。常见折中是普通用户采用写入时分发，超大影响力账户采用读取时分发或特殊处理。 架构上，帖子服务负责写入，关系服务存储关注关系，信息流服务维护时间线，排序服务为候选内容打分，缓存保存热门信息流，媒体资源放在对象存储和 CDN。用队列异步处理分发和排序更新。 需要权衡内容新鲜度与排序质量、关注关系变更的一致性、超大账户、缓存失效、垃圾内容、隐私屏蔽及队列故障后的补发。监控加载延迟、新鲜度、分发积压、互动、缓存命中率、排序错误与滥用报告。

回答框架: 连接 → 消息流 → 持久化 → 投递 → 可靠性

需求包括一对一与群组消息、在线和离线投递、消息历史、已读回执、正在输入提示及推送通知。先澄清是否要求端到端加密、附件和多设备同步。 客户端与网关服务保持 WebSocket 连接。用户发送消息时，网关验证身份、分配或接收幂等键、把消息写入持久化存储、发布事件，再通过在线接收方的现有连接投递消息。离线用户收到推送通知，并可稍后拉取历史记录。 数据模型包括会话、参与者、消息、投递状态、已读状态和设备／会话信息。存储应支持按会话和时间高效读取。中等规模可使用关系型数据库，规模更大时可考虑分布式存储。附件应存入对象存储，而非消息数据库。 可靠性问题包括重复发送、乱序投递、重新连接、漏收消息、大群组分发及在线状态准确性。可使用幂等键、每个会话单调递增的序号、确认机制、重试，以及从上次已读位置继续同步的 API。 监控消息发送延迟、投递成功率、WebSocket 连接数、重连率、队列积压、推送失败及存储写入错误。

回答框架: 验证信号 → 界定范围 → 检查近期变更 → 拆解依赖 → 缓解影响

首先验证信号。检查多个监控系统是否都显示延迟上升，以及影响的是 p50、p95、p99，还是某个特定接口；确认用户能否感受到。 接着按接口、地域、可用区、客户群、版本、主机、依赖和请求类型缩小范围。全局变慢通常指向共享依赖或部署；局部变慢则可能是特定路由、查询、客户或基础设施区域的问题。 然后检查近期变更：部署、配置修改、数据库迁移、流量激增、功能开关、缓存变化或下游服务故障。利用链路追踪拆解各服务调用的耗时。检查数据库查询、缓存命中率、队列积压、CPU、内存、垃圾回收、线程池、连接池和外部 API。 如果用户受到影响，应先缓解故障，而非等到根因完全查明。可在安全前提下回滚、关闭功能开关、扩容、绕开缓慢依赖或延长缓存有效期。恢复后再记录根因、检测盲点和预防方案。

回答框架: 单元测试用例 → 边界 → 无效输入 → 不变量

我会先澄清规则：折扣类型、能否叠加、有效期、最低消费、用户资格、金额舍入，以及税费和运费是否计入。 单元测试应覆盖正常情况、边界情况、无效输入和规则之间的相互作用。例如：无折扣、百分比折扣、固定金额折扣、折扣高于商品小计、恰好满足最低消费、略低于门槛、折扣过期、用户无资格、允许时的多重折扣，以及分的舍入。 还要测试不变量：最终价格不能为负、折扣不应超过可优惠金额、过期优惠不能生效、同样输入重复计算应得出相同结果。如果涉及支付，还应增加与定价服务的集成测试，以及账单结果的快照测试。 为保障生产环境安全，应记录折扣决策及原因代码，让客服和工程团队能查明价格投诉的原因，而不必猜测。

回答框架: 正确性 → 可维护性 → 风险 → 清晰度

我会分层审查代码。第一，是否解决了预期问题并保持正确性？第二，是否易于维护：命名清晰、边界合理、没有不必要的复杂度，风格一致？第三，风险在哪里：迁移、并发、安全、性能、向后兼容及可观测性？第四，测试是否充分覆盖变更行为？ 好的代码审查不是为了显示自己更懂，而是在不拖慢团队交付的前提下改进代码。我会区分必须修改的问题和建议。正确性缺陷、安全问题或迁移风险应阻止合并；命名偏好或小幅重构通常可以不阻止合并。 我也会关注缺失的背景信息：产品行为不清楚、边界情况未经测试、静默失败、错误处理不足，以及高风险变更缺乏监控指标。

回答框架: 背景 → 选项 → 取舍 → 决策 → 结果

选择一个确实存在取舍的决策，例如自研还是采购、SQL 还是 NoSQL、单体还是服务化、快速修补还是深入重构、强一致性还是可用性。先说明背景和约束，再介绍考虑过的选项。 优秀的回答会把取舍讲清楚。例如：“方案 A 能在一周内上线，但增加了运维负担；方案 B 需要三周，却消除了扩展瓶颈。”接着解释决策依据：流量、客户期限、过往故障、团队能力或长期路线图。 最后说明结果和收获。如果决策并不完美，就坦诚说出下次会怎么做。面试官更看重成熟的判断，而不是假装每个决定都显而易见。

回答框架: 故障 → 影响 → 响应 → 根因 → 预防

尽量选用真实故障。先说明对用户的影响：什么坏了、谁受到影响、严重程度如何。再解释自己在响应中的职责，例如发现、分诊、回滚、缓解、沟通或根因分析。 优秀回答体现冷静地确定优先级。故障发生时，恢复服务比证明某种推测更重要。可以说明如何运用日志、指标、链路追踪、功能开关、回滚或依赖检查。 缓解后，解释根因和预防措施。可能的改进包括更好的测试、更安全的上线流程、监控、告警调整、操作手册、熔断、背压或迁移保护。不要归咎于个人；优秀团队会改进系统，降低同类错误再次发生的概率。

回答框架: 共同目标 → 约束 → 选项 → 取舍 → 决策

我会先确认共同的用户目标和业务目标。很多分歧并非工程与产品对立，而是双方基于不同假设。我会清楚说明技术约束：复杂度、可靠性风险、时间、可维护性、安全或性能。 然后提出可选方案，而不是只说“不行”。例如先推出范围更小的最小可行版本、暂时使用人工流程、通过功能开关逐步开放、调整技术工作的先后顺序，或选择仍能解决核心用户问题的更简单设计。 如果取舍影响重大，我会记录方案、风险与建议，让决策过程透明。目标不是让工程团队“赢”，而是让团队在了解后果的前提下作出清晰决策。