Maximum Frequency Stack

HardStackdesign

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

Design a stack-like structure whose pop removes the **most frequent** value instead of simply the last one pushed. Implement: - FreqStack() creates an empty structure. - push(val) pushes the integer val. - pop() removes and returns one occurrence of the value that currently occurs most often. If several values tie for the highest count, remove the one whose latest occurrence is **closest to the top** (pushed most recently among the tied values). The removed occurrence is always that value's most recent one. pop is only called when the structure is non-empty. Both operations should be O(1).

Examples

Input: ["FreqStack","push","push","push","push","push","push","pop","pop","pop","pop"] [[],[4],[7],[4],[9],[7],[4],[],[],[],[]]
Output: [null,null,null,null,null,null,null,4,7,4,9]
4 occurs 3 times, so it is popped first. Then 4 and 7 each occur twice and 7 is nearer the top. Then 4 is the only value left with 2 copies. Finally all values have one copy and 9 is nearest the top.
Input: ["FreqStack","push","push","pop","push","pop","pop"] [[],[1],[2],[],[1],[],[]]
Output: [null,null,null,2,null,1,1]
With a tie, 2 was pushed last. Later 1 occurs twice and is popped, then its remaining copy.

Constraints

  • 0 <= val <= 10^9
  • `pop` is never called on an empty structure.
  • At most 2 * 10^4 calls in total.

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More design problems