Top Five Stories by Latest Popularity
Meta● MediumFULLTIMEPHONE SCREENProblem statement
A stream reports stories and their popularity scores. The same story may appear more than once with a new score.
You receive the completed stream as two arrays, stories and scores, of equal length. Update i assigns scores[i] to the story named stories[i]. Process updates in array order. A new score replaces that story's previous score, even when the new score is lower.
After processing every update, return the names of up to 5 distinct stories whose final score is at least cutoff.
- Rank qualifying stories by final score in descending order.
- Break equal-score ties by story name in ascending lexicographical order.
- Return every qualifying story when fewer than
5qualify, and return an empty array when none qualify. - Only the final ranking is returned; intermediate rankings are not part of the result.
Function
topFiveStories(stories: String[], scores: int[], cutoff: int) → String[]Examples
Example 1
stories = ["a","b","c","a","d","e","f"]scores = [90,75,80,40,65,95,85]cutoff = 60return = ["e","f","c","b","d"]The final score of a is 40, so its earlier score of 90 does not make it qualify. The five remaining stories have scores 95, 85, 80, 75, and 65 in the returned order.
Example 2
stories = ["z","b","a","c"]scores = [50,50,50,49]cutoff = 50return = ["a","b","z"]A score equal to cutoff qualifies. The three qualifying stories all have score 50, so they are ordered by name.
Example 3
stories = ["news","news"]scores = [80,20]cutoff = 30return = []The last update replaces 80 with 20. No story's final score reaches 30.
Example 4
stories = []scores = []cutoff = 0return = []The empty stream contains no stories, so the result is empty.
Constraints
0 <= stories.length == scores.length <= 2 * 10^5.1 <= stories[i].length <= 30.- Story names contain only lowercase English letters and digits. Equal names identify the same story.
0 <= scores[i], cutoff <= 10^9.- The arrays are ordered from the first update to the last update.