Algorithms line

Data Structures

Hash tables, trees & heaps, arrays and memory layout, and how to choose the right structure

4 sections

Start: Arrays, Lists & Memory Layout

Mid-level 3

  1. Arrays, Lists & Memory LayoutArrays are the structure everything else is built on, and their advantage is not an operation count — it is physical contiguity. A CPU reads memory in cache lines of 64 bytes and aggressively prefetches sequential addresses, so a linear…, not read
  2. Hash TablesA hash table turns a key into an array index by hashing it, which is why lookup is O(1) — you compute the address rather than search for it. Everything interesting follows from what happens when two keys compute the same address. The…, not read
  3. Trees & HeapsTrees buy you ordering at O(log n) — but only while they stay balanced, and an unbalanced binary search tree is a linked list wearing a costume. That single fact explains red-black trees, AVL trees, and B-trees, and it explains why…, not read

Senior 1

  1. Choosing the Right StructureThis is the part of the competency that actually shows up in code review. The question is never "what is a red-black tree" — it is "you wrote List.Contains inside a loop over another list, do you know that is O(n·m)?" This note is the…, not read