SDE2 coding rounds are a meaningful step up from SDE1. The problems are harder, the expected solution is more often optimal from the start, and interviewers probe follow-ups more aggressively.
The two topics that separate SDE2 candidates from SDE1 candidates most clearly are graphs and dynamic programming. At Amazon SDE2 (L5), Google L4, and Meta E4, these are not occasional topics, they are expected competencies. Candidates who can't fluently implement BFS, DFS, topological sort, and medium-difficulty DP rarely clear the onsite at this level.
This blog covers the most frequently reported graph and DP problems at SDE2 level, with verified solutions, full complexity analysis, and the reasoning you need to communicate in a live round.
All solutions are in Python. Every solution has been traced through its example.
What SDE2 Coding Rounds Look Like
Amazon SDE2 (L5): 4–5 round onsite. Coding rounds expect medium-hard problems. Graph problems (BFS/DFS, shortest path, topological sort) and DP variants appear frequently. Bar Raiser round evaluates both coding quality and LP signal.
Google L4: One medium problem with 2–3 follow-ups per round, or two medium problems back-to-back. Google expects optimal solutions and complexity stated unprompted. Graph and tree problems dominate.
Meta E4: Two problems per round, 35 minutes each. Speed matters more than at Google. DP and graph problems appear in the second problem slot, typically harder than the first.
Product companies (Razorpay, Swiggy, Flipkart) at senior engineer level: One medium-hard problem per round. Graph and DP problems appear but are slightly more pattern-predictable than FAANG.
The bar across all: arrive at the optimal approach quickly, code it cleanly, handle edge cases without prompting, and explain complexity without being asked.
Part 1: Graph Problems
Graph Representation Used in All Problems Below
python
# Adjacency list - standard for most graph interview problems
graph = {
0: [1, 2],
1: [0, 3],
2: [0],
3: [1]
}
Problem 1: Number of Islands
Difficulty: Medium. Asked at: Amazon, Google, Meta, one of the most reported graph problems across all FAANG companies at SDE2 level. LeetCode: #200
Problem Statement
Given an m × n grid of '1' (land) and '0' (water), count the number of islands. An island is surrounded by water and formed by connecting adjacent land cells horizontally or vertically.
Example:
Input:
grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]
Output: 3
Approach
Iterate through every cell. When we find a '1' (unvisited land), increment the island count and run DFS to mark all connected land cells as visited (change them to '0' to avoid revisiting). After DFS, that entire island is consumed. Continue scanning.
Solution
python
def num_islands(grid):
if not grid:
return 0
rows, cols = len(grid), len(grid[0])
count = 0
def dfs(r, c):
# Out of bounds or water — stop
if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] == '0':
return
grid[r][c] = '0' # mark as visited
dfs(r + 1, c)
dfs(r - 1, c)
dfs(r, c + 1)
dfs(r, c - 1)
for r in range(rows):
for c in range(cols):
if grid[r][c] == '1':
count += 1
dfs(r, c)
return count
Trace Through the Example
Scanning cell by cell:
(0,0)='1' → count=1. DFS marks (0,0),(0,1),(1,0),(1,1) as '0'.
(0,2)='0' → skip
...
(2,2)='1' → count=2. DFS marks (2,2) as '0'.
(3,3)='1' → count=3. DFS marks (3,3),(3,4) as '0'.
Output: 3 ✓
Complexity
- Time: O(m × n) - every cell visited at most once
- Space: O(m × n) - recursion stack depth in worst case (all land)
Common Follow-up at SDE2
"What if the grid is too large to fit in memory? "Use BFS with an explicit queue instead of recursive DFS, this converts stack memory to heap memory and allows streaming row-by-row. Also mention: for a distributed setting, Union-Find across partitions with border reconciliation.
Problem 2: Clone Graph
Difficulty: Medium. Asked at: Amazon, Meta, tests understanding of graph traversal with object creation. LeetCode: #133
Problem Statement
Given a reference to a node in a connected undirected graph, return a deep copy of the graph. Each node has a value and a list of neighbours.
python
class Node:
def __init__(self, val=0, neighbors=None):
self.val = val
self.neighbors = neighbors if neighbors is not None else []
Example:
Input: Node 1 connected to Node 2, Node 2 connected to Node 1
Output: A deep copy with new node objects, same structure
Approach
Use DFS with a hash map that maps each original node to its clone. When we visit a node, create its clone immediately and store the mapping. Then recursively clone all neighbours. The hash map prevents infinite loops on cycles.
Solution
python
def clone_graph(node):
if not node:
return None
cloned = {} # original node -> cloned node
def dfs(n):
if n in cloned:
return cloned[n]
clone = Node(n.val)
cloned[n] = clone
for neighbour in n.neighbors:
clone.neighbors.append(dfs(neighbour))
return clone
return dfs(node)
Complexity
- Time: O(V + E) - every node and edge visited once
- Space: O(V) - hash map stores one entry per node
Problem 3: Course Schedule (Topological Sort / Cycle Detection)
Difficulty: Medium. Asked at: Amazon, Google, topological sort is a required SDE2 competency; this problem is the most common entry point. LeetCode: #207
Problem Statement
There are numCourses courses (labelled 0 to numCourses - 1). You are given a list of prerequisites where prerequisites[i] = [a, b] means you must take course b before course a. Return True if it is possible to finish all courses, False if a cycle exists (making it impossible).
Example:
Input: numCourses=2, prerequisites=[[1,0]]
Output: True (take 0 then 1)
Input: numCourses=2, prerequisites=[[1,0],[0,1]]
Output: False (cycle: 0 requires 1, 1 requires 0)
Approach
Model as a directed graph. The question reduces to: does this graph contain a cycle? Use DFS with three states per node:
0= unvisited1= currently in DFS stack (visiting)2= fully processed (safe)
If during DFS we reach a node with state 1, we've found a cycle → return False.
Solution
python
def can_finish(numCourses, prerequisites):
# Build adjacency list
graph = [[] for _ in range(numCourses)]
for course, prereq in prerequisites:
graph[prereq].append(course)
# 0 = unvisited, 1 = visiting, 2 = visited
state = [0] * numCourses
def dfs(node):
if state[node] == 1: # cycle detected
return False
if state[node] == 2: # already processed, safe
return True
state[node] = 1 # mark as visiting
for neighbour in graph[node]:
if not dfs(neighbour):
return False
state[node] = 2 # mark as fully processed
return True
for course in range(numCourses):
if not dfs(course):
return False
return True
Trace Through the Cycle Example
numCourses=2, prerequisites=[[1,0],[0,1]]
graph[0] = [1], graph[1] = [0]
dfs(0): state[0]=1
dfs(1): state[1]=1
dfs(0): state[0]==1 → cycle! return False
→ False
→ False
Output: False ✓
Complexity
- Time: O(V + E) - every node and edge visited once
- Space: O(V + E) - adjacency list and recursion stack
Important Follow-up: Course Schedule II (LeetCode #210)
If asked to return the actual order, collect nodes in the order they finish DFS (post-order) and reverse. This gives a valid topological sort.
python
def find_order(numCourses, prerequisites):
graph = [[] for _ in range(numCourses)]
for course, prereq in prerequisites:
graph[prereq].append(course)
state = [0] * numCourses
order = []
def dfs(node):
if state[node] == 1:
return False
if state[node] == 2:
return True
state[node] = 1
for neighbour in graph[node]:
if not dfs(neighbour):
return False
state[node] = 2
order.append(node) # add after all descendants processed
return True
for course in range(numCourses):
if not dfs(course):
return []
return order[::-1] # reverse post-order = topological order
Problem 4: Rotting Oranges
Difficulty: Medium. Asked at: Amazon, Google, multi-source BFS; tests whether candidates know BFS is the right tool for "minimum time" grid problems. LeetCode: #994
Problem Statement
You are given an m × n grid. Each cell is:
0- empty1- fresh orange2- rotten orange
Every minute, a rotten orange makes all 4-directionally adjacent fresh oranges rot. Return the minimum number of minutes until no fresh orange remains. Return -1 if it is impossible.
Example:
Input:
grid = [
[2,1,1],
[1,1,0],
[0,1,1]
]
Output: 4
Approach
Multi-source BFS starting from all rotten oranges simultaneously. This is the key insight, all rotten oranges rot their neighbours at the same time, so BFS naturally models this. Track the count of fresh oranges; when it reaches zero, we are done. If fresh oranges remain after BFS, return -1.
Solution
python
from collections import deque
def oranges_rotting(grid):
rows, cols = len(grid), len(grid[0])
queue = deque()
fresh_count = 0
# Initialise queue with all rotten oranges, count fresh ones
for r in range(rows):
for c in range(cols):
if grid[r][c] == 2:
queue.append((r, c, 0)) # (row, col, time)
elif grid[r][c] == 1:
fresh_count += 1
if fresh_count == 0:
return 0
directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
max_time = 0
while queue:
r, c, time = queue.popleft()
for dr, dc in directions:
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
grid[nr][nc] = 2 # rot it
fresh_count -= 1
max_time = max(max_time, time + 1)
queue.append((nr, nc, time + 1))
return max_time if fresh_count == 0 else -1
Complexity
- Time: O(m × n) - each cell processed at most once
- Space: O(m × n) - queue in worst case holds all cells
Part 2: Dynamic Programming Problems
Problem 5: Coin Change
Difficulty: Medium. Asked at: Amazon, Google, Meta, one of the most frequently asked DP problems at SDE2 level; tests unbounded knapsack pattern. LeetCode: #322
Problem Statement
You are given an integer array coins (coin denominations) and an integer amount. Return the minimum number of coins needed to make up that amount. Return -1 if it is not possible.
Example:
Input: coins = [1, 5, 11], amount = 15
Output: 3 (5 + 5 + 5)
Input: coins = [2], amount = 3
Output: -1
Note on Example 1: [1,5,11] with amount 15:
- 15 coins of
1is valid but not minimum 5 + 5 + 5 = 15uses 3 coins ✓11 + 1 + 1 + 1 + 1 = 15uses 5 coins - worse- Minimum is 3
Approach
This is the unbounded knapsack pattern, each coin can be used unlimited times. Define dp[i] as the minimum number of coins to make amount i. Base case: dp[0] = 0. For each amount from 1 to amount, try every coin and take the minimum.
Solution
python
def coin_change(coins, amount):
dp = [float('inf')] * (amount + 1)
dp[0] = 0 # 0 coins needed to make amount 0
for i in range(1, amount + 1):
for coin in coins:
if coin <= i:
dp[i] = min(dp[i], dp[i - coin] + 1)
return dp[amount] if dp[amount] != float('inf') else -1
Trace Through coins=[1,5,11], amount=15
dp[0]=0
dp[1]=min(inf, dp[0]+1)=1 (use coin 1)
dp[2]=2, dp[3]=3, dp[4]=4
dp[5]=min(dp[4]+1, dp[0]+1)=1 (use coin 5)
dp[6]=2, dp[7]=3, dp[8]=4, dp[9]=5
dp[10]=min(dp[9]+1, dp[5]+1)=2 (use coin 5 twice)
dp[11]=min(dp[10]+1, dp[6]+1, dp[0]+1)=1 (use coin 11)
dp[12]=2, dp[13]=3, dp[14]=4
dp[15]=min(dp[14]+1, dp[10]+1, dp[4]+1)=min(5,3,5)=3 (use coin 5 three times)
Output: 3 ✓
Complexity
- Time: O(amount × n) - where n is number of coin denominations
- Space: O(amount) - dp array of size amount + 1
Problem 6: Longest Common Subsequence
Difficulty: Medium. Asked at: Amazon, Google, 2D DP; one of the most asked string DP problems at SDE2 level. LeetCode: #1143
Problem Statement
Given two strings text1 and text2, return the length of their longest common subsequence. A subsequence is a sequence that appears in the same relative order but not necessarily contiguous.
Example:
Input: text1 = "abcde", text2 = "ace"
Output: 3 (the LCS is "ace")
Approach
Define dp[i][j] as the length of the LCS of text1[:i] and text2[:j].
Recurrence:
- If
text1[i-1] == text2[j-1]: characters match →dp[i][j] = dp[i-1][j-1] + 1 - Otherwise: take the best without the current character from either string →
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
Base case: dp[0][j] = 0 and dp[i][0] = 0 (LCS with an empty string is 0).
Solution
python
def longest_common_subsequence(text1, text2):
m, n = len(text1), len(text2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if text1[i - 1] == text2[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
return dp[m][n]
Trace Through text1="abcde", text2="ace"
"" a c e
"" [ 0, 0, 0, 0 ]
a [ 0, 1, 1, 1 ]
b [ 0, 1, 1, 1 ]
c [ 0, 1, 2, 2 ]
d [ 0, 1, 2, 2 ]
e [ 0, 1, 2, 3 ]
dp[5][3] = 3 ✓
Complexity
- Time: O(m × n)
- Space: O(m × n) - can be optimised to O(n) by keeping only the previous row
Space Optimisation Follow-up
python
def longest_common_subsequence_optimised(text1, text2):
m, n = len(text1), len(text2)
prev = [0] * (n + 1)
for i in range(1, m + 1):
curr = [0] * (n + 1)
for j in range(1, n + 1):
if text1[i - 1] == text2[j - 1]:
curr[j] = prev[j - 1] + 1
else:
curr[j] = max(prev[j], curr[j - 1])
prev = curr
return prev[n]
- Space: O(n) - only two rows kept at a time
Problem 7: House Robber
Difficulty: Medium. Asked at: Amazon, Google, linear DP; extremely high frequency across all FAANG companies. LeetCode: #198
Problem Statement
You are a robber planning to rob houses along a street. Each house has a certain amount of money. Adjacent houses have security systems that trigger if both are robbed on the same night. Given an integer array nums representing the amount of money in each house, return the maximum amount you can rob without triggering the alarm.
Example:
Input: nums = [2, 7, 9, 3, 1]
Output: 12 (rob houses 0, 2, 4: 2 + 9 + 1 = 12)
Approach
At each house i, we have two choices: rob it (take nums[i] + best from i-2) or skip it (take best from i-1). Define dp[i] as the maximum money robbed from the first i houses.
Recurrence: dp[i] = max(dp[i-1], dp[i-2] + nums[i])
We only ever need the last two values, so we can optimise to O(1) space.
Solution
python
def rob(nums):
if not nums:
return 0
if len(nums) == 1:
return nums[0]
prev2 = 0 # dp[i-2]
prev1 = 0 # dp[i-1]
for num in nums:
current = max(prev1, prev2 + num)
prev2 = prev1
prev1 = current
return prev1
Trace Through [2, 7, 9, 3, 1]
prev2=0, prev1=0
num=2: current=max(0, 0+2)=2. prev2=0, prev1=2
num=7: current=max(2, 0+7)=7. prev2=2, prev1=7
num=9: current=max(7, 2+9)=11. prev2=7, prev1=11
num=3: current=max(11,7+3)=11. prev2=11, prev1=11
num=1: current=max(11,11+1)=12.prev2=11, prev1=12
Output: 12 ✓
Complexity
- Time: O(n)
- Space: O(1)
Follow-up: House Robber II (LeetCode #213)
Houses are arranged in a circle, the first and last are adjacent. Split into two subproblems: rob houses [0, n-2] or rob houses [1, n-1]. Return the maximum of both.
python
def rob_ii(nums):
if len(nums) == 1:
return nums[0]
def rob_range(houses):
prev2, prev1 = 0, 0
for num in houses:
current = max(prev1, prev2 + num)
prev2, prev1 = prev1, current
return prev1
return max(rob_range(nums[:-1]), rob_range(nums[1:]))
How SDE2 Interviewers Probe These Problems
At SDE2 level, interviewers don't just want a working solution, they expect you to proactively:
- Name the algorithm before coding: "This is a multi-source BFS problem because all rotten oranges spread simultaneously"
- State why DFS is wrong for shortest-path problems: BFS gives the shortest path in unweighted graphs; DFS does not guarantee this
- Identify the DP state clearly: Before writing code, say "I'll define dp[i] as...", this is the most important signal in DP rounds
- Raise space optimisation unprompted: Mentioning "this can be optimised to O(n) space by keeping only the previous row" is the difference between Hire and Strong Hire at many companies
Practising Graph and DP Problems Under Real Conditions
Graph and DP problems are the ones where live interview performance diverges most sharply from solo practice performance.
Candidates who've solved Coin Change 20 times alone still blank on the state definition when asked to explain it under pressure. Candidates who've run Number of Islands 15 times still make off-by-one errors in the boundary condition when someone is watching.
At Intervue.io, SDE2 mock sessions are calibrated to the actual difficulty of mid-level FAANG and product company loops. You get structured feedback on your approach naming, state definition clarity, edge case handling, and communication, the signals that determine SDE2 offer decisions.
👉 Book an SDE2 mock session on Intervue.io
FAQs
How hard are graph problems at Amazon SDE2 specifically? Amazon SDE2 OA and interview rounds include medium graph problems, BFS/DFS on grids, shortest path variants, and topological sort. Hard graph problems (Dijkstra, Bellman-Ford) appear occasionally but are not the baseline expectation. BFS/DFS fluency and topological sort are non-negotiable.
Is DP required at the SDE2 level or just a bonus?Required. Amazon, Google, and Meta all include medium DP problems in SDE2 coding rounds. The patterns that appear most: coin change (unbounded knapsack), house robber (linear DP), and LCS-style string DP. Hard DP (interval DP, bitmask DP) is more of an SDE3 expectation.
Should I use BFS or DFS for Number of Islands? Either works for counting connected components. DFS is slightly simpler to write. BFS is preferred when the problem asks for the shortest path or minimum steps, never use DFS for shortest-path problems in unweighted graphs.
What is the most common DP mistake at SDE2 interviews?Jumping to the recurrence before defining the state. The state definition is the foundation, if it's wrong, the recurrence will be wrong. Always say "dp[i] represents..." out loud before writing anything.
How does topological sort differ from regular DFS? Regular DFS visits nodes and processes them when first encountered. Topological sort uses post-order DFS, nodes are added to the result after all their descendants are processed, then the list is reversed. This guarantees dependencies are resolved before the nodes that depend on them.
Summary
The most frequently asked SDE2 graph and DP problems at FAANG and product companies:
Graphs:
- Number of Islands - DFS flood fill on a grid
- Clone Graph - DFS with hash map for cycle-safe deep copy
- Course Schedule - cycle detection with three-state DFS; follow-up returns topological order
- Rotting Oranges - multi-source BFS; key insight is all rotten oranges spread simultaneously
Dynamic Programming:
- Coin Change - unbounded knapsack;
dp[i] = min(dp[i], dp[i-coin]+1) - Longest Common Subsequence - 2D DP on two strings; optimisable to O(n) space
- House Robber - linear DP with O(1) space; follow-up adds circular constraint
Define the state before writing code. Name the pattern before coding. State complexity unprompted.
