Amazon Data Structures and Algorithms Interview Questions & Answers
Curated interview practice questions with answers. These are practice scenarios, not a verified list of past interview questions.
About Amazon hiring for Data Structures and Algorithms roles
Amazon is a global technology company spanning e-commerce, cloud computing through AWS, devices, advertising and streaming. In India it runs large engineering, operations and analytics teams supporting both Amazon.in and global businesses. It hires for software development engineers, SDETs, quality assurance engineers, business intelligence engineers, data engineers and data scientists.
For Data Structures and Algorithms roles, this Amazon practice set focuses most on Dynamic Programming (6), Graphs and Graph Algorithms (4), Complexity Analysis and Recursion (4), Arrays, Strings and Hashing (4). It has 1 easy, 20 medium, 9 hard questions, so you can start easy and work up to the harder ones.
Company type
Product
Headquarters
Seattle, USA
Main India offices
Bengaluru, Hyderabad, Chennai, Pune, Gurugram
Amazon Data Structures and Algorithms interview process
Online assessment (coding + work style survey)
Technical round 1 (DSA)
Technical round 2 (DSA or system design)
Bar raiser round
Hiring manager round
Typical pattern based on public candidate experiences. Rounds vary by role, team and year.
Solved for AmazonStart practicing
3 QUESTIONS FREESign up to unlock the full question bank and track your progress.Unlock every question and answer, then continue practising company-wise and package-wise.
✓ 3 questions free • Unlock the rest in seconds
01
A learning platform has courses with prerequisites. How do you find a valid order, and what if none exists?
Model courses as vertices with an edge from each prerequisite to the course that needs it, then run topological sort with Kahn's algorithm. Courses with no pending prerequisites enter a queue first, and taking one reduces the in-degree of dependent courses. If the output has fewer courses than the total, there is a cycle, so no valid order exists, and I would report the courses involved so the content team can fix them.
02
A build system hangs because some services depend on each other in a loop. How would you detect and report the cycle?
Model services as a directed graph and run DFS with three colours. When DFS reaches a node that is still on the current stack, it has found a back edge, and walking the parent pointers from the current node back to that node gives the exact cycle to report, such as A to B to C to A. Running this check in CI before every build prevents the problem, and Kahn's algorithm can list all nodes involved.
03
A recursive DFS in Python crashes with RecursionError on a deep input. How do you fix it?
CPython limits recursion depth to about 1000 by default. Raising the limit with sys.setrecursionlimit works for moderate depth but can crash the interpreter on very deep inputs because the C stack is limited. The reliable fix is to rewrite the DFS iteratively with an explicit stack, pushing nodes and processing them in a loop. In Java the same issue appears as StackOverflowError and has the same solution.
def rotate(nums, k):
n = len(nums)
k %= n
def reverse(l, r):
while l < r:
nums[l], nums[r] = nums[r], nums[l]
l += 1
r -= 1
reverse(0, n - 1) # reverse all
reverse(0, k - 1) # reverse first k
reverse(k, n - 1) # reverse the rest
# [1,2,3,4,5,6,7], k=3 -> [5,6,7,1,2,3,4]; O(n) time, O(1) space
05
How does a hash table work, and how are collisions handled?
A hash table computes a hash of the key and maps it to a bucket index, giving average O(1) insert, lookup and delete. A collision happens when two keys map to the same bucket. Separate chaining stores a list or tree in each bucket, which Java HashMap uses and converts to a tree after 8 entries. Open addressing probes other slots, which Python dict uses. Tables resize when the load factor grows too high.
06
How can two heaps maintain the running median of a stream?
Keep a max-heap for the smaller half of the numbers and a min-heap for the larger half, balanced so their sizes differ by at most one. Insert each number into the correct heap, then move the top element across if sizes become unbalanced. The median is the top of the larger heap, or the average of both tops when sizes are equal. Insertion is O(log n) and finding the median is O(1).
def edit_distance(a, b):
m, n = len(a), len(b)
prev = list(range(n + 1)) # distances from empty prefix of a
for i in range(1, m + 1):
cur = [i] + [0] * n
for j in range(1, n + 1):
if a[i - 1] == b[j - 1]:
cur[j] = prev[j - 1]
else:
cur[j] = 1 + min(prev[j], # delete
cur[j - 1], # insert
prev[j - 1]) # replace
prev = cur
return prev[n]
# edit_distance('horse', 'ros') -> 3; O(m * n) time, O(n) space
08
HR wants an employee list sorted by department, and by salary within each department. How would you do it?
Either sort once with a composite key, department first and salary second, using a comparator in Java or a tuple key in Python, or do two passes with a stable sort: first by salary, then by department, relying on stability to keep salary order within departments. The single composite-key sort is clearer. Both are O(n log n), and I would clarify whether salary should be ascending or descending.
import heapq
def merge_k_lists(lists):
heap = []
for i, node in enumerate(lists):
if node:
heapq.heappush(heap, (node.val, i, node)) # i breaks ties
dummy = tail = ListNode()
while heap:
val, i, node = heapq.heappop(heap)
tail.next = node
tail = node
if node.next:
heapq.heappush(heap, (node.next.val, i, node.next))
return dummy.next
# O(N log K) for N total nodes
10
A hash map lookup in your service suddenly becomes very slow under certain traffic. What could cause it?
If many keys produce the same hash, they pile into a few buckets and operations degrade toward O(n). This can come from a poor custom hashCode, such as returning a constant or using only one field, or from attackers sending crafted keys. Fixes include a better hash function combining all fields, randomised hashing, which Python uses for strings, and tree-based buckets as in Java 8 HashMap, which caps the worst case at O(log n).
11
Why are linked lists often slower than arrays in practice, and what is a skip list?
Linked list nodes are scattered in memory, so traversal causes cache misses, and each node needs extra memory for pointers. Arrays are contiguous and benefit from CPU caching and prefetching, so even O(n) shifts can be fast for moderate sizes. A skip list is a layered linked list with express lanes chosen randomly, giving O(log n) average search, insert and delete; Redis uses it for sorted sets.
12
A report generation function loops over all users and, for each user, scans all orders. It was fine at launch but is now very slow. How do you explain and fix it?
The loop is O(users times orders), so when both grow ten times, the work grows a hundred times. I would explain this with numbers and a quick profile. The fix is to group orders by user ID once using a hash map, making the total O(users plus orders), or to push the grouping into a database query with an index. I would add a performance test with production-scale data.
13
Find the minimum number of coins needed to make an amount.
def coin_change(coins, amount):
INF = amount + 1
dp = [0] + [INF] * amount # dp[x] = min coins for amount x
for x in range(1, amount + 1):
for c in coins:
if c <= x and dp[x - c] + 1 < dp[x]:
dp[x] = dp[x - c] + 1
return dp[amount] if dp[amount] != INF else -1
# coin_change([1, 3, 4], 6) -> 2 (3 + 3)
# O(amount * len(coins)) time, O(amount) space
14
Implement Union-Find with path compression and union by size.
First I estimate the complexity of my code against the constraints and find the dominant loop. Often a nested loop or repeated search inside a loop makes it O(n squared). I then look for a better pattern such as a hash map for lookups, sorting plus two pointers, prefix sums or memoisation of repeated subproblems. I also check hidden costs like string concatenation in loops or list.pop(0) in Python.
16
An interviewer asks you to reduce your solution's extra space from O(n) to O(1). How do you approach it?
I check what the extra structure stores and whether the input itself can hold that information. Common techniques: use two pointers instead of a hash set on sorted data, keep only the last few DP values instead of a full table, modify the input in place, such as marking visited indices by negating values, or use bit manipulation like XOR to find a missing number. I state any trade-offs, such as mutating input.
17
Tell me about a time you worked with people from other teams to solve a complex problem.
Situation: delivery route suggestions in our app were slow and the data team blamed the backend while we blamed the data. Task: find the real issue. Action: I set up a joint session, we traced one slow request end to end and found the graph was rebuilt from raw tables on every call. I proposed caching the adjacency lists, and the data team added change notifications. Result: response time dropped from 3 seconds to 200 milliseconds.
18
A search box must suggest the closest dictionary words when a user makes a typo. How would you approach it?
Compute edit distance between the typed word and candidate words, suggesting those within distance 1 or 2. Running O(m times n) DP against a whole dictionary is slow, so narrow candidates first using a BK-tree indexed by edit distance, a trie with bounded edit distance search, or n-gram indexes. Then rank candidates by distance and word popularity. Keyboard-aware substitution costs can improve suggestions further.
19
Generate all permutations of a list of distinct numbers using backtracking.
def knapsack(weights, values, capacity):
dp = [0] * (capacity + 1) # dp[w] = best value with capacity w
for wt, val in zip(weights, values):
for w in range(capacity, wt - 1, -1): # go downwards: each item once
dp[w] = max(dp[w], dp[w - wt] + val)
return dp[capacity]
# knapsack([1, 3, 4], [15, 20, 30], 4) -> 35
# O(n * W) time, O(W) space
21
A company has a fixed budget and several projects with costs and expected returns. How would you choose projects to maximise return?
If each project is all or nothing, this is the 0/1 knapsack problem: budget is capacity, cost is weight and return is value, solved with DP in O(projects times budget), and tracking choices lets me list selected projects. If the budget is very large, I would scale costs to units such as lakhs to keep the table small, or use DP over value instead. Extra constraints like dependencies change the state design.
22
How does heap sort work and how does it compare with quicksort and merge sort?
Heap sort builds a max-heap in O(n), then repeatedly swaps the root with the last element, shrinks the heap and sifts down, giving O(n log n) in all cases with O(1) extra space. It is not stable and has poor cache locality, so in practice it is slower than quicksort. Merge sort is stable but needs O(n) space. Introsort switches from quicksort to heap sort to guarantee O(n log n).
23
You have a 100 GB file of integers and only 4 GB of RAM. How would you find the duplicates?
The data does not fit in memory, so I would partition it. Read the file in streaming fashion and write each number to one of, say, 50 bucket files based on hash of the number modulo 50, so equal numbers land in the same bucket. Each bucket of about 2 GB fits in memory, where a hash set finds duplicates. Alternatively use external merge sort and scan adjacent values. A Bloom filter can pre-screen candidates.
24
Design a simple scheduler that gives each job a fixed time slice in turn.
Round-robin scheduling fits a queue. Put all jobs in a FIFO queue. Repeatedly dequeue a job, run it for one time slice, and if it is not finished, enqueue it at the back with its remaining time. Each step is O(1). For priorities, keep one queue per priority level or use a priority queue. A circular buffer works well if the number of jobs is bounded, avoiding allocations.
25
You need to build a tool that shows the differences between two versions of a file line by line. What algorithm would you use?
The core is the longest common subsequence over lines: lines in the LCS are unchanged, and the rest are additions or deletions. Hash each line first so comparisons are fast. Classic LCS DP is O(m times n), which is too slow for large files, so real diff tools use Myers' algorithm, which runs in O((m plus n) times d), where d is the number of differences, fast when versions are similar.
26
You must sort a 10 GB file of records on a machine with 1 GB of RAM. How would you do it?
Use external merge sort. Read the file in chunks of about 800 MB, sort each chunk in memory and write it to disk as a sorted run, giving around 13 runs. Then perform a K-way merge: open all runs, keep a min-heap with the current record from each, repeatedly output the smallest and refill from that run, using buffered I/O. Total work is O(n log n) with roughly two passes over the data.
27
Write a function to validate a binary search tree.
def is_valid_bst(root, low=float('-inf'), high=float('inf')):
if not root:
return True
if not (low < root.val < high):
return False
return (is_valid_bst(root.left, low, root.val) and
is_valid_bst(root.right, root.val, high))
# Passing bounds checks the whole-subtree property, not just children.
# O(n) time, O(h) space.
28
Find the lowest common ancestor of two nodes in a binary tree.
def lca(root, p, q):
if root is None or root is p or root is q:
return root
left = lca(root.left, p, q)
right = lca(root.right, p, q)
if left and right: # p and q are on different sides
return root
return left or right
# O(n) time, O(h) space; assumes both nodes exist in the tree
29
A teammate's BST validation only checks that each node is greater than its left child and smaller than its right child. Why is that wrong?
The BST property applies to entire subtrees, not just direct children. A node deep in the left subtree could be larger than the root and still pass the local check. The correct approach passes a valid range down the recursion: the left child must lie between the lower bound and the node value, the right child between the node value and the upper bound. Alternatively, check that an inorder traversal is strictly increasing.
30
Find the first and last position of a target in a sorted array.
from bisect import bisect_left, bisect_right
def search_range(nums, target):
lo = bisect_left(nums, target) # first index >= target
if lo == len(nums) or nums[lo] != target:
return [-1, -1]
hi = bisect_right(nums, target) - 1 # last index <= target
return [lo, hi]
# [5,7,7,8,8,10], 8 -> [3, 4]; two binary searches: O(log n)
Tips to crack the Amazon Data Structures and Algorithms interview
Prepare STAR-format stories for each Amazon Leadership Principle, such as Customer Obsession, Ownership and Dive Deep.
Practise medium-level DSA problems on arrays, trees, graphs and dynamic programming, explaining time and space complexity aloud.
For BIE or data roles, practise SQL window functions and metric-driven case questions on e-commerce funnels and delivery operations.
Keep a one-minute story ready for every project on your CV: problem, your part, tools, result.
Practise the hard questions on this page aloud; Amazon interviewers usually ask follow-ups on your first answer.
Frequently asked questions
How many rounds are there in the Amazon Data Structures and Algorithms interview?
Candidates usually go through 5 stages: Online assessment (coding + work style survey); Technical round 1 (DSA); Technical round 2 (DSA or system design); Bar raiser round; Hiring manager round. The exact rounds change with the role, team, location and your experience, so confirm the process with the recruiter.
Which topics should I prepare for the Amazon Data Structures and Algorithms interview?
This practice set leans on Dynamic Programming (6), Graphs and Graph Algorithms (4), Complexity Analysis and Recursion (4), Arrays, Strings and Hashing (4). Revise those first, then practise explaining one or two of your own projects end to end, because most Amazon interviewers ask you to walk through real work.
Are these the exact questions asked at Amazon?
No. These are curated practice questions that match the skills and difficulty usually tested in product interviews like Amazon's. They are not a leaked or verified list of past questions.
Where does Amazon hire Data Structures and Algorithms professionals in India?
Amazon has large teams in Bengaluru, Hyderabad, Chennai, Pune, Gurugram. Openings and locations change often, so check the Amazon careers page and filter by city and experience.
Data Structures and Algorithms questions for similar companies