Top 10 Heap Problems for FAANG interview

Heaps (priority queues) are very popular in FAANG interviews, especially for problems involving efficient min/max tracking, top-k elements, and interval merging. Here's a curated top 10 heap problems, along with what to focus on for each.

Top 10 Heap Problems for FAANG

1. Merge K Sorted Lists

• Problem: Given k sorted linked lists, merge them into one sorted list.
• Concept: Use a min-heap to always extract the smallest head node among all lists.
• Time: O(N log k), where N is total number of nodes.

2. Top K Frequent Elements

• Problem: Given an array, return the k most frequent elements.
• Concept: Use a min-heap of size k to maintain top frequencies.
• Variants: Strings, numbers, hashtags, etc.

3. Kth Largest/Smallest Element in Array

• Problem: Find the kth largest or smallest element in an unsorted array.

• Concept:

  • Min-heap of size k for largest
  • Max-heap of size k for smallest

• Time: O(n log k)

4. Sliding Window Maximum

• Problem: Given an array and window size k, return the max of each sliding window.
• Concept: Heap can solve it, but deque is more efficient (O(n))—interviewers may ask both.

5. Connect Ropes with Minimum Cost

• Problem: Given rope lengths, connect all into one rope with minimum cost (sum of lengths at each merge).
• Concept: Use a min-heap to always merge the two shortest ropes first.
• Classic greedy + heap problem.

6. Median from Data Stream

• Problem: Continuously insert numbers and find median efficiently.

• Concept: Maintain two heaps:

  • Max-heap for left half
  • Min-heap for right half

• Time: O(log n) per insertion

7. K Closest Points to Origin

• Problem: Given points on 2D plane, return k closest to origin.
• Concept: Use a max-heap of size k to maintain closest points.
• Variants: Closest stores, closest numbers, closest cars, etc.

8. Reorganize String / Rearrange Characters

• Problem: Rearrange characters so no two adjacent characters are the same.
• Concept: Use a max-heap to always pick the most frequent character next.

9. Find K Pairs with Smallest Sums

• Problem: Given two sorted arrays, return k pairs with smallest sums.
• Concept: Use min-heap to track next smallest sum pair efficiently.

10. Online Stock Price / Max in Sliding Interval

• Problem: Track max or min price in a time interval or online stream.
• Concept: Heap helps maintain the maximum/minimum efficiently when updates happen.

⚡ Heap Interview Tips

1. Know both min-heap and max-heap implementations in Java (PriorityQueue) and Python (heapq).
2. Be comfortable with heap of custom objects using comparators (Java) or tuples (Python).
3. Time complexity trick: insert = O(log n), extract = O(log n).
4. Many problems can also be solved with sorting, but heap gives better complexity for top-k or streaming data.