Top 10 DSA coding interview questions

Brute force: check every pair, O(n²) time.

Optimal: one pass with a hash map from value to index. For each number, check whether target - x was already seen.

def two_sum(nums, target):
    seen = {}
    for i, x in enumerate(nums):
        if target - x in seen:
            return [seen[target - x], i]
        seen[x] = i

O(n) time, O(n) space. If the array is sorted (or you may sort it and don't need original indices), two pointers give O(1) extra space. Follow-ups: 3Sum (sort + fix one element + two pointers, O(n²)), counting pairs, handling duplicates.

Iterative: walk the list, pointing each node back at the previous one.

def reverse(head):
    prev = None
    while head:
        nxt = head.next      # save the rest
        head.next = prev     # flip the pointer
        prev, head = head, nxt
    return prev

O(n) time, O(1) space.

Recursive: reverse the rest, then hook the current node onto the end.

def reverse_rec(head):
    if not head or not head.next:
        return head
    new_head = reverse_rec(head.next)
    head.next.next = head
    head.next = None
    return new_head

O(n) time and O(n) stack space. Mention the stack overflow risk for very long lists. Follow-ups: reverse in groups of k, reverse between positions m and n, check if a list is a palindrome.

Floyd's tortoise and hare: move slow one step and fast two steps. If there's a cycle, fast laps slow and they meet; if fast reaches the end, there's no cycle.

def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next
        if slow is fast:
            return True
    return False

O(n) time, O(1) space (a hash set of visited nodes also works but uses O(n) space). Follow-up: to find where the cycle starts, after they meet, move one pointer to the head and step both one at a time; they meet at the cycle's start.

Sliding window: extend the right end; when a character repeats inside the window, move the left end just past its previous position.

def length_of_longest_substring(s):
    last, left, best = {}, 0, 0
    for right, ch in enumerate(s):
        if last.get(ch, -1) >= left:
            left = last[ch] + 1
        last[ch] = right
        best = max(best, right - left + 1)
    return best

"abcabcbb" → 3 ("abc"). O(n) time, O(min(n, alphabet)) space. Explain why the brute force (check all substrings, O(n³) or O(n²)) repeats work, and how the window reuses it.

Sort by start, then sweep: if the current interval overlaps the last merged one, extend it; otherwise start a new one.

def merge(intervals):
    intervals.sort(key=lambda x: x[0])
    out = []
    for s, e in intervals:
        if out and s <= out[-1][1]:
            out[-1][1] = max(out[-1][1], e)
        else:
            out.append([s, e])
    return out

[[1,3],[2,6],[8,10],[15,18]] → [[1,6],[8,10],[15,18]]. O(n log n) for sorting. Related: insert interval, meeting rooms (can one person attend all? how many rooms are needed? use a min-heap of end times).

Push opening brackets onto a stack; for each closing bracket, the top of the stack must be its matching opener.

def is_valid(s):
    match = {")": "(", "]": "[", "}": "{"}
    stack = []
    for ch in s:
        if ch in match:
            if not stack or stack.pop() != match[ch]:
                return False
        else:
            stack.append(ch)
    return not stack

O(n) time and space. Edge cases: empty string (valid), only openers (stack not empty, invalid), a closer first (empty stack, invalid). Follow-ups: minimum additions to make valid, longest valid substring, generate all valid combinations (backtracking).

Depth with recursion (DFS):

def max_depth(root):
    if not root:
        return 0
    return 1 + max(max_depth(root.left), max_depth(root.right))

Level order with a queue (BFS), processing one level at a time:

from collections import deque
def level_order(root):
    if not root: return []
    res, q = [], deque([root])
    while q:
        level = []
        for _ in range(len(q)):
            node = q.popleft()
            level.append(node.val)
            if node.left: q.append(node.left)
            if node.right: q.append(node.right)
        res.append(level)
    return res

Both O(n) time. Space: O(h) for recursion, O(width) for BFS. Variants: right-side view, zigzag order, minimum depth (BFS stops at the first leaf).

Treat the grid as a graph. Each time you find unvisited land, count an island and flood-fill (DFS or BFS) every connected land cell so it isn't counted again.

def num_islands(grid):
    R, C = len(grid), len(grid[0])
    def dfs(r, c):
        if not (0 <= r < R and 0 <= c < C) or grid[r][c] != "1":
            return
        grid[r][c] = "#"          # mark visited
        dfs(r + 1, c); dfs(r - 1, c); dfs(r, c + 1); dfs(r, c - 1)
    count = 0
    for r in range(R):
        for c in range(C):
            if grid[r][c] == "1":
                count += 1
                dfs(r, c)
    return count

O(R×C) time. Mention that very large grids can overflow the recursion stack, so BFS with a queue is safer. Union-Find is another approach. Related: rotting oranges (multi-source BFS), max area of island, surrounded regions.

Greedy (take the biggest coin first) fails for coins like [1, 3, 4] and amount 6 (greedy gives 4+1+1, optimal is 3+3). Use dynamic programming: dp[a] = the fewest coins to make a.

def coin_change(coins, amount):
    dp = [0] + [float("inf")] * amount
    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] != float("inf") else -1

O(amount × coins) time, O(amount) space. Explain the state, the recurrence and the base case explicitly: that's what interviewers listen for in DP. Variant: number of ways to make the amount (loop coins on the outside to count combinations, not permutations).

Options, from simplest to best:

1. Sort descending and take index k−1: O(n log n).
2. Min-heap of size k: push each number, pop when size exceeds k; the top is the answer. O(n log k) time, O(k) space; great for streams.

import heapq
def kth_largest(nums, k):
    heap = []
    for x in nums:
        heapq.heappush(heap, x)
        if len(heap) > k:
            heapq.heappop(heap)
    return heap[0]

1. Quickselect (partition like quicksort, recurse into one side only): O(n) on average, O(n²) worst case, which randomised pivots make unlikely.

Discuss the trade-offs: the heap works on streaming data and has a guaranteed bound; quickselect is fastest on average but modifies the array.