Skip to content
Interview prep ยท Data Structures and Algorithms

DSA Interview Questions: 14 Patterns, 40 Practice Problems and a Six-Week Plan

By Younus FardeenUpdated 11 Nov 202616 min read
Short answer

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 typeWhat the evidence saysBasis
Service companies, such as TCS, Infosys and WiproTCS 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 GoogleAmazon'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 companiesOften 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]))   # 49

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

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

5. 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 30

6. 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 4

8. 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]]))   # 4

9. 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 -1

11. 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]]))   # 2

13. 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 True

14. 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]))        # 4

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

TopicProblem (LeetCode number)PatternLevelIn Top Interview 150
Arrays and hashingTwo Sum (1)hash mapEasyYes
Arrays and hashingGroup Anagrams (49)hash mapMediumYes
Arrays and hashingProduct of Array Except Self (238)prefix and suffix productsMediumYes
Arrays and hashingLongest Consecutive Sequence (128)hash setMediumYes
Arrays and hashingSubarray Sum Equals K (560)prefix sums, hash mapMediumNo
Two pointers3Sum (15)sort, two pointersMediumYes
Two pointersContainer With Most Water (11)two pointersMediumYes
Two pointersTrapping Rain Water (42)two pointersHardYes
Sliding windowLongest Substring Without Repeating Characters (3)sliding windowMediumYes
Sliding windowMinimum Window Substring (76)sliding window, countsHardYes
StackValid Parentheses (20)stackEasyYes
StackDaily Temperatures (739)monotonic stackMediumNo
Binary searchSearch in Rotated Sorted Array (33)binary searchMediumYes
Binary searchKoko Eating Bananas (875)binary search on the answerMediumNo
Linked listReverse Linked List (206)pointer rewiringEasyNo
Linked listLinked List Cycle (141)fast and slow pointersEasyYes
Linked listMerge Two Sorted Lists (21)two pointersEasyYes
TreesMaximum Depth of Binary Tree (104)DFSEasyYes
TreesBinary Tree Level Order Traversal (102)BFSMediumYes
TreesValidate Binary Search Tree (98)DFS with boundsMediumYes
TreesLowest Common Ancestor of a Binary Tree (236)DFSMediumYes
GraphsNumber of Islands (200)DFS or BFSMediumYes
GraphsCourse Schedule (207)BFS, topological sortMediumYes
GraphsRotting Oranges (994)multi-source BFSMediumNo
Union-findNumber of Provinces (547)union-find or DFSMediumNo
Union-findRedundant Connection (684)union-findMediumNo
HeapKth Largest Element in an Array (215)heapMediumYes
HeapTop K Frequent Elements (347)hash map, heapMediumNo
HeapMerge k Sorted Lists (23)heapHardYes
IntervalsMerge Intervals (56)sort, mergeMediumYes
IntervalsNon-overlapping Intervals (435)sort, greedyMediumNo
BacktrackingSubsets (78)backtrackingMediumNo
BacktrackingCombination Sum (39)backtrackingMediumYes
Dynamic programmingClimbing Stairs (70)1-D DPEasyYes
Dynamic programmingHouse Robber (198)1-D DPMediumYes
Dynamic programmingCoin Change (322)DPMediumYes
Dynamic programmingLongest Common Subsequence (1143)2-D DPMediumNo
Dynamic programmingLongest Increasing Subsequence (300)DPMediumYes
TrieImplement Trie (Prefix Tree) (208)trieMediumYes
Bit manipulationSingle Number (136)XOREasyYes

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 algorithmTimeNote
List index, appendO(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 lookupO(1) averageO(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 searchO(log n)Needs sorted data or a monotonic yes-or-no test
Heap push or popO(log n)heapify on a list is O(n)
BFS or DFSO(V + E)O(V) extra space for the queue or stack and the visited set
Dijkstra with a binary heapO((V + E) log V)Non-negative edge weights only
Union-findNear O(1) per operationAmortised, with path compression and union by rank
Trie insert or searchO(L)L is the word length
Sliding window, two pointers, prefix sumsO(n)Each index moves forward a bounded number of times
Subsets or permutationsO(2^n) or O(n!)Prune to cut the search
Dynamic programmingStates x work per stateCoin 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.

  1. 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.
  2. 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.
  3. 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.
  4. Week 4, trees and graphs. The four tree problems, then Number of Islands, Course Schedule, Rotting Oranges, Number of Provinces and Redundant Connection.
  5. Week 5, recursion and DP. Subsets, Combination Sum, Climbing Stairs, House Robber, Coin Change, Longest Common Subsequence and Longest Increasing Subsequence.
  6. 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:

  1. Restate and clarify. Say the problem in your own words, then ask about input size, duplicates, negative numbers and empty input.
  2. Work one small example by hand. Write it out; it often shows the pattern.
  3. State the brute force and its cost. Say it aloud, for example 'two loops, O(n squared)'. It shows a correct fallback.
  4. Name the pattern and why the cue fits. Then give the better time and space cost before you write code.
  5. Code in small named pieces, talking as you go. If you get stuck, say what you tried and what you are checking next.
  6. 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

Learn this with mentors

Programmes for builders and engineers with admissions open: live classes, mentors and project work.

Continue learning

Learning path

Data Structures and Algorithms learning path

Arrays to dynamic programming in order, with a problem plan.

Roadmap

Competitive programming roadmap

Platforms, India pathway, a 6-month plan and what it means for jobs

Open →
Interview prep

React interview questions

40 questions, model answers and six coding problems for React 19.3

Open →