Frequency Stack with Recency Tie-Breaking

Question

The question asks the candidate to implement a frequency stack that supports recency tie-breaking, allowing elements to be pushed onto the stack and popped based on their frequency and most recent usage.

Codemia · Accepted Answer

To solve the frequency stack problem, I will use two main data structures: a hash map to store the frequency of each element and a stack to keep track of elements based on their frequency. The stack will allow us to easily pop the most frequent elements, while the hash map will help us manage their counts efficiently.

1. **Push Operation**: When pushing an element, increase its frequency in the hash map. Then, push it onto the corresponding frequency stack. If the frequency stack does not exist, create it.
2. **Pop Operation**: To pop an element, retrieve the stack corresponding to the highest frequency, pop the most recent element from that stack, and decrease its frequency in the hash map. If the stack becomes empty, remove it from the hash map.

The time complexity for both push and pop operations is O(1) on average, since we are using hash maps and stacks for constant time access and modification. The space complexity is O(n), where n is the number of unique elements, as we need to store the frequency and the stacks.

```python
class FreqStack:
    def __init__(self):
        self.freq_map = {}
        self.freq_stack = {}
        self.max_freq = 0

def push(self, val: int) -> None:
        # Update frequency
        self.freq_map[val] = self.freq_map.get(val, 0) + 1
        freq = self.freq_map[val]
        # Update max frequency
        if freq > self.max_freq:
            self.max_freq = freq
        # Push to the stack of that frequency
        if freq not in self.freq_stack:
            self.freq_stack[freq] = []
        self.freq_stack[freq].append(val)

def pop(self) -> int:
        # Pop from the stack of the max frequency
        val = self.freq_stack[self.max_freq].pop()
        # Decrease the frequency
        self.freq_map[val] -= 1
        # If the stack is empty, decrease max frequency
        if not self.freq_stack[self.max_freq]:
            del self.freq_stack[self.max_freq]
            self.max_freq -= 1
        return val
```

Consider edge cases such as popping from an empty stack or pushing the same element multiple times. The implementation should handle these gracefully, ensuring that operations do not fail unexpectedly.

Frequency Stack with Recency Tie-Breaking

Amazon

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Approach

Algorithm

Submit Your Answer

Amazon Software Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string