Computer Science Roadmap

Pick a Language Core

Computer science ideas are language independent, but you learn them by writing code. Pick one language and stay with it. Python is the gentlest start and the most common interview language. C shows you memory, pointers and how data really sits in RAM. C++ adds classes and a rich standard library and is the choice for performance work. Java and C# are strongly typed, object oriented and widely used in industry. Go is simple and built for networked services. Rust gives C-level speed with memory safety checked by the compiler.

A good path is Python for algorithms plus enough C to understand pointers and manual memory.

Practice. Write the same small program, reading numbers from a file and printing their average, in Python and in C.

Basic Math Skills Core

You need less maths than people fear, but some is unavoidable. Logarithms explain why halving a problem is fast: log₂ of a million is about 20. Sums such as 1 + 2 + … + n = n(n + 1)/2 explain why nested loops are quadratic. Modular arithmetic appears in hashing and cryptography.

Combinatorics counts arrangements: there are n factorial orderings of n items and 2ⁿ subsets, which is why brute force over them explodes. Probability lets you reason about hash collisions, randomised algorithms and expected running time.

Practice. Calculate how many 8-character passwords exist using 62 symbols, and how many subsets a 30-item set has.

How Computers Work? Instructions and Programs Core

A computer is a processor, memory and input/output devices joined by buses. Everything is binary: a bit is 0 or 1, and eight bits make a byte. A program is a list of machine instructions, each a small operation such as "load this address into a register", "add two registers" or "jump if zero".

Compilers translate source code such as C into machine instructions ahead of time. Interpreters run source or bytecode step by step, and many runtimes (the JVM, V8) compile hot code to machine instructions while running (just-in-time compilation).

Practice. Compile a tiny C function with gcc -S and read the assembly it produces.

How Computers Calculate? Integers and Bitwise Operators Core

Integers are stored in binary using a fixed number of bits. Unsigned 8-bit values run from 0 to 255. Signed integers use two's complement, where the top bit carries a negative weight, so 8 bits hold −128 to 127. Exceeding the range overflows and wraps around, a classic source of bugs.

Bitwise Operators work on individual bits: AND, OR, XOR, NOT and shifts. Shifting left by one doubles a number; x & 1 tests for odd; masks pack several flags into one integer.

READ, WRITE, EXEC = 1, 2, 4
perms = READ | WRITE          # 0b011
can_exec = bool(perms & EXEC) # False

Practice. Convert 45 and −45 to 8-bit two's complement by hand, then check with code.

Floating Point Numbers Core

Real numbers are stored in IEEE 754 format: a sign bit, an exponent and a fraction, like scientific notation in base two. A 64-bit double gives about 15 to 17 significant decimal digits. Many decimal values, such as 0.1, have no exact binary form, so 0.1 + 0.2 == 0.3 is false in most languages.

Practical rules: compare floats with a tolerance, never use floats for money (use integer cents or a decimal type), and expect rounding error to grow when you add many small values to a large one.

Practice. Sum 0.1 ten million times in a loop and compare the result with 1,000,000.

Character Encodings: ASCII and Unicode Core

Text is stored as numbers. ASCII maps 128 characters (English letters, digits, punctuation, control codes) to 7-bit values. Unicode assigns a code point to every character in every writing system, plus emoji and symbols, well beyond a million possible values.

An encoding turns code points into bytes. UTF-8 uses one byte for ASCII and up to four for other characters, so it is compact for English and backwards compatible; it is the default on the web. UTF-16 uses two or four bytes and is used inside Java, JavaScript and Windows. Bugs arise when bytes are decoded with the wrong encoding, or when string length counts bytes or UTF-16 units instead of visible characters.

Practice. Print the UTF-8 bytes of "café" and "日本" and explain why their byte lengths differ from their character counts.

Endianness: Big Endian and Little Endian Recommended

Endianness is the order in which a multi-byte number is laid out in memory. With Big Endian, the high-order byte sits at the lowest address, so 0x12345678 is laid out as 12 34 56 78. With Little Endian the low-order byte comes first in memory: 78 56 34 12. Most modern processors, including x86 and usual ARM configurations, are little endian.

It matters when bytes cross a boundary: network protocols use big endian ("network byte order"), and binary file formats specify their own order. Functions such as htonl in C or struct.pack('>I', n) in Python convert explicitly.

Practice. Pack the integer 1 as 4 bytes in both orders with Python's struct module and print the bytes.

Array and Linked Lists Core

An Array keeps elements side by side in memory, so the address of element i is computed directly and access is O(1). Inserting in the middle shifts the elements after it, costing O(n). Dynamic arrays grow by copying into a larger block, keeping appends fast on average.

Linked Lists store each element in a separate node with a reference to the next (and in a doubly linked list, the previous) node. Inserting next to a node you already have is O(1), but finding the k-th element means walking the chain.

Practice. Implement a singly linked list with insert at head, delete by value and reverse.

Stack and Queue Core

A Stack is last in, first out: you push and pop at one end. Function calls use a call stack, undo features use a stack, and depth-first search can use one. A Queue is first in, first out: add at the back, remove from the front. Print jobs, breadth-first search and message passing between programs use queues.

Both can be built on an array or a linked list with O(1) operations.

Practice. Implement a queue as a circular buffer with a fixed capacity and a "full" check.

Hash Table Core

A Hash Table stores key-value pairs in an array of buckets. A hash function converts each key to a number, and the number modulo the array size picks the bucket. Lookup, insert and delete are O(1) on average. When two keys land in the same bucket (a collision), chaining keeps a small list per bucket, while open addressing probes for another slot.

Keep the table no more than about three-quarters full by resizing and rehashing. A good hash function spreads keys evenly; a weak one, or an attacker choosing keys, can force O(n) operations.

Practice. Write a hash table with chaining and resizing, then count collisions for two different hash functions.

Tree and Binary Tree Core

A Tree is a hierarchy of nodes with one root and no cycles; each node has children and every node except the root has one parent. File systems, HTML documents and organisation charts are trees. In a Binary Tree each node has at most two children. Shapes worth naming:

• Full Binary Tree: every node has zero or two children.
• Complete Binary Tree: every level is filled except possibly the last, which fills from the left. Heaps use this shape.
• Balanced Tree: left and right subtree heights stay close, so height is O(log n).
• Unbalanced Tree: one side grows much deeper; in the worst case it is a linked list.
• N-ary (K-ary, M-ary) Trees: each node may have up to k children, as in B-trees and tries.

Practice. Draw one example of each tree shape with seven nodes.

Binary Search Tree Core

In a Binary Search Tree, every key in a node's left subtree is smaller and every key on the right is larger. Search starts at the root and goes left or right at each step, so it takes time proportional to the height. A balanced tree keeps that at O(log n); inserting sorted keys into a plain BST produces a chain with O(n) operations.

An in-order walk visits keys in sorted order, which makes BSTs useful for ordered maps, range queries and finding the next larger key.

Practice. Implement insert, search and delete for a BST and print its keys with an in-order walk.

Heap Core

A Heap is a complete binary tree where each parent is no larger than its children (min-heap) or no smaller (max-heap). It is stored compactly in an array: the children of index i are at 2i + 1 and 2i + 2. The smallest item is always at index 0.

Insert places the new item at the end and swaps it upwards; removing the top moves the last item to the root and swaps it downwards. Both are O(log n). Heaps implement priority queues, which drive task schedulers, Dijkstra's algorithm, event simulations and "top k" queries.

Practice. Implement a min-heap with push and pop, and use it to merge three sorted lists.

Graph Core

A Graph is a set of vertices connected by edges. In a Directed Graph each edge has a direction, like a link from one web page to another; in an Undirected Graph edges work both ways, like a road. Edges can carry weights such as distance or cost.

An Adjacency Matrix is a V × V grid where cell (i, j) records an edge; it checks an edge in O(1) but uses O(V²) memory. An Adjacency List keeps, for each vertex, a list of its neighbours; it uses O(V + E) memory and suits the sparse graphs common in practice. A Spanning Tree is a subset of edges that connects all vertices with no cycles; the minimum spanning tree has the smallest total weight.

Practice. Store the same small road network as an adjacency matrix and as an adjacency list and compare memory.

Tries and Skip Lists Recommended

Tries (prefix trees) store strings one character per level. Each path from the root spells a prefix, so prefix lookups and autocomplete take time proportional to the word length, not the number of words. They power autocomplete, spell checking and IP routing tables.

Skip Lists are sorted linked lists with extra layers of "express" links, where each node is promoted to a higher layer by a coin flip. Search drops down layers as it approaches the target, giving O(log n) expected time with simpler code than balanced trees. Redis uses skip lists for its sorted sets.

Practice. Build a trie from a word list and return all words that start with a given prefix.

Asymptotic Notation Core

Asymptotic notation describes how cost grows as input size n becomes large, ignoring constants and machine speed. Five symbols:

• Big O Notation: an upper bound; the cost grows at most this fast.
• Big Omega Notation: a lower bound; the cost grows at least this fast.
• Big Theta Notation: both at once, a tight bound.
• Small O Notation: a strict upper bound; f grows strictly slower than g, as n is o(n²).
• Small Omega: a strict lower bound; f grows strictly faster.

In everyday engineering talk, "Big O" usually means the tight worst case. Analyse best, average and worst cases separately when they differ, as with quick sort.

Practice. For linear search, give the best, average and worst case in Big O and Big Theta.

Common Growth Rates Core

Learn to recognise these classes from code:

• Constant, O(1): array indexing, pushing on a stack.
• Logarithmic, O(log n): binary search, balanced tree lookup.
• Linear, O(n): one loop over the input.
• Linearithmic, O(n log n): efficient sorting.
• Polynomial, O(nᵏ): k nested loops, such as O(n²) pair comparisons.
• Exponential, O(2ⁿ): trying every subset.
• Factorial, O(n!): trying every ordering.

For n = 50, n² is 2,500 steps while 2ⁿ is over a quadrillion. The class matters far more than constant factors.

Practice. Write one short function in each class and time them for n = 10, 20 and 30.

Tail Recursion and Non-Tail Recursion Core

A recursive function calls itself on a smaller input until it reaches a base case. Each call adds a frame to the call stack, so recursion depth costs memory and deep recursion can overflow the stack.

In Tail Recursion the recursive call is the very last action, with nothing left to do afterwards. Some languages and compilers (Scheme, many C compilers with optimisation, Scala with an annotation) reuse the frame, turning it into a loop. In Non-Tail Recursion work remains after the call returns, such as multiplying by n in a plain factorial, so every frame must be kept. Python and Java do not eliminate tail calls, so convert deep recursion to a loop there.

def fact(n):            # non-tail: multiply after the call
    return 1 if n == 0 else n * fact(n - 1)
def fact_acc(n, acc=1): # tail form: the call is the last step
    return acc if n == 0 else fact_acc(n - 1, acc * n)

Practice. Rewrite a recursive sum of a list in tail form, then as a loop, and test both on a list of 100,000 items.

Sorting Algorithms Core

The classic sorts and what each teaches:

• Bubble Sort: repeatedly swap adjacent out-of-order items. O(n²); teaching only.
• Selection Sort: repeatedly pick the minimum of the unsorted part. O(n²), few writes.
• Insertion Sort: grow a sorted prefix by sliding each item into place. O(n²), but fast on small or nearly sorted data.
• Merge Sort: split, sort halves, merge. O(n log n) always, stable, needs O(n) extra memory.
• Quick Sort: partition around a pivot and recurse. O(n log n) on average, in place, O(n²) worst case without a good pivot.
• Heap Sort: build a heap and pop the maximum repeatedly. O(n log n) worst case, in place, not stable.

Library sorts are hybrids such as Timsort and introsort.

Practice. Implement merge sort and quick sort and compare them on sorted, reversed and random arrays.

Searching: Linear, Binary and Brute Force Search Core

Linear Search checks each item until it finds the target: O(n), works on unsorted data. Binary Search works on sorted data: compare with the middle and discard half each time, O(log n). It also applies to any monotonic yes/no question, such as the smallest capacity that ships all parcels in time.

Brute Force Search tries every candidate solution and keeps the ones that work. It is often the only exact method for hard problems, and always a useful baseline: write it first, then use it to test faster versions on small inputs.

def bsearch(a, x):
    lo, hi = 0, len(a) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if a[mid] == x: return mid
        if a[mid] < x: lo = mid + 1
        else: hi = mid - 1
    return -1

Practice. Use binary search to find the integer square root of a large number without floating point.

Tree and Graph Traversal Core

Depth-first traversals of a binary tree differ in when they visit the node. Pre-Order Traversal visits node, then left, then right (good for copying a tree). In-Order Traversal visits left, node, right (sorted order in a BST). Post-Order Traversal visits left, right, node (good for freeing memory or computing sizes).

For general graphs, Depth First Search follows one path as far as possible, then backtracks; it uses a stack or recursion and finds cycles, components and topological orders. Breadth First Search explores neighbours in layers using a queue and finds the shortest path in unweighted graphs. Both are O(V + E) with a visited set.

Practice. Write BFS and DFS for a graph stored as an adjacency list and print the order each visits.

Shortest Paths and Spanning Trees Core

• Dijkstra's Algorithm: shortest paths from one source with non-negative weights, using a priority queue; O((V + E) log V).
• Bellman Ford's Algorithm: relaxes all edges V − 1 times; slower, O(V·E), but handles negative weights and detects negative cycles.
• A* Algorithm: Dijkstra plus a heuristic estimate of remaining distance; used in games and maps to explore far fewer nodes.
• Prim's Algorithm: grows a minimum spanning tree from one vertex by always adding the cheapest edge leaving it.
• Kruskal's algorithm: sorts all edges and adds each one that does not form a cycle, checked with union-find.
• Ford Fulkerson Algorithm: computes maximum flow by repeatedly finding paths with spare capacity; used in matching and network capacity problems.

Practice. Run Dijkstra and Bellman-Ford on the same graph, then add a negative edge and compare results.

Greedy Algorithms and Huffman Coding Recommended

A greedy algorithm makes the locally best choice at each step and never undoes it. It is fast and simple but correct only for problems with the right structure, which you prove with an exchange argument. Dijkstra, Prim and Kruskal are greedy.

Huffman Coding is a greedy compression method. Count how often each symbol appears, then repeatedly merge the two least frequent symbols into a tree node. Frequent symbols end up near the root with short bit codes, and rare ones get long codes. No code is a prefix of another, so decoding is unambiguous. Variants are used inside formats such as ZIP and JPEG.

Practice. Build the Huffman tree for "abracadabra" by hand and compute the total encoded length.

Backtracking: N Queens, Mazes and the Knight's Tour Recommended

Backtracking builds a solution step by step and abandons a partial solution as soon as it cannot lead to a valid answer. It is brute force with early pruning.

Solving n Queen Problem places one queen per row and tracks used columns and diagonals, backing up when a row has no safe square. The Maze Solving Problem explores paths with DFS, marking cells and unmarking them on the way back if they lead nowhere. The Knight's Tour Problem visits every square of a chessboard once with knight moves; Warnsdorff's rule (move to the square with the fewest onward options first) makes it fast in practice.

Practice. Solve 8 queens with backtracking and count how many complete solutions exist.

Dynamic Programming and the Knapsack Problem Core

Dynamic programming solves problems whose subproblems overlap by computing each subproblem once and storing it. Either cache a recursive function (memoisation) or fill a table from small cases up (tabulation).

The 0/1 Knapsack Problem chooses items with weights and values to maximise value without exceeding a capacity. best[i][w] is the best value using the first i items with capacity w: either skip item i, or take it if it fits. That is O(n · W) time, which is fast when the capacity W is small. Note this is "pseudo-polynomial": the general problem is NP-hard, covered later.

Practice. Solve 0/1 knapsack with a table, then reduce the table to one row.

String Search and Manipulations Recommended

Substring Search, or search pattern in text, finds where a pattern occurs. The naive method tries every start position, O(n·m). Faster algorithms:

• Knuth Morris Pratt: builds a failure table from the pattern itself, recording how far the match can fall back after a mismatch, so the text pointer never moves backwards. O(n + m).
• Boyer Moore Algorithm: compares from the end of the pattern and uses mismatches to skip ahead, often reading only part of the text; very fast in practice.
• Rabin-Karp's algorithm: compares rolling hashes of each window and checks characters only when hashes match; good for many patterns at once.
• Suffix Arrays: sort all suffixes of a text once, then binary search any pattern.

Practice. Implement Rabin-Karp and KMP and compare them on a long text with a repetitive pattern.

Balanced Search Trees: AVL and Red / Black Trees Recommended

Balanced Search Trees rebalance after inserts and deletes so height stays O(log n). AVL Trees store each node's height and rotate whenever two sibling subtrees differ by more than one level. They are tightly balanced, so lookups are quick, at the cost of more rotations on writes.

Red / Black Trees colour each node red or black and enforce rules (no two reds in a row, the same number of black nodes on every root-to-leaf path) that keep the longest path at most twice the shortest. They rebalance with fewer rotations and back Java's TreeMap, C++ std::map and the Linux scheduler.

Practice. Insert 10, 20, 30, 40, 50 into an AVL tree on paper and draw each rotation.

2-3 and 2-3-4 Search Trees Optional

2-3 Search Trees let each node hold one key with two children or two keys with three children. Inserts that overflow a node split it and push the middle key up, so all leaves always stay at the same depth and the tree is perfectly balanced.

2-3-4 Search Trees allow up to three keys and four children. They matter mainly as the idea behind other structures: a red-black tree is a binary encoding of a 2-3-4 tree, and B-trees generalise the same splitting rule to hundreds of keys per node.

Practice. Insert the letters A to G into a 2-3 tree on paper, showing every split.

B-Trees Recommended

B-Trees are balanced search trees with very wide nodes, each holding many sorted keys and children. Because a node is sized to fit a disk page, a lookup among billions of keys reads only three or four pages. Inserts split full nodes and deletes merge sparse ones, keeping every leaf at the same depth.

The B+ tree variant keeps all records in the leaves and links leaves together for fast range scans. It is the standard index structure in relational databases and many file systems.

Practice. Estimate how many levels a B+ tree with 200 keys per node needs to index one billion rows.

K-D Trees Optional

K-D Trees organise points in k dimensions. Each level splits space on one coordinate, alternating between them: first by x, then by y, then by x again. Nearest neighbour and range queries can skip whole regions whose bounding box is too far away.

They work well in low dimensions, such as maps and graphics. In high dimensions most branches must be checked anyway, so systems for vector search use approximate methods such as graph-based indexes instead.

Practice. Build a 2-D tree for ten points and find the nearest neighbour of a query point by hand.

P, NP and Co-NP Core

Complexity Classes group problems by how hard they are to solve. P contains decision problems solvable in polynomial time, such as sorting or shortest paths. NP contains problems where a proposed solution can be checked in polynomial time, even if finding one may be hard: given a route, you can quickly confirm it visits every city within a budget.

Co-NP contains problems where a "no" answer has a short, checkable proof. Every problem in P is in both NP and Co-NP. Whether P = NP, that is, whether every quickly checkable problem is also quickly solvable, is the most famous open question in computer science. Almost everyone believes P ≠ NP, and modern cryptography depends on some problems being hard.

Practice. For three problems you know, explain how a proposed answer could be verified quickly.

NP Complete and NP-Hard Core

A problem is NP-Hard if every NP problem can be reduced to it in polynomial time, so solving it fast would solve all of NP fast. NP Complete problems are NP-hard and also in NP. SAT, graph colouring, the decision version of travelling salesman and subset sum are NP-complete.

Practical meaning: if your problem is NP-complete, do not expect an exact fast algorithm for large inputs. Use approximation algorithms with proven bounds, heuristics, restrictions (small n, special structure) or solvers such as integer programming. Recognising this early saves weeks of wasted effort.

Practice. Show how the "subset sum" problem can be phrased as a special case of 0/1 knapsack.

Classic Hard Problems Recommended

• Travelling Salesman Problem: find the shortest tour visiting every city once. Exact dynamic programming is O(n² · 2ⁿ); real routing uses heuristics such as nearest neighbour plus 2-opt improvements.
• Finding Hamiltonian Paths: a path that visits every vertex exactly once. Checking a path is easy; finding one is NP-complete. Compare Euler paths (every edge once), which are easy.
• Longest Path Problem: NP-hard on general graphs, unlike shortest path. On a directed acyclic graph it becomes easy with topological order and DP.
• Knapsack: NP-hard in general, but pseudo-polynomial DP works when capacities are small.

These show how a small change to an easy problem can make it intractable.

Practice. Solve longest path on a small DAG with topological order, then explain why the same method fails with cycles.

How CPU Executes Programs? Core

The CPU runs a loop: fetch the next instruction from memory, decode it, execute it, and write back the result. The program counter tracks the next instruction. Modern CPUs pipeline these stages so several instructions are in flight, execute instructions out of order when inputs are ready, and predict branches to avoid stalls. A mispredicted branch throws away work, which is why sorted data can make an if-heavy loop much faster.

Clock speed alone does not decide performance; instructions per cycle, cache hits and parallelism matter as much.

Practice. Time a loop that sums values above a threshold on sorted versus shuffled data and explain the difference.

Registers and RAMs Core

Registers are a handful of tiny storage slots inside the CPU, read in a single cycle; all arithmetic happens on them. RAM (main memory) is much larger but roughly a hundred times slower to reach. Data moves between them through load and store instructions.

RAM is volatile and byte-addressable: each byte has an address, which is what a pointer holds. Disk and SSD storage are far slower still, but persistent. Knowing these speed gaps explains why the next topics, caches and memory management, exist.

Practice. List the memory hierarchy from registers to network storage with a rough access time for each.

CPU Cache Core

CPU caches (L1, L2, L3) hold recently used memory close to the core. Data moves in cache lines, typically 64 bytes. Programs that access memory sequentially or reuse the same data benefit from spatial and temporal locality; programs that jump randomly through memory miss the cache and wait on RAM.

This is why arrays often beat linked lists, why looping over a 2-D array row by row is faster than column by column in row-major languages, and why "false sharing", two threads writing to different variables on the same cache line, can slow parallel code.

Practice. Sum a large 2-D array row by row and then column by column and compare the timings.

CPU Interrupts Recommended

An interrupt is a signal that makes the CPU pause its current work and run a handler. Hardware interrupts come from devices: a key press, a network packet, a timer tick. Software interrupts and system calls let a program ask the kernel for services such as reading a file.

The timer interrupt is what allows the operating system to take the CPU back from a running program and schedule another one.

Practice. Run cat /proc/interrupts on Linux and identify the timer, disk and network lines.

Processes and Threads Core

A process is a running program with its own address space, open files and at least one thread. Processes are isolated: one crashing does not corrupt another. A thread is a unit of execution inside a process; threads share the process's memory, which makes communication cheap but makes data races possible.

Process Forking on Unix creates a child process with fork(), a copy of the parent that shares memory pages copy-on-write until either writes. The child often calls exec() to run a different program, which is how shells launch commands. Context switching between threads or processes costs time, so very many threads can hurt throughput.

Practice. Write a C or Python program that forks a child, has each print its process ID, and waits for the child.

Concurrency in Multiple Cores Core

Concurrency means several tasks make progress over the same period; parallelism means they run at the same instant on different cores. Multi-core CPUs make parallelism possible, but only if work can be split. Amdahl's law says the part that must run sequentially caps the total speed-up.

Race conditions occur when threads read and write shared data without coordination, and results depend on timing. Deadlock happens when threads wait on each other's locks forever. Avoid both by sharing less: immutable data, message passing, or giving each thread its own data and combining results at the end. Python's global interpreter lock limits CPU parallelism in threads, so CPU-bound Python uses processes.

Practice. Increment a shared counter from four threads without a lock, observe the wrong total, then fix it.

Lock / Mutex / Semaphore Core

Locking protects shared data so only one thread changes it at a time. A mutex (mutual exclusion lock) has one owner: a thread acquires it, works in the critical section and releases it. A semaphore holds a count and allows up to that many threads in at once, useful for limiting access to a pool of connections.

Other tools include read-write locks (many readers or one writer), condition variables (sleep until a condition holds) and atomic operations for simple counters. Keep critical sections short, always acquire multiple locks in the same global order to prevent deadlock, and prefer higher-level structures such as thread-safe queues when they fit.

Practice. Build a bounded producer-consumer buffer using a mutex and two condition variables.

Scheduling Algorithms Recommended

The scheduler decides which ready thread runs next on each core. Classic policies:

• First come, first served: simple, but one long job delays all others.
• Shortest job first: minimises average waiting time but needs to know job lengths.
• Round robin: each thread gets a time slice in turn; fair and responsive.
• Priority scheduling: higher priority first, with ageing so low-priority work is not starved.
• Multilevel feedback queues: adjust priority based on behaviour, favouring interactive tasks.

Linux uses a fair scheduler that tracks how much CPU time each task has received and runs the one that has had least.

Practice. Simulate round robin and shortest job first on five jobs and compare average waiting time.

Memory Management Core

Each process sees its own virtual address space. The operating system and the memory management unit map virtual pages to physical frames using page tables, cached in the TLB. Pages can be swapped to disk; touching one that is not in RAM causes a page fault. This isolation is why one process cannot read another's memory.

Inside a program, the stack holds function frames and local variables and is freed automatically on return. The heap holds data with dynamic lifetime. C and C++ free it manually (risking leaks and use-after-free bugs), Java, Go and Python use garbage collection, and Rust checks ownership at compile time.

Practice. Write a C program with a memory leak and a use-after-free, then find both with Valgrind or AddressSanitizer.

OSI and TCP/IP Models Core

Networking is built in layers, each using the one below. The OSI model has seven layers, from cables and signals at layer 1 up to application protocols at layer 7, with addressing at layer 3 and transport at layer 4. The TCP/IP model used on the internet collapses these into four: link, internet (IP), transport (TCP, UDP) and application (HTTP, DNS, SMTP).

IP moves packets between machines by address, without guarantees. TCP adds reliable, ordered delivery with handshakes, acknowledgements and retransmission. UDP adds only ports and a checksum, trading reliability for low latency. When debugging, ask which layer fails: no route, a refused port or an HTTP error are different problems.

Practice. Capture a web request with Wireshark or tcpdump and label the packets by layer.

DNS Core

DNS is the internet's directory: it maps names such as example.com to IP addresses. A resolver asks a root server, then the top-level domain server for .com, then the domain's authoritative server, and caches the answer for its time-to-live.

Common records: A (IPv4 address), AAAA (IPv6), CNAME (alias to another name), MX (mail server), NS (delegation) and TXT (verification and policy). DNS is also used for load spreading and failover.

Practice. Use dig +trace to follow a lookup from the root to the authoritative server.

HTTP? and REST Core

HTTP is a text-based request-response protocol on top of TCP (or QUIC in HTTP/3). A request has a method, a path, headers and an optional body; a response has a status code, headers and a body. HTTP is stateless, so cookies or tokens carry identity between requests.

REST is an architectural style for HTTP APIs: resources are named by URLs (/orders/42) and manipulated with standard methods, GET to read, POST to create, PUT or PATCH to update and DELETE to remove, with status codes signalling results. It is simple, cacheable and the most common public API style.

Practice. Call a public REST API with curl -v and explain every line of the request and response.

gRPC and GraphQL Recommended

gRPC is a remote procedure call framework from Google. Services are defined in Protocol Buffers files, code is generated for clients and servers, messages are compact binary, and HTTP/2 enables streaming in both directions. It is popular for service-to-service calls where speed and strict contracts matter.

GraphQL exposes one endpoint and a typed schema; clients send queries naming exactly the fields they need, avoiding both over-fetching and multiple round trips. It suits apps with many different screens. Costs include harder HTTP caching and the need to limit expensive queries.

Practice. Define a small service in a .proto file and a GraphQL schema for the same data and compare.

Sockets and Real-Time Communication Recommended

Sockets are the operating system's interface to the network: a program opens a socket, connects or listens on an address and port, then reads and writes bytes. Every higher protocol is built on them.

Web apps that need live updates choose between four techniques. Short Polling asks the server for news on a timer, simple but wasteful. Long Polling keeps the request open until there is news. Server Sent Events stream one-way updates over a long-lived HTTP response, with automatic reconnection. Web Sockets upgrade an HTTP connection to a persistent two-way channel, ideal for chat and games.

Practice. Write a tiny TCP echo server with sockets, then a WebSocket version that broadcasts to all clients.

Hashing/Encryption/Encoding Core

Three different ideas that are often confused:

• Encoding changes representation for compatibility, such as Base64 or UTF-8. It is reversible by anyone and provides no secrecy.
• Hashing maps data to a fixed-size digest one way. Hashing Algorithms such as SHA-256 detect tampering and identify content. Passwords need slow, salted algorithms built for the job (bcrypt, scrypt, Argon2), never plain fast hashes. MD5 and SHA-1 are broken for security use.
• Encryption makes data unreadable without a key and is reversible with the key. Symmetric encryption such as AES uses one shared key and is fast.

If someone says "we encrypt passwords", ask whether they actually hash them.

Practice. Hash a password with bcrypt, encode a file in Base64 and encrypt a message with AES, noting what each protects.

Public Key Cryptography and TLS / HTTPS Core

Public Key Cryptography uses a key pair: anything encrypted with the public key can only be decrypted with the private key, and a signature made with the private key can be verified by anyone with the public key. RSA and elliptic-curve algorithms are common. Asymmetric operations are slow, so they are used to agree on a symmetric key rather than to encrypt bulk data.

TLS, the security layer of HTTPS, combines both. The server presents a certificate signed by a trusted certificate authority, proving its identity; client and server agree a fresh session key using key exchange; then traffic is encrypted symmetrically. Current deployments use TLS 1.2 or 1.3; older SSL and TLS versions are deprecated.

Practice. Inspect a website's certificate chain in your browser and with openssl s_client.

Security and OWASP Core

Security is part of every engineer's job. OWASP is an open community that publishes, among other guides, a regularly updated top ten list of the most common web application risks. Recurring entries include broken access control, injection (such as SQL injection), cryptographic failures, insecure design, security misconfiguration, vulnerable dependencies and authentication failures.

Core defences: parameterised queries, output escaping, least privilege, server-side authorisation checks on every request, secrets kept out of code, dependency scanning and secure defaults.

Practice. Find and fix a SQL injection in a small app by switching to parameterised queries.

Databases and SQL Command Types Core

Databases store data durably and let many users read and change it safely. Relational databases keep records as rows in tables with typed columns, and you query them with SQL. SQL statements fall into four groups:

• DDL (Data Definition Language): CREATE, ALTER, DROP change structure.
• DML (Data Manipulation Language): INSERT, UPDATE, DELETE change rows.
• DQL (Data Query Language): SELECT reads data.
• DCL (Data Control Language): GRANT and REVOKE manage permissions.

The SQL Roadmap roadmap covers SQL in depth; here the goal is to understand what databases guarantee and how.

Practice. Create a two-table schema, insert rows, query them with a join and grant read access to another user.

Entity Relationship Model and Normalization vs Denormalization Core

The Entity Relationship Model describes data as entities (customer, order), their attributes and their relationships (a customer places many orders). Drawing an ER diagram before writing tables exposes one-to-many and many-to-many links, which become foreign keys and join tables.

Normalisation removes duplication so each fact is stored once, avoiding update anomalies; third normal form is the usual target. Denormalisation deliberately duplicates data, such as storing a running total on an order, to make reads faster at the cost of more complex writes. Normalise first, then denormalise specific hot paths with measurements to justify it.

Practice. Draw an ER diagram for a library and turn it into tables in third normal form.

Database Indexes Core

An index is an extra data structure, usually a B+ tree, that lets the database find rows by a column without scanning the whole table. A query that filters on an indexed column can drop from seconds to milliseconds.

Indexes cost storage and slow down writes, because every insert and update must change them too. Composite indexes follow the leftmost-prefix rule: an index on (country, city) helps queries filtering on country, or on both, but not on city alone. Use EXPLAIN to see whether a query uses an index.

Practice. Load a million rows, time a filtered query, add an index and read the query plan before and after.

Views and Stored Procedures Optional

Views are saved queries that behave like virtual tables. They simplify complex joins, present a stable interface while underlying tables change, and limit what a user can see. Materialised views store the result physically and must be refreshed.

Stored Procedures are programs stored and run inside the database. They can reduce round trips and enforce rules close to the data, but they are harder to version, test and scale than application code, and they tie you to one database vendor.

Practice. Create a view that hides salary columns and a stored procedure that transfers stock between warehouses.

Transactions, ACID and Locking Core

Transactions group several statements so they succeed or fail together. ACID describes the guarantees: atomicity (all or nothing), consistency (constraints hold before and after), isolation (concurrent transactions do not see each other's partial work) and durability (committed data survives a crash).

Isolation is implemented with locking or multi-version concurrency control. Isolation levels trade safety for concurrency: read committed avoids dirty reads, repeatable read avoids changing rows mid-transaction, serializable behaves as if transactions ran one at a time. Row locks with SELECT … FOR UPDATE prevent lost updates.

Practice. Open two database sessions and reproduce a lost update, then prevent it with a row lock.

SQL vs NoSQL databases and the BASE Model Core

Relational (SQL) databases offer schemas, joins and strong transactions. NoSQL databases include key-value stores, document stores, wide-column stores and graph databases, each optimised for particular access patterns and easy horizontal scaling.

Many distributed NoSQL systems follow the BASE Model: basically available, soft state, eventually consistent. They stay responsive during failures and let replicas converge over time instead of guaranteeing every read is current. Choose SQL by default for related, transactional data and NoSQL where the data shape, scale or latency needs justify it.

Practice. Model a blog with comments in both a relational schema and a document store and compare the queries.

Replication, Sharding and Database Federation Recommended

Replication copies data to several servers. A primary takes writes and replicas serve reads and stand by for failover; asynchronous replicas may lag behind. Sharding splits one big table across servers by a key, such as user ID, so each holds a part; it scales writes but makes cross-shard queries hard. Database Federation splits by function instead, putting users, orders and products in separate databases.

Each adds operational complexity, so use them when a single well-indexed server with replicas is no longer enough.

Practice. Sketch how a user table with a billion rows could be sharded and what happens to a query by email.

CAP Theorem and PACELC Theorem Core

The CAP Theorem says that when a network partition splits a distributed database, it must choose between consistency (every read sees the latest write) and availability (every request gets an answer). Partitions cannot be ruled out, so the choice is what to give up while one lasts.

The PACELC Theorem adds the normal case: if there is a Partition, choose Availability or Consistency; Else, choose Latency or Consistency. Waiting for replicas to confirm makes reads consistent but slower. Systems such as Cassandra lean towards availability and low latency; traditional relational clusters lean towards consistency.

Practice. Classify three databases you know by their behaviour under CAP and PACELC.

System Design Building Blocks Core

System Design applies these foundations to whole systems. Horizontal vs Vertical Scaling: vertical means a bigger machine, simple but limited; horizontal means more machines, which needs stateless services and shared storage. Load Balancing spreads requests across servers and removes unhealthy ones. Clustering groups machines to act as one for capacity or failover.

Caching keeps frequently read data in memory. When the cache is full, an eviction policy decides what goes: an LRU Cache drops the least recently used item, an LFU Cache the least frequently used, and an MFU Cache the most frequently used (rarely useful except when recent heavy use predicts no further use). A Content Delivery Network (CDN) caches static files near users. The System Design Roadmap roadmap goes much deeper.

Practice. Implement an LRU cache with a hash map and a doubly linked list with O(1) get and put.

Proxy and Queues in Systems Recommended

A Proxy sits between clients and servers. A forward proxy acts for clients, for example to filter outbound traffic. A reverse proxy acts for servers, handling TLS, compression, caching and routing; load balancers are a kind of reverse proxy.

Queues decouple parts of a system. A producer puts messages on a queue and a consumer handles them later, which smooths traffic spikes and lets slow work happen in the background. Message brokers such as RabbitMQ and Kafka provide durable queues and publish-subscribe topics. Consumers must cope with duplicate deliveries.

Practice. Put Nginx in front of two app servers as a reverse proxy and load balancer.

Architectural Styles and Architectural Patterns Recommended

Architectural Styles describe the overall shape of a system: monolith, layered (presentation, business, data), client-server, microservices, event-driven and serverless. Each trades simplicity against independent scaling and deployment.

Architectural Patterns are proven solutions within those styles: model-view-controller for user interfaces, CQRS for separate read and write models, event sourcing for storing changes as events, and publish-subscribe. Cloud Design Patterns, such as circuit breaker, retry with backoff, sidecar and strangler fig, address failure and migration in distributed systems. The Software Design and Architecture Roadmap roadmap covers these in depth.

Practice. Describe a project you know in terms of its style and two patterns it uses.

Design Patterns and GoF Design Patterns Recommended

Design Patterns are named, reusable solutions to recurring problems in object-oriented code. The GoF Design Patterns, from the 1994 "Gang of Four" book, group 23 patterns into three families:

• Creational: factory method, abstract factory, builder, singleton, prototype.
• Structural: adapter, decorator, facade, proxy, composite.
• Behavioural: strategy, observer, command, iterator, state, template method.

Learn the problem each solves, not just its diagram. Many are built into modern languages: iterators, first-class functions as strategies, decorators in Python.

Practice. Refactor a long if-else chain that picks a discount rule into the strategy pattern.

Dependency Injection, Null Object and Type Object Patterns Optional

Dependency Injection means a class receives its collaborators from outside rather than creating them, for example a service takes a repository in its constructor. This makes code easier to test with fakes and to reconfigure. Frameworks such as Spring and ASP.NET Core automate it.

The Null Object Pattern replaces null with an object that does nothing safely, such as a logger that discards messages, removing repeated null checks. The Type Object Pattern represents "kinds" of things as data instead of subclasses: a MonsterType object holds shared stats, so designers can add new types without new classes.

Practice. Refactor a class that creates its own database client so the client is injected, and test it with a fake.

UML Optional

UML (Unified Modeling Language) is a standard notation for drawing software designs. You will rarely draw full UML at work, but a few diagram types are useful in interviews and design documents:

• Class Diagrams: classes, fields, methods and relationships such as inheritance and composition.
• Sequence Diagrams: messages between objects or services over time, ideal for explaining a request flow.
• Activity Diagrams: workflows with decisions and parallel branches, like a flowchart.
• Usecase Diagrams: actors and the goals they achieve with the system.
• State Machine Diagrams: states of one object and the events that move it between them, such as an order going from placed to shipped.

Practice. Draw a sequence diagram for logging into a web app and a state machine diagram for an order.