Meta E4 Phone Screen + VO 过经：括号最大深度、叶到叶最大路径和、Dropbox 设计

流程与 Timeline

Phone Screen：4 天后收到进入 Final Round 的通知，给自己留了两周准备时间。
Final Round：共四轮，分两天进行：两轮 Coding，一轮 System Design，一轮 BQ。
周一面完，周五 HR 来电通知进入 Team Match。

Phone Screen

题目：LC 125（Valid Palindrome）、LC 938（Range Sum of BST）

Coding Round 1

Kth Largest Element
LC 827（Making A Large Island）

Coding Round 2

第一题：最深括号层数

给定字符串，找最深的括号层数。例如 (21)(((233)))(1) 输出 3；如果括号不匹配，输出 -1。

我先用 stack 秒解，面试官提示可以优化，于是想到用一个 int balance 计数，更高效。考虑到时间关系，讲完思路后直接要求进入第二题。

def max_paren_depth(s):
    depth = best = 0
    for c in s:
        if c == "(":
            depth += 1
            best = max(best, depth)
        elif c == ")":
            depth -= 1
            if depth < 0:
                return -1               # 右括号多了
    return best if depth == 0 else -1   # 左括号多了

第二题：二叉树叶子到叶子的最大路径和

Follow-up：N 叉树怎么做？

def max_leaf_to_leaf(root):
    """返回叶子到叶子的最大路径和；少于两个叶子返回 None"""
    best = None

    def down(node):                    # 从 node 往下到某个叶子的最大路径和
        nonlocal best
        if not node.left and not node.right:
            return node.val
        if node.left and node.right:
            l, r = down(node.left), down(node.right)
            cand = l + r + node.val
            best = cand if best is None else max(best, cand)
            return max(l, r) + node.val
        return down(node.left or node.right) + node.val

    if root:
        down(root)
    return best

N 叉树 Follow-up 参考思路：对每个节点，求出所有孩子各自往下的最大路径和，取最大的两个加上当前节点值来更新答案，再把最大的那个加上当前节点值返回给父节点。

System Design Round

题目：设计 Dropbox。因为是 E4 级别，Hello Interview 的内容基本够用。

Follow-up：

如何处理并发写（两人同时更新同一个文件）？
如何处理 stale file？—— 这个我当时没答出来，面试官提示可以考虑 long polling。

BQ Round

有没有做过组里别人都不想做的项目？你为什么愿意接？
一次失败的项目经历。
如何 ramp up 新项目？（这个问题在其他公司面试也经常出现）

总结心得

Meta 一直是我心心念念的公司，也算是我检验自己是否是合格 SDE 的标准。这次终于通过进入 Team Match，第三次终于成功。

Coding：把 LeetCode Meta tag 近 30 天的题目刷了两遍，练习「30 分钟两题」的节奏。
System Design：认真看了一亩三分地上的高频题，Hello Interview + SD mentor + peer mock 都帮助很大。
BQ：参照 Amazon 的 Leadership Principles 准备回答，也和 mentor 进行了多次 mock。