DSA interview questions repeat a small set of patterns, so learn the patterns before grinding hundreds of problems. This page gives 14 patterns with a cue, a canonical problem and tested Python code, then 40 commonly practised LeetCode problems, a complexity table, a six-week plan and a way to talk through a solution.
This page is for students and freshers preparing for coding rounds at service companies, product companies and startups in India. Company notes come from pages opened on 11 November 2026 where a company publishes them, and are labelled typical where it does not. Every Python block ran under Python 3.9, and its output is in the comments.
The 40 problems were checked against LeetCode on 11 November 2026: titles, numbers and levels are as LeetCode lists them, and all are free to open. We describe problems in our own words and do not copy statements. Masai's 7-step approach to solve any coding problem covers the process; this page covers the patterns and the practice set.
What coding rounds ask, by company type
| Company type | What the evidence says | Basis |
|---|---|---|
| Service companies, such as TCS, Infosys and Wipro | TCS iON's NQT page lists a 65-question, 75-minute Foundation part, then an Advanced part of 16 questions in 115 minutes that includes Advanced Coding. Expect arrays, strings, hashing, sorting and maths at easy to medium level. | TCS iON page read 11 Nov 2026 for the structure; the problem types are typical, not stated by TCS |
| Product companies, such as Amazon, Microsoft, Meta and Google | Amazon's online assessment tests coding, problem solving and its Leadership Principles, and the coding part averages 70 minutes. Microsoft rounds are 45 minutes, in your strongest language with no pseudocode, and expect you to test your own code. Meta's first screen has two problems in a 35-minute coding block. | Amazon, Microsoft and Meta career pages read 11 Nov 2026; Meta's page is dated October 2022. Google: no public page opened |
| Startups and mid-size companies | Often a practical task, such as a small feature or a bug, plus one or two array, string or hash map problems. Hard graph or DP questions are less common. | Typical; we found no published source |
Amazon's topics page lists data structures, algorithms and coding, and says interviewers look at how you apply what you know, not whether you memorised details. Formats change by company and by drive, so read your own invitation. Time per problem is short in the formats above, which is why recognising the pattern matters more than remembering solutions.
The 14 patterns, each with a tested Python solution
Each pattern has a cue that tells you to reach for it, one canonical problem (named, not copied) and a solution whose output is in the comments. Learn the cue first, because the cue is what you recognise in an interview.
1. Two pointers
Cue: a sorted array, a pair or triple condition, or two cursors moving inward or at different speeds. Canonical problem: Container With Most Water (LeetCode 11). Cost: O(n) time, O(1) space. Linked lists use the fast and slow version: see linked lists explained.
def max_area(height):
left, right = 0, len(height) - 1
best = 0
while left < right:
best = max(best, min(height[left], height[right]) * (right - left))
if height[left] < height[right]: # the shorter wall limits the area, so move it
left += 1
else:
right -= 1
return best
print(max_area([1, 8, 6, 2, 5, 4, 8, 3, 7])) # 492. Sliding window
Cue: longest, shortest or at most k, over a contiguous substring or subarray. Canonical problem: Longest Substring Without Repeating Characters (3). Cost: O(n) time, O(k) space for k distinct characters.
def longest_unique(s):
last_seen = {} # character -> index of its latest copy
start = best = 0
for i, ch in enumerate(s):
if ch in last_seen and last_seen[ch] >= start:
start = last_seen[ch] + 1 # shrink the window past the earlier copy
last_seen[ch] = i
best = max(best, i - start + 1)
return best
print(longest_unique("abcabcbb"), longest_unique("pwwkew")) # 3 33. Hash map
Cue: you keep asking whether you have seen a value, or you need counts or groups. Canonical problem: Two Sum (1). Cost: O(n) time, O(n) space. The hash map explainer covers collisions and average-case cost.
def two_sum(nums, target):
seen = {} # value -> index where we saw it
for i, x in enumerate(nums):
if target - x in seen: # the partner we need appeared earlier
return [seen[target - x], i]
seen[x] = i
return []
print(two_sum([2, 7, 11, 15], 9)) # [0, 1]4. Prefix sums
Cue: many range-sum questions, or a subarray whose sum equals a target. Canonical problem: Subarray Sum Equals K (560). Cost: O(n) time and space; it combines a running sum with a hash map.
from collections import defaultdict
def subarray_sum(nums, k):
seen = defaultdict(int)
seen[0] = 1 # the empty prefix
running = total = 0
for x in nums:
running += x
total += seen[running - k] # earlier prefixes that leave a slice summing to k
seen[running] += 1
return total
print(subarray_sum([1, 2, 3], 3), subarray_sum([1, 1, 1], 2)) # 2 25. Binary search
Cue: sorted data, or a yes-or-no test that flips once as the answer grows, such as the slowest speed that still finishes in time. Canonical problem: Koko Eating Bananas (875). Cost: O(n log m) for n piles and largest pile m.
def min_speed(piles, hours):
lo, hi = 1, max(piles) # the answer lies between 1 and the biggest pile
while lo < hi:
mid = (lo + hi) // 2
needed = sum((p + mid - 1) // mid for p in piles) # hours at speed mid (ceiling)
if needed <= hours:
hi = mid # mid works, try slower
else:
lo = mid + 1
return lo
print(min_speed([3, 6, 7, 11], 8), min_speed([30, 11, 23, 4, 20], 5)) # 4 306. Stack and monotonic stack
Cue: matching brackets, undo order, or the next greater or smaller element. Canonical problem: Daily Temperatures (739). Cost: O(n), because each index is pushed and popped once. See applications of stack.
def daily_temperatures(temps):
answer = [0] * len(temps)
stack = [] # indexes still waiting for a warmer day
for i, t in enumerate(temps):
while stack and temps[stack[-1]] < t:
j = stack.pop()
answer[j] = i - j
stack.append(i)
return answer
print(daily_temperatures([73, 74, 75, 71, 69, 72, 76, 73])) # [1, 1, 4, 2, 1, 1, 0, 0]7. Heap
Cue: the k largest, smallest or most frequent items, or repeatedly taking the minimum of a changing set. Canonical problem: Kth Largest Element in an Array (215). Cost: O(n log k) time, O(k) space.
import heapq
def kth_largest(nums, k):
heap = [] # a min-heap holding the k largest values so far
for x in nums:
heapq.heappush(heap, x)
if len(heap) > k:
heapq.heappop(heap) # drop the smallest of the k+1
return heap[0]
print(kth_largest([3, 2, 1, 5, 6, 4], 2), kth_largest([3, 2, 3, 1, 2, 4, 5, 5, 6], 4)) # 5 48. BFS and DFS
Cue: a grid, graph or tree. Connected regions suit DFS; fewest steps or level by level suits BFS. Canonical problems: Number of Islands (200) and Rotting Oranges (994). Cost: O(rows x columns). See the graph explainer and tree explainer.
from collections import deque
def num_islands(grid): # depth-first search with an explicit stack
rows, cols = len(grid), len(grid[0])
seen, islands = set(), 0
for r in range(rows):
for c in range(cols):
if grid[r][c] == "1" and (r, c) not in seen:
islands += 1
stack = [(r, c)]
while stack:
y, x = stack.pop()
if (y, x) in seen or not (0 <= y < rows and 0 <= x < cols) or grid[y][x] != "1":
continue
seen.add((y, x))
stack += [(y + 1, x), (y - 1, x), (y, x + 1), (y, x - 1)]
return islands
def minutes_to_rot(grid): # breadth-first search from every rotten orange at once
rows, cols = len(grid), len(grid[0])
queue, fresh = deque(), 0
for r in range(rows):
for c in range(cols):
if grid[r][c] == 2:
queue.append((r, c, 0))
elif grid[r][c] == 1:
fresh += 1
minutes = 0
while queue:
y, x, minutes = queue.popleft()
for ny, nx in ((y + 1, x), (y - 1, x), (y, x + 1), (y, x - 1)):
if 0 <= ny < rows and 0 <= nx < cols and grid[ny][nx] == 1:
grid[ny][nx] = 2
fresh -= 1
queue.append((ny, nx, minutes + 1))
return minutes if fresh == 0 else -1
print(num_islands(["11000", "11000", "00100", "00011"])) # 3
print(minutes_to_rot([[2, 1, 1], [1, 1, 0], [0, 1, 1]])) # 49. Backtracking
Cue: list all combinations, subsets or permutations, with small input. Choose, explore, undo. Canonical problem: Combination Sum (39). Cost: exponential, so prune early. Recursion is the base skill.
def combination_sum(candidates, target):
result = []
def go(start, path, remaining):
if remaining == 0:
result.append(path[:]) # a copy, because path keeps changing
return
for i in range(start, len(candidates)):
if candidates[i] <= remaining:
path.append(candidates[i]) # choose
go(i, path, remaining - candidates[i]) # explore (i, so a number can repeat)
path.pop() # un-choose
go(0, [], target)
return result
print(combination_sum([2, 3, 6, 7], 7)) # [[2, 2, 3], [7]]10. Dynamic programming
Cue: fewest, most or number of ways, with choices at each step and repeated sub-problems. Canonical problem: Coin Change (322). Cost: O(amount x coins) time. Start with the dynamic programming explainer.
def coin_change(coins, amount):
INF = amount + 1
dp = [0] + [INF] * amount # dp[a] = fewest coins that make amount a
for a in range(1, amount + 1):
for c in coins:
if c <= a:
dp[a] = min(dp[a], dp[a - c] + 1)
return dp[amount] if dp[amount] != INF else -1
print(coin_change([1, 2, 5], 11), coin_change([2], 3)) # 3 -111. Intervals
Cue: ranges with a start and end, and words like merge, overlap or schedule. Sort by start first. Canonical problem: Merge Intervals (56). Cost: O(n log n) for the sort.
def merge_intervals(intervals):
intervals = sorted(intervals) # sort by start so overlaps become neighbours
merged = [intervals[0][:]]
for start, end in intervals[1:]:
if start <= merged[-1][1]: # overlaps the last merged interval
merged[-1][1] = max(merged[-1][1], end)
else:
merged.append([start, end])
return merged
print(merge_intervals([[1, 3], [8, 10], [2, 6], [15, 18]])) # [[1, 6], [8, 10], [15, 18]]12. Union-find
Cue: are two items connected, how many groups, and groups that merge over time. Canonical problem: Number of Provinces (547). Cost: nearly constant per operation with path compression and union by size, as in the code below.
def count_provinces(is_connected):
n = len(is_connected)
parent = list(range(n))
size = [1] * n
def find(x):
while parent[x] != x:
parent[x] = parent[parent[x]] # path halving keeps trees flat
x = parent[x]
return x
groups = n
for i in range(n):
for j in range(i + 1, n):
if is_connected[i][j]:
ri, rj = find(i), find(j)
if ri != rj: # two separate groups just joined
if size[ri] < size[rj]:
ri, rj = rj, ri # attach the smaller tree under the bigger one
parent[rj] = ri
size[ri] += size[rj]
groups -= 1
return groups
print(count_provinces([[1, 1, 0], [1, 1, 0], [0, 0, 1]])) # 213. Trie
Cue: many words with prefix queries, such as autocomplete. Canonical problem: Implement Trie (Prefix Tree) (208). Cost: O(L) to insert or search a word of length L.
class Trie:
def __init__(self):
self.root = {}
def insert(self, word):
node = self.root
for ch in word:
node = node.setdefault(ch, {})
node["$"] = True # marks the end of a stored word
def _walk(self, text):
node = self.root
for ch in text:
if ch not in node:
return None
node = node[ch]
return node
def search(self, word):
node = self._walk(word)
return node is not None and "$" in node
def starts_with(self, prefix):
return self._walk(prefix) is not None
t = Trie()
t.insert("apple")
print(t.search("apple"), t.search("app"), t.starts_with("app")) # True False True14. Bit manipulation
Cue: one value appears once while the others come in pairs, powers of two, or flags packed into an integer. Canonical problem: Single Number (136). Cost: O(n) time, O(1) space.
def single_number(nums):
result = 0
for x in nums:
result ^= x # equal pairs cancel out under XOR
return result
print(single_number([4, 1, 2, 1, 2])) # 440 commonly practised problems
No company publishes its question bank, so this is a practice set chosen to cover every pattern above, not a leaked list. Titles, numbers and levels were read from LeetCode on 11 November 2026, and 29 of the 40 are in LeetCode's own Top Interview 150 study plan. Solve one pattern at a time.
| Topic | Problem (LeetCode number) | Pattern | Level | In Top Interview 150 |
|---|---|---|---|---|
| Arrays and hashing | Two Sum (1) | hash map | Easy | Yes |
| Arrays and hashing | Group Anagrams (49) | hash map | Medium | Yes |
| Arrays and hashing | Product of Array Except Self (238) | prefix and suffix products | Medium | Yes |
| Arrays and hashing | Longest Consecutive Sequence (128) | hash set | Medium | Yes |
| Arrays and hashing | Subarray Sum Equals K (560) | prefix sums, hash map | Medium | No |
| Two pointers | 3Sum (15) | sort, two pointers | Medium | Yes |
| Two pointers | Container With Most Water (11) | two pointers | Medium | Yes |
| Two pointers | Trapping Rain Water (42) | two pointers | Hard | Yes |
| Sliding window | Longest Substring Without Repeating Characters (3) | sliding window | Medium | Yes |
| Sliding window | Minimum Window Substring (76) | sliding window, counts | Hard | Yes |
| Stack | Valid Parentheses (20) | stack | Easy | Yes |
| Stack | Daily Temperatures (739) | monotonic stack | Medium | No |
| Binary search | Search in Rotated Sorted Array (33) | binary search | Medium | Yes |
| Binary search | Koko Eating Bananas (875) | binary search on the answer | Medium | No |
| Linked list | Reverse Linked List (206) | pointer rewiring | Easy | No |
| Linked list | Linked List Cycle (141) | fast and slow pointers | Easy | Yes |
| Linked list | Merge Two Sorted Lists (21) | two pointers | Easy | Yes |
| Trees | Maximum Depth of Binary Tree (104) | DFS | Easy | Yes |
| Trees | Binary Tree Level Order Traversal (102) | BFS | Medium | Yes |
| Trees | Validate Binary Search Tree (98) | DFS with bounds | Medium | Yes |
| Trees | Lowest Common Ancestor of a Binary Tree (236) | DFS | Medium | Yes |
| Graphs | Number of Islands (200) | DFS or BFS | Medium | Yes |
| Graphs | Course Schedule (207) | BFS, topological sort | Medium | Yes |
| Graphs | Rotting Oranges (994) | multi-source BFS | Medium | No |
| Union-find | Number of Provinces (547) | union-find or DFS | Medium | No |
| Union-find | Redundant Connection (684) | union-find | Medium | No |
| Heap | Kth Largest Element in an Array (215) | heap | Medium | Yes |
| Heap | Top K Frequent Elements (347) | hash map, heap | Medium | No |
| Heap | Merge k Sorted Lists (23) | heap | Hard | Yes |
| Intervals | Merge Intervals (56) | sort, merge | Medium | Yes |
| Intervals | Non-overlapping Intervals (435) | sort, greedy | Medium | No |
| Backtracking | Subsets (78) | backtracking | Medium | No |
| Backtracking | Combination Sum (39) | backtracking | Medium | Yes |
| Dynamic programming | Climbing Stairs (70) | 1-D DP | Easy | Yes |
| Dynamic programming | House Robber (198) | 1-D DP | Medium | Yes |
| Dynamic programming | Coin Change (322) | DP | Medium | Yes |
| Dynamic programming | Longest Common Subsequence (1143) | 2-D DP | Medium | No |
| Dynamic programming | Longest Increasing Subsequence (300) | DP | Medium | Yes |
| Trie | Implement Trie (Prefix Tree) (208) | trie | Medium | Yes |
| Bit manipulation | Single Number (136) | XOR | Easy | Yes |
The mix is 8 easy, 29 medium and 3 hard. Start with the easy and medium problems in each pattern. More practice sites are in the coding practice websites list.
Time and space complexity cheat table
| Operation or algorithm | Time | Note |
|---|---|---|
| List index, append | O(1) | Append is amortised O(1) in Python |
List insert or pop(0) | O(n) | Use collections.deque to add or remove at both ends |
| Dict or set lookup | O(1) average | O(n) in the worst case if many keys collide |
list.sort() | O(n log n) | Sorting first often turns a nested loop into one pass |
| Binary search | O(log n) | Needs sorted data or a monotonic yes-or-no test |
| Heap push or pop | O(log n) | heapify on a list is O(n) |
| BFS or DFS | O(V + E) | O(V) extra space for the queue or stack and the visited set |
| Dijkstra with a binary heap | O((V + E) log V) | Non-negative edge weights only |
| Union-find | Near O(1) per operation | Amortised, with path compression and union by rank |
| Trie insert or search | O(L) | L is the word length |
| Sliding window, two pointers, prefix sums | O(n) | Each index moves forward a bounded number of times |
| Subsets or permutations | O(2^n) or O(n!) | Prune to cut the search |
| Dynamic programming | States x work per state | Coin Change: amount x number of coins |
Python costs come from the time complexity page of the Python documentation. Say the space cost too: a hash map or visited set is O(n) extra.
A six-week plan
This is our suggested order, not a published syllabus. Stretch it if you have more time, and re-solve any problem you could not finish unaided. Use a practice site with a code editor and run your own tests.
- Week 1, arrays and hashing. Big-O basics, then Two Sum, Group Anagrams, Product of Array Except Self, Longest Consecutive Sequence and Subarray Sum Equals K.
- Week 2, windows and searching. 3Sum, Container With Most Water, Trapping Rain Water, Longest Substring Without Repeating Characters, Minimum Window Substring, Search in Rotated Sorted Array and Koko Eating Bananas.
- Week 3, stacks, lists and heaps. Valid Parentheses, Daily Temperatures, the three linked-list problems, Kth Largest Element, Top K Frequent Elements and Merge k Sorted Lists.
- Week 4, trees and graphs. The four tree problems, then Number of Islands, Course Schedule, Rotting Oranges, Number of Provinces and Redundant Connection.
- Week 5, recursion and DP. Subsets, Combination Sum, Climbing Stairs, House Robber, Coin Change, Longest Common Subsequence and Longest Increasing Subsequence.
- Week 6, the rest, then mocks. Merge Intervals, Non-overlapping Intervals, Implement Trie and Single Number, then timed 45-minute mock rounds. For harder contest-style problems, see the competitive programming roadmap.
Keep the data structures and algorithms path open for the theory behind each week. Masai's data structures and algorithms explained with examples covers arrays, stacks, recursion, searching and sorting if a week starts from zero.
How to talk through a solution
Interviewers watch how you think as well as the answer. Microsoft's guidance says to ask clarifying questions and make a plan before you code, and to test your solution before you say you are done. A routine you can repeat:
- Restate and clarify. Say the problem in your own words, then ask about input size, duplicates, negative numbers and empty input.
- Work one small example by hand. Write it out; it often shows the pattern.
- State the brute force and its cost. Say it aloud, for example 'two loops, O(n squared)'. It shows a correct fallback.
- Name the pattern and why the cue fits. Then give the better time and space cost before you write code.
- Code in small named pieces, talking as you go. If you get stuck, say what you tried and what you are checking next.
- Test and close. Trace your example, an empty input and one edge case, then repeat the final time and space cost.
Frequently asked questions
Which DSA topics are asked most in interviews?
Arrays and strings, hash maps, linked lists, trees, graphs, heaps, recursion and dynamic programming. Microsoft's guidance names arrays and strings, queues and lists, linked lists, trees and tries, hash maps and sets, and graphs. No company publishes frequency counts, so this follows the pages above.
How many DSA problems should I solve before interviews?
No source gives a reliable number. Our view: 40 problems you can solve unaided and explain, spread across the 14 patterns, beat 300 half-understood ones. Re-solve missed problems a week later, and add easy-to-medium variants of the patterns you find hardest.
Is DSA asked at service companies like TCS?
Yes, in TCS's test: the iON NQT page lists Advanced Coding in the Advanced part. The problems are typically easier than product-company rounds, though that is our reading, not a TCS statement. Drives differ by year and role, so read the notice for yours.
Which language should I use for DSA interviews?
Use the one you know best. Microsoft says to code in the language you are strongest in, and Amazon advises practising the language you plan to use. Python is short to write, while Java and C++ are common too. Know your language's hash map, heap and sort.
How do I know which pattern a problem needs?
Look for the cue: sorted input suggests two pointers or binary search, longest contiguous range suggests a sliding window, k largest suggests a heap, and a grid suggests BFS or DFS. Then test the pattern on a tiny example before coding.
Do I need LeetCode premium?
No. None of the 40 problems in the table was marked paid-only in LeetCode's data on 11 November 2026. Other free practice sites are listed on our coding practice websites page.
Sources checked
- Amazon SDE online assessment
- Amazon software development interview topics
- Microsoft technical interviewing guidance
- Meta software engineering interview prep (dated Oct 2022)
- TCS iON NQT test structure
- LeetCode Top Interview 150 study plan
- LeetCode problem titles, numbers and levels
- Python built-in time complexity
- Union-find cost
- Dijkstra cost with a binary heap
Learn this with mentors
Programmes for builders and engineers with admissions open: live classes, mentors and project work.


