这次分享一道 Google 的 Coding 面试真题。题目围绕广告投放系统（Ad Server）展开，从基础的广告优先级选择，到加入不同广告的冷却时间，主要考察数据结构设计、状态维护以及动态调度逻辑。
Part 1: Basic Ad Server
Design an AdServer class with two APIs:
- InsertAd(content, score): Insert a new advertisement with a score.
- GetAd(): Return the best eligible advertisement.
Requirements:
- Always select the ad with the highest score.
- Never return the same ad twice consecutively.
- After an ad is served, decrease its score by 1.
Part 2: Ad Cooldown / Delay
Extend the existing implementation to support:
- InsertAd(content, score, delay)
- GetAd() (remains unchanged)
Additional requirements:
- delay specifies how many other ads must be served before the same ad can be served again.
- Each ad can have a different delay.
设计一个广告投放系统 AdServer，支持插入广告和获取当前最合适的广告。
第一部分：基础广告系统
系统需要提供两个接口：
InsertAd(content, score)：插入一条广告，并设置初始分数。GetAd()：返回当前符合条件且分数最高的广告。
每次获取广告时，必须选择分数最高的可用广告，但不能连续两次返回同一条广告。同时，一条广告每被投放一次，其分数就减少 1。
第二部分：广告冷却机制
现在为每条广告增加一个 delay 参数。
delay 表示某条广告投放后，必须先投放多少条其他广告，才能再次投放该广告。不同广告可以设置不同的冷却时间。
例如，广告 A 的 delay = 2，那么 A 被投放后，必须先投放两条其他广告，A 才能再次参与选择。
第一部分看起来是简单的最大值选择，但由于广告分数会动态变化，而且不能连续投放同一条广告，直接维护一个最大值并不能解决问题。
一种常见思路是使用最大堆（Max Heap）管理广告分数，同时记录上一条投放的广告。每次选择时，需要跳过当前不符合条件的广告，选出分数最高的可用广告，再更新其分数和状态。
第二部分是这道题真正需要注意的地方。
加入 delay 后，系统不仅需要维护广告的分数，还需要追踪每条广告何时能够重新参与投放。
这里的关键是：冷却时间并不是实际经过的秒数，而是其他广告被投放的次数。
因此，可以考虑使用投放序号来维护每条广告的下一次可用位置，将广告分为可投放和冷却中的两类。
面试中比较容易出错的地方包括冷却计数的边界条件、多个广告分数相同时的选择、广告分数降低后的优先级调整，以及所有广告都处于冷却状态时如何处理。
尤其需要注意，不能为了跳过冷却期而忽略最高分规则，也不能把一次未成功的 GetAd() 调用当作一次有效投放。
这道题的难点不在代码量，而在于如何让多个动态规则同时成立，并且保证每一次选择的正确性。
总结
Google 这道题采用了比较典型的递进式设计：先实现基础功能，再引入新的业务约束，观察候选人能否在已有设计上合理扩展。
对于这类题目，除了熟悉 Heap 等数据结构，更重要的是提前明确状态变化、边界条件和规则之间的关系。
csoahelp 持续整理 Google、Apple、Stripe 等公司的真实技术面试题目，同时提供 Mock Interview 和面试实时文本辅助服务，帮助求职者熟悉英文技术面试的节奏、梳理解题思路，并练习如何清晰地向面试官表达自己的方案。
我们也有代面试，面试辅助，OA代写等服务助您早日上岸~
