Algorithm tutorials

100 resources · Page 3 of 5

1. Algorithm tutorials

   Knapsack DP: 0/1, Unbounded, Bounded and Counting

   The knapsack family in one place: 0/1 versus unbounded loop direction, bounded knapsack with binary splitting, exactly-full versus at-most initialization, coin change, counting combinations versus sequences, and subset-sum tricks.

2. Algorithm tutorials

   Knapsack Variants: Groups, Two Budgets, Reconstruction and Counting

   Extensions of the 0/1 knapsack that show up in harder OAs: group knapsack, two-dimensional costs, recovering the chosen items, counting optimal subsets and undoing an item in a counting knapsack.

3. Algorithm tutorials

   State-Space Shortest Paths (Layered Graphs)

   When the best move depends on more than your current vertex (discounts used, obstacles removed, keys held, nodes visited), make that extra information part of the vertex and run ordinary BFS or Dijkstra on the expanded graph.

4. Algorithm tutorials

   Linked List Techniques

   Singly and doubly linked lists with the pointer toolkit interviews test: dummy heads, fast/slow pointers, in-place reversal, merging, and the hash map + doubly linked list LRU cache.

5. Algorithm tutorials

   Lowest Common Ancestor and Binary Lifting

   From the classic one-query LCA in a binary tree to binary lifting, which answers k-th ancestor, LCA and distance queries in O(log n) each after O(n log n) preprocessing.

6. Algorithm tutorials

   Majority Element and Boyer-Moore Voting

   Find the value that occurs more than n/2 times in one pass and O(1) memory with Boyer-Moore voting, why the verification pass matters, and the generalization to more than n/3 or n/k occurrences (Misra-Gries heavy hitters).

7. Algorithm tutorials

   Manacher's Algorithm (All Palindromes in O(n))

   Manacher's algorithm computes the longest palindrome centered at every position in linear time by mirroring inside the rightmost palindrome found so far: longest palindromic substring, palindrome counting and O(1) palindrome queries.

8. Algorithm tutorials

   Manhattan and Chebyshev Distance Tricks

   Use the (x+y, x-y) rotation that turns Manhattan distance into Chebyshev distance to find the farthest pair in O(n), extend it to k dimensions with sign patterns, and minimize or sum Manhattan distances one axis at a time with medians and prefix sums.

9. Algorithm tutorials

   Matrix Exponentiation for Linear Recurrences

   Turn a linear recurrence or a small step-by-step DP into a matrix and raise it to the n-th power in O(k^3 log n): companion matrices, Fibonacci by fast doubling, augmenting the state with constants, and counting walks of exact length in a graph.

10. Algorithm tutorials

    Maximum Flow and Minimum Cut (Intro)

    Residual graphs, augmenting paths and the max-flow min-cut theorem, with an Edmonds-Karp template, min-cut recovery, and the modeling tricks (super source, node splitting, project selection) that make flow useful in interviews.

11. Algorithm tutorials

    Largest Rectangle in a Histogram and Maximal Rectangle

    For every bar, find how far it can stretch left and right while staying the lowest: the hanging-line jump method and the monotonic stack, applied to the largest histogram rectangle, the largest all-ones rectangle in a binary matrix, and min-times-sum subarray problems.

12. Algorithm tutorials

    Memoization (Top-Down DP) and DP on DAGs

    Turn a brute-force recursion into dynamic programming by making it pure and caching it, compare top-down with bottom-up, and use the DAG view to solve longest-path style problems such as increasing paths in a grid and block stacking.

13. Algorithm tutorials

    Merge Sort and Inversion Counting

    Stable, guaranteed O(n log n) merge sort (top-down and bottom-up), sorting linked lists, and the merge-step counting trick behind inversion counts and 'count smaller numbers after self'.

14. Algorithm tutorials

    Minimax and Alpha-Beta Pruning

    Searching two-player zero-sum games: minimax and its negamax form, memoized game DP for 'predict the winner' and 'can I win' style questions, and alpha-beta pruning that returns the same answer while skipping branches that cannot matter.

15. Algorithm tutorials

    Minimum Spanning Tree: Kruskal and Prim

    Connect every vertex of a weighted undirected graph at minimum total cost. Kruskal sorts edges and uses union-find; Prim grows one tree with a heap, or with an O(n^2) scan on dense graphs.

16. Algorithm tutorials

    Modular Arithmetic and Modular Inverses

    Working modulo 10^9+7 without mistakes: which operations commute with the remainder, language differences for negative numbers and overflow, modular inverses via Fermat's little theorem or extended Euclid, linear-time inverse and factorial tables, modular fractions and huge exponents.

17. Algorithm tutorials

    Monotonic Queue

    A deque of candidates kept in sorted order gives the max or min of every sliding window in O(n). Also speeds up window DP and solves shortest-subarray problems with negative numbers.

18. Algorithm tutorials

    Monotonic Stack

    A stack kept sorted by popping violators finds every element's next/previous greater or smaller neighbor in O(n). Powers histogram rectangles, contribution counting, greedy digit removal and Cartesian tree construction.

19. Algorithm tutorials

    Newton's Method and Integer Square Roots

    Compute square roots and k-th roots with Newton's method: why x = (x + n/x)/2 converges quadratically and monotonically from above, exact integer square roots for arbitrarily large numbers, the binary search alternative, perfect-square checks and floating-point pitfalls.

20. Algorithm tutorials

    Number Bases, Base Conversion and Gray Code

    Convert between number systems: repeated divmod and Horner's rule for any base up to 36, negative bases such as base -2, the bijective base 26 behind spreadsheet column titles, mixed radix, and Gray code with its inverse.

21. Algorithm tutorials

    Permutations: Cycles, Next Permutation, Ranking and Inversions

    Work with permutations as functions: cycle decomposition for minimum swaps and in-place rearrangement, inverses, the next lexicographic permutation, converting between a permutation and its rank with the factorial number system, and counting inversions by merge sort.

22. Algorithm tutorials

    Prefix Sums and Difference Arrays

    O(1) range sums after O(n) preprocessing, the prefix-sum plus hash map pattern for counting subarrays, 2D prefix sums for rectangle queries, and difference arrays for batches of range updates.

23. Algorithm tutorials

    Primes, Sieves and Prime Factorization

    Primality testing by trial division, the sieve of Eratosthenes, the linear sieve with a smallest-prime-factor table for fast factorization, listing divisors, and a segmented sieve for primes in a far-away range.

24. Algorithm tutorials

    Probability and Expected Value for Coding Interviews

    The probability toolkit interviews actually use: conditional probability and Bayes' rule, linearity of expectation with indicator variables, geometric waiting times and the coupon collector, first-step analysis for expected times, rejection sampling, and exact or simulated sanity checks.