Design an advertisement server that stores advertisements and returns the best eligible advertisement whenever requested.

Every advertisement has unique content and a score. A higher score gives the advertisement a higher priority.

After an advertisement is returned, decrease its score by 1. The same advertisement must not be returned in two consecutive GetAd calls.

If multiple eligible advertisements have the same score, return the advertisement whose content is lexicographically smaller.

Constructor

AdvertisementServer

AdvertisementServer()

Initialize an empty advertisement server.

Main Methods

InsertAd

void InsertAd(String adContent, int score)

Parameters

• adContent: The unique content of the advertisement.
• score: The advertisement's initial score.

Behavior

Insert an advertisement into the server. After this advertisement is returned, it is ineligible for the next GetAd call. This prevents it from being returned in two consecutive calls.

GetAd

String GetAd()

Returns

Return the eligible advertisement with the highest current score. If multiple eligible advertisements have the same score, return the one with lexicographically smaller content.

After returning an advertisement, decrease its score by 1.

Return an empty string if no advertisement is currently eligible. This call still counts when determining when delayed advertisements become eligible again.

An eligible advertisement may be returned even when its score is negative. Return an empty string only when no advertisement is currently eligible.

Follow-up Method

In the follow-up version, each advertisement has an additional delay value.

InsertAdWithDelay

void InsertAdWithDelay(String adContent, int score, int delay)

Parameters

• adContent: The unique content of the advertisement.
• score: The advertisement's initial score.
• delay: The number of subsequent GetAd calls during which the advertisement remains ineligible after being returned.

Behavior

Insert an advertisement with the specified delay. After the advertisement is returned, it cannot be returned during the next delay calls to GetAd.

The advertisement becomes eligible again after those calls have completed.

For example, if an advertisement with a delay of 2 is returned, it is unavailable for the next two GetAd calls and may be returned again on the third subsequent call.

Deterministic Ordering

• Prefer the eligible advertisement with the higher current score.
• If scores are equal, prefer the advertisement whose adContent is smaller according to Java's case-sensitive String.compareTo ordering.
• Advertisements with the same content are not inserted more than once.

Constraints

• 1 ≤ adContent.length() ≤ 100
• adContent contains visible ASCII characters.
• Every adContent value is unique.
• 0 ≤ score ≤ 1,000,000,000
• 1 ≤ delay ≤ 100,000
• At most 100,000 method calls are made.
• Calls to InsertAd and InsertAdWithDelay may be used on the same server.
• The current score of an advertisement may become negative after repeated selections.

Examples

Example 1: Consecutive Advertisements

AdvertisementServer()

InsertAd(adContent = "spring sale", score = 6)

InsertAd(adContent = "travel deal", score = 8)

InsertAd(adContent = "book offer", score = 8)

GetAd() returns "book offer". It wins the score tie lexicographically, and its score becomes 7.

GetAd() returns "travel deal". The previously returned advertisement is ineligible, and the score of "travel deal" becomes 7.

GetAd() returns "book offer". It is eligible again and has a higher score than "spring sale".

Example 2: Different Advertisement Delays

AdvertisementServer()

InsertAdWithDelay( adContent = "premium plan", score = 10, delay = 2 )

InsertAdWithDelay( adContent = "music trial", score = 8, delay = 1 )

InsertAdWithDelay( adContent = "game pass", score = 7, delay = 1 )

GetAd() returns "premium plan". Its score becomes 9, and it is unavailable for the next two calls.

GetAd() returns "music trial" because "premium plan" is delayed.

GetAd() returns "game pass" because the other two advertisements are delayed.

GetAd() returns "premium plan" because its two-call delay has ended.

Example 3: No Eligible Advertisement

AdvertisementServer()

InsertAdWithDelay( adContent = "daily offer", score = 5, delay = 2 )

GetAd() returns "daily offer".

GetAd() returns "" because the advertisement is delayed.

GetAd() returns "" because the advertisement remains delayed.

GetAd() returns "daily offer" because its two-call delay has ended.

Example 4: Mixing Both Insertion Methods

AdvertisementServer()

InsertAd(adContent = "food coupon", score = 9)

InsertAdWithDelay( adContent = "hotel discount", score = 8, delay = 3 )

GetAd() returns "food coupon".

GetAd() returns "hotel discount" because "food coupon" is ineligible.

GetAd() returns "food coupon" because it is eligible again while "hotel discount" is delayed.