How should I practice Max Frequency Tracker?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Procol phone screen problems in FastPrep.

Is Max Frequency Tracker associated with Procol?

FastPrep tags this as a Procol phone screen coding practice problem when the problem catalog has that company and stage context.

Max Frequency Tracker

Procol● MediumFULLTIMEPHONE SCREEN

Problem statement

Design a data structure that keeps a frequency for each element. It starts empty. Process the operations in operations in order. For each index i, values[i] holds the element used by operations[i].

"get_elem": increase the frequency of element values[i] by 1. If the element is not present, add it with frequency 1.
"pop_element": remove element values[i] completely, whatever its frequency. If the element is not present, nothing happens.
"get_max": record the present element with the highest frequency. If several elements share the highest frequency, record the one that reached that frequency first. If no element is present, record -1.

An element reaches its current frequency at its latest "get_elem". After an element is removed, it may be added again later. It then starts over with frequency 1.

Return the recorded values of all "get_max" operations, in order. If there are no "get_max" operations, return an empty array.

Follow-up: Can you make every operation run in O(1) time?

Function

runFrequencyTracker(operations: String[], values: int[]) → int[]

Examples

Example 1

operations = ["get_elem","get_elem","get_elem","get_max","get_elem","get_max","get_elem","get_max","pop_element","get_max"]values = [5,3,5,0,3,0,3,0,3,0]return = [5,5,3,5]

After the first three operations, element 5 has frequency 2 and element 3 has frequency 1, so the first "get_max" records 5. The next "get_elem" raises 3 to frequency 2. Both elements now have frequency 2, but 5 reached it first, so 5 is recorded again.

Element 3 then reaches frequency 3 and is recorded. After 3 is removed, only 5 is left, so the last "get_max" records 5.

Example 2

operations = ["get_elem","get_elem","get_max","get_elem","get_elem","get_max","get_elem","get_max"]values = [7,2,0,2,7,0,9,0]return = [7,2,2]

Elements 7 and 2 both have frequency 1, and 7 got there first, so 7 is recorded. Next, 2 reaches frequency 2 before 7 does, so the tie at frequency 2 goes to 2. Adding 9 gives it only frequency 1, so 2 is recorded again.

Example 3

operations = ["get_max","pop_element","get_elem","get_elem","get_elem","get_elem","pop_element","get_elem","get_max","get_elem","get_max"]values = [0,4,4,4,4,6,4,4,0,4,0]return = [-1,6,4]

The first "get_max" finds no element and records -1. Removing 4 while it is not present does nothing.

Element 4 is added three times and then removed, so its frequency of 3 is gone. When 4 is added again, it starts over at frequency 1. It ties with 6, which reached frequency 1 first, so 6 is recorded. One more "get_elem" lifts 4 to frequency 2, so 4 is recorded last.

Constraints

1 <= operations.length <= 10^4
values.length == operations.length
Each operations[i] is "get_elem", "pop_element", or "get_max".
0 <= values[i] <= 10^9
If operations[i] is "get_elem" or "pop_element", then values[i] >= 1.
If operations[i] is "get_max", then values[i] == 0.