Google OA Interview Coding Question: Maximum Frequency Stack

Design a data structure that supports the following operations:

• push(x): pushes an integer x onto the stack
• pop(): removes and returns the most frequent element in the stack. If there is a tie for the most frequent element, remove the one closest to the top

Implement the class to support these operations efficiently.

This problem asks you to design a frequency stack that behaves like a stack but pops the most frequent element first, breaking ties by recency. A standard solution uses a hash map to track each value’s frequency, another map from frequency to a stack of values, and a variable for the current maximum frequency. With this structure, both push and pop can be handled efficiently, typically in O(1) time.