Learn: 157 topics
Data structures
How data sits in memory, and what each layout makes cheap.
Dynamic arrays
A dynamic array keeps its items in one contiguous block and doubles that block when it fills, so a push costs O(1) on average.
Hash tables
A hash table turns a key into a bucket index, so lookups cost O(1) on average as long as keys spread out and the table resizes before it fills.
Linked lists
A linked list chains nodes with pointers, so splicing is O(1) once you hold a node but finding one is O(n).
Stacks and queues
A stack hands back the newest item and a queue the oldest; a ring buffer gives a fixed-size queue with two indices that wrap.
Heaps
A binary heap is a complete tree stored in an array where every parent beats its children, so the best item is always at index 0.
Binary search trees
A binary search tree keeps smaller keys left and larger keys right, so search is O(height), which balancing keeps at O(log n).
B and B+ trees
A B+ tree packs hundreds of keys into each disk page, so a billion rows sit three or four page reads from the root.
Tries
A trie stores strings one character per edge, so every word sharing a prefix shares a path.
Graphs
A graph is nodes plus edges, stored either as a list of neighbors per node or as an n×n matrix.
Union-find
Union-find tracks which items are connected by pointing each item at a parent, with the root naming the set.
Segment and Fenwick trees
A segment tree stores a summary per range so any range query or point update touches O(log n) nodes.
Skip lists
A skip list is a sorted linked list with express lanes chosen by coin flips, giving O(log n) search on average.
Bloom filters
A Bloom filter answers “definitely not here” or “probably here” using a bit array and k hash functions.
LSM trees
An LSM tree buffers writes in memory and flushes them as sorted immutable files that are merged in the background.
Algorithms and patterns
The handful of patterns behind most interview problems.
Binary search
Binary search keeps an invariant on a sorted range and halves it each step, finding the boundary in O(log n).
Two pointers and sliding window
A sliding window grows on the right and shrinks on the left, so each index enters and leaves once: O(n).
Prefix sums
A prefix sum stores running totals so any range sum is one subtraction.
Sorting
Comparison sorts can’t beat O(n log n) in the worst case; the practical winners exploit runs, caches and stability.
Recursion and backtracking
Backtracking builds a solution choice by choice and undoes a choice as soon as it can’t lead anywhere.
Breadth-first search
BFS explores in rings of equal distance, so the first time it reaches a node is along a shortest unweighted path.
Depth-first search
DFS follows one path as deep as it can before backing up, which exposes cycles and gives a topological order.
Shortest paths
Dijkstra settles nodes in order of distance with a priority queue; it breaks when an edge is negative.
Minimum spanning trees
A minimum spanning tree connects every node at least total cost; the cheapest edge across any cut is always safe to take.
Dynamic programming
Dynamic programming solves each overlapping subproblem once and stores the answer in a table.
Greedy
A greedy algorithm takes the locally best choice and never revisits it, which is correct only when an exchange argument says so.
Intervals
Sort interval endpoints and sweep a line across them, tracking how many are active.
Strings
String matching avoids re-reading text: KMP reuses what already matched, Rabin–Karp compares rolling hashes.
Bit manipulation
Integers are rows of bits, and AND, OR, XOR and shifts act on all of them at once.
Randomized algorithms
Randomness buys simple algorithms with good expected cost, like reservoir sampling and quickselect.
Complexity and math
The math every other section leans on.
Big-O and the master theorem
Big-O describes how cost grows with input size, ignoring constants.
Space complexity
Space complexity counts memory, including the call stack that recursion uses.
P vs NP
NP problems have answers you can check fast; nobody knows how to find them fast in general.
Probability
Most systems intuitions are probability: collisions, tails, false positives.
Floating point
A float is sign × mantissa × 2^exponent, so most decimals, like 0.1, are stored approximately.
Overflow and two’s complement
Fixed-width integers live on a wheel: past the maximum they wrap to the minimum.
Languages and runtimes
What C++ and Python actually do with your objects.
C++ memory and objects
In C++ you choose where objects live, stack or heap, and their destructors run at a precise moment.
Python internals
CPython frees objects by reference counting, with a cycle collector and a global interpreter lock on top.
Garbage collection
A tracing collector marks everything reachable from the roots and frees the rest.
Compilers
A compiler turns text into tokens, a syntax tree, an intermediate form and finally machine code.
Operating systems
Processes, memory and the machine under them.
Processes vs threads
A process owns an address space; threads are schedules that share one.
Scheduling
A scheduler decides which ready task runs next, trading throughput, latency and fairness.
Virtual memory
Every address a program uses is virtual; the MMU walks page tables to find the physical frame.
Memory hierarchy
Each level of memory is about ten times bigger and slower than the one above it.
Syscalls
A syscall is a controlled jump from user code into the kernel.
File systems
A write lands in the page cache first; only fsync forces it to disk.
I/O models
Blocking I/O parks a thread per connection; epoll lets one thread wait on thousands.
Running a program
fork copies a process, exec replaces its image, and the loader and linker map in code and libraries.
Concurrency
Two threads, one variable, and everything that goes wrong.
Races
A race happens when the outcome depends on how two threads’ steps interleave.
Locks, semaphores, condition variables
A lock admits one thread, a semaphore admits n, and a condition variable lets a thread sleep until a predicate may be true.
Deadlock
Deadlock is a cycle of threads each holding a lock the next one needs.
Atomics and CAS
Compare-and-swap writes a new value only if the old one is unchanged, the base of lock-free code.
Memory models
CPUs and compilers reorder memory operations; a memory model says which reorderings other threads may see.
Producer–consumer
A bounded queue lets fast producers and slow consumers meet without unbounded memory.
Async vs threads vs processes
Async suits I/O-bound waiting, threads share memory, processes isolate and use every core.
Actor model
Actors share nothing and talk only by messages to each other’s mailboxes.
Networking
From a URL to pixels, one layer at a time.
What happens when you type a URL
A URL becomes a DNS lookup, a TCP connection, a TLS handshake, an HTTP request and finally a rendered page.
TCP
TCP gives an ordered, reliable byte stream by numbering bytes, acknowledging them and resending what’s lost.
UDP
UDP sends independent datagrams with no ordering, retries or connection.
HTTP/1.1 vs 2 vs 3
HTTP/2 multiplexes streams over one TCP connection; HTTP/3 moves to QUIC to escape TCP’s head-of-line blocking.
TLS
TLS agrees on keys with a Diffie–Hellman exchange and proves the server’s identity with a certificate chain.
DNS
DNS resolves a name by walking from the root to the TLD to the authoritative server, caching each answer for its TTL.
Load balancers
A load balancer spreads requests across servers by round robin, least connections or hashing.
Proxies and CDNs
A CDN caches content at edges near users so most requests never reach the origin.
API styles
REST, gRPC and GraphQL trade simplicity, speed and query flexibility.
NAT and subnets
A subnet mask splits an address into network and host bits; NAT maps many private addresses onto one public one.
Databases
Indexes, transactions and what the storage engine is doing.
Normalization
Normalization stores each fact once so updates can’t leave copies disagreeing.
Indexes
An index is a B+ tree from column values to rows, trading slower writes for fast lookups.
EXPLAIN and joins
A query plan is a tree of operators; joins run as nested loops, hash joins or merge joins.
ACID
ACID promises transactions are all-or-nothing, valid, isolated and durable.
Isolation levels
Weaker isolation levels allow specific anomalies in exchange for less blocking.
2PL vs MVCC
Two-phase locking makes readers and writers wait; MVCC lets readers see an old version instead.
WAL and recovery
A write-ahead log records each change before it touches the data, so a crash can be replayed.
Storage engines
B-trees update pages in place; LSM trees append and merge. Row stores suit transactions; column stores suit scans.
NoSQL families
Key-value, document, wide-column and graph stores each give up joins or schemas for a particular access pattern.
Time-series databases
Time-series stores append points in time order and downsample old data into coarser tiers.
Pooling and N+1
An N+1 query fetches a list and then one row per item; a pool reuses connections instead of opening one per request.
Distributed systems
One cluster sandbox: cut links, skew clocks, kill nodes.
Partial failure
In a distributed system some parts fail while others run, and a slow node looks the same as a dead one.
CAP and PACELC
During a partition you choose consistency or availability; otherwise you choose latency or consistency.
Consistency models
A consistency model says which orders of operations clients are allowed to observe.
Replication and quorums
Replicas copy each write; a read is guaranteed fresh only when its quorum overlaps the write’s.
Partitioning
Consistent hashing places keys and nodes on a ring, so adding a node moves only about 1/n of the keys.
Raft
Raft elects one leader per term and commits a log entry once a majority stores it.
Time and ordering
Lamport clocks give an order consistent with causality; vector clocks also detect concurrency.
Distributed transactions
Two-phase commit makes all participants agree, but blocks if the coordinator dies; sagas undo with compensations instead.
Delivery guarantees and idempotency
Networks give at-most-once or at-least-once delivery; idempotency keys turn retries into effectively-once.
Failure detection and leases
A lease grants a lock that expires, and a fencing token stops an expired holder from writing.
Gossip and CRDTs
Gossip spreads state like an infection; CRDTs are data types whose replicas always merge to the same result.
Event sourcing and CQRS
Event sourcing stores every change as an event and rebuilds state by replaying them.
System design building blocks
The parts every design interview reuses.
Capacity estimation
Back-of-envelope math turns users and actions into requests per second, storage and bandwidth.
Scaling and storage types
Scale up with a bigger machine or out with more machines, and pick block, file or object storage by access pattern.
Caching
A cache keeps hot data close; the hard parts are eviction and invalidation.
Kafka vs queues
Kafka is an append-only log that consumers read at their own offsets; a queue deletes a message once handled.
Backpressure
Backpressure slows producers when consumers fall behind instead of letting queues grow forever.
Rate limiting
A token bucket refills at a steady rate and spends a token per request, allowing short bursts up to its size.
Stream processing
Stream processors group events by when they happened, using watermarks to decide when a window is complete.
Search
An inverted index maps each term to the documents that contain it.
IDs
A Snowflake ID packs a timestamp, a machine number and a sequence into 64 bits so IDs sort by time without coordination.
Pagination
Offset pagination skips or repeats rows when data changes; a cursor continues after the last item seen.
Multi-region
Multi-region systems run active-passive for simplicity or active-active for latency, paying in conflict resolution.
Classic design problems
Wire blocks, load test, inject failure. Then a 45-minute mock.
URL shortener
A URL shortener maps a short ID to a long URL; the interesting part is generating IDs.
Rate limiter
A distributed rate limiter shares token buckets across servers.
Key-value store
A distributed KV store partitions keys on a ring and replicates each with quorums.
News feed
A feed is fan-out on write for most users and fan-out on read for celebrities.
Chat
Chat holds a WebSocket per client and orders messages per conversation.
Notifications
A notification system is a queue plus retries plus dedup.
Web crawler
A crawler is a frontier queue with politeness rules per host.
Typeahead
Typeahead serves top completions per prefix from a trie fronted by a cache.
Job scheduler
A job scheduler uses leases so each job runs effectively once.
Metrics system
A metrics system ingests time series and downsamples them for long retention.
Ride sharing
Ride matching indexes drivers by geohash or quadtree to find the nearest quickly.
Payments
Payments use a double-entry ledger and reconcile against the processor.
Video streaming
Adaptive bitrate switches quality chunk by chunk to match bandwidth.
Fleet telemetry and command
Devices stream telemetry up and take commands down, and must fail safe when the control plane disappears.
Reliability and observability
Budgets, tails, retries and how systems recover.
SLOs
An SLO sets a reliability target, and the error budget is what’s left to spend.
Golden signals
Latency, traffic, errors and saturation tell you most of what’s wrong.
Retries
Retries help with transient failures and cause storms without backoff and jitter.
Circuit breakers
A circuit breaker stops calling a failing dependency and probes it before trusting it again.
Health checks
Liveness asks “restart me?”, readiness asks “send me traffic?”.
Deployments
A canary ships a build to a slice of traffic and rolls back if its metrics go bad.
Incidents and chaos engineering
Incidents are handled by roles and learned from with blameless postmortems; chaos engineering rehearses them.
Security
Passwords, tokens and the usual holes.
Passwords
Store passwords with a slow, salted hash so stolen hashes are expensive to crack.
OAuth and OIDC
OAuth delegates access with tokens; OIDC adds an ID token that says who the user is.
OWASP
Most web vulnerabilities come from treating input as code.
Encryption, least privilege, zero trust
Encrypt in transit and at rest, grant only what’s needed, and authenticate every request.
Cloud and infrastructure
Containers, clusters and the plan before apply.
Docker
A container is a process fenced by namespaces and cgroups, started from a stack of image layers.
Kubernetes
Kubernetes compares desired state with actual state and acts until they match.
Terraform
Terraform diffs your config against recorded state and plans the changes.
CI/CD
CI tests every change; CD ships the ones that pass.
Serverless
Serverless runs code per request on demand and pays a cold start when idle.
AWS networking and IAM
A VPC isolates your network into subnets; IAM decides who may call what.
ML systems
From loss curves to serving and drift.
Bias–variance
A model too simple underfits and one too flexible overfits; validation error finds the middle.
Data leakage
Leakage lets information from the answer into the features, so test accuracy lies.
Optimizers
Optimizers follow the gradient downhill; momentum and Adam smooth and scale the steps.
Backprop
Backprop applies the chain rule from the loss backward through the graph.
Transformers
Attention lets each token mix in information from every other token, weighted by learned similarity.
Evaluation
A classifier’s threshold trades precision for recall along the ROC curve.
Embeddings and vector search
Embeddings place similar items near each other; HNSW finds neighbors through a layered graph.
RAG
Retrieval-augmented generation fetches relevant documents and puts them in the prompt.
Model serving
Batching requests raises GPU throughput at the cost of latency; quantization shrinks memory.
Distributed training
Data parallelism splits batches, tensor parallelism splits layers, pipeline parallelism splits the stack.
MLOps
Models decay as the world drifts away from their training data.
Embedded, robotics and real-time
Control loops, sensors and deadlines.
Real-time
A real-time system is correct only if it finishes before its deadline.
PID control
A PID controller pushes against the current error, its accumulated history and its rate of change.
Kalman filter
A Kalman filter blends a prediction with a noisy measurement, weighted by their uncertainties.
Frames and rotations
Euler angles can lose a degree of freedom (gimbal lock); quaternions don’t.
Sensor noise
Integrating a noisy sensor accumulates its errors into drift.
Embedded protocols
UART, SPI, I2C and CAN trade wires, speed and multi-device support.
SITL vs HITL
Software-in-the-loop runs the code on a simulator; hardware-in-the-loop runs it on the real board.
Fail-safes
A watchdog resets the system if the software stops checking in.
Applied math
Linear algebra, optimization, statistics, numerics.
Linear algebra
A matrix is a transformation; its eigenvectors are the directions it only stretches.
Optimization
In a convex problem any local minimum is global.
Statistics
A 95% confidence interval procedure covers the true value in 95% of repeated experiments.
Numerical methods
Numerical methods differ in how errors grow: Euler drifts, RK4 holds.
Software engineering practice
Tests, git, design and debugging.