Data structures and algorithms (DSA) come down to a handful of ideas: how data is laid out, which item comes out next, and how many steps a job takes as the input grows. Get these right and most interview questions, and a lot of everyday performance bugs, stop being mysterious.
Arrays and indexing
An array is a single block of memory with its items side by side. That layout is what makes reading any item instant: to find item i, the computer starts at the array's address and jumps i items along. The index is an offset from the start, which is why most languages, including C, Java, Python and JavaScript, count from 0. The first item is zero steps from the start.
A few languages, such as Lua and MATLAB, count from 1 instead, so check before you port code between them.
Counting from 0 has one consequence that catches everyone at some point: the last item's index is the length minus one.
cats = ["Mochi", "Tofu", "Biscuit"]
cats[0] # "Mochi"
cats[len(cats) - 1] # "Biscuit"
cats[len(cats)] # IndexErrorReading by index is O(1), constant time, however long the array. Inserting at the front is not: every other item has to shuffle along one place, which is O(n).
Stacks and queues
Stacks and queues both hold items waiting to be dealt with. The difference is which one leaves next.
A stack is Last In, First Out (LIFO). You push onto the top and pop from the top, like a pile of plates. Your language's call stack works this way: the function called most recently is the first to return. Undo history, bracket matching and depth-first search all lean on a stack.
A queue is First In, First Out (FIFO). Items join at the back and leave from the front, like people waiting for a bus. Print jobs, message queues and breadth-first search all use one, because fairness (first come, first served) is the point.
In Python a list makes a fine stack, but a poor queue: list.pop(0) moves every remaining item. Use collections.deque, which adds and removes at both ends in O(1).
from collections import deque
stack = []
stack.append("a"); stack.append("b")
stack.pop() # "b": last in, first out
queue = deque()
queue.append("a"); queue.append("b")
queue.popleft() # "a": first in, first outBinary search and logarithmic time
Big O notation describes how the work grows with the input size, n, ignoring constant factors. O(n) means doubling the input roughly doubles the work. O(log n) means doubling the input adds just one more step.
Binary search is the classic O(log n) algorithm. It only works on sorted data. Look at the middle item: if it is the target, stop. If the target is bigger, it can only be in the right half, so throw the left half away, and the other way round. Each comparison halves what is left.
Here it is finding 23 in a sorted array of eight numbers:
Binary search finding 23
- Comparing
- Writing
- Done
Step 1 of 6: Look for 23. The whole array is still in play.
The saving grows fast. A million sorted items need about 20 comparisons, because 2 to the power of 20 is just over a million. A plain scan could need a million.
def binary_search(items, target):
lo, hi = 0, len(items) - 1
while lo <= hi:
mid = (lo + hi) // 2
if items[mid] == target:
return mid
if items[mid] < target:
lo = mid + 1
else:
hi = mid - 1
return -1Sorting: stability and worst cases
Sorting algorithms differ in more than speed. Two properties come up again and again.
Stability
A sort is stable if items that compare as equal keep their original order. That matters when you sort by one field after another. Sort a list of orders by date, then stably by customer, and each customer's orders stay in date order.
Merge sort is stable: it splits the list in half, sorts each half, then merges them, and whenever two items are equal it takes the one from the left half first. Selection sort, quicksort and heapsort, in their standard forms, move items long distances in swaps, which can jump an item past an equal one. Python's built-in sorted is guaranteed stable.
orders = [("Tofu", 2), ("Mochi", 1), ("Tofu", 1)]
sorted(orders, key=lambda o: o[0])
# [("Mochi", 1), ("Tofu", 2), ("Tofu", 1)]
# The two Tofu orders keep their order.Quicksort's worst case
Quicksort picks a pivot, puts smaller items to its left and bigger ones to its right, then sorts each side. With a pivot near the middle, each level halves the problem, giving O(n log n) on average.
The trouble comes when the pivot is always the smallest or largest item. A naive quicksort that picks the first item as its pivot does exactly that on data that is already sorted. Each pass then peels off one item, so the work is n, then n minus 1, then n minus 2, and so on: O(n²). Choosing the pivot at random, or as the median of three items, makes that case vanishingly unlikely. Merge sort has no bad case: it is O(n log n) every time, at the cost of extra memory.
Binary search trees
A binary search tree (BST) keeps its items in order by shape. Each node has at most two children, and for every node, everything in its left subtree is smaller and everything in its right subtree is bigger.
Here is a small one:
In-order traversal visits the left subtree, then the node, then the right subtree. Because of the ordering rule, that visits every item from smallest to largest: 1, 3, 6, 8, 10, 14. The other orders have their own uses. Pre-order (node first) copies a tree, and post-order (node last) deletes one, since children go before their parent.
def in_order(node):
if node is None:
return
in_order(node.left)
print(node.value)
in_order(node.right)Search, insert and delete take time proportional to the tree's height. A balanced tree is O(log n) tall, but inserting items in sorted order builds a tree that is one long chain, and every operation becomes O(n). Self-balancing trees, such as red-black trees, exist to prevent that.
Breadth-first and depth-first search
A graph is a set of nodes joined by edges, and a tree is a graph with no cycles. There are two basic ways to visit everything in one.
Breadth-first search (BFS) explores level by level: the start node, then all its neighbours, then all of theirs. It uses a queue, so nodes are handled in the order they were found. Because it reaches every node by the fewest possible edges, BFS finds the shortest path in a graph where every edge costs the same.
Depth-first search (DFS) follows one path as far as it goes, then backs up and tries the next. It uses a stack, often the call stack through recursion. In-order and post-order traversal are depth-first orders on a tree.
from collections import deque
def bfs(graph, start):
seen = {start}
queue = deque([start])
while queue:
node = queue.popleft()
print(node)
for nxt in graph[node]:
if nxt not in seen:
seen.add(nxt)
queue.append(nxt)The seen set matters. Unlike a tree, a graph can have cycles, and without it the search would loop forever.
Heaps and priority queues
A priority queue hands back the most important item next, not the oldest. Job schedulers, event simulations and shortest-path algorithms all need one.
The simple options each have a slow side. An unsorted list adds in O(1) but has to scan everything, O(n), to find the smallest. A sorted list finds the smallest at once but needs O(n) to insert in the right place. A stack or a plain queue ignores priority altogether.
A binary heap balances the two. It is a tree stored in an array, where every parent is smaller than its children (a min-heap). The smallest item is always at the root, and adding or removing an item only repairs one path from the root to a leaf, which is O(log n). Python ships one as heapq:
import heapq
tasks = []
heapq.heappush(tasks, (2, "write tests"))
heapq.heappush(tasks, (1, "fix the bug"))
heapq.heappop(tasks) # (1, "fix the bug")Dijkstra's shortest paths
BFS finds the fewest edges. When edges have weights, such as distances or costs, you need Dijkstra's algorithm. It keeps a priority queue of nodes ordered by the best distance found so far, repeatedly takes the closest unfinished node, and checks whether going through it makes any neighbour cheaper to reach.
With a binary min-heap as the priority queue, each edge can add at most one entry to the heap, and each heap operation costs O(log V). That gives O((V + E) log V), usually written O(E log V) because in a connected graph there are at least as many edges as vertices, less one. The simpler version that scans an array for the closest node instead is O(V²), which can win on very dense graphs.
Dijkstra's algorithm assumes no edge has a negative weight. With negative weights, use Bellman-Ford instead.
Common mistakes
- Off-by-one errors. The last index is the length minus one, and binary search loops go wrong at the boundaries more than anywhere else.
- Binary search on unsorted data. It returns an answer, just not a correct one.
- Using a list as a queue. Removing from the front of a Python list is O(n) per call.
- Forgetting the visited set in a graph search, which loops forever on a cycle.
- Quoting quicksort as O(n log n) without a qualifier. That is its average case, not its worst.
Key takeaways
- Most languages index arrays from 0 because the index is an offset from the start.
- A stack returns the newest item (LIFO), a queue the oldest (FIFO), and a heap the smallest.
- Binary search halves sorted data each step, so it is O(log n).
- BFS explores level by level with a queue; DFS goes deep first with a stack.
- Check both the average and worst cases, and stability, before trusting a sort.
