19 — Prerequisites, Math & Glossary#

Reference. Read §19.1 and §19.2 once before 01-foundations; look the rest up as needed.

Everything the other files quietly assume you already know. If a word in this curriculum stopped you, it's here.

19.1 The maths you actually need#

Less than you fear. This is all of it.

Exponents and scientific notation#

10³ means 10 × 10 × 10 = 1,000. The small raised number is the exponent — how many times to multiply.

10¹ = 10            10⁵ = 100,000           2¹⁰ = 1,024  (≈ a thousand)
10² = 100           10⁶ = 1,000,000         2²⁰ ≈ 1,000,000
10³ = 1,000         10⁹ = 1,000,000,000     2³⁰ ≈ 1,000,000,000

Reading 10⁵ quickly: it's a 1 followed by 5 zeros. Constraints are always written this way — 1 <= n <= 10^5 means n can be up to 100,000.

Two facts worth memorising because they recur everywhere:

• 2¹⁰ ≈ 10³. So 2²⁰ ≈ 10⁶ and 2³⁰ ≈ 10⁹. This is why "n ≤ 20 suggests 2ⁿ" works — 2²⁰ is about a million, which is fine.
• 10⁸ operations per second is roughly what a machine does. Every constraint judgement in this curriculum comes from that number.

In Python, ** is the exponent operator: 2 ** 10 is 1024.

Logarithms#

A logarithm is the inverse of an exponent. It answers: "how many times do I multiply the base to reach this number?"

2³ = 8          so    log₂(8) = 3
2¹⁰ = 1024      so    log₂(1024) = 10

For algorithms, only base 2 matters, and there's a single interpretation you need:

log₂(n) = how many times you can halve n before reaching 1.

Halve 1,000,000: 500k, 250k, 125k, … you reach 1 after about 20 steps. So log₂(10⁶) ≈ 20.

log₂(1,000)         ≈ 10
log₂(1,000,000)     ≈ 20
log₂(1,000,000,000) ≈ 30

Why this dominates algorithms: any procedure that throws away half the remaining possibilities each step finishes in log₂(n) steps. Binary search on a billion items takes 30 comparisons. A balanced tree of a billion nodes is 30 levels deep. That's the whole reason "O(log n)" is treated as nearly free.

You never compute a logarithm by hand in an interview. You only need "log means repeated halving, and it's a small number."

O, Ω, and Θ#

Three related notations. You'll use one.

In practice everyone says "O(n)" even when they mean Θ(n). That's fine and expected. Ω appears once in this curriculum: the proof that comparison-based sorting cannot beat Ω(n log n) — meaning no comparison sort can ever be faster than that, as a matter of mathematics, not engineering.

Series and why "amortized" works#

Some sums that appear constantly:

1 + 2 + 3 + ... + n  =  n(n+1)/2  ≈  n²/2      → O(n²)

That's why a nested loop where the inner one shrinks (for j in range(i+1, n)) is still O(n²).

n + n/2 + n/4 + n/8 + ...  =  2n                → O(n)

This one is the key to several "surprisingly fast" results. Each term is half the last, and the whole infinite sum converges to just 2n. It's why:

• quickselect is O(n) on average, not O(n log n)
• building a heap (heapify) is O(n), not O(n log n)
• a dynamic array's repeated doubling costs O(1) per append amortized

Amortized means: averaged over a sequence of operations, even in the worst case. One append might trigger an expensive copy, but that copy buys many cheap appends, so the average stays O(1). It is not the same as "average case", which is about random inputs.

Modular arithmetic#

a % b is the remainder after dividing. 17 % 5 = 2.

Uses you'll actually hit:

n % 2 == 0                  # even?
i % len(arr)                # wrap around to 0 — circular arrays
(i + 1) % n                 # next index, cyclically
hash(key) % capacity        # which bucket — this is how dicts work
result % (10**9 + 7)        # keep huge numbers manageable

Why 10**9 + 7? Competitive problems ask for answers "modulo 10⁹+7" because results overflow otherwise. It's a large prime, which makes the arithmetic well-behaved. In Python, integers never overflow, so you just apply % MOD where the problem says to.

Combinatorics#

Only two facts needed.

Permutations — orderings of n distinct things: n! (n factorial) = n × (n−1) × … × 1.

3! = 6     4! = 24     10! = 3,628,800     20! ≈ 2.4 × 10¹⁸

Factorials explode. That's why "generate all permutations" problems always have n ≤ 10.

Subsets — for n items, each is either in or out, so there are 2ⁿ subsets.

2¹⁰ = 1,024      2²⁰ ≈ 1,000,000      2³⁰ ≈ 10⁹

That's why "generate all subsets" problems cap at n ≈ 20.

Combinations — choosing k from n without caring about order: written C(n,k) or "n choose k". Python: math.comb(n, k).

Proof styles you'll be asked to gesture at#

You never write a formal proof in an interview. You do need to argue convincingly.

Proof by contradiction — assume the opposite, derive nonsense, conclude the opposite is impossible. Used in: "this pointer can't be part of any solution, so discarding it is safe."

The exchange argument (for greedy) — suppose an optimal answer differs from your greedy choice; show you can swap your choice in without making it worse; conclude some optimal answer contains your choice. Two sentences of this is a strong senior signal.

Induction — prove it for the smallest case, then prove that "if it works for k it works for k+1". This is the formal skeleton behind recursion: your base case plus your recursive step is an induction proof.

Invariant — a statement that stays true throughout a loop. "Everything left of write is already sorted." "The window always contains at most k distinct characters." Naming your invariant out loud is how you convince an interviewer your loop is correct, and how you debug it when it isn't.

19.2 CS vocabulary, decoded#

Words this curriculum uses as if you know them.

19.3 The engineering vocabulary#

Needed for files 09, 13, 14, 15, 16.

19.4 The interview lexicon#

Words recruiters and engineers use that nobody explains to you.

19.5 Terminal and Git survival#

You need maybe fifteen commands, ever.

Terminal#

pwd                     # where am I?
ls                      # what's here?          (PowerShell: dir also works)
cd foldername           # go into a folder
cd ..                   # go up one level
mkdir newfolder         # make a folder
cat file.txt            # print a file
python file.py          # run a Python file

Everything is relative to where you are standing. That's the single concept. pwd when confused.

Ctrl+C stops a running program. Up-arrow recalls your last command. Tab auto-completes file names — use it, it prevents typos.

Git — what it is#

Git records snapshots of your project over time, so you can see what changed, undo mistakes, and work on several things at once. GitHub is a website that hosts those snapshots online.

The eight commands you'll use#

git init                          # start tracking this folder
git status                        # what's changed? — run this constantly
git add .                         # stage everything
git commit -m "message"           # save a snapshot
git log --oneline                 # history
git diff                          # what changed since the last commit
git push                          # send to GitHub
git pull                          # fetch from GitHub

Your daily rhythm for this curriculum is two lines:

git add .
git commit -m "Day 3: sliding window - min window substring"

A public repo with 200 daily commits demonstrates consistency, which is the hardest thing to fake on a resume.

19.6 Notation used in this curriculum#

19.7 How to use this file#

Do not read it cover to cover. It's a dictionary.

• Before 01-foundations: read §19.1 (maths) and §19.2 (CS vocabulary). About 20 minutes.
• Before 09/13/14: read §19.3.
• Now, once: skim §19.4 so recruiter emails make sense.
• Whenever a word stops you: search this file first.

If a term stops you and it isn't here, that's a gap worth fixing — note it in tracker.md so it can be added.

→ Back to README · Next: 00 — Python From Zero