Grokking the Coding Interview: Patterns for Coding Questions
Vote

0% completed

​

Solution: Problem Challenge 3: Frequency Stack

Problem Statement

Design a class that simulates a Stack data structure, implementing the following two operations:

  1. push(int num): Pushes the number num on the stack.
  2. pop(): Returns the most frequent number in the stack. If there is a tie, return the number which was pushed later.

Example:

After following push operations: push(1), push(2), push(3), push(2), push(1), push(2), push(5)

1. pop() should return 2, as it is the most frequent number
2. Next pop() should return 1
3. Next pop() should return 2

Constraints:

  • 0 <= val <= 10<sup>9</sup>

.....

.....

.....

Like the course? Get enrolled and start learning!
Saravana Balaji

Saravana Balaji

· 9 days ago

The given solution will not work and is flawed because there is no logic for deletion in the heap and they are not handling it correctly. Stack of stacks is the correct solution

Nemanja Milovančević

Nemanja Milovančević

· 2 months ago

For some reason, example testcases fail even when I copy-paste your solution,.

Show 1 reply
Mohammed Dh Abbas

Mohammed Dh Abbas

· 2 years ago

lets take this case 5,5,5,2,2,2,1,1,1

The output should be 5, 2, 1, 5, 2, 1, 5, 2, 1

initially all are the same but 5 got inserted first so it goes out. if we pop out 5 then we have more 2 and 2 got inserted before 1 then it gets popped out then 1

Here is my solution to the problem.

from heapq import *
import sys

class Element:
  def __init__(self, val, freq, time):
    self.val = val 
    self.freq = freq
    self.time = time
  
  def __lt__(self, other):
    # compare the frequencies first then compare the time
    if self.freq < other.freq:
        return True
    elif self.freq > other.freq:
        return False
    else:
        return self.time < other.time
    
class Solution:
  def __init__(self):
    self.max_heap = []
    self.tracker = {}
    self.time =
Show 1 reply
C

CaptainKidd

· 3 years ago

Could we not just check the frequency there and decrement and if it's 0 not push it back onto the heap?

Show 1 reply
B

Ben

· 4 years ago

Why do we not need to push the element back onto the heap during the pop() method??

Show 1 reply
W

Will

· 4 years ago

There's an optimal solution for this question using a 'stack of stacks' (more like a map of stacks) which runs in O(1) time instead of O(logn) time with this heap solution; both solutions have the same space complexity of O(n).

Although it doesn't follow this pattern, it may be useful to understand this alternate solution (see Leetcode Hard: 895. Maximum Frequency Stack).

Reading Progress

0%

Vote for new content