Data Structures & Algorithms

Describe how an algorithm's work grows with its input, and compare O(1), O(log n), O(n) and O(n^2) code.

Search an unsorted list step by step, then halve a sorted list each time with binary search.

Implement insertion sort and merge sort, and see why one is O(n^2) and the other O(n log n).

Know what lists and dicts are fast and slow at, and use a dict to count things and solve two-sum in one pass.

Use a stack (last in, first out) to check brackets, and a deque as a queue (first in, first out).

Build a singly linked list from nodes, walk it, and reverse it in place by re-pointing links.

Write functions that call themselves on a smaller input, with a base case that stops them.

Represent a binary tree with nodes, traverse it in pre-, in- and post-order, and insert into a binary search tree.

Represent a graph as an adjacency list, explore it with depth-first search, and find shortest paths in a grid with breadth-first search.

Recognise two-pointer and sliding-window problems and turn O(n^2) pair and subarray searches into one pass.

Speed up recursive solutions by remembering answers to sub-problems (memoisation), then build them bottom-up in a table.

Use a repeatable framework to understand, plan, code, test and explain a problem while talking through your thinking.