Algorithm tutorials

100 resources · Page 4 of 5

1. Algorithm tutorials

   Probability and Expected-Value DP

   Compute probabilities by pushing probability mass forward through states and expected costs by working backward from the goal with linearity of expectation, including how to handle self-loops, with knight-on-board, biased-coin and coupon-collector style examples.

2. Algorithm tutorials

   Queue and Deque

   First-in-first-out queues and double-ended queues: the engine behind BFS, time-window counters and ring buffers, plus the classic queue-from-two-stacks and circular-queue designs.

3. Algorithm tutorials

   Quicksort and Quickselect

   Randomized quicksort with a three-way (Dutch national flag) partition, quickselect for the k-th smallest or largest element in expected O(n), and the pitfalls that make quicksort quadratic.

4. Algorithm tutorials

   Randomized Algorithms: Shuffling, Sampling and Random Choices

   The randomness questions interviews actually ask: Fisher-Yates shuffle, reservoir sampling, weighted random pick, rejection sampling, O(1) random sets, random pivots and random hashing, plus Las Vegas versus Monte Carlo and how to test random code.

5. Algorithm tutorials

   Recursion and Divide and Conquer

   How to design recursive functions by contract (base case, smaller subproblem, trust the call), how divide and conquer splits and combines, and when to memoize or convert recursion to an explicit stack.

6. Algorithm tutorials

   Segment Tree

   A binary tree of range summaries that answers range queries and point updates in O(log n) for any mergeable operation. Includes a compact bottom-up template, lazy propagation for range updates, and tree descent for 'first index' queries.

7. Algorithm tutorials

   Shortest Cycle in a Graph (Girth and Minimum Weight Cycle)

   Find the shortest cycle in an unweighted graph with a BFS from every vertex, the minimum-weight cycle of an undirected graph with a Floyd-Warshall twist, and of a directed graph with one Dijkstra per vertex.

8. Algorithm tutorials

   Shortest Paths: Dijkstra, Bellman-Ford, Floyd-Warshall

   How to pick and implement a shortest-path algorithm: heap-based Dijkstra for non-negative weights, Bellman-Ford for negative edges and edge-count limits, Floyd-Warshall for all pairs on small graphs.

9. Algorithm tutorials

   Simulation

   Implementing exactly what the statement describes, cleanly and without off-by-one errors: direction vectors, in-place state updates, unit normalization, closed forms and cycle detection when the step count is huge.

10. Algorithm tutorials

    Skip List

    A sorted linked list with randomized express lanes that supports search, insert and delete in expected O(log n) without any rebalancing; the structure behind Redis sorted sets and a classic 'design a skiplist' question.

11. Algorithm tutorials

    Sorting Basics: Stability and the Simple O(n^2) Sorts

    Sorting vocabulary every interview assumes (stable, in-place, adaptive, the n log n comparison lower bound) plus selection, bubble and insertion sort, when each still matters, and a comparison table of all common sorts.

12. Algorithm tutorials

    Sorting in Practice: Built-in Sorts and Custom Comparators

    What Python, C++ and Java library sorts actually guarantee (Timsort, introsort, stability), how to write correct keys and comparators, partial sorting and nth element, and the many problems that become easy after sorting.

13. Algorithm tutorials

    Sparse Table

    Precompute answers for all power-of-two ranges to get O(1) range min, max, gcd, AND and OR queries on a static array after O(n log n) preprocessing.

14. Algorithm tutorials

    Square Root Decomposition

    Split an array into blocks of about sqrt(n) and keep a summary per block to answer range updates and queries in O(sqrt n), including queries like 'count elements >= x' that segment trees handle poorly.

15. Algorithm tutorials

    Stack

    A last-in-first-out container with O(1) push, pop and peek. The go-to tool for matching brackets, nested structures, expression evaluation and turning recursion into iteration.

16. Algorithm tutorials

    String Basics for Interviews

    Substring vs. subsequence, prefixes and suffixes, lexicographic order, palindromes and Hamming distance, plus the cost of common string operations and the small templates (two pointers, center expansion, counting) that most string questions start from.

17. Algorithm tutorials

    Rolling Hash (Rabin-Karp)

    Polynomial string hashing with prefix hashes gives the hash of any substring in O(1), which turns substring equality into integer comparison: Rabin-Karp matching, longest duplicate substring, palindrome checks and more.

18. Algorithm tutorials

    Strongly Connected Components (Tarjan and Kosaraju)

    Split a directed graph into maximal groups of mutually reachable vertices in O(n + m), with iterative Tarjan or Kosaraju, then shrink each group to a vertex to get a DAG you can reason about.

19. Algorithm tutorials

    Subsequence Automaton (Next-Occurrence Table)

    Precompute, for every position and character, where that character next occurs. Then any subsequence check is a greedy walk in O(len(t)), and DPs over the table count distinct subsequences or find the shortest string that is not a subsequence.

20. Algorithm tutorials

    Suffix Array and LCP Array (Intro)

    Sort all suffixes of a string with prefix doubling, compute the LCP of neighbouring suffixes with Kasai's algorithm, and use the pair to count distinct substrings, find the longest repeated substring and the longest common substring.

21. Algorithm tutorials

    Topological Sort (Kahn's Algorithm and DFS)

    Order the vertices of a directed acyclic graph so every edge points forward, detect cycles along the way, and run DP over a DAG for longest paths and scheduling.

22. Algorithm tutorials

    Tree Basics and Traversals

    Tree vocabulary, how to root a tree given as an edge list, bottom-up work in reverse traversal order, ancestor checks with entry/exit indices, and the binary-tree traversals interviewers expect.

23. Algorithm tutorials

    Tree Diameter and Center

    Find the longest path in a tree with two BFS passes or one bottom-up DP (needed for negative weights and binary-tree variants), and find the center(s) by peeling leaves or taking the middle of a diameter.

24. Algorithm tutorials

    Tree DP: Subtree States, Path Sums, Tree Knapsack and Rerooting

    Dynamic programming on rooted trees: take/skip states, returning a downward value while recording a bent path, merging children like a knapsack, and the two-pass rerooting technique, with recursion-free traversal order for big trees.