Google OA 面试真题解析：Ad Server with Score Decay and Cooldown

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.

这道题考察的是“广告调度器”的设计：每次调用 GetAd 时，都要在满足限制的候选广告里选出分数最高的一个，同时还要避免连续两次返回同一条广告，并在投放后将该广告分数减 1。第二部分进一步加入每条广告独立的冷却时间 delay，本质上需要用优先队列维护当前可投放广告的最高分，用另一个队列或时间表记录尚未冷却完成的广告，按“已投放次数 / 时间”决定何时重新进入候选集合。实现时要特别注意并列分数、同一广告的重复投放限制，以及分数衰减后对后续排序的影响。