Rotating Title Selector
MediumHeap ยท Netflix
Implement TitleRotator, which keeps a score for each title on a homepage row.
upsert(title, score)sets the title's score, adding the title if it is new.remove(title)deletes the title and returns whether it was present.next()returns the title with the highest score, ties going to the lexicographically smaller title, but never the title returned by the previousnext()call while another title exists. It returns""when there are no titles.
Example 1
- Input:
- TitleRotator(), upsert("a", 5), upsert("b", 5), upsert("c", 3), next(), next(), next(), next()
- Output:
- [null, null, null, null, "a", "b", "a", "b"]
- Explanation
awins the tie withb. Each later call must skip the title just returned, so the top two alternate.
Example 2
- Input:
- TitleRotator(), upsert("x", 4), next(), next(), upsert("y", 1), next(), remove("x"), next()
- Output:
- [null, null, "x", "x", null, "y", true, "y"]
- Explanation
- A lone title may repeat; once
yexists,xis skipped.
Example 3
- Input:
- TitleRotator(), upsert("m", 9), next(), upsert("n", 2), upsert("m", 1), next(), next(), remove("q"), next()
- Output:
- [null, null, "m", null, null, "n", "m", false, "n"]
Constraints
- At most
10^5calls are made -10^9 <= score <= 10^9titleis a non-empty string of at most 20 lowercase letters and digits