Data Structures & Algorithms

A collection of elements stored in contiguous memory locations, indexed from 0. Arrays offer O(1) random access by index but O(n) insertion/deletion in the middle. The foundational data structure in most languages.

"We use an array to store the daily temperature readings — each index maps to a day number, so accessing day 30's reading is O(1)."

A sequence of nodes where each node stores a value and a pointer to the next node. Unlike arrays, insertion at the head is O(1) but random access is O(n). Doubly linked lists also have a pointer to the previous node.

"A linked list is better than an array here because we're constantly inserting at the front — O(1) with a linked list versus O(n) array shift."

A data structure that maps keys to values using a hash function. Provides average O(1) lookup, insertion, and deletion. Also called a dictionary, hash table, or object (in JavaScript). Hash collisions (two keys mapping to the same slot) are handled by chaining or open addressing.

"We cache the API responses in a hash map keyed by request URL — lookups are O(1), so repeated requests for the same data never hit the network."

A Last-In First-Out (LIFO) collection. Elements are pushed onto the top and popped from the top. Used in: call stacks, undo/redo systems, expression parsing, DFS traversal. O(1) push and pop.

"The undo feature uses a stack — each user action is pushed onto the stack. Pressing Ctrl+Z pops the last action and reverses it."

A First-In First-Out (FIFO) collection. Elements are enqueued at the back and dequeued from the front. Used in: task scheduling, BFS traversal, message queues, printer spooling. O(1) enqueue and dequeue.

"Customer support tickets are processed as a queue — the ticket that arrived first is handled first, ensuring fair ordering."

A hierarchical data structure with a root node and child nodes, where no cycles exist. A binary tree has at most two children per node. Trees model file systems, HTML DOM, organisation charts, and expression evaluation.

"The file system is a tree — the root is /, each directory is a node, and files are leaf nodes. Traversing the tree with DFS lists all files recursively."

A collection of nodes (vertices) connected by edges. Can be directed (edges have direction) or undirected. Graphs model networks, social connections, route planning, and dependency trees. Traversed via BFS or DFS.

"We model the service dependency graph as a directed graph — an edge from A to B means A calls B. Running a topological sort tells us the deployment order."

A mathematical notation describing an algorithm's worst-case time or space complexity as input grows. Common complexities: O(1) constant, O(log n) logarithmic, O(n) linear, O(n log n) linearithmic, O(n²) quadratic, O(2ⁿ) exponential.

"The nested loop is O(n²) — for 1,000 items, that's 1,000,000 operations. We need to redesign using a hash map to bring the lookup to O(1) and the overall algorithm to O(n)."

A function that calls itself with a smaller version of the problem, converging toward a base case that terminates the recursion. Recursive solutions are elegant for tree traversal, divide-and-conquer algorithms, and problems with self-similar structure.

"The directory listing function uses recursion — it processes the current directory, then calls itself for each subdirectory. The base case is a directory with no subdirectories."

An O(log n) search algorithm that finds a target in a sorted array by repeatedly halving the search space. Requires sorted input. Finds an element in 1 million items with at most 20 comparisons.

"The auto-complete suggestions are stored in a sorted array — we use binary search to find the matching prefix in O(log n) rather than scanning linearly."

An algorithm that arranges elements in order. Examples: Bubble sort O(n²), Merge sort O(n log n), Quick sort O(n log n) average, Radix sort O(nk). Most production code uses the built-in sort which typically uses Timsort (O(n log n)).

"Don't implement your own sort — use the language's built-in sort which is well-tested and O(n log n). Custom sorts are only needed for special ordering requirements."

An optimisation technique that solves complex problems by breaking them into overlapping subproblems and storing solutions to avoid recomputation (memoization). Transforms exponential brute-force into polynomial time.

"The naive recursive Fibonacci is O(2ⁿ) because it recalculates the same sub-problems. Dynamic programming with memoization reduces it to O(n) by caching each computed value."

How the runtime of an algorithm grows as the input size (n) increases, expressed in Big O notation. Measures computational work, not wall-clock time. Analysing time complexity helps choose the right algorithm before writing code.

"The current search is O(n) — it scans every record. Switching to a B-tree index makes it O(log n), which means 1 million records require 20 operations instead of 1 million."

How much memory an algorithm uses relative to input size, expressed in Big O. Trade-offs between time and space are common — caching (memoization) trades space for time. An O(n) space algorithm needs memory proportional to input size.

"Reversing a string in-place is O(1) space — we swap characters using two pointers without allocating a new string. Creating a reversed copy is O(n) space."

A graph/tree traversal that explores as far down a branch as possible before backtracking. Implemented with a stack (or recursion). Used for: cycle detection, topological sort, maze solving, finding connected components.

"DFS on the dependency graph detects circular dependencies — if we encounter a node already in the current path, we've found a cycle."