这次分享一道 Google 面试中出现的设计题。题目本身结构很清晰API 只有两个规则也只有三条但真正写起来会发现细节非常多——不能连续返回同一条广告这条规则直接把单纯的 Max Heap 方案卡住了。很多候选人第一反应是“堆排序取最大”然后被这条规则绊住后面的逻辑越补越乱。下面把这道题的完整拆解、正确解法、以及面试中应该主动确认的边界条件全部梳理出来。题目原文实现一个广告服务器提供两个 APIInsertAd(content, score)向可用广告池中插入一条广告。GetAd()返回当前最好的广告。规则score 越高广告越好。不能连续两次返回同一条广告。广告每被返回一次其 score 减 1。题目理解表面上看这是一个“总是取最高分”的问题Max Heap 天然适用。但第二条规则打破了这种直觉——如果你每次都从堆顶拿就可能连续两次拿到同一条广告违反规则。这就意味着堆不能单独解决问题。你必须额外维护一个“上次返回的广告”的引用在取广告时做一个判断堆顶是不是上一次刚返回的如果是就要临时跳过它取下一个。解题思路核心数据结构Max Heap last served ad 引用。InsertAd将广告对象包含 content、score放入 Max Heap。堆的比较器按 score 降序排列。如果分数相同可以按插入顺序或其他 tie-breaker 处理这一点面试时建议主动确认。GetAd如果堆为空返回 null。查看堆顶广告如果堆顶广告不是上一次返回的广告弹出堆顶记录为本次返回的广告。将其 score 减 1。如果 score 仍大于 0或题目允许负数则无所谓放回堆中。更新lastAd引用返回该广告。如果堆顶广告恰好是上一次返回的广告先将堆顶弹出暂存在一个临时变量中。查看新的堆顶即第二高分的广告如果堆为空说明整个广告池只有这一条广告且它刚被返回过。此时返回 null并将暂存的广告放回堆中。如果堆不为空弹出新的堆顶作为本次返回的广告。处理 score 减 1 和放回逻辑。更新lastAd引用。最后把暂存的广告放回堆中。关键细节不能只弹一个很多同学在第一版实现时会写成遇到lastAd在堆顶就跳过它取下一个取完把下一个减分放回然后结束。这漏掉了把跳过的广告放回去。如果不放回那这条广告就凭空消失了之后再也没机会被返回。正确的做法是被跳过的广告必须原封不动地放回堆中因为它在本次调用中并没有被返回不消耗 score。示例推演插入广告A: score 5B: score 4C: score 2调用次数操作堆状态lastAd返回1GetAd()A(5), B(4), C(2)nullA(5)A 弹出减分后放回A(4), B(4), C(2)A2GetAd()A(4), B(4), C(2)A堆顶是 A lastAd跳过 A取 BA(4), B(3), C(2)BB(4)3GetAd()A(4), B(3), C(2)B堆顶是 A ≠ B返回 AA(3), B(3), C(2)AA(3)第三步时A 因为在第二步被跳过并完整保留所以它仍然是最高分可以重新返回。边界条件面试时必须主动确认这类题在 Google 面试中的得分点不只在于写对逻辑还在于你能不能主动发现题目没写清楚的地方。建议在写代码前主动问Tie-breaker 怎么处理两条广告分数相同时返回谁可以按 content 字典序、按插入时间先后、或者任意。关键是你要问出来并明确写进代码注释。score 可以变成负数吗如果 score 减到 0 还可以继续扣成 -1、-2 吗还是 score ≤ 0 的广告直接废弃这决定了减分后是否放回堆。只有一个广告时怎么办如果只有一条广告第一次返回了它第二次 GetAd() 应该返回什么题目隐含的逻辑是返回 null但你最好口头确认。并发场景需要考虑吗如果不考虑并发用单线程堆即可如果提到多线程需要讨论锁的粒度和线程安全。把这些 clarification 做在前面面试官会认为你是一个考虑周全的工程师而不是只会写代码的刷题人。复杂度分析InsertAd堆插入 O(log n)GetAd每次最多弹出两个广告再放回常数次堆操作O(log n)空间复杂度O(n)n 为广告总数一句话总结Max Heap 负责“找最高分”lastAd 负责“避免连续重复”。两个机制协作才能完整满足题目三条规则。这道题的陷阱不在算法本身而在于第二条规则对堆方案的单点破坏以及跳过广告后是否正确放回。想清楚这两个点代码写起来其实很顺。备考建议Google 的 OOD 或设计题经常走这个路线先用一个经典数据结构解决 80%再用一两个补充规则打乱你的初始方案看你能否在原有设计上做最小改动完成适配而不是推翻重来。练这类题的时候建议每次问自己如果规则再加一条我的代码需要改多少改动越小说明设计越稳健。如果自己在练的时候缺乏真实面试的压力感或者想知道自己的解法在 Google 面试官眼中能打几分oavoservice 的 VO 辅助 可以帮你安排一次全真模拟。导师都是在职大厂工程师会用 Google 风格的追问方式帮你找到逻辑盲区打磨表达的精准度。还在准备 OA 的同学oavoservice 的 OA 辅助 覆盖当前最新高频题包代码完全按你的习惯手写零查重风险确保一次通关。与其一个人对着题面猜边界不如让过来人带着你把每一处细节都过清楚。
Google 面试真题：Design Ad Server，一道题把 Heap 和 OOD 的细节考穿了
这次分享一道 Google 面试中出现的设计题。题目本身结构很清晰API 只有两个规则也只有三条但真正写起来会发现细节非常多——不能连续返回同一条广告这条规则直接把单纯的 Max Heap 方案卡住了。很多候选人第一反应是“堆排序取最大”然后被这条规则绊住后面的逻辑越补越乱。下面把这道题的完整拆解、正确解法、以及面试中应该主动确认的边界条件全部梳理出来。题目原文实现一个广告服务器提供两个 APIInsertAd(content, score)向可用广告池中插入一条广告。GetAd()返回当前最好的广告。规则score 越高广告越好。不能连续两次返回同一条广告。广告每被返回一次其 score 减 1。题目理解表面上看这是一个“总是取最高分”的问题Max Heap 天然适用。但第二条规则打破了这种直觉——如果你每次都从堆顶拿就可能连续两次拿到同一条广告违反规则。这就意味着堆不能单独解决问题。你必须额外维护一个“上次返回的广告”的引用在取广告时做一个判断堆顶是不是上一次刚返回的如果是就要临时跳过它取下一个。解题思路核心数据结构Max Heap last served ad 引用。InsertAd将广告对象包含 content、score放入 Max Heap。堆的比较器按 score 降序排列。如果分数相同可以按插入顺序或其他 tie-breaker 处理这一点面试时建议主动确认。GetAd如果堆为空返回 null。查看堆顶广告如果堆顶广告不是上一次返回的广告弹出堆顶记录为本次返回的广告。将其 score 减 1。如果 score 仍大于 0或题目允许负数则无所谓放回堆中。更新lastAd引用返回该广告。如果堆顶广告恰好是上一次返回的广告先将堆顶弹出暂存在一个临时变量中。查看新的堆顶即第二高分的广告如果堆为空说明整个广告池只有这一条广告且它刚被返回过。此时返回 null并将暂存的广告放回堆中。如果堆不为空弹出新的堆顶作为本次返回的广告。处理 score 减 1 和放回逻辑。更新lastAd引用。最后把暂存的广告放回堆中。关键细节不能只弹一个很多同学在第一版实现时会写成遇到lastAd在堆顶就跳过它取下一个取完把下一个减分放回然后结束。这漏掉了把跳过的广告放回去。如果不放回那这条广告就凭空消失了之后再也没机会被返回。正确的做法是被跳过的广告必须原封不动地放回堆中因为它在本次调用中并没有被返回不消耗 score。示例推演插入广告A: score 5B: score 4C: score 2调用次数操作堆状态lastAd返回1GetAd()A(5), B(4), C(2)nullA(5)A 弹出减分后放回A(4), B(4), C(2)A2GetAd()A(4), B(4), C(2)A堆顶是 A lastAd跳过 A取 BA(4), B(3), C(2)BB(4)3GetAd()A(4), B(3), C(2)B堆顶是 A ≠ B返回 AA(3), B(3), C(2)AA(3)第三步时A 因为在第二步被跳过并完整保留所以它仍然是最高分可以重新返回。边界条件面试时必须主动确认这类题在 Google 面试中的得分点不只在于写对逻辑还在于你能不能主动发现题目没写清楚的地方。建议在写代码前主动问Tie-breaker 怎么处理两条广告分数相同时返回谁可以按 content 字典序、按插入时间先后、或者任意。关键是你要问出来并明确写进代码注释。score 可以变成负数吗如果 score 减到 0 还可以继续扣成 -1、-2 吗还是 score ≤ 0 的广告直接废弃这决定了减分后是否放回堆。只有一个广告时怎么办如果只有一条广告第一次返回了它第二次 GetAd() 应该返回什么题目隐含的逻辑是返回 null但你最好口头确认。并发场景需要考虑吗如果不考虑并发用单线程堆即可如果提到多线程需要讨论锁的粒度和线程安全。把这些 clarification 做在前面面试官会认为你是一个考虑周全的工程师而不是只会写代码的刷题人。复杂度分析InsertAd堆插入 O(log n)GetAd每次最多弹出两个广告再放回常数次堆操作O(log n)空间复杂度O(n)n 为广告总数一句话总结Max Heap 负责“找最高分”lastAd 负责“避免连续重复”。两个机制协作才能完整满足题目三条规则。这道题的陷阱不在算法本身而在于第二条规则对堆方案的单点破坏以及跳过广告后是否正确放回。想清楚这两个点代码写起来其实很顺。备考建议Google 的 OOD 或设计题经常走这个路线先用一个经典数据结构解决 80%再用一两个补充规则打乱你的初始方案看你能否在原有设计上做最小改动完成适配而不是推翻重来。练这类题的时候建议每次问自己如果规则再加一条我的代码需要改多少改动越小说明设计越稳健。如果自己在练的时候缺乏真实面试的压力感或者想知道自己的解法在 Google 面试官眼中能打几分oavoservice 的 VO 辅助 可以帮你安排一次全真模拟。导师都是在职大厂工程师会用 Google 风格的追问方式帮你找到逻辑盲区打磨表达的精准度。还在准备 OA 的同学oavoservice 的 OA 辅助 覆盖当前最新高频题包代码完全按你的习惯手写零查重风险确保一次通关。与其一个人对着题面猜边界不如让过来人带着你把每一处细节都过清楚。
