--- title: Topics description: The full checklist of data structures, algorithms and named patterns worth knowing, with what to know about each and which ones are already written up. tags: [dsa, topics, checklist, algorithms, data-structures, interview] --- A coverage map rather than a tutorial. Use it to find the gap in what you know, then go to [patterns](https://brain.narayann.dev/notes/engineering/problem-solving/patterns) for the template and [collections](https://brain.narayann.dev/notes/engineering/java/collections) for the Java API. The three lists below overlap on purpose. Data structures are what you store things in, algorithms are what you do to them, and the named patterns are the combinations that keep reappearing in interview questions. ## Data structures | Structure | What to know | Java | | ---------------------------------------------------------------------------------------- | -------------------------------------------------------------------------------------------------------------------------------------------- | ------------------------------------- | | [Array](/notes/engineering/java/collections#arrays) | Fixed length, O(1) by index, O(n) to insert in the middle. Sorting unlocks two pointers and binary search. | `int[]`, `Arrays` | | [String](/notes/engineering/java/collections#strings) | Immutable, so concatenation in a loop is O(n^2). Build with a builder. | `String`, `StringBuilder` | | [Matrix or grid](/notes/engineering/problem-solving/patterns#matrix-traversal) | A 2D array is a graph with implicit neighbours. Keep one direction array, and check whether movement is 4 way or 8 way. | `int[][]` | | [Hash map and hash set](/notes/engineering/java/collections#hashmap) | O(1) average, worst case O(log n) per bucket. A key needs `equals` and `hashCode` to agree, and must not mutate after insertion. | `HashMap`, `HashSet`, `LinkedHashMap` | | [Ordered map and set](/notes/engineering/java/collections#treemap) | Sorted keys, plus `floor`, `ceiling`, `higher`, `lower` and range views. O(log n) for everything. | `TreeMap`, `TreeSet` | | [Linked list](/notes/engineering/problem-solving/patterns#linked-list-surgery) | Singly and doubly. A dummy head removes the empty and first node special cases. Reversal and merging are the two moves. | Hand rolled `ListNode`, `LinkedList` | | [Stack](/notes/engineering/java/collections#stack) | Last in, first out. Use the deque, not the legacy synchronised class. | `ArrayDeque` | | [Queue and deque](/notes/engineering/java/collections#queue) | First in, first out, or both ends in O(1). The deque is also the sliding window maximum structure. | `ArrayDeque` | | [Heap or priority queue](/notes/engineering/java/collections#priorityqueue) | O(log n) insert and remove, O(1) peek. Iteration order is not sorted. | `PriorityQueue` | | [Binary tree and BST](/notes/engineering/problem-solving/patterns#binary-tree-traversal) | Height, depth, the three DFS orders, level order. On a BST, inorder comes out sorted and the ordering property prunes half the search. | Hand rolled `TreeNode` | | [Trie](/notes/engineering/problem-solving/patterns#trie) | A tree keyed by character, so lookup costs word length rather than dictionary size. | Hand rolled node with `next[26]` | | [Graph](/notes/engineering/problem-solving/patterns#dfs) | Adjacency list against adjacency matrix, directed against undirected, weighted against unweighted. The representation decides the algorithm. | `List>` | | [Disjoint set](/notes/engineering/problem-solving/patterns#union-find) | Union find with path compression and union by rank, effectively constant per operation. | Hand rolled `DSU` | | [Fenwick or segment tree](/notes/engineering/problem-solving/patterns#fenwick-tree) | Range queries that survive updates, O(log n) each. Fenwick for sums, segment tree for anything not subtractable. | Hand rolled `int[]` | | [Bitmask](/notes/engineering/problem-solving/patterns#bit-manipulation) | An integer as a set of flags, which makes subset enumeration a plain loop. | `int`, `long` | ## Algorithms and techniques | Technique | What to know | | -------------------------------------------------------------------------------------------- | ---------------------------------------------------------------------------------------------------------------------------- | | [Sorting](/notes/engineering/java/collections#sorting-and-comparators) | O(n log n), custom comparators, stability, and the fact that most greedy solutions open with a sort. | | [Binary search](/notes/engineering/problem-solving/patterns#binary-search) | Two forms: on an index, and on the answer when the question is the smallest value that works. | | [Two pointers](/notes/engineering/problem-solving/patterns#two-pointers) | Opposite ends on sorted input, or same direction with a read and a write pointer for in-place edits. | | [Fast and slow pointers](/notes/engineering/problem-solving/patterns#fast-and-slow-pointers) | Cycle detection and finding the middle, in O(1) space. | | [Sliding window](/notes/engineering/problem-solving/patterns#sliding-window) | Fixed and variable size, usually paired with a hash map or a frequency array. | | [Prefix sum and difference array](/notes/engineering/problem-solving/patterns#prefix-sum) | Range sums with no updates, and range updates with one read at the end. | | Recursion | Base case, progress toward it, and what the call stack is holding for you. | | [Backtracking](/notes/engineering/problem-solving/patterns#backtracking) | Choose, recurse, undo. Subsets, permutations, and constraint filling. | | Divide and conquer | Merge sort, quicksort, quickselect for the kth element in O(n) average. | | [Greedy](/notes/engineering/problem-solving/patterns#greedy) | Sort by the right key, then argue why a local choice cannot block a better global one. | | [Dynamic programming](/notes/engineering/problem-solving/patterns#dynamic-programming) | Memoisation against tabulation, 1D and 2D states, subsequences, and 0/1 knapsack as the shape most others reduce to. | | [DFS](/notes/engineering/problem-solving/patterns#dfs) | Reachability, connected components, and enumerating every path. | | [BFS](/notes/engineering/problem-solving/patterns#bfs) | Shortest path on unweighted edges, and level by level work. | | [Topological sort](/notes/engineering/problem-solving/patterns#topological-sort) | Ordering under dependencies, and cycle detection as a side effect. | | [Union find](/notes/engineering/problem-solving/patterns#union-find) | Merging groups and answering whether two things are connected. | | Shortest paths | Dijkstra for non negative weights, Bellman-Ford when weights can be negative, Floyd-Warshall for all pairs on a small graph. | | Minimum spanning tree | Kruskal with union find, or Prim with a heap. | | [Bit manipulation](/notes/engineering/problem-solving/patterns#bit-manipulation) | XOR cancelling pairs, clearing and isolating the lowest set bit, subset masks. | | [Math and number theory](/notes/engineering/problem-solving/patterns#math-and-geometry) | GCD and LCM by Euclid, the sieve for primes, modular arithmetic to keep numbers in range. | | [Geometry](/notes/engineering/problem-solving/patterns#math-and-geometry) | Compare squared distances instead of taking roots, and use the cross product sign for turn direction. | | [Game theory](/notes/engineering/problem-solving/patterns#game-theory) | Minimax, and the rule that a position wins when some move leaves the opponent losing. | | String matching | KMP and Rabin-Karp for substring search in linear time. | | [Concurrency](/notes/engineering/problem-solving/patterns#concurrency) | Threads, locks, `synchronized`, and the standard producer and consumer setup. | ## The named patterns The list most interview prep material is organised around. Each row jumps straight to the section holding that template, not to the top of the page. | # | Pattern | Jump to | | -- | ---------------------------------- | -------------------------------------------------------------------------------------------- | | 1 | Two pointers | [Two pointers](/notes/engineering/problem-solving/patterns#two-pointers) | | 2 | Fast and slow pointers | [Fast and slow pointers](/notes/engineering/problem-solving/patterns#fast-and-slow-pointers) | | 3 | Sliding window | [Sliding window](/notes/engineering/problem-solving/patterns#sliding-window) | | 4 | Merge intervals | [Merge intervals](/notes/engineering/problem-solving/patterns#merge-intervals) | | 5 | Cyclic sort | [Cyclic sort](/notes/engineering/problem-solving/patterns#cyclic-sort) | | 6 | In-place reversal of a linked list | [Linked list surgery](/notes/engineering/problem-solving/patterns#linked-list-surgery) | | 7 | Stack | [Stack](/notes/engineering/problem-solving/patterns#stack) | | 8 | Monotonic stack | [Monotonic stack](/notes/engineering/problem-solving/patterns#monotonic-stack) | | 9 | Hash maps | [Hashing](/notes/engineering/problem-solving/patterns#hashing) | | 10 | Tree breadth first search | [Binary tree traversal](/notes/engineering/problem-solving/patterns#binary-tree-traversal) | | 11 | Tree depth first search | [Binary tree traversal](/notes/engineering/problem-solving/patterns#binary-tree-traversal) | | 12 | Graphs | [DFS and BFS](/notes/engineering/problem-solving/patterns#dfs) | | 13 | Islands and matrix traversal | [Matrix traversal](/notes/engineering/problem-solving/patterns#matrix-traversal) | | 14 | Two heaps | [Two heaps](/notes/engineering/problem-solving/patterns#two-heaps) | | 15 | Subsets | [Backtracking](/notes/engineering/problem-solving/patterns#backtracking) | | 16 | Modified binary search | [Binary search](/notes/engineering/problem-solving/patterns#binary-search) | | 17 | Bitwise XOR | [Bit manipulation](/notes/engineering/problem-solving/patterns#bit-manipulation) | | 18 | Top k elements | [Heap](/notes/engineering/problem-solving/patterns#heap) | | 19 | K-way merge | [K-way merge](/notes/engineering/problem-solving/patterns#k-way-merge) | | 20 | Greedy algorithms | [Greedy](/notes/engineering/problem-solving/patterns#greedy) | | 21 | 0/1 knapsack | [Dynamic programming](/notes/engineering/problem-solving/patterns#dynamic-programming) | | 22 | Backtracking | [Backtracking](/notes/engineering/problem-solving/patterns#backtracking) | | 23 | Trie | [Trie](/notes/engineering/problem-solving/patterns#trie) | | 24 | Topological sort | [Topological sort](/notes/engineering/problem-solving/patterns#topological-sort) | | 25 | Union find | [Union-Find](/notes/engineering/problem-solving/patterns#union-find) | | 26 | Ordered set | [TreeSet](/notes/engineering/java/collections#treeset) | | 27 | Multi-threading | [Concurrency](/notes/engineering/problem-solving/patterns#concurrency) | | 28 | Miscellaneous | [Design](/notes/engineering/problem-solving/patterns#design) | ## Still open Every named pattern above now has a template. What is left is the deeper graph work, which is big enough to deserve its own page rather than a section: Dijkstra for non negative weights, Bellman-Ford when weights can go negative, Floyd-Warshall for all pairs on a small graph, and the two minimum spanning tree constructions, Kruskal with union find and Prim with a heap. String matching is the other gap. KMP and Rabin-Karp both find a substring in linear time, and neither is hard, but they come up rarely enough that they are easy to keep putting off.