Coding Interview Resources

🚀 Coding Interview Questions with Answers — Part 4

🗂️ Stacks, Queues & Heaps

🚀 31. How do you implement a stack with a max-stack (O(1) max query)?

A Max Stack supports:
• Push
• Pop
• Get Maximum Element in O(1)

🔹 Idea
Maintain:
1. Main stack
2. Max stack

Max stack stores current maximums.

🔹 Python Solution

class MaxStack:
    def __init__(self):
        self.stack = []
        self.max_stack = []

    def push(self, value):
        self.stack.append(value)

        if not self.max_stack or value >= self.max_stack[-1]:
            self.max_stack.append(value)

    def pop(self):
        if self.stack[-1] == self.max_stack[-1]:
            self.max_stack.pop()

        return self.stack.pop()

    def get_max(self):
        return self.max_stack[-1]

🔹 Complexity
Operation - Complexity
Push - O(1)
Pop - O(1)
Get Max - O(1)

🔹 Interview Tip
Very common design-based stack question.

🚀 32. How do you implement a queue using two stacks?

Queues are FIFO. Stacks are LIFO.
We can combine two stacks.

🔹 Idea
Stack1 → enqueue
Stack2 → dequeue

🔹 Python Solution

class Queue:
    def __init__(self):
        self.s1 = []
        self.s2 = []

    def enqueue(self, value):
        self.s1.append(value)

    def dequeue(self):
        if not self.s2:
            while self.s1:
                self.s2.append(self.s1.pop())

        return self.s2.pop()

🔹 Complexity
Operation - Complexity
Enqueue - O(1)
Dequeue - Amortized O(1)

🔹 Interview Tip
Interviewers love this because it tests understanding of stack behavior.

🚀 33. How do you design a stack that supports getMin() in O(1)?

Very similar to Max Stack.

🔹 Idea
Maintain:
• Main stack
• Min stack

🔹 Python Solution

class MinStack:
    def __init__(self):
        self.stack = []
        self.min_stack = []

    def push(self, value):
        self.stack.append(value)

        if not self.min_stack or value <= self.min_stack[-1]:
            self.min_stack.append(value)

    def pop(self):
        if self.stack[-1] == self.min_stack[-1]:
            self.min_stack.pop()

        return self.stack.pop()

    def get_min(self):
        return self.min_stack[-1]

🔹 Complexity
Operation - Complexity
Push - O(1)
Pop - O(1)
Get Min - O(1)

🔹 Interview Tip
This is one of the highest-frequency interview problems.

🚀 34. What is a monotonic stack and when is it useful?

A monotonic stack maintains elements in:
• Increasing order OR
• Decreasing order

🔹 Uses
✅ Next Greater Element
✅ Largest Rectangle in Histogram
✅ Stock Span Problem
✅ Daily Temperatures

🔹 Example

arr = [2, 1, 3]

stack = []

for num in arr:
    while stack and stack[-1] > num:
        stack.pop()

    stack.append(num)

🔹 Complexity
Most monotonic stack problems:
O(n)

because every element is pushed and popped once.

🔹 Interview Tip
Extremely important pattern for medium/hard problems.

🚀 35. How do you implement a priority queue / heap?

A heap is a complete binary tree.

Types:
• Min Heap
• Max Heap

🔹 Python Min Heap

import heapq

heap = []

heapq.heappush(heap, 10)
heapq.heappush(heap, 5)
heapq.heappush(heap, 20)

print(heapq.heappop(heap))

🔹 Output
5

🔹 Complexity
Operation - Complexity
Insert - O(log n)
Delete - O(log n)
Peek - O(1)

🔹 Uses
✅ Task scheduling
✅ Dijkstra’s algorithm
✅ Top K problems
✅ Priority processing

🚀 36. How do you find the top K frequent elements?

🔹 Approach
1. Count frequency using hashmap
2. Use heap

🔹 Python Solution

from collections import Counter
import heapq

def top_k(nums, k):
    freq = Counter(nums)

    return heapq.nlargest(k, freq.keys(), key=freq.get)

print(top_k([1, 1, 1, 2, 2, 3], 2))

🔹 Output
[1, 2]

🔹 Complexity
Complexity - Value
Time - O(n log k)
Space - O(n)

🔹 Interview Tip
Heap + hashmap combination is frequently tested.

1K viewsedited 22:44