石老师最近又复盘了一场 Google 风格的高强度算法面试。这场面试连续 2 小时 38 分钟，全程无切屏，双面试官轮番追问，题目分为两大部分：数据结构设计 + 贪心算法问题。

今天这篇文章，我不讲教科书式答案，而是还原真实面试节奏，告诉你候选人是怎么“活下来”的。

第一题：Category 传递关系设计（Graph + DFS）

面试官先给出这样一个结构：

class Category {
    int id;
    List<Category> parents;
    List<Category> children;
}class Item {
    String name;
    Category category;
    List<Category> getTransitiveCategories() {
    }
}

然后给了一张图：

1 = electronic device
2 = communications device
3 = wireless device
4 = telephone
5 = smartphone
6 = landline

结构是一个 多父节点 DAG，不是简单树结构。

面试官问：

如果一个 Item 属于 smartphone（5），你如何返回它的所有“传递类别”？

也就是：5 → 4 → (2,3) → 1 …

面试真实考察点

很多人第一反应是递归往上爬。但真正的坑在这里：

• 这不是树，是 DAG
• 可能有多个 parent
• 可能有环
• 可能重复访问

候选人一开始写了简单 DFS，面试官立刻追问：

如果存在环怎么办？
如果类别有 10 万个节点怎么办？
时间复杂度是多少？

这时思路必须升级：

• 使用 visited set 防止死循环
• 递归或显式栈 DFS
• 时间复杂度 O(V + E)
• 如果频繁查询，可以缓存 transitive closure

这类题目 Google 很爱出，因为它考察的是：

• 图建模能力
• 是否能识别 DAG
• 是否考虑极端情况

不是写代码，是看你“脑子是否在线”。

第二题：Largest K Digit Subsequence（经典贪心）

然后面试官切换到算法题：

Given a sequence S of N digits, find a subsequence of K digits such that the number formed by these K digits (in order) is the largest.

这题看似简单，其实非常典型 Google 风格。

例如：

S = 1 9 2 4 6
K = 3

最大应该选：9 4 6

真实面试过程还原

候选人一开始想用暴力枚举组合。

面试官马上打断：

N 可以是 10^5，你的复杂度是多少？

这时就必须想到：

这是一个单调栈问题。

核心思想：

• 从左到右扫描
• 保证栈内保持“尽量大”
• 如果当前数字更大且还有删除机会，就 pop
• 最终保持长度 K

时间复杂度 O(N)

这类题的核心不是写代码，而是：

• 是否识别出“单调栈模板”
• 是否能清晰说明为什么贪心成立
• 是否能证明复杂度

为什么 Google 喜欢这种组合？

这场面试其实很典型：

第一题考 系统建模 + 图结构理解
第二题考 贪心思维 + 模板掌握程度

两道题组合在一起，其实在测：

• 你是不是刷题机器
• 还是理解底层结构的人

真正通过 Google 的候选人，不是写得快，而是：

• 逻辑清晰
• 主动讨论 trade-off
• 复杂度分析完整
• 边界情况主动覆盖

如果你正在准备 LinkedIn、Meta、Google 这类偏系统思维的题目，这种“数据依赖 + 影响评估”类型其实非常常见。建议联系我

我们也有代面试，面试辅助，OA代写等服务助您早日上岸~