Data structure and algorithm fundamentals show up in nearly every technical interview, testing how you reason about time and space tradeoffs rather than memorized syntax.
Big-O notation describes the upper bound on how an algorithm's resource usage, time or space, grows as the input size n increases, and it focuses on the dominant term while ignoring constants and lower-order terms because those become irrelevant at scale. To analyze time complexity, you count how the number of basic operations scales with n, typically by examining loop structures, recursive calls, and any nesting between them. Space complexity works the same way but tracks additional memory allocated, like arrays, recursion stack frames, or auxiliary data structures, beyond the input itself. For instance, a single loop over n elements is O(n), a loop nested inside another is typically O(n^2), and binary search cuts the problem in half each step giving O(log n). It's worth noting Big-O is conventionally a worst-case bound, while Big-Omega gives the best case and Big-Theta gives a tight bound when the upper and lower bounds match.
Arrays store elements in contiguous memory, which gives O(1) random access by index and strong cache locality, but inserting or deleting in the middle requires shifting elements, making that O(n). Linked lists store elements as nodes with pointers to the next node, so insertion and deletion at a known position are O(1) once you have a reference to that node, but you lose random access and have to traverse from the head, making lookup O(n). Arrays also have a fixed or amortized-growth size depending on the language, while linked lists grow and shrink dynamically without needing to reallocate a contiguous block. I'd reach for an array when I need fast indexed access or the data size is stable, and a linked list when I'm doing frequent insertions and deletions in the middle of a sequence, such as maintaining an LRU cache's ordering. The pointer overhead and poor cache performance of linked lists mean they're often slower in practice than arrays even for operations they're theoretically better at.
A stack is LIFO, last in first out, so you use it whenever you need to process the most recently added item first, like undo functionality, parsing balanced parentheses, evaluating expressions, or tracking function calls during recursion, which is literally how the call stack works. A queue is FIFO, first in first out, so it's the right choice when order of arrival matters and things should be processed in the sequence they arrived, like a print queue, task scheduling, or breadth-first traversal of a graph. The core distinguishing question is whether you need to reverse order, a stack, or preserve order, a queue. Both typically support O(1) push and pop when implemented with a linked list or a dynamic array with two pointers, so the choice comes down to the access pattern the problem demands rather than performance. A common gotcha is that BFS requires a queue while DFS naturally uses a stack, and mixing them up gives you the wrong traversal order entirely.
A hash table maps keys to values by running the key through a hash function that produces an index into an underlying array, giving average-case O(1) insertion, lookup, and deletion. Collisions happen when two different keys hash to the same index, and there are two main strategies to handle that: chaining, where each bucket holds a linked list or small array of all entries that hash there, and open addressing, where you probe for the next available slot using a scheme like linear probing, quadratic probing, or double hashing. Chaining degrades gracefully since each bucket just gets a bit longer, while open addressing needs careful handling of deletions and tends to cluster if the load factor gets too high. The load factor, the ratio of stored entries to bucket count, determines when the table resizes and rehashes everything into a bigger array to keep operations close to O(1). A good hash function should distribute keys uniformly and be fast to compute, since a poor one causes excessive collisions and degrades performance toward O(n) in the worst case.
A binary search tree keeps every node's left subtree values smaller and right subtree values larger than the node itself, which lets you search, insert, and delete in O(log n) time on average by discarding half the remaining tree at each step. The problem is that a plain BST can degenerate into something resembling a linked list if you insert already-sorted data, pushing every operation to O(n) in the worst case. Self-balancing trees solve this by enforcing an invariant that keeps the tree's height close to log n regardless of insertion order. AVL trees do this strictly, tracking a balance factor at each node and rotating whenever the height difference between left and right subtrees exceeds one, which gives very fast lookups but more frequent rotations on writes. Red-Black trees relax that balance requirement using color properties and a rule that no root-to-leaf path is more than twice as long as any other, trading slightly less strict balance for cheaper rebalancing, which is why they're the default choice behind many standard library map and set implementations.
Binary search finds a target value in O(log n) time by repeatedly comparing the target to the middle element of the search range and discarding the half that can't contain it, narrowing the range until it finds the value or the range is empty. The critical precondition is that the data must be sorted, because the algorithm relies entirely on being able to infer which half to eliminate based on an ordering comparison. You also need random access to elements in constant time, which is why binary search works cleanly on arrays but is awkward on plain linked lists since finding the middle element there is itself O(n). A subtle implementation detail people get wrong is the midpoint calculation and loop exit condition, off-by-one errors around low, high, and mid are one of the most common bugs in binary search implementations. Beyond exact lookups, the same idea generalizes to finding boundaries, like the first or last occurrence of a value, or searching over an answer space in optimization problems, as long as there's a monotonic property to exploit.
Breadth-first search explores a graph level by level, visiting all neighbors of a node before moving further out, and it's implemented using a queue plus a visited set to avoid revisiting nodes. Depth-first search goes as deep as possible down one path before backtracking, implemented either recursively, using the call stack, or iteratively with an explicit stack. BFS is the right choice when you need the shortest path in an unweighted graph, because it guarantees you reach nodes in order of increasing distance from the source. DFS is better suited for problems like detecting cycles, topological sorting, or exploring all paths, and it typically uses less memory than BFS on wide graphs. Both run in O(V + E) time where V is vertices and E is edges, so the choice usually comes down to what property of the traversal order you need rather than raw performance.
A heap is a complete binary tree, usually stored as an array, that satisfies the heap property: in a min-heap every parent is smaller than or equal to its children, and in a max-heap every parent is larger than or equal to its children. This guarantees the smallest or largest element is always at the root, so you get O(1) access to that extreme value, O(log n) insertion, and O(log n) removal of the root, since both operations only need to fix the heap property along a single path rather than the whole tree. A priority queue is the abstract data type that says give me the highest priority element next, and a heap is simply the most common and efficient way to implement it. You can build a heap from an arbitrary array in O(n) time using a bottom-up heapify process, which is faster than inserting elements one at a time. Priority queues built on heaps show up constantly in practice, like Dijkstra's shortest path algorithm, Huffman coding, and task schedulers that need to always process the most urgent item next.
Recursion solves a problem by having a function call itself on a smaller subproblem until it hits a base case, while iteration solves it using loops that repeat a block of code while updating state variables. Recursion often expresses divide-and-conquer or tree and graph problems more naturally, but every call adds a frame to the call stack, so it uses O(depth) additional memory and risks a stack overflow on deep recursion, whereas iteration typically runs in O(1) auxiliary space. Tail recursion is a special case where the recursive call is the very last operation in the function, with nothing left to compute after it returns, meaning the current stack frame doesn't need to be kept around waiting for the result. Some languages and compilers detect this pattern and perform tail-call optimization, converting the recursion into a loop under the hood so it doesn't grow the stack at all. Not all languages guarantee this though, Python notably does not, so relying on tail recursion for deep recursion in Python will still overflow the stack even if the code is technically tail-recursive.
Quicksort picks a pivot, partitions the array so smaller elements land on one side and larger on the other, then recursively sorts each side, giving average-case O(n log n) time with very good constant factors and in-place sorting, but it degrades to O(n^2) on already-sorted or adversarially chosen input unless you use randomized or median-of-three pivot selection. Mergesort splits the array in half recursively and merges the sorted halves back together, guaranteeing O(n log n) in every case, and it's stable, meaning equal elements keep their relative order, but it needs O(n) auxiliary space for the merge step. Heapsort builds a max-heap from the array and repeatedly extracts the maximum to build the sorted result, guaranteeing O(n log n) time with O(1) extra space, but it's not stable and tends to have worse cache performance than quicksort because of the scattered access pattern heaps require. In practice, quicksort is usually fastest for general-purpose in-memory sorting, mergesort is preferred when stability matters or when sorting linked lists or external data that doesn't fit in memory, and heapsort is chosen when you need a worst-case time guarantee alongside constant extra space. This is also why many standard library sorts, like Timsort or introsort, are actually hybrids that switch strategies based on input characteristics.
Dynamic programming solves a problem by breaking it into overlapping subproblems, solving each one once, and storing the result so it can be reused, which works when the problem has both optimal substructure and overlapping subproblems. Greedy algorithms instead make the locally optimal choice at each step without reconsidering it later, betting that a sequence of locally best decisions leads to a globally optimal solution. Greedy is much faster and simpler when it applies, often O(n log n) or O(n), but it only produces the correct answer when the problem has the greedy-choice property, like in Kruskal's or Prim's minimum spanning tree algorithms or Huffman coding. Dynamic programming is more broadly applicable and guarantees correctness whenever optimal substructure holds, but it costs more time and space to explore and store all the relevant subproblems, as seen in the knapsack problem or edit distance. A good way to decide between them in an interview is to test whether a greedy choice could ever need to be undone later, if it can, you need DP instead.
An adjacency matrix is a V by V grid where cell (i, j) indicates whether an edge exists between vertex i and vertex j, or stores the weight of that edge, giving O(1) edge lookup but O(V^2) space regardless of how many edges actually exist. An adjacency list stores, for each vertex, a list of its neighbors, using O(V + E) space, much more efficient for sparse graphs, but checking whether a specific edge exists takes O(degree of the vertex) instead of O(1). Traversals like BFS and DFS run in O(V + E) time on an adjacency list versus O(V^2) on a matrix, since the matrix forces you to scan an entire row even for vertices with few neighbors. Dense graphs, where the number of edges approaches V^2, can make the matrix's space cost worthwhile for O(1) edge queries, while sparse graphs, far more common in practice, almost always favor adjacency lists. Weighted graphs can be represented either way, with the matrix storing weights directly in cells and the list storing weight alongside each neighbor entry.
A trie, or prefix tree, is a tree structure where each node represents a single character, and paths from the root down to a node spell out a prefix, with complete words typically marked by a flag at the terminating node. Looking up, inserting, or checking a word of length m takes O(m) time, independent of how many words are stored in the trie, which is a big advantage over hashing or sorting-based approaches for prefix-heavy workloads. Its real strength is prefix operations, like autocomplete, spell checkers, and IP routing tables, because all words sharing a prefix share the same path down from the root, so you can find every word starting with a given prefix by walking to that prefix node and exploring its subtree. The main downside is space, since each node typically holds an array or map of child pointers for every possible next character, which can waste memory compared to a hash set when the alphabet is large or the trie is sparse. Compressed variants like radix trees or Patricia tries address that by merging chains of single-child nodes into one edge labeled with a substring.
Amortized analysis looks at the average cost of an operation over a sequence of operations, rather than the worst-case cost of any single operation in isolation, giving a more honest picture of an algorithm's real performance over time. The classic example is a dynamic array like Python's list or Java's ArrayList, where appending an element is usually O(1), but occasionally the array is full and needs to be reallocated with every existing element copied into a bigger array, an O(n) operation. If you only looked at that worst single operation, you'd conclude appends are O(n), but because the array typically doubles in size each time it resizes, those expensive resizes happen exponentially less often, and spreading that cost across all appends gives an amortized cost of O(1) per append. This distinction matters because a shallow read of complexity might flag a data structure as inefficient based on one bad-case operation, while a deeper analysis using techniques like the aggregate method, accounting method, or potential method shows the true long-run behavior. Amortized analysis shows up again in hash table resizing and in union-find operations with path compression, where individual operations can look expensive but the sequence as a whole is efficient.
Divide and conquer is an algorithmic strategy that breaks a problem into smaller, typically independent, subproblems of the same type, solves each subproblem recursively, and then combines those solutions into an answer for the original problem. It's a specific pattern of recursion, not just recursion in general, defined by three steps, divide the input, conquer each piece independently, and combine the results, whereas plain recursion is the broader mechanism of a function calling itself and doesn't require this divide-solve-combine structure. Classic examples are mergesort, which divides the array in half, sorts each half, and merges them, and binary search, which divides the search space in half and recurses into only one side rather than both. The time complexity of divide and conquer algorithms is often analyzed with the master theorem, which relates the number of subproblems, the size of each subproblem, and the cost of combining them to derive the overall complexity, like O(n log n) for mergesort. The technique is powerful because it naturally parallelizes, since independent subproblems can be solved concurrently, and it often turns an O(n^2) brute-force approach into something closer to O(n log n).
A hash map gives average-case O(1) insertion, lookup, and deletion by hashing keys to array indices, which makes it the faster choice when you don't care about ordering and just need quick access by key. A tree-based map, backed by something like a Red-Black tree, gives O(log n) for those same operations, slower on average, but it keeps keys in sorted order automatically, letting you efficiently do range queries, find the minimum or maximum key, or iterate keys in order, none of which a hash map supports without an expensive separate sort. Hash maps also have no meaningful worst-case guarantee unless the implementation defends against pathological hash collisions, while tree maps guarantee O(log n) even in the worst case because of their balancing invariant. So the decision really comes down to whether you need ordering: pick a hash map for pure key-value lookups where speed is the priority, and pick a tree map when you need sorted iteration, range queries, or predecessor and successor operations. Memory-wise, hash maps also tend to have more overhead per entry due to load factor and bucket allocation, while tree maps have consistent per-node pointer overhead.
The two-pointer technique uses two indices that move through a data structure, usually an array or string, according to some condition, instead of using nested loops, which often turns an O(n^2) brute-force solution into O(n). A common pattern is one pointer starting at each end of a sorted array moving inward, useful for finding a pair that sums to a target, or two pointers moving in the same direction at different speeds, like cycle detection in a linked list. The sliding window technique is a specialized case of two pointers where you maintain a contiguous subrange, or window, that expands or contracts based on a condition, letting you track running sums, counts, or character frequencies without recomputing them from scratch for every possible subrange. Both techniques rely on the insight that you can reuse work from the previous position instead of restarting, which is what gets you from quadratic to linear time. They show up constantly in interview problems involving subarrays, substrings, or pairs, like longest substring without repeating characters or maximum sum subarray of a fixed size.
Union-Find keeps track of a collection of disjoint sets and supports two operations efficiently: find, which tells you which set an element belongs to by returning a representative or root, and union, which merges two sets together. In its naive form, both operations can degrade to O(n) if the underlying trees become tall and skewed. Union by rank, or union by size, fixes this by always attaching the smaller or shallower tree under the root of the larger one during a union, which keeps trees from growing unnecessarily tall. Path compression fixes it further by having every node visited during a find operation point directly to the root afterward, flattening the tree for all future queries along that path. Combined, these two optimizations bring the amortized time per operation down to nearly O(1), technically O(inverse Ackermann function of n), which grows so slowly it's effectively constant for any input size you'd encounter in practice, and this is exactly why Union-Find is the go-to structure for Kruskal's algorithm and cycle detection in undirected graphs.
Memoization is the top-down approach, where you write the recursive solution naturally and then cache the result of each subproblem the first time it's computed, so subsequent calls with the same inputs return instantly from the cache instead of recomputing. Tabulation is the bottom-up approach, where you identify the smallest subproblems first, solve them iteratively, and build up to the final answer by filling in a table in an order that guarantees each subproblem's dependencies are already solved. Memoization tends to be easier to write since it mirrors the natural recursive definition of the problem, and it only computes the subproblems that are actually needed, but it carries recursion overhead and stack depth risk. Tabulation avoids recursion entirely and is often more space-efficient, since you can frequently reduce the table to just the last row or last few values needed, like in Fibonacci or the knapsack problem, but it requires you to figure out a valid computation order up front. Both achieve the same asymptotic time complexity for a given problem, so the choice is mostly about code clarity, stack safety, and how much you can optimize the space afterward.
A stable sort preserves the relative order of elements that compare as equal, so if two records share the same sort key, the one that appeared earlier in the input still appears earlier in the output. An unstable sort makes no such guarantee, equal elements might get reordered relative to each other during the sorting process. This matters most when you're sorting by one key but care about a previously established order on another key, like sorting a list of employees by department after they were already sorted by last name, where you want people in the same department to still appear in last-name order. Mergesort, insertion sort, and bubble sort are naturally stable, while quicksort and heapsort are not stable in their typical implementations, though quicksort can be made stable at the cost of extra memory. In an interview, if you're asked to sort composite records by multiple keys applied one after another, recognizing that you need a stable sort for that approach to work correctly is often the key insight.