Data Structures & Algorithms Interview Questions and Answers

Big O describes how runtime or memory grows with input size, ignoring constants and lower-order terms.

From fastest to slowest:

• O(1) constant: hash lookup, array index.
• O(log n) logarithmic: binary search, balanced tree operations.
• O(n) linear: single pass over input.
• O(n log n): efficient comparison sorts (merge, heap).
• O(n^2): nested loops such as naive pair comparison.
• O(2^n) exponential: naive recursive subsets.
• O(n!) factorial: brute-force permutations.

Also cover best/average/worst cases (quicksort is O(n log n) average, O(n^2) worst), space complexity, and amortised analysis (dynamic array append is amortised O(1)).

Binary search finds a target in a sorted array by halving the search range each step, giving O(log n).

def binary_search(nums, target):
    lo, hi = 0, len(nums) - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2      # avoids overflow
        if nums[mid] == target:
            return mid
        if nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

Pitfalls: off-by-one in the boundary update, using the wrong loop condition, integer overflow with (lo + hi) / 2, and forgetting the array must be sorted. Variants find the first/last occurrence using lower-bound and upper-bound templates.

Iterative (O(n) time, O(1) space):

def reverse(head):
    prev = None
    while head:
        nxt = head.next
        head.next = prev
        prev = head
        head = nxt
    return prev

Recursive (O(n) time, O(n) stack space):

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

Follow-ups: reverse a sublist between positions m and n, reverse in groups of k, and detect a cycle with Floyd's tortoise and hare.

• BFS explores level by level using a queue. It finds the shortest path in an unweighted graph, and is used for social-degree separation, maze shortest paths and level-order tree traversal. Space can be O(width) of the graph.
• DFS explores as deep as possible using a stack or recursion. It is used for cycle detection, topological sort, connected components, backtracking and path existence. Space is O(depth).

from collections import deque

def bfs(graph, start):
    seen, queue = {start}, deque([start])
    while queue:
        node = queue.popleft()
        for nxt in graph[node]:
            if nxt not in seen:
                seen.add(nxt)
                queue.append(nxt)

Recursive DFS can overflow the stack on deep graphs; use an explicit stack when needed.

Options and trade-offs:

1. Sort then slice: O(n log n) time, simplest, fine for small n.
2. Min-heap of size k: O(n log k) time, O(k) space. Preferred when k is small relative to n.

import heapq

def k_largest(nums, k):
    return heapq.nlargest(k, nums)   # maintains a size-k heap internally

1. Quickselect: average O(n), worst O(n^2), mutates/partitions the array, good when k is close to n.

Follow-ups: streaming data (keep the heap across batches), finding the kth smallest, or using a bucket approach when values are bounded.

DP solves problems with overlapping subproblems and optimal substructure by storing results and reusing them. Two styles:

• Top-down memoisation: recursion plus a cache, easy to write from the recurrence.
• Bottom-up tabulation: fill a table iteratively, avoids recursion depth issues.

# Fibonacci, bottom-up, O(n) time O(1) space
def fib(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

# 0/1 knapsack, O(n * capacity)
def knapsack(items, cap):
    dp = [0] * (cap + 1)
    for weight, value in items:
        for c in range(cap, weight - 1, -1):
            dp[c] = max(dp[c], dp[c - weight] + value)
    return dp[cap]

Signals: count ways, min/max cost, "can you reach", subsequence problems. State definition and transition are the key interview skills.