At SDE3 and senior level, dynamic programming and graph problems show up in their harder forms. The patterns from SDE2 are assumed. What gets tested is your ability to recognise less obvious DP formulations, handle graph problems with more constraints, and extend your solution under follow-up questioning without needing a reset.
This blog covers the advanced DP and graph problems most reported by senior engineers in Google L5, Amazon SDE3, and Meta E5 coding rounds in 2025 and 2026. Every solution is fully verified and traced through its example.
What Changes at SDE3 for DP and Graphs
On DP: The problems are not always harder in terms of the solution complexity. What is harder is the state definition. Senior candidates are expected to identify the DP formulation faster, define the state precisely before coding, and optimise space without prompting.
On Graphs: The problems at SDE3 often involve constraints layered on top of standard BFS or DFS. Cycle detection in directed graphs, topological sort with dependency resolution, and BFS on implicitly defined graphs all appear. Dijkstra for weighted shortest paths is an SDE3 expectation at Google and Amazon.
Part 1: Advanced Dynamic Programming
Problem 1: Longest Increasing Subsequence
Difficulty: Medium (but the O(n log n) optimisation is the SDE3 expectation) Asked at: Google, Amazon, Meta. Reported frequently at senior level. The O(n log n) solution is explicitly required at L5 and above. LeetCode: #300
Problem Statement
Given an integer array nums, return the length of the longest strictly increasing subsequence.
Example:
Input: nums = [10,9,2,5,3,7,101,18]
Output: 4
Explanation: [2,3,7,101] or [2,5,7,101] are both valid.
Approach 1: O(n^2) DP (mention and move on at SDE3)
python
def length_of_LIS_n2(nums):
n = len(nums)
dp = [1] * n
for i in range(1, n):
for j in range(i):
if nums[j] < nums[i]:
dp[i] = max(dp[i], dp[j] + 1)
return max(dp)
This is the baseline. At SDE3, you should name this and then immediately offer the O(n log n) version.
Approach 2: O(n log n) with Binary Search (expected at SDE3)
Maintain a tails array where tails[i] is the smallest possible tail value of any increasing subsequence of length i + 1 seen so far. For each number, binary search to find where it fits.
Key property: tails is always sorted, which is why binary search works.
python
import bisect
def length_of_LIS(nums):
tails = []
for num in nums:
pos = bisect.bisect_left(tails, num)
if pos == len(tails):
tails.append(num)
else:
tails[pos] = num
return len(tails)
Trace Through [10,9,2,5,3,7,101,18]
num=10: tails=[], pos=0=len(tails). Append. tails=[10]
num=9: bisect_left([10],9)=0. Replace. tails=[9]
num=2: bisect_left([9],2)=0. Replace. tails=[2]
num=5: bisect_left([2],5)=1=len(tails). Append. tails=[2,5]
num=3: bisect_left([2,5],3)=1. Replace. tails=[2,3]
num=7: bisect_left([2,3],7)=2=len(tails). Append. tails=[2,3,7]
num=101:bisect_left([2,3,7],101)=3=len(tails). Append. tails=[2,3,7,101]
num=18: bisect_left([2,3,7,101],18)=3. Replace. tails=[2,3,7,18]
len(tails) = 4 ✓
Note: tails does not represent the actual subsequence. It represents the minimum tail values. The length is correct but you cannot reconstruct the sequence from tails directly.
Complexity
- Time: O(n log n)
- Space: O(n)
What the Interviewer Probes at SDE3
"Can you reconstruct the actual subsequence, not just its length?"
Yes. Maintain a parent array and a position array tracking where each element was placed in tails. Trace back through parent from the last placed element. This adds O(n) space and no asymptotic time cost.
Problem 2: Word Break
Difficulty: Medium. Asked at: Amazon, Google. Reported in senior loops as a DP problem with a graph framing follow-up. LeetCode: #139
Problem Statement
Given a string s and a dictionary wordDict, return True if s can be segmented into one or more dictionary words.
Example:
Input: s = "leetcode", wordDict = ["leet","code"]
Output: True
Input: s = "applepenapple", wordDict = ["apple","pen"]
Output: True
Input: s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]
Output: False
Approach
Define dp[i] as True if the substring s[:i] can be segmented into dictionary words.
Base case: dp[0] = True (empty string is always valid).
Transition: For each position i, check all positions j < i. If dp[j] is True and s[j:i] is in the word set, then dp[i] = True.
Solution
python
def word_break(s, wordDict):
word_set = set(wordDict)
n = len(s)
dp = [False] * (n + 1)
dp[0] = True
for i in range(1, n + 1):
for j in range(i):
if dp[j] and s[j:i] in word_set:
dp[i] = True
break # no need to check further j values for this i
return dp[n]
Trace Through s="leetcode", wordDict=["leet","code"]
word_set = {"leet","code"}
dp = [T, F, F, F, F, F, F, F, F]
i=1: j=0: dp[0]=T, s[0:1]="l" not in set.
i=2: j=0: s[0:2]="le" no. j=1: dp[1]=F.
i=3: j=0: s[0:3]="lee" no. j=1,2: dp=F.
i=4: j=0: dp[0]=T, s[0:4]="leet" in set! dp[4]=True. break.
i=5: j=0..4: s[0:5]="leetc" no, ..., j=4: dp[4]=T, s[4:5]="c" no.
i=6: j=4: dp[4]=T, s[4:6]="co" no.
i=7: j=4: dp[4]=T, s[4:7]="cod" no.
i=8: j=4: dp[4]=T, s[4:8]="code" in set! dp[8]=True.
return dp[8] = True ✓
Complexity
- Time: O(n^2) for the nested loop; O(n^3) if string slicing is counted
- Space: O(n)
Senior Follow-up: Word Break II (LeetCode #140)
Return all possible ways to segment the string. Use backtracking with memoization. The DP result from Word Break I can prune branches early: only recurse from positions j where dp[j] is True.
Problem 3: Partition Equal Subset Sum
Difficulty: Medium. Asked at: Amazon, Google. A 0/1 knapsack DP problem. Frequently reported at SDE2 and SDE3 level. LeetCode: #416
Problem Statement
Given a non-empty integer array nums, determine if it can be partitioned into two subsets such that both subsets have equal sum.
Example:
Input: nums = [1,5,11,5]
Output: True
Explanation: [1,5,5] and [11]
Approach
If the total sum is odd, the answer is immediately False (you cannot split an odd number into two equal integers).
Otherwise, the target for each partition is total // 2. The problem reduces to: can we find a subset that sums to target?
This is the 0/1 knapsack pattern. Define dp[j] as True if a subset summing to exactly j is achievable.
Iterate in reverse when updating (right to left) to avoid using the same element twice in one pass.
Solution
python
def can_partition(nums):
total = sum(nums)
if total % 2 != 0:
return False
target = total // 2
dp = [False] * (target + 1)
dp[0] = True # empty subset sums to 0
for num in nums:
for j in range(target, num - 1, -1): # iterate right to left
dp[j] = dp[j] or dp[j - num]
return dp[target]
Trace Through [1,5,11,5]
total=22, target=11
dp = [T,F,F,F,F,F,F,F,F,F,F,F] (indices 0..11)
num=1: j from 11 to 1: dp[1] = dp[1] or dp[0] = True
dp = [T,T,F,F,F,F,F,F,F,F,F,F]
num=5: j from 11 to 5:
dp[6]=dp[6] or dp[1]=True
dp[5]=dp[5] or dp[0]=True
dp = [T,T,F,F,F,T,T,F,F,F,F,F]
num=11: j from 11 to 11:
dp[11]=dp[11] or dp[0]=True
dp = [T,T,F,F,F,T,T,F,F,F,F,T]
return dp[11] = True ✓
Complexity
- Time: O(n x target) where target = sum(nums) / 2
- Space: O(target)
Why Right-to-Left Iteration Matters
If we iterated left to right, dp[j - num] might already reflect the current num being added in this same pass, effectively counting it twice. Right-to-left ensures we only use the values from the previous pass.
Part 2: Advanced Graph Problems
Problem 4: Alien Dictionary
Difficulty: Hard. Asked at: Amazon, Google, Meta. Topological sort on a derived graph. Very frequently reported at SDE3. LeetCode: #269 (LeetCode Premium)
Problem Statement
You are given a sorted list of words from an alien language. The characters are the same as English letters but their ordering may differ. Derive the order of characters in the alien alphabet. Return any valid order, or an empty string if no valid order exists (cycle) or if the input is contradictory.
Example:
Input: words = ["wrt","wrf","er","ett","rftt"]
Output: "wertf"
Approach
Compare adjacent words pairwise. Find the first character where they differ and record that the character from the earlier word comes before the character from the later word. This gives us directed edges in a graph where nodes are characters and edges represent ordering constraints.
Then run topological sort (using DFS with cycle detection) on this graph. If a cycle exists, return an empty string.
Edge case: if a shorter word appears after a longer word with the same prefix (e.g., "abc" before "ab"), the input is invalid.
Solution
python
from collections import defaultdict
def alien_order(words):
# All unique characters
adj = defaultdict(set)
all_chars = set(c for word in words for c in word)
# Build graph from adjacent word pairs
for i in range(len(words) - 1):
w1, w2 = words[i], words[i+1]
min_len = min(len(w1), len(w2))
found = False
for j in range(min_len):
if w1[j] != w2[j]:
adj[w1[j]].add(w2[j])
found = True
break
if not found and len(w1) > len(w2):
return "" # invalid: longer word before shorter with same prefix
# Topological sort with cycle detection
# 0=unvisited, 1=visiting, 2=visited
state = {c: 0 for c in all_chars}
result = []
def dfs(c):
if state[c] == 1:
return False # cycle
if state[c] == 2:
return True
state[c] = 1
for neighbour in adj[c]:
if not dfs(neighbour):
return False
state[c] = 2
result.append(c)
return True
for c in all_chars:
if not dfs(c):
return ""
return "".join(reversed(result))
Trace Through ["wrt","wrf","er","ett","rftt"]
Compare "wrt" vs "wrf": differ at index 2. t -> f. adj[t]={f}
Compare "wrf" vs "er": differ at index 0. w -> e. adj[w]={e}
Compare "er" vs "ett": differ at index 1. r -> t. adj[r]={t}
Compare "ett" vs "rftt":differ at index 0. e -> r. adj[e]={r}
Graph edges: t->f, w->e, r->t, e->r
DFS from each char in all_chars = {w,r,t,f,e}:
dfs(w): state[w]=1
dfs(e): state[e]=1
dfs(r): state[r]=1
dfs(t): state[t]=1
dfs(f): state[f]=2. result=[f]
state[t]=2. result=[f,t]
state[r]=2. result=[f,t,r]
state[e]=2. result=[f,t,r,e]
state[w]=2. result=[f,t,r,e,w]
reversed: [w,e,r,t,f] -> "wertf" ✓
Complexity
- Time: O(C) where C is the total number of characters across all words
- Space: O(1) bounded by the alphabet size (26 characters maximum)
The Critical Edge Case
When a longer word appears before a shorter word with the same prefix (e.g., ["abc", "ab"]), the ordering is impossible. The solution returns "" immediately upon detecting this. Missing this edge case in an interview is a red flag at senior level.
Problem 5: Network Delay Time (Dijkstra's Algorithm)
Difficulty: Medium. Asked at: Google, Amazon. Dijkstra is expected knowledge at SDE3. This is the most commonly used vehicle for testing it. LeetCode: #743
Problem Statement
You are given a network of n nodes (labelled 1 to n) and a list of directed edges times where times[i] = (u, v, w) means there is a directed edge from node u to node v with weight w. Find the minimum time for a signal sent from node k to reach all other nodes. Return -1 if not all nodes are reachable.
Example:
Input: times=[[2,1,1],[2,3,1],[3,4,1]], n=4, k=2
Output: 2
Approach
This is the single-source shortest path problem on a weighted directed graph. Use Dijkstra's algorithm with a min-heap.
Start from node k with distance 0. Process nodes in order of their current shortest distance. When we reach a node, update its neighbours if a shorter path is found. The answer is the maximum distance across all nodes (the last node to receive the signal). If any node is unreachable (distance is infinity), return -1.
Solution
python
import heapq
from collections import defaultdict
def network_delay_time(times, n, k):
graph = defaultdict(list)
for u, v, w in times:
graph[u].append((w, v))
dist = {i: float('inf') for i in range(1, n + 1)}
dist[k] = 0
heap = [(0, k)] # (distance, node)
while heap:
d, node = heapq.heappop(heap)
if d > dist[node]:
continue # outdated entry, skip
for weight, neighbour in graph[node]:
new_dist = d + weight
if new_dist < dist[neighbour]:
dist[neighbour] = new_dist
heapq.heappush(heap, (new_dist, neighbour))
max_dist = max(dist.values())
return max_dist if max_dist < float('inf') else -1
Trace Through times=[[2,1,1],[2,3,1],[3,4,1]], n=4, k=2
graph = {2: [(1,1),(1,3)], 3: [(1,4)]}
dist = {1:inf, 2:0, 3:inf, 4:inf}
heap = [(0,2)]
Pop (0,2): process node 2.
neighbour 1: new_dist=1 < inf. dist[1]=1. Push (1,1).
neighbour 3: new_dist=1 < inf. dist[3]=1. Push (1,3).
heap = [(1,1),(1,3)]
Pop (1,1): process node 1.
No neighbours. heap=[(1,3)]
Pop (1,3): process node 3.
neighbour 4: new_dist=2 < inf. dist[4]=2. Push (2,4).
Pop (2,4): process node 4. No neighbours.
dist = {1:1, 2:0, 3:1, 4:2}
max_dist = 2. Return 2 ✓
Complexity
- Time: O((V + E) log V) where V is nodes, E is edges
- Space: O(V + E)
Why if d > dist[node]: continue is Critical
When we push a node to the heap multiple times (once per relaxation), old entries with outdated distances remain in the heap. Checking if d > dist[node] skips these stale entries efficiently. Without this check, the algorithm still produces correct results but processes nodes multiple times, degrading performance. Senior interviewers watch for this detail.
Problem 6: Pacific Atlantic Water Flow
Difficulty: Medium. Asked at: Google, Amazon. Multi-source BFS or DFS on a grid with two constraints. LeetCode: #417
Problem Statement
You are given an m x n rectangular island. The Pacific Ocean borders the left and top edges. The Atlantic Ocean borders the right and bottom edges. Rain water can flow to adjacent cells (4 directions) if the height of the destination is less than or equal to the current height.
Return a list of coordinates where water can flow to both the Pacific and Atlantic Oceans.
Example:
Input: heights = [
[1,2,2,3,5],
[3,2,3,4,4],
[2,4,5,3,1],
[6,7,1,4,5],
[5,1,1,2,4]
]
Output: [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]
Approach
Instead of checking each cell to see if water can flow to both oceans (which is expensive), reverse the problem. Start BFS from the Pacific border cells (top row, left column) and find all cells that can reach the Pacific. Do the same from Atlantic border cells (bottom row, right column). A cell is in the answer if it appears in both sets.
Reverse flow logic: water flows downhill (to lower or equal cells). Flowing in reverse means we can move to cells with height greater than or equal to the current cell.
Solution
python
from collections import deque
def pacific_atlantic(heights):
if not heights:
return []
rows, cols = len(heights), len(heights[0])
directions = [(1,0),(-1,0),(0,1),(0,-1)]
def bfs(starts):
visited = set(starts)
queue = deque(starts)
while queue:
r, c = queue.popleft()
for dr, dc in directions:
nr, nc = r + dr, c + dc
if (0 <= nr < rows and 0 <= nc < cols
and (nr, nc) not in visited
and heights[nr][nc] >= heights[r][c]):
visited.add((nr, nc))
queue.append((nr, nc))
return visited
pacific_starts = (
[(0, c) for c in range(cols)] +
[(r, 0) for r in range(rows)]
)
atlantic_starts = (
[(rows-1, c) for c in range(cols)] +
[(r, cols-1) for r in range(rows)]
)
pacific_reachable = bfs(pacific_starts)
atlantic_reachable = bfs(atlantic_starts)
return [
[r, c] for r, c in pacific_reachable & atlantic_reachable
]
Complexity
- Time: O(m x n) for each BFS; O(m x n) total
- Space: O(m x n) for the visited sets
Why Reversing the Flow Direction Is the Key Insight
The naive approach visits each cell and runs DFS to check reachability to both oceans. This is O((m x n)^2) in the worst case. Reversing the problem and running BFS from ocean borders gives O(m x n). Articulating this insight cleanly before coding is the signal senior interviewers look for.
Communicating at SDE3 Level
At SDE3, the communication expectation shifts in a specific way. You are not just explaining what you are doing. You are explaining why the approach is correct and why alternatives are inferior.
For every problem above, before writing code, you should be able to say:
- Why this specific algorithmic approach is the right one
- What the time and space complexity will be before you start
- What the tradeoff is if you had to optimise one at the cost of the other
- What the one or two edge cases are that could break a naive implementation
Candidates who can do all four of these before coding demonstrate the kind of technical clarity that hiring committees look for in senior hires.
Practising Advanced DP and Graph Problems at SDE3 Level
These problems are not solved in isolation. In a real SDE3 round, you solve the base problem and then get pushed on extensions, optimisations, and correctness edge cases for the rest of the session.
That kind of sustained technical discussion under pressure is what Intervue.io's SDE3 mock sessions are designed to simulate. You work through the problem with a senior engineer who probes the same way a real FAANG interviewer would, and you receive specific, calibrated feedback afterward.
Visit intervue.io to book a senior-level mock session.
FAQs
Is the O(n log n) LIS solution required at SDE3, or is O(n^2) acceptable? At SDE3 level, you should mention the O(n^2) solution in under 30 seconds and then move to O(n log n) using binary search. Coding only the O(n^2) solution without offering the optimisation is a signal that you are not operating at senior level. The follow-up at L5 almost always asks for the optimal approach.
When does Alien Dictionary have no valid ordering? Two cases: a cycle in the derived character graph (circular dependency, e.g., a before b and b before a), or a longer word appearing before a shorter word with the same prefix (e.g., "abc" before "ab" is an impossible ordering). Both must be handled.
Is Dijkstra on the scope for all SDE3 FAANG loops? Google and Amazon explicitly expect it. Meta less frequently in coding rounds but in system design discussions around routing. At SDE3 level, being unable to implement Dijkstra from memory in 15 to 20 minutes is a gap worth closing.
What is the most common Dijkstra mistake in interviews? Not skipping stale heap entries with if d > dist[node]: continue. Without this, the algorithm produces correct output but can be slower on graphs with many edges. Senior interviewers consistently look for this check.
How do I handle the Pacific Atlantic problem if asked to optimise further? The BFS solution is already O(m x n) which is optimal since every cell must be evaluated. If asked about memory, note that the two visited sets can be represented as boolean grids to reduce constant factor overhead.
Summary
The most frequently reported advanced DP and graph problems at SDE3 and senior FAANG level:
Advanced DP:
- Longest Increasing Subsequence: O(n^2) DP to name, O(n log n) with binary search to implement
- Word Break:
dp[i]= cans[:i]be segmented; check allj < iwheredp[j]is True - Partition Equal Subset Sum: 0/1 knapsack on target = total/2; iterate right to left
Advanced Graphs:
- Alien Dictionary: derive character ordering from adjacent words; topological sort with cycle detection
- Network Delay Time: Dijkstra from source node; answer is max of all shortest distances
- Pacific Atlantic Water Flow: reverse-BFS from both ocean borders; intersect the two reachable sets
Explain the why before the how. State complexity before coding. Surface edge cases unprompted.
Visit intervue.io to practice these in a live SDE3 mock session.
