Popular Content Stream
MediumData Structures · Atlassian
You are building the "most popular" widget for a content platform. Each element of events is [action, content_id], processed in order. Every content id starts with a score of 0, and the actions change it as follows:
"VIEW"adds1to the content's score."UPVOTE"adds3."DOWNVOTE"subtracts2(scores can go negative)."DELETE"removes the content entirely. If the same id appears again later, it starts over from0. Deleting an id that does not exist does nothing.
After every event, record the content id with the highest score, considering only content whose score is strictly greater than 0. If several ids share the highest score, record the lexicographically smallest one. If no content has a positive score, record the empty string "".
Return the list of recorded ids, one per event.
Example 1
- Input:
- events = [["VIEW", "home"], ["UPVOTE", "faq"], ["VIEW", "home"], ["VIEW", "home"], ["DELETE", "faq"], ["DOWNVOTE", "home"]]
- Output:
- ["home", "faq", "faq", "faq", "home", "home"]
- Explanation
homeleads at 1 until the upvote putsfaqat 3. Two more views bringhometo 3 as well, and the tie goes to the smaller id,faq. Oncefaqis deleted,homeleads, and it still has a positive score of 1 after the downvote.
Example 2
- Input:
- events = [["DOWNVOTE", "a"], ["VIEW", "a"], ["VIEW", "a"], ["VIEW", "a"]]
- Output:
- ["", "", "", "a"]
- Explanation
- The downvote leaves
aat -2, and the views raise it to -1, then 0, then 1. Only at 1 is the score positive, so the first three results are empty.
Example 3
- Input:
- events = [["UPVOTE", "x"], ["DELETE", "x"], ["VIEW", "x"]]
- Output:
- ["x", "", "x"]
- Explanation
- After the delete nothing is left. The view then creates
xagain from 0, so its score is 1, not 4.
Constraints
0 <= events.length <= 10^5actionis one of"VIEW","UPVOTE","DOWNVOTE","DELETE".content_idis a non-empty string of letters, digits and dashes; ids are case-sensitive.