At SDE3, the coding bar is not dramatically different in difficulty from SDE2. What changes is the expectation around speed, depth of optimisation, and the quality of communication under pressure.
Google L5 and L6 interviewers expect you to arrive at the optimal solution in 15 to 20 minutes, leaving the remaining time for follow-ups and edge case discussion. Amazon SDE3 coding rounds expect clean, well-explained code with zero hints. Meta E5 loops push speed hardest of all, with two problems in 35 minutes per round being the norm.
The problems in this blog are the ones most reported by senior candidates across FAANG loops. These are not the hardest problems that exist on LeetCode. They are the hard problems that actually appear in real senior interviews, repeatedly.
All solutions are in Python and have been manually verified for correctness.
What Makes SDE3 Coding Rounds Different From SDE2
Speed: You are expected to identify the optimal approach faster. Spending 10 minutes exploring a brute-force approach before pivoting costs you at SDE3 in a way it might not at SDE2.
Optimisation without prompting: At SDE2, the interviewer might ask "can you do better?" At SDE3, you are expected to raise the space or time optimisation yourself.
Follow-up depth: Senior interviewers go 3 to 4 follow-up questions deep. They want to see how you handle problem extensions you have not prepared for.
Communication quality: The clarity of your explanation matters as much as the solution itself. An SDE3 who cannot articulate their design clearly is not demonstrating leadership readiness.
Problem 1: Trapping Rain Water
Difficulty: Hard. Asked at: Google, Amazon, Meta, Netflix. One of the most consistently reported hard problems across all FAANG companies at senior level. LeetCode: #42
Problem Statement
Given an array height where height[i] represents the height of a bar at index i, compute how much water can be trapped after it rains.
Example:
Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Approach
For each index i, the water trapped above it equals:min(max_left[i], max_right[i]) - height[i]
where max_left[i] is the tallest bar to the left of i (including i) and max_right[i] is the tallest bar to the right.
A two-pointer approach avoids building the full prefix/suffix arrays and achieves O(1) space.
Use left and right pointers starting at both ends. At each step, process the side with the smaller max height. If max_left <= max_right, then the water above left is determined by max_left, so we can safely compute and add it. Move the pointer inward.
Solution (Two Pointer, O(1) Space)
python
def trap(height):
left, right = 0, len(height) - 1
max_left, max_right = 0, 0
water = 0
while left < right:
if height[left] <= height[right]:
if height[left] >= max_left:
max_left = height[left]
else:
water += max_left - height[left]
left += 1
else:
if height[right] >= max_right:
max_right = height[right]
else:
water += max_right - height[right]
right -= 1
return water
Trace Through [0,1,0,2,1,0,1,3,2,1,2,1]
left=0, right=11, max_left=0, max_right=0
h[0]=0 <= h[11]=1: max_left=0, water+=0-0=0. left=1
h[1]=1 <= h[11]=1: max_left=1, water+=0. left=2
h[2]=0 <= h[11]=1: water+=1-0=1. left=3
h[3]=2 > h[11]=1: max_right=1, water+=0. right=10
h[3]=2 > h[10]=2: max_right=2, water+=0. right=9
h[3]=2 > h[9]=1: water+=2-1=1. right=8
h[3]=2 > h[8]=2: max_right=2. right=7
h[3]=2 <= h[7]=3: max_left=2. left=4
h[4]=1 <= h[7]=3: water+=2-1=1. left=5
h[5]=0 <= h[7]=3: water+=2-0=2. left=6
h[6]=1 <= h[7]=3: water+=2-1=1. left=7
left=right=7, exit.
Total water = 0+0+1+0+0+1+0+1+2+1 = 6 ✓
Complexity
- Time: O(n)
- Space: O(1)
Why This Works
When height[left] <= height[right], the right side is at least as tall as the left side. So whatever the maximum on the left is, it is the binding constraint for water at left. We do not need to know the exact right maximum.
Follow-up Asked at Senior Level
"Extend this to Trapping Rain Water II (3D grid, LeetCode #407)."
The 3D version requires a min-heap (priority queue) for a BFS-like approach processing cells from the outside inward, always processing the lowest boundary cell first. This is an O(m x n x log(m x n)) solution and is a genuine hard-hard problem.
Problem 2: LRU Cache
Difficulty: Medium (but consistently treated as SDE3 level due to design complexity). Asked at: Google, Amazon, Meta, Netflix. Extremely high reported frequency at senior level across all FAANG companies. LeetCode: #146
Problem Statement
Design a data structure that follows a Least Recently Used (LRU) cache eviction policy. It should support:
get(key): Return the value if it exists, otherwise return -1.put(key, value): Insert or update the key. If the cache is at capacity, evict the least recently used item before inserting.
Both operations must run in O(1) time.
Example:
LRUCache cache = LRUCache(2) # capacity = 2
cache.put(1, 1)
cache.put(2, 2)
cache.get(1) # returns 1
cache.put(3, 3) # evicts key 2 (least recently used)
cache.get(2) # returns -1 (evicted)
cache.get(3) # returns 3
Approach
O(1) for both get and put requires:
- Hash map: for O(1) key lookup
- Doubly linked list: for O(1) insertion and removal of any node
The doubly linked list maintains usage order. The most recently used item is at the head. The least recently used is at the tail. Use two sentinel nodes (dummy head and dummy tail) to eliminate edge cases around empty list operations.
On every get or put of an existing key, move that node to the head. On put when at capacity, remove the tail node (LRU item) and delete it from the hash map.
Solution
python
class DLinkedNode:
def __init__(self, key=0, val=0):
self.key = key
self.val = val
self.prev = None
self.next = None
class LRUCache:
def __init__(self, capacity):
self.capacity = capacity
self.cache = {} # key -> DLinkedNode
# Sentinel head and tail
self.head = DLinkedNode()
self.tail = DLinkedNode()
self.head.next = self.tail
self.tail.prev = self.head
def _remove(self, node):
node.prev.next = node.next
node.next.prev = node.prev
def _insert_at_head(self, node):
node.next = self.head.next
node.prev = self.head
self.head.next.prev = node
self.head.next = node
def get(self, key):
if key not in self.cache:
return -1
node = self.cache[key]
self._remove(node)
self._insert_at_head(node)
return node.val
def put(self, key, value):
if key in self.cache:
node = self.cache[key]
node.val = value
self._remove(node)
self._insert_at_head(node)
else:
if len(self.cache) == self.capacity:
# Evict LRU: the node just before tail
lru = self.tail.prev
self._remove(lru)
del self.cache[lru.key]
node = DLinkedNode(key, value)
self.cache[key] = node
self._insert_at_head(node)
Trace Through the Example
put(1,1): cache={1:node1}. List: head <-> 1 <-> tail
put(2,2): cache={1:node1, 2:node2}. List: head <-> 2 <-> 1 <-> tail
get(1): move 1 to head. List: head <-> 1 <-> 2 <-> tail. Returns 1 ✓
put(3,3): capacity=2, evict LRU (tail.prev = node2, key=2).
cache={1:node1, 3:node3}. List: head <-> 3 <-> 1 <-> tail
get(2): key 2 not in cache. Returns -1 ✓
get(3): move 3 to head. Returns 3 ✓
Complexity
- Time: O(1) for both
getandput - Space: O(capacity)
Why Sentinel Nodes Matter
Without dummy head and tail, every insertion and removal requires null checks for edge cases (empty list, single node). Sentinels eliminate all of these, making the code cleaner and less error-prone in a live interview.
Problem 3: Serialize and Deserialize Binary Tree
Difficulty: Hard. Asked at: Google, Amazon, Meta. Reported consistently at L5 and senior level. LeetCode: #297
Problem Statement
Design an algorithm to serialize a binary tree to a string and deserialize that string back to the original tree. There is no restriction on the format.
python
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
Example:
Input tree:
1
/ \
2 3
/ \
4 5
serialize(root) -> "1,2,None,None,3,4,None,None,5,None,None"
deserialize(above) -> original tree
Approach
Use preorder traversal (root, left, right). During serialization, record each node's value. Record "None" when we encounter a null child. This encoding is self-describing: during deserialization, reading the values in order and recursively rebuilding produces the exact original tree.
Solution
python
class Codec:
def serialize(self, root):
result = []
def dfs(node):
if not node:
result.append("None")
return
result.append(str(node.val))
dfs(node.left)
dfs(node.right)
dfs(root)
return ",".join(result)
def deserialize(self, data):
values = iter(data.split(","))
def dfs():
val = next(values)
if val == "None":
return None
node = TreeNode(int(val))
node.left = dfs()
node.right = dfs()
return node
return dfs()
Trace Through the Example
Serialize DFS:
Visit 1 -> result=["1"]
Visit 2 -> result=["1","2"]
Visit None -> result=["1","2","None"]
Visit None -> result=["1","2","None","None"]
Visit 3 -> result=["1","2","None","None","3"]
Visit 4 -> result=["1","2","None","None","3","4"]
Visit None -> ["1","2","None","None","3","4","None"]
Visit None -> ["1","2","None","None","3","4","None","None"]
Visit 5 -> [...,"5"]
Visit None, None
Result: "1,2,None,None,3,4,None,None,5,None,None"
Deserialize reads values in order using iter():
next()=1 -> TreeNode(1)
next()=2 -> TreeNode(2)
next()=None -> return None (left of 2)
next()=None -> return None (right of 2)
next()=3 -> TreeNode(3)
next()=4 -> TreeNode(4)
next()=None, next()=None
next()=5 -> TreeNode(5)
next()=None, next()=None
Tree reconstructed correctly ✓
Complexity
- Time: O(n) for both serialize and deserialize
- Space: O(n) for the output string and recursion stack
Key Insight to Communicate in Interview
The use of iter() and next() lets us consume the values array across recursive calls without passing an index. This is cleaner than managing a global or mutable index variable and is the pattern senior interviewers expect to see.
Problem 4: Word Ladder
Difficulty: Hard. Asked at: Amazon, Google. Reported frequently in SDE3 and senior loops. Tests BFS on implicit graphs. LeetCode: #127
Problem Statement
Given a start word beginWord, an end word endWord, and a dictionary wordList, return the number of words in the shortest transformation sequence from beginWord to endWord. Each step changes exactly one letter. Every intermediate word must be in wordList. Return 0 if no sequence exists.
Example:
Input:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log","cog"]
Output: 5
Explanation: "hit" -> "hot" -> "dot" -> "dog" -> "cog"
Approach
This is a shortest-path problem on an implicit graph where nodes are words and edges connect words that differ by one letter. BFS gives the shortest path in an unweighted graph.
For each word in the queue, generate all possible one-letter transformations by replacing each character with 'a' to 'z'. If the transformation is in the word set, add it to the queue and remove it from the set (to avoid revisiting). Track the number of levels to measure path length.
Solution
python
from collections import deque
def ladder_length(beginWord, endWord, wordList):
word_set = set(wordList)
if endWord not in word_set:
return 0
queue = deque([(beginWord, 1)]) # (word, level)
visited = {beginWord}
while queue:
word, level = queue.popleft()
for i in range(len(word)):
for c in 'abcdefghijklmnopqrstuvwxyz':
new_word = word[:i] + c + word[i+1:]
if new_word == endWord:
return level + 1
if new_word in word_set and new_word not in visited:
visited.add(new_word)
queue.append((new_word, level + 1))
return 0
Trace Through the Example
word_set = {"hot","dot","dog","lot","log","cog"}
queue = [("hit", 1)], visited = {"hit"}
Process ("hit", 1):
Replace each char with a-z:
"hot" is in word_set, not visited -> queue=[("hot",2)], visited+="hot"
(no other valid transforms)
Process ("hot", 2):
"dot" in word_set -> queue=[("dot",3)]
"lot" in word_set -> queue=[("dot",3),("lot",3)]
Process ("dot", 3):
"dog" in word_set -> queue=[("lot",3),("dog",4)]
Process ("lot", 3):
"log" in word_set -> queue=[("dog",4),("log",4)]
Process ("dog", 4):
"cog" == endWord -> return 4+1 = 5 ✓
Complexity
- Time: O(M x N x 26) where M is word length, N is number of words in the list
- Space: O(N) for the queue and visited set
Why DFS Cannot Be Used Here
DFS finds a path, not the shortest path. BFS level-by-level traversal guarantees the first time we reach the endWord is via the shortest sequence. This distinction is something senior interviewers probe explicitly.
Problem 5: Merge K Sorted Lists
Difficulty: Hard. Asked at: Amazon, Google, Meta, Netflix. Very high frequency at SDE2 and SDE3. LeetCode: #23
Problem Statement
Given an array of k linked lists, each sorted in ascending order, merge all the lists into one sorted linked list and return it.
python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
Example:
Input: lists = [[1,4,5], [1,3,4], [2,6]]
Output: [1,1,2,3,4,4,5,6]
Approach
Use a min-heap. Push the first node of each non-empty list into the heap. At each step, extract the smallest node, append it to the result, and push that node's next node into the heap.
Python's heapq compares tuples element by element. Since ListNode objects are not comparable, push (node.val, index, node) where index is a unique tie-breaker preventing comparison of ListNode objects.
Solution
python
import heapq
def merge_k_lists(lists):
dummy = ListNode(0)
current = dummy
heap = []
for i, node in enumerate(lists):
if node:
heapq.heappush(heap, (node.val, i, node))
while heap:
val, i, node = heapq.heappop(heap)
current.next = node
current = current.next
if node.next:
heapq.heappush(heap, (node.next.val, i, node.next))
return dummy.next
Trace Through the Example
lists = [1->4->5, 1->3->4, 2->6]
Initial heap: [(1,0,node1_0), (1,1,node2_0), (2,2,node3_0)]
Pop (1,0,node1_0=1): append 1. Push (4,0,node1_1). heap=[(1,1,n2_0),(2,2,n3_0),(4,0,n1_1)]
Pop (1,1,node2_0=1): append 1. Push (3,1,node2_1). heap=[(2,2,n3_0),(3,1,n2_1),(4,0,n1_1)]
Pop (2,2,node3_0=2): append 2. Push (6,2,node3_1). heap=[(3,1,n2_1),(4,0,n1_1),(6,2,n3_1)]
Pop (3,1,node2_1=3): append 3. Push (4,1,node2_2). heap=[(4,0,n1_1),(4,1,n2_2),(6,2,n3_1)]
Pop (4,0,node1_1=4): append 4. Push (5,0,node1_2). heap=[(4,1,n2_2),(5,0,n1_2),(6,2,n3_1)]
Pop (4,1,node2_2=4): append 4. No next. heap=[(5,0,n1_2),(6,2,n3_1)]
Pop (5,0,node1_2=5): append 5. No next. heap=[(6,2,n3_1)]
Pop (6,2,node3_1=6): append 6. No next. heap=[]
Result: 1->1->2->3->4->4->5->6 ✓
Complexity
- Time: O(N log k) where N is total number of nodes, k is number of lists
- Space: O(k) for the heap
Why the Tie-Breaker Index Matters
Without the i index in the tuple, Python will attempt to compare ListNode objects when two values are equal, causing a TypeError. The index makes every tuple unique, so ListNode comparison never occurs.
How Senior Interviewers Evaluate These Problems
The evaluation rubric shifts at SDE3. These are the signals that distinguish Hire from Strong Hire at senior level:
Pattern named immediately: Before writing a single line, saying "this is a two-pointer problem where the binding constraint comes from the shorter side" shows senior-level pattern recognition.
Optimal approach without prompting: At SDE3, exploring a brute force solution is acceptable only as a 30-second verbal mention before moving to optimal. Starting to code the brute force is a signal against.
Follow-up extensions handled fluently: Senior interviewers will extend every problem. For Trapping Rain Water, expect the 3D variant. For LRU Cache, expect "add a TTL expiry feature." For Merge K Lists, expect "what if lists are too large to fit in memory?" Having a framework for these extensions matters.
Code quality: Senior engineers are expected to produce clean, production-adjacent code. Meaningful variable names, no magic numbers, edge cases handled cleanly without a wall of if-else statements.
Practising These at the Right Level
The problems above are not difficult to understand after reading a solution. They are difficult to produce correctly, quickly, and with clear narration under a 45-minute time limit.
That specific combination is a skill that only develops through repeated practice under conditions that mirror the real interview.
At Intervue.io, SDE3 mock sessions are conducted by senior engineers who have been in real FAANG hiring loops at this level. The feedback is calibrated to SDE3 expectations: not just whether you solved it, but whether you solved it at the speed and quality a senior hire is expected to demonstrate.
Visit intervue.io to book an SDE3 mock session.
FAQs
Are these problems actually asked at SDE3 or are they just LeetCode Hard? These are drawn from verified candidate reports from 2025 and 2026 FAANG loops. LRU Cache, Trapping Rain Water, Serialize and Deserialize Binary Tree, Word Ladder, and Merge K Sorted Lists are among the most frequently reported hard-difficulty problems across real senior interview experiences.
How fast should I solve a hard problem at SDE3 level?T he expectation is an optimal solution in 15 to 25 minutes, leaving the rest of the 45-minute round for follow-ups and edge case discussion. If you are regularly taking 35 minutes to arrive at the optimal approach, speed practice under timed conditions is the priority.
Is LRU Cache really Hard difficulty? It says Medium on LeetCode. LeetCode rates it Medium. In practice, it is one of the most tricky problems to implement correctly under time pressure because it requires co-ordinating a doubly linked list and a hash map simultaneously. The sentinel node pattern is something most candidates forget under stress. It is consistently treated as a senior-level problem in real interviews.
What is the most common mistake candidates make on Word Ladder? Using DFS instead of BFS. DFS finds a path from start to end but does not guarantee it is the shortest. BFS guarantees the shortest path in an unweighted graph. Arriving at DFS on a shortest-path problem is a clear signal to the interviewer that the candidate has not internalised when to use which traversal.
What follow-up should I prepare for LRU Cache? "Add a TTL (time-to-live) to each entry so that entries expire after a fixed duration." The clean extension: store the expiry timestamp alongside each node, and check it during get. Use a separate background sweep or lazy deletion on access. Being able to extend the design fluently in real time is the senior signal.
Summary
The most frequently reported hard coding problems in SDE3 and senior FAANG loops:
- Trapping Rain Water: Two-pointer approach; binding constraint comes from the shorter side
- LRU Cache: Hash map plus doubly linked list with sentinel nodes; O(1) for all operations
- Serialize and Deserialize Binary Tree: Preorder DFS with None markers; use
iter()for clean deserialization - Word Ladder: BFS on an implicit word graph; never use DFS for shortest-path problems
- Merge K Sorted Lists: Min-heap with tie-breaker index; O(N log k)
Know why each approach works. Arrive at the optimal solution without prompting. Handle follow-ups without rewriting your core logic.
Visit intervue.io to practice these problems in a real SDE3 mock session.
