Microsoft 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 Microsoft hiring for Data Structures and Algorithms roles
Microsoft builds software, cloud and hardware products including Windows, Microsoft 365, Azure, Dynamics, GitHub, LinkedIn and Xbox. The India Development Center in Hyderabad and Bengaluru is one of its largest engineering hubs outside the US. It hires for software engineers, data scientists, data and applied scientists, and engineers working on Azure data and quality.
For Data Structures and Algorithms roles, this Microsoft practice set focuses most on Graphs and Graph Algorithms (7), Arrays, Strings and Hashing (4), Heaps, Priority Queues and Greedy (4), Dynamic Programming (4). It has 20 medium, 10 hard questions, so you can start easy and work up to the harder ones.
Company type
Product
Headquarters
Redmond, Washington, USA
Main India offices
Hyderabad, Bengaluru, Noida, Gurugram, Pune
Microsoft Data Structures and Algorithms interview process
Online coding assessment
Technical round 1 (DSA)
Technical round 2 (DSA or design)
Hiring manager round
AA (As Appropriate) round
Typical pattern based on public candidate experiences. Rounds vary by role, team and year.
Solved for MicrosoftStart 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
Your brute-force solution for the longest substring without repeating characters is O(n cubed). How would you improve it?
I would use a variable sliding window. Keep a map from character to its last index and a left pointer. Move the right pointer through the string; when the current character was seen at an index at or after left, move left to that index plus one. Update the best length at each step. Each character is processed a constant number of times, giving O(n) time and O(alphabet size) space.
02
What are the complexities of heap operations, and why does building a heap take O(n)?
Peek at the root is O(1). Insert adds at the end and sifts up, and extract removes the root, moves the last element to the top and sifts down, both O(log n). Building a heap from n elements by sifting down from the last internal node to the root takes O(n), not O(n log n), because most nodes are near the bottom and move only a few levels; the sum of heights is linear.
03
Find the next greater element for every element of an array.
def next_greater(nums):
res = [-1] * len(nums)
stack = [] # indices with decreasing values
for i, x in enumerate(nums):
while stack and nums[stack[-1]] < x:
res[stack.pop()] = x
stack.append(i)
return res
# [4, 5, 2, 25] -> [5, 25, 25, -1]
# Each index is pushed and popped once: O(n)
04
Packages with given weights must be shipped in order within D days. How do you find the minimum ship capacity?
The capacity lies between the heaviest package and the total weight, and if a capacity works, any larger one also works, so binary search the answer. For a candidate capacity, greedily load packages day by day, starting a new day when the next package does not fit, and count days. If the days are within D, try smaller; otherwise try larger. Time is O(n log of total weight).
05
How is the longest common subsequence computed with DP?
Let dp[i][j] be the LCS length of the first i characters of A and the first j characters of B. If A[i-1] equals B[j-1], dp[i][j] is dp[i-1][j-1] plus 1; otherwise it is the maximum of dp[i-1][j] and dp[i][j-1]. Fill the table row by row in O(m times n) time. Backtracking from dp[m][n] recovers the actual subsequence. LCS underlies diff tools and DNA sequence comparison.
06
Find the shortest path length from the top-left to the bottom-right of a grid where 1 is a wall.
from collections import deque
def shortest_path(grid):
R, C = len(grid), len(grid[0])
if grid[0][0] or grid[R-1][C-1]:
return -1
q = deque([(0, 0, 1)])
seen = {(0, 0)}
while q:
r, c, d = q.popleft()
if (r, c) == (R - 1, C - 1):
return d
for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
nr, nc = r + dr, c + dc
if 0 <= nr < R and 0 <= nc < C and not grid[nr][nc] and (nr, nc) not in seen:
seen.add((nr, nc))
q.append((nr, nc, d + 1))
return -1
# BFS: O(R * C)
07
Your knapsack DP has n equal to 100 items but capacity up to 10 to the power 9, so the table does not fit in memory. What do you do?
A table indexed by capacity is impossible, so I change the state. If item values are small, use dp[v] as the minimum weight needed to achieve value v, then pick the largest v whose weight fits the capacity; that is O(n times total value). If n is about 40, meet in the middle: enumerate subsets of each half, sort one side and binary search. Otherwise approximation or branch and bound are options.
08
An array of size 100000 must answer 100000 queries asking for the sum between two indices. What approach would you use?
Recomputing each sum is O(n) per query, about 10 to the power 10 operations in total, which is too slow. Since the array does not change, I would build a prefix sum array once in O(n) and answer each query in O(1) as pre[r+1] minus pre[l], giving O(n plus q) overall. If the array also receives updates, I would switch to a Fenwick tree or segment tree for O(log n) updates and queries.
09
Solve jump game: can you reach the last index if nums[i] is the maximum jump from i?
def can_jump(nums):
farthest = 0
for i, step in enumerate(nums):
if i > farthest: # this index is unreachable
return False
farthest = max(farthest, i + step)
if farthest >= len(nums) - 1:
return True
return True
# [2,3,1,1,4] -> True, [3,2,1,0,4] -> False
# Greedy: track the farthest reachable index, O(n) time, O(1) space
10
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
11
Generate all subsets of a list of distinct numbers.
def subsets(nums):
result = []
current = []
def backtrack(i):
if i == len(nums):
result.append(current[:])
return
current.append(nums[i]) # include nums[i]
backtrack(i + 1)
current.pop() # exclude nums[i]
backtrack(i + 1)
backtrack(0)
return result
# 2^n subsets, each up to n long: O(n * 2^n) time
12
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.
13
Return an array where each element is the product of all other elements, without using division.
def product_except_self(nums):
n = len(nums)
out = [1] * n
prefix = 1
for i in range(n): # product of everything to the left
out[i] = prefix
prefix *= nums[i]
suffix = 1
for i in range(n - 1, -1, -1): # multiply by everything to the right
out[i] *= suffix
suffix *= nums[i]
return out
# [1,2,3,4] -> [24,12,8,6]; O(n) time, O(1) extra space besides output
14
Implement Union-Find with path compression and union by size.
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
16
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.
17
How does cycle detection differ in directed and undirected graphs?
In an undirected graph, DFS finds a cycle when it reaches an already visited vertex that is not the parent of the current vertex; Union-Find also works by checking whether an edge joins vertices already in the same set. In a directed graph you need three states, unvisited, in the current recursion stack and finished, and a cycle exists when DFS reaches a vertex still on the stack. Kahn's algorithm also detects directed cycles.
18
A Sudoku solver using plain backtracking is too slow on hard puzzles. How would you speed it up?
Add stronger pruning and better choice ordering. Keep bitmasks of used digits for each row, column and box, so validity checks are O(1). Always fill the empty cell with the fewest candidates first, the minimum remaining values heuristic, which shrinks the search tree dramatically. Apply constraint propagation, filling cells with a single candidate before guessing. For the hardest cases, exact cover with Dancing Links is very fast.
19
Given meeting start and end times for a day, how do you find the minimum number of rooms needed?
Sort meetings by start time and keep a min-heap of end times for rooms in use. For each meeting, if the earliest ending room is free by its start time, pop it; then push this meeting's end time. The heap size at the end, or its maximum, is the answer. This is O(n log n). An alternative sorts start and end times separately and sweeps with two pointers, counting overlaps.
20
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.
21
Why are you looking for a change from your current job?
Situation: in my current role I have learned a lot maintaining internal tools for two years. Task: I want to grow into harder engineering problems. Action: I have been strengthening my data structures, system design and backend skills through projects and by taking ownership of performance work in my team. Result: I am now ready for a role with larger scale and more technical depth, which is why this position appeals to me.
22
Detect whether a linked list has a cycle and return the node where the cycle begins.
def detect_cycle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow is fast: # cycle found
slow = head
while slow is not fast: # move both one step
slow = slow.next
fast = fast.next
return slow # start of the cycle
return None
# O(n) time, O(1) space
23
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.
24
You can use an O(n log n) algorithm with high constant factors or a simple O(n squared) one. For what inputs might the O(n squared) choice be better?
Big-O ignores constants, so for small n the simpler algorithm can be faster in practice. Insertion sort beats merge sort for arrays below roughly 16 to 32 elements, which is why library sorts such as Timsort switch to insertion sort for small runs. I would benchmark on realistic input sizes, choose the asymptotically better algorithm when n can grow, and use a hybrid when both ranges occur.
25
Serialize a binary tree to a string and deserialize it back.
Run a BFS limited to depth 2 from the user. For every friend, look at their friends, skip the user and existing friends, and count how many mutual friends each candidate has using a hash map. Rank candidates by mutual friend count and other signals. For users with thousands of friends this gets expensive, so production systems precompute suggestions offline in batch jobs and cache them.
A topological order lists the vertices of a DAG so every edge goes from earlier to later, such as an order to take courses. Kahn's algorithm computes in-degrees, pushes zero in-degree vertices into a queue and repeatedly removes them while decreasing neighbours' in-degrees; if not all vertices are output, a cycle exists. The DFS method adds a vertex to a list after visiting its descendants and reverses the list. Both are O(V plus E).
28
A network has 10 million devices and connections are added continuously. You must answer whether two devices are connected in real time. How?
Running BFS for every query is too slow. Since connections are only added, Union-Find is ideal: each new link is a union, and each query compares find results, both nearly O(1) amortised with path compression and union by size. Memory is two integer arrays of 10 million entries, about 80 MB. If links can also be removed, the problem becomes much harder and needs offline processing or specialised dynamic connectivity structures.
29
Explain the recurrence for the 0/1 knapsack problem.
Let dp[i][w] be the maximum value using the first i items with capacity w. For item i with weight wt and value val, either skip it, giving dp[i-1][w], or take it if wt is at most w, giving dp[i-1][w - wt] plus val; take the larger. Base cases are zero items or zero capacity. Time and space are O(n times W), and space can drop to O(W) by iterating w downwards in a single array.
30
Two linked lists merge at some node and share the rest. How do you find the merge point efficiently?
A hash set of the first list's nodes works in O(m plus n) time but uses O(m) space. The O(1) space trick uses two pointers: walk each list, and when a pointer reaches the end, redirect it to the head of the other list. Both pointers travel m plus n steps, so they meet at the intersection, or both become null if there is none. Comparing node references, not values, is essential.
Tips to crack the Microsoft Data Structures and Algorithms interview
Practise DSA on linked lists, trees and graphs, and be ready to write clean, compilable code with edge cases handled.
Learn basic Azure data services such as Azure SQL, Synapse and Data Factory if you are applying for data roles.
Prepare examples showing a growth mindset, which Microsoft highlights as a core part of its culture.
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; Microsoft interviewers usually ask follow-ups on your first answer.
Frequently asked questions
How many rounds are there in the Microsoft Data Structures and Algorithms interview?
Candidates usually go through 5 stages: Online coding assessment; Technical round 1 (DSA); Technical round 2 (DSA or design); Hiring manager round; AA (As Appropriate) 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 Microsoft Data Structures and Algorithms interview?
This practice set leans on Graphs and Graph Algorithms (7), Arrays, Strings and Hashing (4), Heaps, Priority Queues and Greedy (4), Dynamic Programming (4). Revise those first, then practise explaining one or two of your own projects end to end, because most Microsoft interviewers ask you to walk through real work.
Are these the exact questions asked at Microsoft?
No. These are curated practice questions that match the skills and difficulty usually tested in product interviews like Microsoft's. They are not a leaked or verified list of past questions.
Where does Microsoft hire Data Structures and Algorithms professionals in India?
Microsoft has large teams in Hyderabad, Bengaluru, Noida, Gurugram, Pune. Openings and locations change often, so check the Microsoft careers page and filter by city and experience.
Data Structures and Algorithms questions for similar companies