An ad server logs one record per impression (an ad being shown). Each record is a pair of strings [timestamp, ad_id], where timestamp is a non-negative integer written in decimal, possibly with leading zeros ("0042" is 42). Records are not sorted.
Implement:
def most_common_ads(impressions: list[list[str]], k: int, start: int, end: int) -> list[str]
Consider only the records whose timestamp t satisfies start <= t <= end (compare as numbers, not strings: "9" < "10" as integers). Return the k ad ids shown most often in that window, most impressions first. Ads with the same count are ordered by ad_id in ascending string order, compared character by character (case-sensitive, so "B" comes before "a", as with Python's < on strings). If fewer than k ads appear in the window, return all of them. Ads with no impressions in the window never appear in the answer.
log = [["10", "shoes"], ["3", "tea"], ["12", "shoes"], ["007", "tea"],
["11", "lamp"], ["9", "lamp"], ["20", "shoes"], ["8", "tea"]]
most_common_ads(log, 2, 5, 12) # ["lamp", "shoes"] window 5..12: lamp 2, shoes 2, tea 2 -> ties by name
most_common_ads(log, 1, 0, 100) # ["shoes"] shoes 3, tea 3 -> "shoes" < "tea"
most_common_ads(log, 5, 13, 19) # []
Constraints: up to 200,000 records and 100,000 distinct ads, 1 <= k <= 100,000, 0 <= start <= end. Count in one pass; don't rescan the log once per ad.
Show hint
Count with a dictionary, then pick the k best with a heap keyed on (-count, ad_id). Sorting everything is also fine when k is close to the number of distinct ads.