Data Structures and Algorithms

Measuring the cost of code and approaching a new problem calmly.

• Time and space complexity
• Big-O, Big-Omega and Big-Theta
• Counting loops and common growth rates
• Best, average and worst case
• Brute force to optimal
• Edge cases and testing

• Big O notation
• Start with brute force
• What Big-O Means and Counting Steps

The patterns behind most easy and medium problems.

• Array traversal and in-place changes
• Two pointers
• Sliding window
• Prefix sums and difference arrays
• Hashing for counting and lookup
• Binary search and its variants

• The two pointers idea
• The sliding window idea
• Prefix sum arrays
• Classic binary search in Java
• Two Pointers from Both Ends: Pair Sum, Palindrome and Container

Nodes and pointers, and the classic list problems.

• Singly and doubly linked lists
• Insert, delete and search
• Reversing a list
• Fast and slow pointers
• Merging sorted lists
• Array versus linked list trade-offs

• Build a singly linked list
• Reverse a linked list
• Fast and slow pointers
• The Node Class: Build and Traverse
• Insert and Delete

Linear structures and fast lookup.

• Stack and queue operations
• Balanced brackets and expression evaluation
• Monotonic stack
• Deque and circular queue
• Hash functions and collisions
• Chaining and open addressing

• Stacks: last in, first out
• Balanced brackets
• How hashing works
• Stacks with a List: Push, Pop and Peek
• Collisions, Chaining and Probing

Thinking recursively and the classic sorting algorithms.

• Base case and recursive case
• Recursion trees
• Bubble, selection and insertion sort
• Merge sort and quick sort
• Counting and radix sort
• Subsets, permutations and pruning

• Recursion trees
• Merge sort
• Quick sort
• Generating subsets
• Merge Sort and Counting Inversions

Hierarchical data and ordered search.

• Tree terms and binary trees
• Pre-order, in-order and post-order traversal
• Level-order traversal
• Height, diameter and balance
• Binary search tree insert, search and delete
• Lowest common ancestor

• Preorder, inorder and postorder
• The BST rule
• Delete from a BST
• Preorder, Inorder and Postorder Traversals
• The BST Rule, Search and Insert

Getting the smallest or largest item fast, and searching by prefix.

• Binary heap and its array form
• Sift up and sift down
• Heap sort
• Priority queues and top-k problems
• Tries for prefix search

• What a heap is
• Build a heap yourself
• How a Heap Works: Sift Up and Sift Down

Modelling networks and finding paths.

• Graph terms and representations
• Adjacency list versus matrix
• Breadth-first and depth-first search
• Connected components and cycle detection
• Shortest paths: BFS, Dijkstra, Bellman-Ford
• Topological sort and union-find
• Minimum spanning trees

• Storing graphs in Java
• Breadth-first search
• Shortest path with BFS
• Graph Terms and Adjacency Lists
• Topological Sort: Kahn and DFS

Making the best local choice, and knowing when that is enough.

• The greedy choice idea
• Activity selection
• Merging and scheduling intervals
• Exchange argument at a glance
• When greedy fails

• What greedy means
• Merge and insert intervals
• Activity Selection and Job Sequencing

Solving big problems by reusing answers to small ones.

• Overlapping subproblems and optimal substructure
• Memoization and tabulation
• 1D DP: stairs, robber, coin change
• Grid DP
• Knapsack and subset sum
• Longest common subsequence

• What dynamic programming is
• Memoization
• 0/1 knapsack
• From Recursion to Memoization to a Table
• 0/1 Knapsack and Subset Sum

Pattern matching and structures for range queries.

• Naive and KMP string search
• Rolling hash
• Segment trees
• Fenwick tree at a glance
• Choosing a structure under constraints

• The KMP algorithm
• Segment trees