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 = -sys.maxsize # the smallest time goes first / its the oldest "no max heap in python"

  def push(self, num):
    freq = self.tracker.get(num, 0)
    freq -= 1
    self.time += 1
    element = Element(num, freq, self.time)
    
    self.tracker[num] = freq
    heappush(self.max_heap, element)

  def pop(self):
    while self.max_heap:
      element = heappop(self.max_heap)
      freq = element.freq
      # if the heap contains a dirty element "element with the wrong frequency as a result of an old push. just pop it out"
      if freq != self.tracker[element.val]:
        continue
      freq += 1
      # if frequency is 0 clean up the tracking map and return the element
      if freq == 0 and element.val in self.tracker:
        del self.tracker[element.val]
        return element.val
      # if all good. decrement the tracker and push the new updates to the heap
      if freq < 0:
        self.tracker[element.val] = freq
        heappush(self.max_heap, Element(element.val, freq, self.time))
        return element.val
      
    return float('inf')


sol = Solution() 

input = [5,5,5,2,2,2,1,1,1]
for i in input:
  sol.push(i)

for i in range(9):
  x = sol.pop()
  print(x)

BTW. this question is very tricky and I don't think any company should ask for something like this in an interview!