Grokking the Coding Interview: Patterns for Coding Questions

0% completed

​

Problem Challenge 3: Frequency Stack (hard)

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!
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).

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
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
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