Amazon OA Walkthrough: 3 Problems, 90 Minutes, Here’s My Code
- Posted
- 4 May 2025
Summary
I just wrapped up Amazon’s SDE-2 Online Assessment and thought I’d share a step-by-step recap—the exact problems, my solutions (with edge-case handling!), and what I’d change if I did it again. Hopefully this helps anyone on the fence about how to tackle that dreaded 90-minute timer.
How it went
Hey everyone,
I just wrapped up Amazon’s SDE-2 Online Assessment and thought I’d share a step-by-step recap—the exact problems, my solutions (with edge-case handling!), and what I’d change if I did it again. Hopefully this helps anyone on the fence about how to tackle that dreaded 90-minute timer.
The Setup
- Duration: 90 minutes
- Environment: HackerRank-style editor, no external libraries
- Problems:
- Medium: Merge k Sorted Lists
- Hard: Word Ladder II
- Medium: Count of Smaller Numbers After Self
1️ Problem 1: Merge k Sorted Lists (Medium)
Prompt (summarized):
You have k linked lists, each sorted ascending. Merge them into one sorted list and return its head.
My Approach:
- Use a min-heap keyed by node value.
- Push the head of each non-empty list into the heap.
- Repeatedly pop the smallest node, append it to the result, and if that node has a
next, pushnextinto the heap.
import heapqdef mergeKLists(lists): heap = [] for idx, node in enumerate(lists): if node: heapq.heappush(heap, (node.val, idx, node)) dummy = ListNode(0) tail = dummy
while heap: val, idx, node = heapq.heappop(heap) tail.next = node tail = tail.next if node.next: heapq.heappush(heap, (node.next.val, idx, node.next)) return dummy.next
Edge Cases & Lessons:
- Identical values: I included
idxin the heap tuple to avoid tie issues. - Empty input list: Checked
if nodebefore pushing.
2️ Problem 2: Word Ladder II (Hard)
Prompt (summarized):
Given beginWord, endWord, and a wordList, return all shortest transformation sequences from beginWord to endWord. Each step must change one letter and land in wordList.
My Approach:
- BFS to build a graph of shortest-level connections.
- DFS/backtracking from
beginWordtoendWord, following only edges that move to the next level.
from collections import defaultdict, dequedef findLadders(begin, end, wordList): wordSet = set(wordList) if end not in wordSet: return []
# Build adjacency by BFS levels levels = {begin: 0} graph = defaultdict(list) queue = deque([begin]) while queue: word = queue.popleft() for i in range(len(word)): for c in 'abcdefghijklmnopqrstuvwxyz': nxt = word[:i] + c + word[i+1:] if nxt in wordSet: if nxt not in levels: levels[nxt] = levels[word] + 1 queue.append(nxt) if levels[nxt] == levels[word] + 1: graph[word].append(nxt) # Backtrack all shortest paths res = [] def dfs(path): if path[-1] == end: res.append(path[:]) return for nxt in graph[path[-1]]: dfs(path + [nxt]) dfs([begin]) return res
What I’d improve:
- I got TLE on large inputs because I regenerated all 26-letter possibilities each time. Pre-computing generic patterns (
h*t,ho*, etc.) would be faster.
3️ Problem 3: Count of Smaller Numbers After Self (Medium)
Prompt (summarized):
For each element in nums, count how many elements to its right are smaller. Return the list of counts.
My Approach:
- Used a Fenwick Tree (Binary Indexed Tree) on the compressed ranks of the values.
- Traverse from right to left, query the BIT for how many have rank < current rank, then update the BIT at current rank.
def countSmaller(nums): # Coordinate compression sorted_unique = sorted(set(nums)) rank = {v: i+1 for i, v in enumerate(sorted_unique)} size = len(sorted_unique) BIT = [0] * (size + 1)def update(i): while i <= size: BIT[i] += 1 i += i & -i def query(i): s = 0 while i > 0: s += BIT[i] i -= i & -i return s res = [] for x in reversed(nums): r = rank[x] res.append(query(r - 1)) update(r) return res[::-1]
Key Points:
- Compression handles negatives/large values.
- Fenwick guarantees O(n log n).
What I’d Do Differently
- Time allocation: I spent 35 min on Word Ladder II and got TLE. Next time, I’d allocate only 25 min to it and move on.
- Edge-case checklist: I missed testing
[]and single-element inputs on the first problem—would write simple asserts before coding. - Quick skimming: I’d note “constraints:
wordListup to 5 k words” and opt for pattern-based adjacency pre-compute immediately.
Questions asked (3)
- 01
Merge k Sorted Lists
Data Structures & Algorithms · Medium
You have
klinked lists, each sorted ascending. Merge them into one sorted list and return its head. - 02
Word Ladder II
Data Structures & Algorithms · Hard
Given
beginWord,endWord, and awordList, return all shortest transformation sequences frombeginWordtoendWord. Each step must change one letter and land inwordList. - 03
Count of Smaller Numbers After Self
Data Structures & Algorithms · Medium
For each element in
nums, count how many elements to its right are smaller. Return the list of counts.