FastPrep
Problem · Hash Table

Maximum Frequency Stack

Learn this problem
● HardInMobi logoInMobiFULLTIMEPHONE SCREEN

Problem statement

Process a sequence of operations on a frequency stack. A frequency stack supports the following operations:

  • push adds an integer to the top of the stack.
  • pop removes and returns an element whose current frequency in the stack is greatest. If several elements have the same greatest frequency, remove the one closest to the top of the stack.

The arrays operations and values have the same length. For index i:

  • If operations[i] is "push", push values[i].
  • If operations[i] is "pop", ignore values[i], perform a pop, and append the removed value to the result.

Return the popped values in operation order.

Function

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

Examples

Example 1

operations = ["push","push","push","push","push","push","pop","pop","pop","pop"]values = [5,7,5,7,4,5,0,0,0,0]return = [5,7,5,4]

The first pop removes 5 because it occurs three times. The next pop removes 7 because 5 and 7 are then tied and 7 is closer to the top. The final two pops return 5 and 4.

Example 2

operations = ["push","push","pop","pop"]values = [1,2,0,0]return = [2,1]

Both values have frequency 1, so the first pop removes 2, which is closer to the top. The next pop removes 1.

Example 3

operations = ["push","push","push","pop"]values = [9,9,3,0]return = [9]

Value 9 has frequency 2, which is greater than the frequency of 3.

Constraints

  • 1 ≤ operations.length = values.length ≤ 20,000
  • operations[i] is either "push" or "pop".
  • 0 ≤ values[i] ≤ 10^9 when operations[i] is "push".
  • Every pop operation occurs while the stack is non-empty.

More InMobi problems

drafts saved locally
public int[] processFrequencyStack(String[] operations, int[] values) {
  // write your code here
}
operations["push","push","push","push","push","push","pop","pop","pop","pop"]
values[5,7,5,7,4,5,0,0,0,0]
expected[5,7,5,4]
checking account