Interview Preptop-k-elementshardAmazonFacebookGoogle

Frequency Stack (Max Frequency First)

Choose your preparation mode4 modes available

Try It Solution Trace

📋

Problem

Imagine a social media platform where you want to show the most frequently interacted posts first, but if two posts have the same frequency, the most recent one should appear first.

Design a stack-like data structure that supports push and pop operations. The pop operation removes and returns the element with the highest frequency. If multiple elements have the same highest frequency, pop the most recently pushed one among them. Implement the class FreqStack with methods push(int val) and pop() that behave as described.

1 ≤ number of operations ≤ 10^5Values pushed are integers in the range [0, 10^9]pop() will only be called if the stack is non-empty

Edge cases: pop() called when only one element is present → returns that elementmultiple elements with same frequency pushed in different orders → pop returns most recentall elements have frequency 1 → pop returns most recently pushed element

</>

IDE

class FreqStack:
    def __init__(self):
        pass
    def push(self, val: int) -> None:
        pass
    def pop(self) -> int:
        pass

class FreqStack:
    def __init__(self):
        # Write your solution here
        pass
    def push(self, val: int) -> None:
        pass
    def pop(self) -> int:
        pass

public class FreqStack {
    public FreqStack() {
        // Write your solution here
    }
    public void push(int val) {
    }
    public int pop() {
        return 0;
    }
}

class FreqStack {
public:
    FreqStack() {
        // Write your solution here
    }
    void push(int val) {
    }
    int pop() {
        return 0;
    }
};

class FreqStack {
    constructor() {
        // Write your solution here
    }
    push(val) {
    }
    pop() {
        return 0;
    }
}

0/9

Common Bugs to Avoid

Wrong: Pop returns element with max frequency but ignores recency order.Not using stacks per frequency; popping any max frequency element instead of most recent.✅ Maintain a stack for each frequency and pop from the stack of current max frequency.

Wrong: Pop returns incorrect element when multiple pushes of same element occur.Frequency not incremented on repeated pushes of same element.✅ Increment frequency count on every push of the element.

Wrong: Pop returns elements in FIFO order instead of LIFO when frequencies tie.Not maintaining recency order within frequency groups.✅ Use stacks (LIFO) per frequency to maintain recency order.

Wrong: Solution times out on large inputs.Brute force approach scanning entire stack on each pop causing O(n^2) complexity.✅ Use frequency map and stacks per frequency for O(1) amortized push and pop.

✓

Test Cases

t1_01basic

Input["push(5)","push(7)","push(5)","push(7)","push(4)","push(5)","pop()","pop()","pop()","pop()"]

Expected[null,null,null,null,null,null,5,7,5,4]

After pushing, frequencies are: 5↓3, 7↓2, 4↓1. pop() returns 5 (highest freq), next pop returns 7 (freq 2), next pop returns 5 (freq 2 after previous pop), last pop returns 4.

t1_02basic

Input["push(1)","push(2)","push(3)","push(2)","push(1)","push(2)","push(5)","pop()","pop()","pop()","pop()"]

Expected[null,null,null,null,null,null,null,2,2,1,5]

Frequencies after pushes: 2↓3, 1↓2, 3↓1, 5↓1. pop() returns 2 (freq 3), next pop returns 2 (freq 2), next pop returns 1 (freq 2), last pop returns 5 (freq 1).

Practice

(1/5)

1. You are given a list of words and need to find the top k words that appear most frequently, with ties broken by lexicographical order. Which algorithmic approach guarantees an optimal solution in terms of time complexity?

easy

A. Sort all unique words by frequency descending and lex order ascending, then pick top k

B. Use a dynamic programming approach to count frequencies and select top k

C. Use a greedy approach by repeatedly picking the most frequent word until k are chosen

D. Use bucket sort by frequency, then sort words lexicographically within each bucket, and collect top k

Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard

Frequency Stack (Max Frequency First)

Practice

Solution

Step 1: Understand frequency distribution

Step 2: Use bucket sort to group words by frequency

Final Answer:

Quick Check:

Solution

Step 1: Identify partition logic

Step 2: Locate bug

Final Answer:

Quick Check:

Solution

Step 1: Identify loops and heap operations

Step 2: Analyze heap operations per coordinate

Final Answer:

Quick Check:

Solution

Step 1: Understand duplicates impact

Step 2: Modify partition to handle duplicates correctly

Final Answer:

Quick Check:

Solution

Step 1: Understand infinite reuse impact

Step 2: Recognize problem class change

Step 3: Bucket sort no longer applies

Final Answer:

Quick Check:

Ready to prove it?