Data structures and algorithms flashcards

How to store data and solve problems fast, from arrays to graphs.

Beginner friendly, starts from zero

CardsCheatsheetTips and tricks

Data structures and algorithmsStart from zero · 1 of 12

What are and , in plain words?

Think of the answer, then tap

A is a way of arranging information so it is quick to use. An is a step-by-step recipe for solving a problem with that information.

Kitchen shelves are the ; the recipe is the .

Space turn over · K got it · J again · ← back

All topics

Data structures and algorithms at a glance

Data structures are ways to arrange information, and algorithms are step-by-step recipes that use them to solve problems fast.

Like a kitchen: shelves and jars keep things easy to find, and a recipe tells you the steps to cook.

Words you will meet

Data structure: A way of arranging information so it is quick to use
Algorithm: A step-by-step recipe for solving a problem
Index: The number of a box in a list, counting from 0
Big O: A rough way to say how the work grows when the data grows
Stack: A pile where the last thing in is the first thing out
Queue: A line where the first thing in is the first thing out
Hash map: A store of key and value pairs that finds a value straight from its key
Recursion: A function that solves a problem by calling itself on a smaller piece

The steps

1. Start from zero (12 cards): What data structures and algorithms are, where you meet them, and the plain words the core basics use.
2. Core basics (16 cards): Big O, arrays, lists, stacks, queues, hash maps, sets, searching and recursion.
3. Next steps (17 cards): Sorting, trees, heaps, graphs, BFS and DFS, two pointers, sliding windows and indexes.
4. Go deeper (17 cards): Dynamic programming, greedy proofs, backtracking, shortest paths, union-find, tries and amortised cost.

All 12 cards in Start from zero

What are data structures and algorithms, in plain words?: A data structure is a way of arranging information so it is quick to use. An algorithm is a step-by-step recipe for solving a problem with that information.
What goes wrong when a program ignores them?: It works with ten items but crawls with a million. Checking every name one by one is fine for a class list and hopeless for a whole country.
Where do you meet these ideas in daily life?: A queue at the ticket counter, a stack of plates, a phone book in name order, a lift that stops at the nearest floor first. Each is a way to arrange things or a rule for handling them.
In Python, what are a list and an index?: A list is a row of numbered boxes in the computer's memory, its short-term workspace. The index is a box's number, and it starts at 0, so orders[0] is the first box.
What do input, output and function mean?: A function is a named set of steps. You give it input (the data to work on), and it gives back output (the answer), like a juicer taking fruit and giving juice.
What are a stack and a queue?: A stack is like a pile of plates: the last one in is the first one out. A queue is like a ticket line: the first one in is the first one out.
What are a hash map and a set?: A hash map stores pairs: a key and its value, like a coat check where your ticket (the key) gets your coat at once. A set is a bag of items with no repeats.
What do "n" and Big O mean?: n is how many items you have. Big O is a rough way to say how the work grows as n grows: O(1) stays the same, O(n) grows with the items, O(log n) grows very slowly.
What is the difference between linear search and binary search?: Linear search checks items one by one. Binary search works on sorted items: look in the middle, throw away the half that cannot hold it, and repeat.
What is recursion?: Recursion is a function that solves a problem by calling itself on a smaller piece. It needs a base case: the smallest piece, answered directly, so it knows when to stop.
What do you need before starting?: Basic Python (variables, if and loops) and a computer with Python 3, or any online Python editor in your browser. Paper and a pencil help to trace steps.
What will you be able to do after this topic?: Pick the right structure for a job, guess how fast code will be as data grows, and solve classic problems like searching, matching pairs and checking brackets.

Data structures and algorithms cheatsheet

Big O, fast to slow

O(1) Hash lookup, array index
O(log n) Binary search, balanced tree, heap push
O(n) One pass, linear search
O(n log n) Good sorting, n heap operations
O(n^2) Nested loops over the same data
O(2^n) / O(n!) All subsets / all orderings
~10^8 simple steps/s Compiled code; Python is ~10 to 50x slower

Data structure costs

list: index O(1), append O(1)*, insert(0) O(n) Dynamic array (* amortised)
deque: append/popleft O(1) Queue or stack at both ends
dict/set: get, add, in O(1) avg Hash table, O(n) worst
heapq: push/pop O(log n), peek O(1) Priority queue
balanced BST / B-tree: O(log n) Ordered keys, range scans
trie: O(length of key) Prefix search
union-find: ~O(1) Group membership and merging

Python helpers

collections.deque Queue, BFS
collections.Counter / defaultdict Counting / grouping
heapq.heappush / nlargest(k, xs) Heap / top k
heapq.heappush_max (3.14+) Built-in max-heap functions
bisect.bisect_left / insort Binary search in a sorted list
functools.cache Memoisation
itertools.accumulate Prefix sums
sorted(xs, key=...) Stable Timsort, O(n log n)

Pattern to use

Sorted array, find pair or range Two pointers or binary search
Longest or shortest subarray with a rule Sliding window
Seen it before? Complement? Hash map or set
Top k or next smallest Heap
Fewest steps, unweighted BFS
All combinations, constraints Backtracking with pruning
Best or count with overlapping subproblems Dynamic programming
Next greater or smaller element Monotonic stack
Connected groups, merging Union-find

Graph algorithms

BFS / DFS O(V + E) traversal
Dijkstra (heap) O((V + E) log V), weights >= 0
Bellman-Ford O(V x E), negative edges, cycle check
Topological sort (Kahn) O(V + E), DAG ordering
Kruskal / Prim Minimum spanning tree
Three-colour DFS Cycle detection in directed graphs