Amazon OA Walkthrough: 3 Problems, 90 Minutes, Here’s My Code

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:
  1. Medium: Merge k Sorted Lists
  2. Hard: Word Ladder II
  3. Medium: Count of Smaller Numbers After Self

I paced myself about 30 minutes per problem, leaving a few minutes at the end of each for quick review.

---

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, push next into the heap.

import heapq
def 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 idx in the heap tuple to avoid tie issues.
• Empty input list: Checked if node before pushing.

Could’ve been 3–4 minutes faster by pre-allocating the dummy and skipping the tuple index, but safe is better under pressure.

---

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:

1. BFS to build a graph of shortest-level connections.
2. DFS/backtracking from beginWord to endWord, following only edges that move to the next level.

from collections import defaultdict, deque
def 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

1. 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.
2. Edge-case checklist: I missed testing [] and single-element inputs on the first problem—would write simple asserts before coding.
3. Quick skimming: I’d note “constraints: wordList up to 5 k words” and opt for pattern-based adjacency pre-compute immediately.