SDE2 FAANG Interview Questions: Heaps, Binary Search & Sliding Window

Three patterns separate candidates who clear SDE2 coding rounds from those who don't: heaps, binary search on answer space, and advanced sliding window.

At SDE1, heaps barely appear. At SDE2, they show up in problems that require dynamic ordering, top-K elements, median tracking, and scheduling. Binary search at SDE2 is no longer just "find a target in a sorted array", interviewers expect you to recognise when to binary search on the answer itself. Sliding window problems at this level involve more complex conditions and follow-ups that require moving beyond the basic expand-and-contract template.

This blog covers the most frequently reported problems from these three areas in Amazon SDE2, Google L4, Meta E4, and product company senior engineer loops, with verified solutions and full complexity analysis.

All solutions are in Python. Every solution is traced through its example.

What SDE2 Expects Across These Three Patterns

Heaps: You should be able to use Python's heapq module fluently. Know that Python's heapq is a min-heap by default, for max-heap behaviour, negate values. Understand when to use a heap vs. sorting (heap is better for dynamic streams where you keep adding elements).

Binary Search on Answer Space: The pattern: if a problem asks for a minimum or maximum value satisfying some monotonic condition, binary search over the answer range. This is harder to recognise than binary search on a sorted array, and that difficulty is exactly why it appears at SDE2.

Sliding Window at SDE2: The window condition becomes more complex. Instead of "all characters are unique," you might have "at most K distinct elements" or "product less than K." The expand-contract logic remains, but choosing what to track inside the window requires more thought.

Part 1: Heap Problems

Problem 1: Kth Largest Element in an Array

Difficulty: Medium. Asked at: Amazon, Google, Meta, extremely high frequency; tests heap fundamentals. LeetCode: #215

Problem Statement

Given an integer array nums and an integer k, return the kth largest element in the array. Note: it is the kth largest in sorted order, not the kth distinct element.

Example:

Input:  nums = [3, 2, 1, 5, 6, 4], k = 2
Output: 5

Approach

Maintain a min-heap of size k. Iterate through every number. Push each number onto the heap. If the heap exceeds size k, pop the smallest element. After processing all numbers, the top of the heap is the kth largest.

Why a min-heap of size k works: the smallest element in the heap is always the kth largest seen so far. Any element smaller than the current kth largest gets pushed out.

Solution

python

import heapq

def find_kth_largest(nums, k):
   min_heap = []

   for num in nums:
       heapq.heappush(min_heap, num)
       if len(min_heap) > k:
           heapq.heappop(min_heap)

   return min_heap[0]  # smallest in heap = kth largest overall

Trace Through [3, 2, 1, 5, 6, 4], k=2

num=3: heap=[3]
num=2: heap=[2,3]
num=1: heap=[1,2,3] → size>2 → pop min=1 → heap=[2,3]
num=5: heap=[2,3,5] → pop min=2 → heap=[3,5]
num=6: heap=[3,5,6] → pop min=3 → heap=[5,6]
num=4: heap=[4,5,6] → pop min=4 → heap=[5,6]

heap[0] = 5 (smallest in heap = 2nd largest) ✓

Complexity

• Time: O(n log k) - each of n elements pushed/popped from a heap of size k
• Space: O(k) - heap stores at most k elements

Follow-up Interviewers Ask

"Can you do this in O(n) average time?"

Yes. QuickSelect algorithm. Partition the array around a pivot (like QuickSort). If the pivot lands at index n-k, we found our answer. Recurse only on the relevant partition. Average O(n), worst case O(n²).

Problem 2: Top K Frequent Elements

Difficulty: Medium. Asked at: Amazon, Google, very high frequency at SDE2; combines hashing and heap. LeetCode: #347

Problem Statement

Given an integer array nums and an integer k, return the k most frequent elements. The answer can be in any order.

Example:

Input:  nums = [1, 1, 1, 2, 2, 3], k = 2
Output: [1, 2]

Approach

First, count the frequency of each element using a hash map. Then use a min-heap of size k to track the top-k most frequent. Heap stores (frequency, element) pairs. After processing all elements, the heap contains the k most frequent.

Solution

python

import heapq
from collections import Counter

def top_k_frequent(nums, k):
   freq = Counter(nums)  # {element: count}
   min_heap = []

   for num, count in freq.items():
       heapq.heappush(min_heap, (count, num))
       if len(min_heap) > k:
           heapq.heappop(min_heap)

   return [num for count, num in min_heap]

Trace Through [1,1,1,2,2,3], k=2

freq = {1:3, 2:2, 3:1}

Push (3,1): heap=[(3,1)]
Push (2,2): heap=[(2,2),(3,1)]
Push (1,3): heap=[(1,3),(3,1),(2,2)] → pop min=(1,3) → heap=[(2,2),(3,1)]

Output: [2, 1] — both are correct (order doesn't matter) ✓

Complexity

• Time: O(n log k) - counting is O(n), heap operations are O(log k) per element
• Space: O(n) - frequency map; O(k) for the heap

Bucket Sort Alternative (O(n) time)

python

def top_k_frequent_bucket(nums, k):
   freq = Counter(nums)
   buckets = [[] for _ in range(len(nums) + 1)]
   for num, count in freq.items():
       buckets[count].append(num)

   result = []
   for i in range(len(buckets) - 1, 0, -1):
       for num in buckets[i]:
           result.append(num)
           if len(result) == k:
               return result
   return result

Mentioning this O(n) alternative in an interview is a strong signal at SDE2 level.

Problem 3: Find Median from Data Stream

Difficulty: Hard. Asked at: Google, Amazon, Meta, one of the most reported hard problems at SDE2/L4 level; tests two-heap design. LeetCode: #295

Problem Statement

Design a data structure that supports:

• add_num(num) - adds a number to the data structure
• find_median() - returns the median of all numbers added so far

Example:

add_num(1) → stream = [1]       → find_median() = 1.0
add_num(2) → stream = [1, 2]    → find_median() = 1.5
add_num(3) → stream = [1, 2, 3] → find_median() = 2.0

Approach

Use two heaps:

• small - a max-heap for the lower half of numbers (simulate with negation in Python)
• large - a min-heap for the upper half

Invariant: len(small) == len(large) or len(small) == len(large) + 1

The median is:

• small[0] (negated) if small has one more element
• Average of -small[0] and large[0] if sizes are equal

Adding a number:

1. Push to small (max-heap). Pop the max of small and push to large (this ensures large always has values ≥ all values in small).
2. If large becomes larger than small, pop from large and push back to small.

Solution

python

import heapq

class MedianFinder:
   def __init__(self):
       self.small = []  # max-heap (negate values)
       self.large = []  # min-heap

   def add_num(self, num):
       # Push to small (max-heap)
       heapq.heappush(self.small, -num)
       # Balance: ensure max of small <= min of large
       if self.small and self.large and (-self.small[0]) > self.large[0]:
           heapq.heappush(self.large, -heapq.heappop(self.small))
       # Balance sizes: small can have at most 1 more element than large
       if len(self.small) > len(self.large) + 1:
           heapq.heappush(self.large, -heapq.heappop(self.small))
       if len(self.large) > len(self.small):
           heapq.heappush(self.small, -heapq.heappop(self.large))

   def find_median(self):
       if len(self.small) > len(self.large):
           return float(-self.small[0])
       return (-self.small[0] + self.large[0]) / 2.0

Trace Through add(1), add(2), add(3)

add(1):
 Push -1 to small → small=[-1]
 large is empty, no balance needed
 sizes: small=1, large=0 → ok
 find_median() → -(-1) = 1.0 ✓

add(2):
 Push -2 to small → small=[-2,-1] (heap: -2 at top)
 -(-2)=2 > large[nothing]? large empty, skip
 small size 2 > large size 0 + 1 → rebalance:
   pop -2 from small → push 2 to large
   small=[-1], large=[2]
 find_median() → (-(-1) + 2) / 2 = 1.5 ✓

add(3):
 Push -3 to small → small=[-3,-1]
 -(-3)=3 > large[0]=2 → rebalance:
   pop -3 from small → push 3 to large
   small=[-1], large=[2,3]
 large(2) > small(1) → rebalance:
   pop 2 from large → push -2 to small
   small=[-2,-1], large=[3]
 find_median() → small size > large size → -(-2) = 2.0 ✓

Complexity

• Time: O(log n) for add_num, O(1) for find_median
• Space: O(n)

Part 2: Binary Search on Answer Space

Problem 4: Find Minimum in Rotated Sorted Array

Difficulty: Medium. Asked at: Amazon, Google, standard rotated array binary search; very high frequency. LeetCode: #153

Problem Statement

Given a sorted array that has been rotated between 1 and n times, find the minimum element. All elements are unique.

Example:

Input:  nums = [3, 4, 5, 1, 2]
Output: 1

Input:  nums = [4, 5, 6, 7, 0, 1, 2]
Output: 0

Approach

The array has two sorted halves. The minimum is at the rotation point, the only place where the value is less than its predecessor. Binary search: if nums[mid] > nums[right], the minimum is in the right half. Otherwise it's in the left half (including mid).

Solution

python

def find_min(nums):
   left, right = 0, len(nums) - 1

   while left < right:
       mid = left + (right - left) // 2
       if nums[mid] > nums[right]:
           # Minimum is in the right half
           left = mid + 1
       else:
           # Minimum is in the left half (including mid)
           right = mid

   return nums[left]

Trace Through [3, 4, 5, 1, 2]

left=0, right=4
mid=2, nums[2]=5, nums[4]=2. 5 > 2 → left=3

left=3, right=4
mid=3, nums[3]=1, nums[4]=2. 1 < 2 → right=3

left=3, right=3 → exit

nums[3] = 1 ✓

Complexity

• Time: O(log n)
• Space: O(1)

Problem 5: Koko Eating Bananas

Difficulty: Medium. Asked at: Google, Amazon, binary search on answer space; one of the most reported "non-obvious" binary search problems at SDE2. LeetCode: #875

Problem Statement

Koko has n piles of bananas. She can eat at most k bananas per hour. She wants to eat all bananas in h hours. Find the minimum integer k such that she can eat all bananas within h hours.

Example:

Input:  piles = [3, 6, 7, 11], h = 8
Output: 4

Why This Is Binary Search on Answer Space

The key insight: as k increases, the number of hours needed decreases (monotonic). We can binary search on the value of k between 1 and max(piles). For each candidate k, check if Koko can finish in h hours.

Hours needed for a pile of size p at speed k = ceil(p / k) = (p + k - 1) // k using integer arithmetic.

Solution

python

import math

def min_eating_speed(piles, h):
   left, right = 1, max(piles)

   def can_finish(k):
       hours = sum(math.ceil(p / k) for p in piles)
       return hours <= h

   while left < right:
       mid = left + (right - left) // 2
       if can_finish(mid):
           right = mid  # try slower (smaller k)
       else:
           left = mid + 1  # need to go faster

   return left

Trace Through piles=[3,6,7,11], h=8

left=1, right=11

mid=6: hours=ceil(3/6)+ceil(6/6)+ceil(7/6)+ceil(11/6)=1+1+2+2=6 ≤ 8 → can finish. right=6
mid=3: hours=ceil(3/3)+ceil(6/3)+ceil(7/3)+ceil(11/3)=1+2+3+4=10 > 8 → can't. left=4
mid=5: hours=ceil(3/5)+ceil(6/5)+ceil(7/5)+ceil(11/5)=1+2+2+3=8 ≤ 8 → can finish. right=5
mid=4: hours=ceil(3/4)+ceil(6/4)+ceil(7/4)+ceil(11/4)=1+2+2+3=8 ≤ 8 → can finish. right=4

left=4, right=4 → exit

Output: 4 ✓

Complexity

• Time: O(n log m) - where m is max(piles), n is number of piles
• Space: O(1)

Part 3: Advanced Sliding Window

Problem 6: Longest Substring with At Most K Distinct Characters

Difficulty: . at: Google, Amazon, Meta, sliding window with a more complex window condition than SDE1 problems. LeetCode: #340

Problem Statement

Given a string s and an integer k, return the length of the longest substring that contains at most k distinct characters.

Example:

Input:  s = "eceba", k = 2
Output: 3  ("ece" has 2 distinct characters)

Approach

Sliding window with a hash map tracking character frequencies in the current window. Expand right. When the number of distinct characters (keys in the map) exceeds k, shrink from left, decrement that character's count and remove it from the map when count reaches zero. Track the maximum window size.

Solution

python

from collections import defaultdict

def length_of_longest_substring_k_distinct(s, k):
   if k == 0:
       return 0

   char_count = defaultdict(int)
   left = 0
   max_length = 0

   for right in range(len(s)):
       char_count[s[right]] += 1

       # Shrink window while more than k distinct chars
       while len(char_count) > k:
           char_count[s[left]] -= 1
           if char_count[s[left]] == 0:
               del char_count[s[left]]
           left += 1

       max_length = max(max_length, right - left + 1)

   return max_length

Trace Through s="eceba", k=2

right=0, char='e': count={'e':1}. distinct=1≤2. window="e", len=1
right=1, char='c': count={'e':1,'c':1}. distinct=2≤2. window="ec", len=2
right=2, char='e': count={'e':2,'c':1}. distinct=2≤2. window="ece", len=3
right=3, char='b': count={'e':2,'c':1,'b':1}. distinct=3>2.
 Shrink: s[0]='e' → count={'e':1,'c':1,'b':1}. left=1. still 3>2
 Shrink: s[1]='c' → del 'c'. count={'e':1,'b':1}. left=2. distinct=2≤2
 window="eb", len=2
right=4, char='a': count={'e':1,'b':1,'a':1}. distinct=3>2.
 Shrink: s[2]='e' → del 'e'. count={'b':1,'a':1}. left=3. distinct=2≤2
 window="ba", len=2

max_length = 3 ✓

Complexity

• Time: O(n) - each character added and removed at most once
• Space: O(k) - hash map stores at most k+1 keys before shrinking

Problem 7: Minimum Window Substring

Difficulty: Hard. Asked at: Google, Amazon, Meta, most challenging sliding window problem reported at SDE2 level; tests complete mastery of the pattern. LeetCode: #76

Problem Statement

Given strings s and t, return the minimum window substring of s that contains every character in t (including duplicates). Return an empty string if no such window exists.

Example:

Input:  s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"

Approach

Two hash maps: need (character counts required from t) and window (character counts in current window). Track have (how many characters are satisfied) and need_count (how many unique characters we need to satisfy).

A character is "satisfied" when its count in the window meets or exceeds its count in need. Expand right and update window. When have == need_count, we have a valid window, try to shrink from left to minimise. Record the minimum window seen.

Solution

python

from collections import Counter

def min_window(s, t):
   if not t or not s:
       return ""

   need = Counter(t)
   need_count = len(need)  # number of unique chars to satisfy

   window = {}
   have = 0  # number of unique chars currently satisfied
   left = 0
   min_len = float('inf')
   result = ""

   for right in range(len(s)):
       char = s[right]
       window[char] = window.get(char, 0) + 1

       # Check if this char's requirement is now satisfied
       if char in need and window[char] == need[char]:
           have += 1

       # Try to shrink window while valid
       while have == need_count:
           # Record if this is the smallest valid window
           if right - left + 1 < min_len:
               min_len = right - left + 1
               result = s[left:right + 1]

           # Shrink from left
           left_char = s[left]
           window[left_char] -= 1
           if left_char in need and window[left_char] < need[left_char]:
               have -= 1
           left += 1

   return result

Trace Through s="ADOBECODEBANC", t="ABC"

need = {'A':1, 'B':1, 'C':1}, need_count = 3

Expanding right until all 3 satisfied:
After right=5 (char='C'): window has A,B,C → have=3
Valid window: s[0:6]="ADOBEC" (len=6)

Shrink left:
left=0 (char='A'): window['A']=0 < need['A']=1 → have=2. left=1

Expand right until have=3 again...
right=10 (char='B'): have=3
Valid window: s[1:11]="DOBECODEBA" — check "BANC" at end...

Eventually: right=12 (char='C'): have=3
Valid window: s[10:13]="BANC" (len=4) — new minimum

Final result: "BANC" ✓

Complexity

• Time: O(|s| + |t|) - each character in s visited at most twice
• Space: O(|s| + |t|) - two hash maps

What SDE2 Interviewers Specifically Look For

Across heap, binary search, and sliding window problems at SDE2 level, the signals that drive offer decisions:

On Heaps:

• Can you explain why a min-heap of size k gives you the k-th largest? (Not just that it works, why)
• Do you proactively mention the QuickSelect O(n) alternative for Kth Largest?
• For Find Median, can you clearly explain the two-heap invariant before writing code?

On Binary Search:

• Can you recognise that Koko Eating Bananas is a binary search problem even though there's no sorted array?
• Do you articulate the monotonic condition: "as k increases, hours needed decreases"?

On Sliding Window:

• Do you choose the right condition for shrinking the window?
• Do you handle the case where the window contains more than needed correctly?
• For Minimum Window, do you track have and need_count separately, or do you recompute the whole window on each step?

Practising These Patterns Before Your SDE2 Loop

The two-heap approach for Find Median and the binary search on answer space for Koko are the problems where most SDE2 candidates fail, not because they couldn't eventually solve them, but because they couldn't arrive at the right approach fast enough in a live session.

Both require pattern recognition under pressure. That specific skill only develops through practice in interview-like conditions.

At Intervue.io, SDE2 mock sessions include problems calibrated to the medium-hard difficulty of Google L4, Amazon SDE2, and Meta E4 loops. The structured feedback after each session tells you not just whether you got the answer, but whether you got there fast enough and communicated it clearly enough to pass.

👉 Book an SDE2 mock session on Intervue.io

FAQs

How does Python's heapq work, is it a min-heap or max-heap? Python's heapq module implements a min-heap only. The smallest element is always at index 0. For a max-heap, negate values before pushing and negate them again when popping. This is the standard Python interview convention and interviewers expect you to know it.

When should I use binary search on answer space instead of on a sorted array? When the problem asks for a minimum or maximum value satisfying some condition, and the feasibility of that condition changes monotonically as the value increases or decreases. The tell: "find the minimum X such that condition Y is satisfied." Koko, Capacity to Ship Packages, Split Array Largest Sum, all binary search on answer space.

Is Minimum Window Substring really expected at SDE2, or is it more SDE3? It's reported at SDE2 level at Google and Meta. At Amazon SDE2, it appears less frequently. It's a strong indicator of sliding window mastery, knowing the have/need_count tracking pattern is the key signal. Practice it at SDE2, but don't deprioritise the medium problems in this blog.

Can I solve Kth Largest with sorting instead of a heap? Yes, sorted(nums)[-k] gives the correct answer in O(n log n) time. But interviewers will ask you to optimise. The heap solution is O(n log k), which is better when k << n. Know the heap solution from the start and mention the sort as the brute force.

What's the most important thing to say before writing sliding window code? Define what the window represents and what the shrink condition is. "I'll maintain a window where the number of distinct characters is at most k. I'll shrink from the left when that count exceeds k." This one sentence tells the interviewer you understand the approach, before you write a single line.

Summary

The most frequently asked SDE2 heap, binary search, and sliding window problems at FAANG and product companies:

Heaps:

• Kth Largest Element - min-heap of size k; O(n log k)
• Top K Frequent Elements - frequency count + min-heap; mention O(n) bucket sort alternative
• Find Median from Data Stream - two-heap design; explain the invariant before coding

Binary Search on Answer Space:

• Find Minimum in Rotated Sorted Array - compare mid to right to determine which half to search
• Koko Eating Bananas - binary search on k between 1 and max(piles); check feasibility with ceiling division

Sliding Window:

• Longest Substring with At Most K Distinct Characters - hash map tracks distinct chars; shrink when count exceeds k
• Minimum Window Substring - track have/need_count; shrink while valid window exists

Know why each approach works, not just that it works. State complexity unprompted. Name the pattern before coding.

👉 Practice these patterns in a live SDE2 mock on Intervue.io