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.
Quick Answer: 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.