Section 1 of 5 · Algorithms & Data Structures
Complexity & Linear Structures
The first algorithmic skill is translating constraints into a cost budget and preserving a simple invariant. Arrays, hashing, windows and queues expose these habits with minimal abstraction.
8 units 16 topics 0/8
Units
8 in this section
- 1.1 Cost models, asymptotic notation and cases explain · derive4 h
- 1.2 Aggregate, accounting and potential amortized analysis derive4 h
- 1.3 Loop invariants, brute-force oracles and differential tests derive · implement4 h
- 1.4 Arrays, strings, locality and linked structures explain · implement5 h
- 1.5 Hash tables: collisions, load factor, resizing and tombstones explain · implement4 h
- 1.6 Stacks, queues, deques and monotone structures implement5 h
- 1.7 Two pointers and sliding windows derive · implement5 h
- 1.8 Prefix sums, difference arrays and prefix plus hash implement4 h
Before moving on
Checkpoint
Solve two tag-hidden linear-structure problems, state each invariant before coding, and use randomized tests to expose and minimize one plausible wrong solution.
Deliberately out of scope
Leave for later
- Cryptographic and learned hashing
- Persistent and concurrent collections
- Specialized succinct data structures
Resources for this section
Shared by every unit above
- DSA Handbook - Foundations and linear patterns Study Part 0, Part 1, Part 3 and Part 4 in order, plus the Part 5 Linked-list fundamentals chapter. Use the routing-rule pages for arrays versus lists, map choice, stack versus queue, two pointers, sliding windows and prefix methods before seeing solved code.
- AlgoMaster DSA - linear structures slice Attempt Design HashMap, Longest Substring Without Repeating Characters and Sliding Window Maximum cold. Hide tags, state the invariant first, and add randomized operation histories to Design HashMap.
- MIT 6.042J - asymptotics and invariants Use the asymptotics, state-machine invariants and proof-method readings when a cost or correctness argument is weak. Solve only the matching problems.
- Algorithms lecture notes - amortized analysis and hashing Use note 9 Amortized Analysis for the summation, taxation, charging and potential-function proofs, and note 5 Hashing for chaining, universal hashing and open-addressing analysis, when the handbook treatment is too brief for a proof.
- Algorithmica - memory and data layout Read the memory hierarchy, cache and complexity-model chapters, then measure one contiguous-versus-linked and one hash-versus-ordered workload crossover.
- NeetCode - unseen linear problems Use only for two tag-hidden transfer problems after the AlgoMaster slice. Do not start another full roadmap or watch a solution before the attempt is complete.
- Hypothesis documentation - Quickstart and stateful testing Follow Quickstart for
@givenstrategies and the pytest combination, Configuring test settings formax_examplesandderandomize, then Rule-based state machines (rule,precondition,invariant,run_state_machine_as_test) for randomized operation histories againstdictanddequeoracles. - CPython source - list and dict objects Read
list_resizeinObjects/listobject.cfor the growth formula and pattern comment, and theUSABLE_FRACTIONdefinition, perturbation-probing comment and dummy-entry handling inObjects/dictobject.c. Read the cited functions and comments only.
Apply the section
Mini-project · Hash map, two tag-hidden linear problems and a shrunk wrong solution (8 to 12 h)
Build an open-addressing hash map checked against
dict with randomized operation histories. Solve two tag-hidden linear-structure problems from invariants stated before code. Shrinking exposes one plausible wrong solution, and a probe-cost prediction tested by measurement closes the loop on the cost model.Steps
- Implement a linear-probing hash map with
get,put, tombstonedeleteand resizing at a stated load factor. Write its probe invariant and the amortized cost ofputfrom the doubling argument. - Test it with a Hypothesis rule-based state machine against a
dictoracle, checking the probe invariant and the load factor after every step. Draw colliding keys so probe chains and tombstones are exercised. - Seed one defect of each kind, a
deletethat empties the slot and aresizethat copies slots by index. Show the state machine fails on each, and keep the shrunk histories as regression tests. - Solve LC 1248 Count Number of Nice Subarrays with tags hidden. Write the counting invariant and the time and space bounds first, then check the result against an \(O(n^2)\) brute force.
- Solve LC 862 Shortest Subarray with Sum at Least K with tags hidden. First write the shrinking-window attempt and let Hypothesis shrink a failing input against brute force, then solve with prefix sums and a monotone deque and state the broken assumption.
- Predict probe counts across load factors and key distributions, then measure and compare the random-key rows against the linear-probing estimate. Record predictions beside measurements and explain the gaps.
Deliverables
- The hash map module with its invariant, cost notes, state machine and seeded-defect histories.
- Both LC solutions with invariants and bounds stated first, differential tests and the shrunk counterexample.
- A probe-count table with predictions beside measurements and the comparison against the estimate.
Checks
- rubric · Self-grade with the rubric below
- external-tests · LeetCode 1248: Count Number of Nice Subarrays
- external-tests · LeetCode 862: Shortest Subarray with Sum at Least K
Rubric
| Criterion | Pass | Strong |
|---|---|---|
| Hash map correctness | The state machine agrees with the dict oracle on randomized histories with colliding keys, and both seeded defects fail with shrunk histories. | Each shrunk history is short and readable, kept as a regression test and mapped to the invariant clause it broke. |
| Invariants before code | Both solutions state the invariant and the time and space bounds before the code, and differential tests against brute force pass. | The invariants are also asserted in a debug mode that the randomized tests switch on. |
| Wrong solution exposed | Hypothesis shrinks a failing window input, and the write-up states the assumption the counterexample breaks. | A property test on restricted inputs shows where the same window stays correct. |
| Probe measurement | The probe table covers several load factors and key distributions, with predictions recorded before measuring and random-key rows compared against the estimate. | A timing comparison against dict names the setup and explains the gap from implementation costs. |
Feeds into: Capstone correctness library: the hash map and its state machine. Failure evidence: the two seeded hash-map defects and the shrunk window counterexample.