这次 Google 面试考了一道很典型的 OOD + Heap 设计题。面试记录显示，这场面试总用时约 2 小时 11 分钟。

题目原文

Implement an ad server with two APIs,

InsertAd(content, score) that inserts an ad to the set of available ads,
and GetAd() that returns the best ad among them.

These are the rules:

An ad is better if it has a higher score.
Do not return the same ad consecutively.
Once served, the ad's score is reduced by 1.

中文理解

实现一个广告服务器，有两个接口：

InsertAd(content, score)：插入一条广告。
GetAd()：返回当前最好的广告。

规则是：

1. score 越高，广告越好。
2. 不能连续两次返回同一条广告。
3. 广告每被返回一次，score 减 1。

解题思路

这题核心可以用：

Max Heap + last served ad

因为每次都要拿当前最高分广告，所以用 max heap 最合适。

但题目要求不能连续返回同一条广告，所以还要记录上一次返回的广告 lastAd。

InsertAd 很简单，把广告放进 heap。

GetAd 时：

1. 先取 heap 顶部广告。
2. 如果它不是上一次返回的广告，直接返回它。
3. 返回后 score 减 1，再放回 heap。
4. 如果 heap 顶部广告刚好是上一次返回的广告，就临时跳过它，取第二高的广告。
5. 第二高广告返回后 score 减 1，再放回 heap，同时把刚才跳过的广告也放回去。

如果只有一条广告，并且它刚刚被返回过，那么这次 GetAd() 应该返回 null。

例子

假设插入：

A: 5
B: 4
C: 2

第一次 GetAd() 返回 A，A 变成 4。

第二次不能继续返回 A，所以返回 B，B 变成 3。

第三次可以重新返回 A，因为上一次返回的是 B。

复杂度

InsertAd：O(log n)

GetAd：O(log n)

因为最多只会弹出两个广告，再放回去，仍然是常数次 heap 操作。

空间复杂度是 O(n)。

总结

这题不难，但很考察细节。最关键的是不能只想到 heap，还要处理“不能连续返回同一条广告”这个限制。

一句话总结：

用 max heap 找最高分广告，用 lastAd 避免连续返回同一个广告。

面试时还可以主动问清楚 tie-breaker、score 是否能变成负数、只有一个广告时如何处理，这些边界情况讲清楚会比较加分。

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