Track Highest-Earning Experience
Company: Roblox
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
You are building a core component for a real-time analytics system that tracks the profitability of experiences on a large online platform.
Implement a function that processes a sequence of operations and returns the result of each query.
You are given three arrays of equal length:
- `operations[i]`: either `'U'` for an update or `'Q'` for a query
- `experiences[i]`: the name of the experience involved in operation `i`
- `deltas[i]`: the profit change for the experience if `operations[i] == 'U'`; otherwise this value is ignored
Rules:
- For an update operation `'U'`, add `deltas[i]` to the current total earnings of `experiences[i]`
- For a query operation `'Q'`, return the name of the experience with the highest total earnings at that moment
- If an experience has not been updated before, treat its earnings as `0` before applying its first update
- If multiple experiences are tied for the highest earnings, returning any one of them is acceptable
- You may assume each query happens after at least one update
Return an array containing the answers for all query operations, in order.
Example:
- `operations = ['U', 'U', 'Q', 'U', 'Q']`
- `experiences = ['GameA', 'GameB', '', 'GameA', '']`
- `deltas = [5, 7, 0, 4, 0]`
Processing:
- Update `GameA` by `+5` → totals: `GameA = 5`
- Update `GameB` by `+7` → totals: `GameB = 7`
- Query → return `GameB`
- Update `GameA` by `+4` → totals: `GameA = 9`
- Query → return `GameA`
Output: `['GameB', 'GameA']`
Design an efficient solution for processing many updates and queries.
Overview: This question evaluates the ability to maintain and query aggregated state with frequent updates, focusing on data structures for efficient real-time tracking of maximum values and dynamic key-value aggregations in the coding and algorithms domain.
You are building a real-time analytics component for an online platform. Given a sequence of update and query operations, return the answer for each query.
You are given three arrays of equal length:
- operations[i]: either 'U' for an update or 'Q' for a query
- experiences[i]: the experience name involved in operation i
- deltas[i]: the profit change if operations[i] == 'U'; otherwise it is ignored
Processing rules:
- For an update 'U', add deltas[i] to the current total earnings of experiences[i]
- For a query 'Q', return the name of the experience with the highest total earnings at that moment
- If an experience is updated for the first time, its previous total is 0
- If multiple experiences are tied for the highest earnings, any one of them is acceptable
- Queries only consider experiences that have been updated at least once so far
- You may assume every query happens after at least one update
Return a list containing the answers to all query operations in order.
Constraints
- 1 <= len(operations) == len(experiences) == len(deltas) <= 200000
- operations[i] is either 'U' or 'Q'
- For update operations, experiences[i] is a non-empty string
- -10^9 <= deltas[i] <= 10^9
- Each query occurs after at least one update
Examples
Input: (['U', 'U', 'Q', 'U', 'Q'], ['GameA', 'GameB', '', 'GameA', ''], [5, 7, 0, 4, 0])
Expected Output: ['GameB', 'GameA']
Explanation: GameA becomes 5, GameB becomes 7, so the first query returns GameB. After GameA is updated by 4, it becomes 9, so the second query returns GameA.
Input: (['U', 'U', 'U', 'Q', 'U', 'Q'], ['A', 'B', 'A', '', 'B', ''], [10, 8, -5, 0, -10, 0])
Expected Output: ['B', 'A']
Explanation: A goes 0->10->5, B goes 0->8->-2. After the third update, B has the highest total (8). After B decreases to -2, A has the highest total (5).
Hints
- Use a hash map to store the current total earnings for each experience.
- A single max variable is not enough if an update can decrease an experience's total. Consider a max-heap with lazy removal of outdated totals.
Community answers
Answer by feneberg.michael194
Test case 4 is incorect as it fails you even if you follow the spec, it says any query that is of the same size is acceptable but it rejects Y,Y and says you need X,Y even though Y and X are both 4.