amazon logo
Amazon· SDE-2

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

Posted
4 May 2025
318 reads

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:
    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 &lt;= size:
        BIT[i] += 1
        i += i &amp; -i

def query(i):
    s = 0
    while i &gt; 0:
        s += BIT[i]
        i -= i &amp; -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.

Questions asked (3)

  1. 01

    Merge k Sorted Lists

    Data Structures & Algorithms · Medium

    You have k linked lists, each sorted ascending. Merge them into one sorted list and return its head.

  2. 02

    Word Ladder II

    Data Structures & Algorithms · Hard

    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.

  3. 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.

Know someone preparing? Send it to them:WhatsAppLinkedInX

Interviewed at Amazon recently?

Write up your rounds while you still remember the questions. It helps the next person more than you would think.

Share your experience
Discussion 0

Questions for the author, or how your own interview compared.

Join the discussion

Sign in with Google to comment or ask the author a question.

No comments yet

Be the first to share your thoughts and start the discussion!