Data Structures and Algorithms: A Practical Guide with Python

Big O notation

Big O notation describes how the running time or memory use of an algorithm grows as the input size n grows. It ignores constant factors and lower-order terms, because for large inputs the growth rate dominates everything else: an algorithm that does 3n + 100 steps is O(n), and one that does n²/2 steps is O(n²). Big O usually describes the worst case unless you say otherwise, and many structures are discussed in terms of average or amortised cost — appending to a Python list is O(1) amortised, even though an occasional resize copies every element.

To find the complexity of code, count how the work scales with the input. A single loop over n items is O(n). Two nested loops over the same input are O(n²). Halving the problem on each step, as binary search does, gives O(log n). Splitting the problem in half and doing linear work to combine the halves, as merge sort does, gives O(n log n). Space complexity works the same way for the extra memory you allocate, including the call stack used by recursion.

The example below shows the most common optimisation in coding interviews: trading memory for time. Comparing every pair is O(n²); a set remembers what you have seen and brings it down to O(n) at the cost of O(n) extra space.

def has_duplicate_slow(items):      # O(n^2) time, O(1) space
    for i in range(len(items)):
        for j in range(i + 1, len(items)):
            if items[i] == items[j]:
                return True
    return False

def has_duplicate_fast(items):      # O(n) time, O(n) space
    return len(set(items)) != len(items)

Arrays and strings

An array stores elements in contiguous memory, so reading or writing any index is O(1) and iterating is very cache-friendly. The cost is that inserting or deleting anywhere except the end shifts every later element, which is O(n). Python's list is a dynamic array that grows automatically; strings are immutable sequences of characters, so building a string piece by piece in a loop creates many copies — collect parts in a list and use "".join(parts) instead.

Two techniques solve a large share of array and string problems. Two pointers walk from both ends, or at different speeds, to avoid nested loops — checking palindromes, merging sorted arrays or finding pairs in a sorted array. A sliding window keeps a running summary of a contiguous range and updates it in O(1) as the window moves, which turns problems like "maximum sum of k consecutive elements" or "longest substring without repeating characters" from O(n·k) or O(n²) into O(n).

def is_palindrome(s: str) -> bool:
    left, right = 0, len(s) - 1
    while left < right:
        if s[left] != s[right]:
            return False
        left += 1
        right -= 1
    return True

def max_window_sum(nums: list[int], k: int) -> int:
    window = sum(nums[:k])
    best = window
    for i in range(k, len(nums)):
        window += nums[i] - nums[i - k]   # slide: add new, drop old
        best = max(best, window)
    return best

Hash maps and sets

A hash map stores key-value pairs. It runs each key through a hash function to choose a bucket, so lookups, inserts and deletes take O(1) time on average. Collisions — two keys landing in the same bucket — are resolved by the implementation, and the table resizes as it fills, which keeps the average cost constant. In the worst case, with many collisions, operations degrade to O(n), but that is rare with good hash functions. Keys must be hashable, which in Python means immutable types such as strings, numbers and tuples.

In Python, dict is a hash map and set is a hash set. They are the single most useful tools in coding interviews: counting frequencies, detecting duplicates, remembering previously seen values (as in two-sum) and grouping items by a computed key. The collections module adds Counter for counting and defaultdict for grouping without checking whether a key exists. If you only remember one thing from this guide, make it this: when a solution has a nested loop that searches for something, ask whether a hash map could find it in O(1).

from collections import Counter, defaultdict

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

counts = Counter("mississippi")          # {'i': 4, 's': 4, 'p': 2, 'm': 1}
groups = defaultdict(list)
for word in ["eat", "tea", "tan", "nat"]:
    groups["".join(sorted(word))].append(word)

Linked lists

A linked list is a chain of nodes, each holding a value and a pointer to the next node (and, in a doubly linked list, the previous one). Inserting or removing a node is O(1) once you hold a reference to the right position, because you only rewire pointers. The trade-off is that reaching the i-th element requires walking from the head, which is O(n), and nodes are scattered in memory, so iteration is slower than with arrays in practice.

You will rarely build a linked list in application code — Python's deque covers most queue needs — but linked lists are interview favourites because they test pointer manipulation. The core patterns are reversing a list in place, finding the middle with slow and fast pointers, detecting a cycle with Floyd's algorithm, and merging two sorted lists. A dummy head node simplifies edge cases when the head itself might change.

class Node:
    def __init__(self, val, next=None):
        self.val = val
        self.next = next

def reverse(head: Node | None) -> Node | None:
    prev = None
    while head:
        head.next, prev, head = prev, head, head.next
    return prev

def has_cycle(head: Node | None) -> bool:
    slow = fast = head
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next
        if slow is fast:
            return True
    return False

Stacks and queues

A stack is last in, first out (LIFO): you push onto the top and pop from the top. Function calls, undo history and expression parsing are all stacks. In Python, a plain list works as a stack, with append and pop at the end in O(1). Stack problems often involve matching pairs — balanced brackets, for example — or the monotonic stack pattern, which finds the next greater or smaller element for every item in O(n).

A queue is first in, first out (FIFO): you add at the back and remove from the front. Queues model task processing, buffering and, most importantly for interviews, breadth-first search. Use collections.deque for queues in Python, because removing from the front of a list with pop(0) shifts every element and costs O(n), while deque.popleft() is O(1).

from collections import deque

def is_balanced(s: str) -> bool:
    pairs = {")": "(", "]": "[", "}": "{"}
    stack = []
    for ch in s:
        if ch in "([{":
            stack.append(ch)
        elif ch in pairs:
            if not stack or stack.pop() != pairs[ch]:
                return False
    return not stack

queue = deque()
queue.append("a")       # enqueue, O(1)
queue.popleft()         # dequeue, O(1) — list.pop(0) would be O(n)

Trees and binary search trees

A tree is a hierarchy of nodes with a single root and no cycles; file systems, the DOM and organisation charts are all trees. In a binary tree, each node has at most two children. Most tree problems are solved recursively: compute the answer for the left and right subtrees, then combine them at the current node. The four traversals to know are preorder (node, left, right), inorder (left, node, right), postorder (left, right, node) and level-order, which is BFS with a queue.

A binary search tree (BST) adds an ordering rule: every value in a node's left subtree is smaller than the node, and every value in the right subtree is larger (or equal, depending on how you handle duplicates). That rule lets search, insert and delete skip half the remaining tree at each step, giving O(log n) time when the tree is balanced. An inorder traversal of a BST visits values in sorted order, which is a common interview check for whether a tree is a valid BST. The catch is balance: inserting already-sorted data into a plain BST produces a tree that is really a linked list, with O(n) operations. Self-balancing variants such as AVL and red-black trees fix this and back ordered maps in many languages, such as Java's TreeMap and C++'s std::map.

class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

def insert(root, val):
    if root is None:
        return TreeNode(val)
    if val < root.val:
        root.left = insert(root.left, val)
    else:
        root.right = insert(root.right, val)
    return root

def contains(root, val) -> bool:
    while root:
        if val == root.val:
            return True
        root = root.left if val < root.val else root.right
    return False

def inorder(root):                       # yields values in sorted order
    if root:
        yield from inorder(root.left)
        yield root.val
        yield from inorder(root.right)

Heaps and priority queues

A binary heap is a complete binary tree stored in an array, where every parent is smaller than its children (a min-heap) or larger (a max-heap). The smallest (or largest) element is always at index 0, so peeking is O(1), while pushing and popping take O(log n) because an element sifts up or down one level at a time. Building a heap from an existing list with heapify takes only O(n).

Heaps implement priority queues, which appear whenever you repeatedly need the "next best" item: scheduling tasks by priority, merging k sorted lists, finding the k largest or most frequent elements, or Dijkstra's shortest-path algorithm. Python's heapq module provides a min-heap on a regular list; for a max-heap, push negated values. Keeping a heap of size k while scanning a large input finds the top k elements in O(n log k), much better than sorting everything when k is small.

import heapq

nums = [5, 1, 8, 3, 9, 2]
heapq.heapify(nums)              # O(n), min-heap in place
smallest = heapq.heappop(nums)   # O(log n) -> 1
heapq.heappush(nums, 0)          # O(log n)

def top_k_largest(items, k):
    heap = []
    for x in items:
        heapq.heappush(heap, x)
        if len(heap) > k:
            heapq.heappop(heap)  # drop the smallest; heap keeps the k largest
    return sorted(heap, reverse=True)

Graphs: BFS and DFS

A graph data structure is a set of vertices (nodes) connected by edges, which can be directed or undirected and weighted or unweighted. Road networks, social networks, package dependencies and web links are all graphs, and so are many interview problems in disguise — a grid of cells where you can move between neighbours is a graph too. Graphs are usually stored as an adjacency list, a dictionary mapping each vertex to its neighbours, which uses O(V + E) space. An adjacency matrix uses O(V²) space and only makes sense for dense graphs.

The two fundamental traversals are breadth-first search and depth-first search. The BFS algorithm explores neighbours level by level using a queue, so in an unweighted graph it finds the shortest path in number of edges. DFS goes as deep as possible along one branch before backtracking, using recursion or an explicit stack; it is the natural fit for detecting cycles, finding connected components, topological sorting and exploring all paths. Both visit every vertex and edge once, for O(V + E) time, and both need a visited set so cycles do not cause infinite loops. For weighted shortest paths, Dijkstra's algorithm replaces the BFS queue with a heap.

from collections import deque

graph = {
    "A": ["B", "C"],
    "B": ["D"],
    "C": ["D", "E"],
    "D": ["F"],
    "E": ["F"],
    "F": [],
}

def bfs_shortest_path(graph, start, goal):
    queue = deque([[start]])
    visited = {start}
    while queue:
        path = queue.popleft()
        node = path[-1]
        if node == goal:
            return path
        for nxt in graph[node]:
            if nxt not in visited:
                visited.add(nxt)
                queue.append(path + [nxt])
    return None

def dfs(graph, node, visited=None):
    if visited is None:
        visited = set()
    visited.add(node)
    for nxt in graph[node]:
        if nxt not in visited:
            dfs(graph, nxt, visited)
    return visited

bfs_shortest_path(graph, "A", "F")  # ['A', 'B', 'D', 'F']

Sorting: merge sort, quicksort and heap sort

Sorting is worth studying less because you will write your own sort — Python's built-in sorted() and list.sort() use Timsort, a stable O(n log n) hybrid that is faster than anything you will write by hand — and more because sorting algorithms teach the main algorithm design strategies. Many problems also become easy once the input is sorted, such as finding duplicates, merging intervals or using two pointers.

Merge sort is divide and conquer: split the list in half, sort each half recursively, then merge the two sorted halves in linear time. It always runs in O(n log n), is stable (equal elements keep their order) and needs O(n) extra memory. Quicksort picks a pivot, partitions elements into those smaller and larger than it, and recurses on each side. It averages O(n log n) and is very fast in practice when done in place, but a consistently bad pivot gives O(n²), which randomised or median-of-three pivots make unlikely. Heap sort builds a max-heap, then repeatedly swaps the maximum to the end of the array and restores the heap. It guarantees O(n log n) with O(1) extra space but is not stable and is usually slower in practice than a good quicksort because of its scattered memory access.

def merge_sort(a):
    if len(a) <= 1:
        return a
    mid = len(a) // 2
    left, right = merge_sort(a[:mid]), merge_sort(a[mid:])
    out, i, j = [], 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            out.append(left[i]); i += 1
        else:
            out.append(right[j]); j += 1
    return out + left[i:] + right[j:]

def quick_sort(a):
    if len(a) <= 1:
        return a
    pivot = a[len(a) // 2]
    return (quick_sort([x for x in a if x < pivot])
            + [x for x in a if x == pivot]
            + quick_sort([x for x in a if x > pivot]))

def heap_sort(a):
    def sift_down(start, end):
        root = start
        while (child := 2 * root + 1) <= end:
            if child + 1 <= end and a[child] < a[child + 1]:
                child += 1
            if a[root] >= a[child]:
                return
            a[root], a[child] = a[child], a[root]
            root = child
    n = len(a)
    for start in range(n // 2 - 1, -1, -1):   # build a max-heap
        sift_down(start, n - 1)
    for end in range(n - 1, 0, -1):            # move max to the end
        a[0], a[end] = a[end], a[0]
        sift_down(0, end - 1)
    return a

Binary search

Binary search finds a target in a sorted array by comparing it with the middle element and discarding the half that cannot contain it. Each step halves the search space, so it takes O(log n) time: about 20 comparisons for a million elements. The classic bugs are off-by-one errors in the loop condition and bounds, so pick one convention — here, an inclusive range with while lo <= hi — and stick to it.

The bigger idea is that binary search works on any monotonic condition, not just on arrays. If you can ask "is the answer at least x?" and the response flips from no to yes exactly once, you can binary search the answer itself — the minimum capacity to ship packages in d days, or the smallest speed that finishes on time. In Python, the bisect module gives you correct lower- and upper-bound searches on sorted lists.

def binary_search(a: list[int], target: int) -> int:
    lo, hi = 0, len(a) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if a[mid] == target:
            return mid
        if a[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

import bisect
idx = bisect.bisect_left([1, 3, 3, 7], 3)   # 1: first position where 3 fits

Dynamic programming basics

Dynamic programming (DP) solves problems that break into overlapping subproblems with optimal substructure — the best answer for the whole is built from the best answers to smaller pieces. Naive recursion recomputes the same subproblems many times; DP computes each once and stores it. Fibonacci is the standard illustration: the naive recursive version is O(2ⁿ), while the memoised version is O(n).

There are two styles. Top-down memoisation keeps the natural recursive solution and caches results, which in Python is one decorator: functools.cache. Bottom-up tabulation fills a table from the smallest subproblems upward, which avoids recursion limits and often allows reducing memory to a few variables. To design a DP solution, define the state (what dp[i] means), write the recurrence (how dp[i] is computed from smaller states), set the base cases and choose the order of evaluation. Start with classics — climbing stairs, house robber, coin change, longest common subsequence and 0/1 knapsack — because most interview DP problems are variations on them.

from functools import cache

@cache
def fib(n: int) -> int:                 # top-down (memoisation)
    return n if n < 2 else fib(n - 1) + fib(n - 2)

def coin_change(coins: list[int], amount: int) -> int:   # bottom-up (tabulation)
    INF = amount + 1
    dp = [0] + [INF] * amount           # dp[x] = fewest coins to make x
    for x in range(1, amount + 1):
        for c in coins:
            if c <= x:
                dp[x] = min(dp[x], dp[x - c] + 1)
    return dp[amount] if dp[amount] != INF else -1

coin_change([1, 2, 5], 11)  # 3  (5 + 5 + 1)

An 8-week DSA study plan

This plan assumes one to two hours a day, five or six days a week. Spend each session on a short review of the concept, then two or three problems, and finish by re-solving one problem from a previous week without looking at your notes. Time yourself from week three onward: aim for 20–25 minutes on easy problems and 35–45 on medium ones.

Keep a log of every problem you could not solve, with the key insight in one sentence, and revisit it after a few days. Patterns matter more than individual problems: once you recognise that a question is really a sliding window, a BFS or a coin-change variant, the solution follows. When you are preparing for interviews, combine this plan with language-specific practice from the Python interview questions, Java interview questions or C++ interview questions, and add system design interview questions for mid-level and senior roles. For quick syntax reminders, keep the Python cheat sheet open while you practise.