Algorithm tutorials

100 resources · Page 2 of 5

1. Algorithm tutorials

   Dynamic Programming Basics: States, Transitions, LCS and LIS

   How to design a DP (state, transition, base case, order) and the classic sequence DPs every interview expects: grid/triangle paths, longest common subsequence, edit distance and LIS in O(n log n).

2. Algorithm tutorials

   Endianness: Byte Order in Memory, Files and Networks

   What little-endian and big-endian mean, when byte order matters (raw bytes, files, network protocols) and when it does not, how to detect it, and how to swap or decode bytes portably in Python and C++.

3. Algorithm tutorials

   Eulerian Paths and Circuits (Hierholzer's Algorithm)

   Use every edge exactly once: degree conditions tell you whether it is possible, and Hierholzer's stack-based walk builds the path in O(n + m). Covers reconstruct-itinerary, valid arrangement of pairs and de Bruijn sequences.

4. Algorithm tutorials

   Expression Evaluation: RPN, Calculators and Parsing

   Evaluating arithmetic expressions from strings: reverse Polish notation with a stack, the one-stack calculator for + - * /, the two-stack shunting-yard method with parentheses, unary minus and right-associative operators, and a recursive-descent parser.

5. Algorithm tutorials

   Fast Exponentiation (Binary Exponentiation)

   Compute a^n with O(log n) multiplications by squaring along the binary digits of n: iterative and recursive modular power, pow(x, n) with negative exponents, exponents given as digit arrays, and the generic version for permutations or any associative operation.

6. Algorithm tutorials

   Fenwick Tree (Binary Indexed Tree)

   A tiny array-based structure for point updates and prefix sums in O(log n). Covers O(n) build, inversion counting over compressed values, k-th smallest via binary lifting, and range-add range-sum with two trees.

7. Algorithm tutorials

   Finite State Machines for Parsing and Validation

   Model validation and parsing tasks as automata: table-driven DFAs (valid number, divisibility of binary prefixes), counter-style machines (UTF-8 validation), NFA simulation for regex matching with '.' and '*', and the subsequence automaton for many queries.

8. Algorithm tutorials

   Fractional Programming: Binary Search on a Ratio

   Maximize a ratio such as sum(a)/sum(b) or an average by binary searching the answer λ and checking whether some choice makes sum(a - λb) non-negative, plus Dinkelbach's iteration for exact answers.

9. Algorithm tutorials

   Game Theory Basics: Winning Positions, Nim and Minimax DP

   Solve optimal-play questions as DP on the game graph: label winning and losing positions, use the XOR rule for Nim and Sprague-Grundy numbers for sums of games, and compute score games with the best-difference recurrence.

10. Algorithm tutorials

    GCD, LCM and the Extended Euclidean Algorithm

    Euclid's algorithm for GCD and LCM, the extended version that returns Bezout coefficients, and what Bezout's identity buys you in interviews: jug problems, integer linear equations, modular inverses for non-prime moduli, and GCD-normalized slopes and ratios.

11. Algorithm tutorials

    Computational Geometry Basics: Cross Product, Segments, Polygons and Convex Hull

    Exact integer geometry for interviews: dot and cross products, orientation tests, segment intersection including touching and collinear cases, the shoelace area formula, ray-casting point-in-polygon, and Andrew's monotone chain convex hull with or without collinear boundary points.

12. Algorithm tutorials

    Graph Basics and Representations

    The vocabulary interviewers expect (directed, weighted, degree, path, cycle, component) and how to store a graph as an edge list, adjacency matrix, adjacency list, or implicit grid.

13. Algorithm tutorials

    Breadth-First Search on Graphs and Grids

    BFS explores a graph layer by layer, so the first time it reaches a vertex is along a fewest-edges path. Covers path reconstruction, grid BFS, multi-source BFS and 0-1 BFS.

14. Algorithm tutorials

    Depth-First Search on Graphs

    DFS on adjacency lists and grids: connected components, flood fill, iterative traversal without recursion limits, and cycle detection in undirected and directed graphs.

15. Algorithm tutorials

    Greedy Algorithms

    Making the locally best choice and proving it is safe: sort-then-scan greedy, heap-based greedy, regret (undo the worst choice) greedy, and exchange arguments for ordering and scheduling problems.

16. Algorithm tutorials

    Hash Table

    Average O(1) insert and lookup by hashing keys into buckets. Covers collisions, load factor and resizing, plus the interview patterns: complement lookup, canonical-key grouping and prefix-sum counting.

17. Algorithm tutorials

    Heap and Priority Queue

    Binary heaps give O(1) access to the minimum and O(log n) push/pop in a plain array. Learn sift up/down, O(n) heapify, Python's heapq idioms, and the top-k, k-way merge and two-heap median patterns.

18. Algorithm tutorials

    Heap Sort

    In-place, worst-case O(n log n) sorting with a binary max-heap stored in an array: sift-down, O(n) bottom-up heapify, and how the same pieces solve k-sorted arrays and partial sorting.

19. Algorithm tutorials

    Huffman Coding

    Build an optimal prefix-free code by repeatedly merging the two lightest trees with a min-heap. The same greedy solves 'minimum cost to connect ropes' because total cost equals the sum of all merges.

20. Algorithm tutorials

    Inclusion-Exclusion Principle

    Count objects satisfying at least one or none of several conditions by alternating sums over intersections: divisibility by any of several numbers (with binary search for the n-th one), distributions with upper bounds, derangements and surjections.

21. Algorithm tutorials

    Interval DP

    Dynamic programming over contiguous ranges: split-point recurrences such as merging piles and bursting balloons, shrink-from-the-ends recurrences such as palindromic subsequences, correct iteration order and circular inputs.

22. Algorithm tutorials

    Interval Maps: Range Assignment over Disjoint Segments

    Keep a line as an ordered map of disjoint constant segments; split at the endpoints and overwrite whole ranges with amortized cost. Covers range modules, calendars, painting problems and counting covered integers.

23. Algorithm tutorials

    The Josephus Problem

    Who survives when every k-th person in a circle is eliminated: queue simulation, the O(n) recurrence J(n) = (J(n-1) + k) mod n and its derivation, the k = 2 closed form, and an O(k log n) method for huge n.

24. Algorithm tutorials

    KMP and the Prefix Function

    The prefix function records, for every prefix, its longest border (a proper prefix that is also a suffix). With it, KMP finds all occurrences of a pattern in O(n + m) and answers period, repetition and palindrome-prefix questions.