Data Structures and Algorithms Interview India 2026: Complete DSA Guide

Arrays are the most tested topic in Indian coding interviews.

Two-pointer technique:

• Pair sum in sorted array: initialize left=0, right=n-1; move left right if sum too small, move right left if too large
• Container with most water: same two-pointer; min(height[l], height[r]) * (r-l); move the shorter side
• Three-sum: sort, then for each element fix it and use two-pointer for the rest; skip duplicates

Sliding window:

• Longest substring without repeating characters: expand right, shrink left when duplicate found in a HashSet; track max window size
• Maximum sum subarray of size K: add element at right, remove element at left, track running sum
• Minimum window substring: two frequency maps; expand right until all characters covered, shrink left while still valid

Prefix sums:

• Range sum query: precompute prefix[i] = prefix[i-1] + arr[i]; query sum(l, r) = prefix[r] - prefix[l-1] in O(1)
• Subarray sum equals K: for each index, check if prefix[i] - K exists in a HashMap of previous prefix sums

Kadane's algorithm (maximum subarray sum):

• Track currentMax and globalMax; at each index: currentMax = max(arr[i], currentMax + arr[i]); update globalMax

Merge intervals:

• Sort by start; iterate and if current start <= previous end, merge (extend end); else add to result

Tree traversal questions:

DFS (recursion):

• In-order (left, root, right): gives sorted output for a BST
• Pre-order (root, left, right): used for serialization
• Post-order (left, right, root): used for deletion (delete children before parent)

Iterative DFS using a stack:

• Pre-order: push root; while stack not empty: pop, process, push right then left (so left is processed first)
• In-order: maintain a curr pointer; push curr to stack and go left; when null, pop and process, then go right

BFS (level-order) using a queue:

• While queue not empty: capture queue.size() as the level count; dequeue that many nodes and process each; enqueue their non-null children

Key tree problems:

• Check if BST is valid: pass a (min, max) range to each node; root has (-inf, +inf); left child gets (min, root.val); right child gets (root.val, max)
• Lowest common ancestor: if both target nodes are greater than current, go right; if both less, go left; else current is the LCA
• Diameter: for each node, diameter through it = leftHeight + rightHeight; track global max; return height (1 + max(leftH, rightH))
• Serialize/deserialize: BFS with null markers; or pre-order DFS with null markers; reconstruct by reading the same order

Graph interview questions:

BFS (Breadth-First Search):

• Use a queue and a visited set
• Best for: shortest path in an unweighted graph, level-order traversal, finding connected components
• Time: O(V+E), Space: O(V)

DFS (Depth-First Search):

• Use recursion or an explicit stack; mark visited before recursive calls
• Best for: cycle detection, topological sort, connected components, path existence

Topological sort (Kahn's algorithm):

• Compute in-degree for all nodes
• Add all nodes with in-degree 0 to a queue
• While queue not empty: dequeue, add to result, decrement in-degree of all neighbours; if any neighbour's in-degree becomes 0, enqueue it
• If result length < total nodes: cycle exists (course schedule problem)

Union-Find (Disjoint Set Union):

• find(x): return x if parent[x] == x, else parent[x] = find(parent[x]) (path compression)
• union(x, y): link the roots; use rank to keep the tree flat
• Use for: number of connected components, detect cycle in an undirected graph, minimum spanning tree (Kruskal's)

Dijkstra's algorithm (weighted shortest path):

• Priority queue (min-heap) of (distance, node)
• Relax edges: if dist[u] + weight < dist[v], update dist[v] and push to heap
• Time: O((V+E) log V) with a binary heap

Dynamic programming patterns:

1D DP:

• Climbing stairs: dp[i] = dp[i-1] + dp[i-2]; same as Fibonacci
• House robber: dp[i] = max(dp[i-1], dp[i-2] + nums[i]); cannot rob adjacent houses
• Jump game: track maxReach; at each index if i > maxReach, return false; else maxReach = max(maxReach, i + nums[i])
• Longest increasing subsequence: dp[i] = max over all j < i where nums[j] < nums[i] of dp[j] + 1; overall max

2D DP:

• Coin change (minimum coins): dp[amount] = min over all coins of (1 + dp[amount - coin]); initialize dp[0] = 0, rest = infinity
• Longest common subsequence: if chars match, dp[i][j] = dp[i-1][j-1] + 1; else max(dp[i-1][j], dp[i][j-1])
• Edit distance: if chars match, dp[i][j] = dp[i-1][j-1]; else min(insert, delete, replace) + 1
• Knapsack 0/1: dp[i][w] = max(dp[i-1][w], dp[i-1][w-wt[i]] + val[i]) if wt[i] <= w, else dp[i-1][w]

Interval DP (SDE-2+):

• Burst balloons: dp[l][r] = max over k in (l, r) of dp[l][k] + dp[k][r] + nums[l]nums[k]nums[r]

Memoization pattern:

• Convert recursion to memoization by adding a cache; only compute each subproblem once

Sorting algorithms for interviews:

Merge sort:

• Divide in half recursively until single elements, then merge in sorted order
• Time: O(n log n) always; Space: O(n) for the merge step; Stable
• Use for: counting inversions (count how many swaps the merge step makes)

Quick sort:

• Choose a pivot; partition so all elements left < pivot, right > pivot; recurse
• Time: O(n log n) average, O(n^2) worst (bad pivot); Space: O(log n) stack
• QuickSelect: find Kth smallest in O(n) average by only recursing into one partition

Heap sort:

• Build a max-heap O(n); repeatedly extract max O(log n) * n times
• Time: O(n log n); Space: O(1); Unstable

Counting/Radix sort:

• For integers in a known range [0, k]: count occurrences, compute prefix sums, place elements in output
• Time: O(n + k); Space: O(k); use when k is small relative to n

Binary search variants:

• Standard: lo=0, hi=n-1; mid=(lo+hi)/2; if arr[mid]==target return mid; update lo or hi
• Find first occurrence of target: continue even when found; update hi = mid - 1
• Find insertion position (lower bound): find first index where arr[index] >= target
• Search in rotated sorted array: determine which half is sorted, decide which half contains target