Data Structures

  1. 1 Arrays and Strings Most interview problems hand you an array or a string, and most slow solutions come from treating them as if every operation were free. Inserting at the front of a list of a million items, or building a string one character at a time, can quietly turn an O(n) idea into O(n²). Knowing what arrays ... 4 min read
  2. 2 Hash Maps The first idea for many problems is a loop inside a loop: for every element, search the rest for something. That's O(n²), and with 10⁵ elements it is too slow. A hash map fixes this by remembering what you have already seen, so "search the rest" becomes a single O(1) lookup. It is the most common... 5 min read
  3. 3 Linked Lists Arrays are great until you need to insert or remove in the middle, again and again: each change shifts everything after it. A linked list makes those changes O(1) if you already hold the right node, at the price of slow access by position. Linked list problems are common in interviews less becaus... 4 min read
  4. 4 Stacks and Queues Some problems are about order: the most recent thing you opened must be the first one you close, or the first thing you discovered must be the first one you process. Trying to track that with indexes into an array gets messy fast. Stacks and queues are arrays (or lists) with a rule about which en... 4 min read
  5. 5 Binary Trees Folder structures, org charts, expression parsers and decision rules are all hierarchies, and a flat list can't answer questions like "how deep is this?" or "what do these two have in common?" without a lot of bookkeeping. Trees are the most common data structure in coding interviews after arrays... 4 min read
  6. 6 Binary Search Trees A hash map finds an exact key in O(1), but it can't answer "what is the smallest key larger than 42?" or "list everything between 10 and 20, in order" without scanning everything. A sorted array can, but inserting into it is O(n). A binary search tree keeps data sorted and supports fast inserts, ... 5 min read
  7. 7 Heaps "Give me the 10 most frequent words", "merge these k sorted lists", "schedule the next task that's due": each asks for the smallest or largest item, over and over, while new items keep arriving. Sorting everything after each change is O(n log n) each time; scanning for the minimum is O(n). A heap... 5 min read
  8. 8 Graphs Course prerequisites, friend networks, flight routes, a maze, a grid of islands: whenever things are connected to other things in arbitrary ways, neither a list nor a tree fits. Interviewers love these problems because the hard part is rarely the algorithm. It's seeing that the problem is a graph... 6 min read
  9. 9 Tries Type "ca" into a search box and it suggests "car", "cart", "cat" before you finish. Doing that with a list of a million words means checking every word for the prefix on every keystroke. A hash set can't help either: it only answers "is this exact word here?". A trie stores words by their shared ... 5 min read
  10. 10 Union-Find Connections keep arriving: "user 3 and user 7 are the same person", "server A can now reach server B", "these two accounts share an email". After each one you need to answer "are X and Y in the same group?" or "how many groups are there now?". Re-running a DFS over the whole graph after every new... 5 min read