Meta SWE/ML 电话面试 Phone Screen

编程环节 1

• 题目 1： 判断是否存在一个连续子数组，其元素和等于目标值（LeetCode「Subarray Sum Equals K」变体）

  • 解法： 双指针滑动窗口
  • 追问 1： 需要支持负数
    • 解法： 前缀和 + 哈希表
  • 追问 2： 返回和为 K 的子数组个数
    • 解法： 在追问 1 的基础上稍作修改即可

• 题目 2： 求从左上角到右下角的最短路径，并返回路径本身（LeetCode「Shortest Path in a Matrix」变体）

  • 解法： BFS，利用 parent 哈希表逆向还原路径
  • 追问 1： 为什么选择 BFS 而不是 DFS？如果用 DFS 会怎样？
  • 追问 2： 如果要求路径必须经过坐标 (a, b)？
    • 我一开始理解错了，只在找到的最短路径中检查是否包含 (a, b)。面试官提示可拆分成两段 BFS：
      1. (0, 0) → (a, b)
      2. (a, b) → (m − 1, n − 1)
  • 追问 3： 如果有 k 个必经坐标？
    • 我答：可以按顺序拆分成多段（start → must1 → must2 → … → end），因时间不足未编码
  • 追问 4： 必经坐标列表需要提前排好序吗？
    • 我答：需要。时间已到，会议结束

整轮又紧张又耗费心神，接着立刻开始下一轮。

编程环节 2

• 题目 1： 将二叉树转换为循环双向链表（LeetCode 同名题）

  • 解法： 中序 DFS，过程中用两个指针串联；最后首尾相连并返回头节点
  • 追问 1： 不允许使用全局变量
    • 解法： 递归返回子树对应的双向链表 (leftHead, leftTail, node, rightHead, rightTail)
  • 追问 2： 左子树不存在尾节点时怎么办？
    • 我回答得有些磕巴

• 题目 2： 「糖果消除」变体：相同字符数量 ≥ 2 即可消除

  • 示例 "abbba" → ""
  • 示例 "ad" → "ad"
  • 解法： 栈记录 (字符, 计数)，字符变化时检查计数 ≥ 2 则弹栈
  • 追问： 如何优化案例 "aabbccba" → ""？
    • 还剩 5 分钟，面试官只让讨论未要求编码。我尝试了几种思路但没想出满意方案，面试结束

刷完 Meta Tagged list 和 MinMer's Variant list 还是觉得被暴打，情绪稍低 ↓

明天还有Behavior和 ML 设计轮，祝我好运吧 :')