CS fundamentals

A process owns an address space, file descriptors and kernel bookkeeping; a thread is a schedulable stream of execution inside one. So threads of a process share the heap, the code and the open files, and hold only their own stack, registers and program counter privately. That sharing is the whole trade: a thread switch is cheaper than a process switch and communication is a pointer rather than a pipe, but one thread corrupting shared memory takes the process down with it, and every shared structure now needs synchronisation. Processes buy isolation at the price of explicit inter-process communication, which is why a browser puts each tab in its own process and a web server puts each request on a thread.

The number people quote is the register save, which is the cheapest part of it.

what the kernel must do             what it really costs
----------------------------------  ------------------------------------------
save registers, switch stacks       ~100 ns of direct instructions
switch page tables on a process     TLB entries invalidated, tens of
switch                              microseconds of refill misses afterwards
scheduler bookkeeping               the new task's working set is cold in L1/L2

typical, one modern core
  plain function call               ~1 ns
  thread switch, same address space  1-5 us including cache effects
  process switch                     3-10 us

The indirect cost dominates, and it is invisible to a microbenchmark that switches between two tiny loops with no working set. Real code touches memory, so after a switch the caches hold the previous task's data and the incoming task takes thousands of misses before it runs at full speed.

That arithmetic is what decides thread-pool sizing. A thread that blocks on a lock or a socket a hundred thousand times a second spends the majority of its wall clock inside the scheduler rather than in your code, which is why the fix for a slow, heavily contended service is usually fewer threads doing longer units of work rather than more threads.

It is also the argument for asynchronous I/O and for user-space scheduling — green threads, goroutines, virtual threads. They do not make the kernel switch faster; they avoid needing one, because a task that blocks is parked by the runtime while the operating-system thread underneath it keeps running. The cost that remains is that any genuinely blocking call inside such a task pins the carrier thread and quietly removes the benefit.

It is a request for the kernel to do something your process is not privileged to do — read a file, send a packet, map memory. It costs more than a function call because it crosses a protection boundary: the CPU changes privilege level, arguments are validated because the kernel cannot trust your pointers, and speculative-execution mitigations flush or restrict predictors on the way in and out. That is hundreds of nanoseconds rather than one. The practical consequence is batching. Reading a file one byte at a time is thousands of times slower than reading it in 64 KB chunks, and the difference is almost entirely the boundary crossings rather than the disk.

Which runnable thread gets a core next, and for how long. A general-purpose scheduler is optimising for two things in tension: throughput, which favours long time slices and few switches, and responsiveness, which favours short slices so an interactive task is not stuck behind a batch job. Modern Linux uses a fair-share scheme that tracks how much CPU time each task has received and runs the one furthest behind, with priority expressed as a weight on that accounting. The consequence worth knowing is that priority is relative, not absolute: a low-priority task still runs, so a busy loop at low priority still burns a core and still evicts your caches.

Concurrency is a structural property — the program is composed of tasks whose execution can overlap in time — while parallelism is an execution property, tasks actually running at the same instant on different cores. A single-core machine runs concurrent programs without any parallelism by interleaving them. The distinction matters because it tells you what a change will buy: making an I/O bound service concurrent helps enormously on one core, since the waiting overlaps, while making a CPU-bound computation concurrent buys nothing until there are cores to run it on. Concurrency is about dealing with many things at once, parallelism about doing many things at once.

A zombie has exited but its parent has not yet collected its exit status, so the kernel keeps a minimal entry alive to report it. It consumes no memory or CPU, only a process-table slot, and the bug is always in the parent: it never called wait. An orphan is the reverse — the parent died first — and it is re-parented to init, which reaps it correctly, so orphans are harmless. This matters in containers, because the process running as PID 1 in a container is your application rather than init, and if it does not reap adopted children the table fills with zombies until nothing can fork.

Three, and candidates usually name only the first. It gives each process the illusion of a large private contiguous address space, so programs need not know what else is running or how much physical memory exists. It provides isolation, because a process can only name addresses the kernel has mapped for it, which is what stops one program reading another's data. And it decouples the size of a program's address space from the amount of RAM, so pages can live on disk, be shared between processes, or be backed by a file. The cost is a translation step on every single memory access, which is why the hardware caches translations.

Every load and store goes through this, so the hardware is built to make the common path free.

flowchart LR
    V[Virtual address<br/>page number + offset] --> T[TLB lookup]
    T -->|hit| P[Physical frame number]
    T -->|miss| W[Walk the page table in memory]
    W --> P
    W -->|entry not present| F[Page fault<br/>kernel maps or loads the page]
    F --> P
    P --> M[Physical address<br/>frame + offset]

The address splits into a page number and an offset within the page, typically 4 KB, so the low twelve bits pass through untouched and only the page number is translated. The page table maps page numbers to physical frames, and on x86-64 it is a four-level tree, which means a miss costs four dependent memory reads before your original read can even start.

The translation lookaside buffer is what makes this viable. It is a small associative cache of recent translations, and its hit rate on ordinary code is well over ninety-nine per cent, so the four-level walk is rare. When it is not rare, the effect is dramatic: a random-access pattern over several gigabytes misses the TLB constantly, and the program spends more time translating addresses than reading data. Huge pages exist precisely for this — a 2 MB page covers five hundred times the memory per TLB entry.

Two details are worth offering. The page-table entry carries permission bits, so the same mechanism that translates also enforces read-only and no-execute, which is how shared libraries are shared and how a write to a constant traps. And a page fault is not necessarily an error: it is simply the kernel being asked to supply a mapping, which is how demand paging, memory-mapped files and copy-on-write after fork are all implemented.

The regions differ in who allocates them, how they grow, and what happens when they run out.

high addresses
  0x7fff_ffff_f000   [ stack ]   grows downward; one per thread
                        |        automatic: frames pushed on call, popped on return
                        v        fixed maximum, typically 1-8 MB
                     [ guard ]   an unmapped page: overflow traps rather than
                                 silently overwriting the heap
                        ^
                        |
                     [ heap  ]   grows upward; malloc / new / object allocation
                                 explicit lifetime, limited by address space
                     [ bss   ]   zero-initialised globals; occupies no file bytes
                     [ data  ]   initialised globals and statics
  0x0000_0040_0000   [ text  ]   code; read-only and executable
  0x0000_0000_0000   unmapped    so dereferencing null faults instead of working

The stack is fast because allocation is one register adjustment and deallocation is automatic — returning from a function frees every local in one instruction, with perfect cache locality because the same few kilobytes are reused constantly. Its price is the fixed limit and the lifetime rule: a pointer to a local is invalid the moment the function returns.

The heap trades that speed for flexibility. Objects outlive the function that created them and can be any size, but allocation involves searching free lists, freeing is explicit or collected, and the memory fragments over time so a large allocation can fail while plenty of total space remains.

Two questions follow reliably. Deep recursion overflows the stack rather than slowing down, which is why an algorithm with recursion depth proportional to input size is a production risk in a language without tail calls. And a thread needs its own stack while sharing everything else, so thread count multiplies stack reservations — ten thousand threads at 1 MB each is ten gigabytes of address space before your program has allocated anything.

A page fault is the hardware telling the kernel that a virtual page has no valid mapping. A minor fault is resolved from memory — the page is already resident, or must be zero-filled, or is a copy-on-write clone — and costs microseconds. A major fault must read from disk and costs milliseconds, four orders of magnitude worse. Thrashing is what happens when the active working set exceeds physical memory: every fault evicts a page some other process is about to need, so the system spends its time paging rather than executing. The signature is high I/O, near-zero CPU utilisation and a machine that responds to nothing, which is why swap is often disabled on servers in favour of failing fast.

The stack is a per-thread region managed by the calling convention: entering a function pushes a frame holding its locals and return address, returning pops it, and both operations are a single pointer adjustment. The heap is a shared region managed by an allocator, where lifetime is decided by the programmer or a collector rather than by control flow. So the stack gives you speed, automatic cleanup and excellent locality at the cost of a small fixed size and function-scoped lifetime; the heap gives you arbitrary size and lifetime at the cost of allocation overhead, fragmentation and the need to decide when memory is no longer needed.

A leak is memory still reachable but never used again, so it is never freed and the process grows until it is killed. A dangling pointer is the mirror image: memory freed while a reference to it survives, so the next dereference reads whatever now occupies that address. Their failure modes differ completely. A leak degrades predictably and shows up as a rising memory graph and eventual restart — annoying but diagnosable. A use-after-free is undefined behaviour that may work in testing, corrupt unrelated data in production, or be exploitable, and it is the reason garbage-collected and ownership-checked languages exist. Note that garbage collection prevents the second entirely and the first not at all.

Reference counting frees an object as soon as its count reaches zero, giving predictable timing and immediate reuse, but it cannot collect cycles and every assignment costs a counter update that is atomic under threading. Tracing collectors start from roots and mark everything reachable, so cycles are handled, at the cost of a pause proportional to the live set. Mark-and-sweep leaves fragmentation; a copying or compacting collector eliminates it by moving survivors, which costs a copy but makes allocation a pointer bump. Generational collection exploits the fact that most objects die young, collecting a small nursery frequently and the old generation rarely — cheap, provided objects really do die young.

Identical work, identical big-O, and an order of magnitude between them.

int matrix[4096][4096];   // 64 MB; 4-byte ints, so 16 per 64-byte cache line

row-major     for i: for j:  sum += matrix[i][j]
column-major  for j: for i:  sum += matrix[i][j]

                    cache misses per 16 elements     time, one core
row-major  (i,j)    1  - the line is then reused     ~55 ms
column-major (j,i)  16 - every element a new line    ~900 ms

Same 16.7 million additions. Roughly 16x, which is exactly the number of
ints that share a cache line.

Memory is never fetched a byte at a time. The smallest unit moved between RAM and cache is a line, typically 64 bytes, so reading one integer brings its fifteen neighbours whether you want them or not. The row-major loop uses all sixteen before moving on; the column-major loop uses one and strides 16 KB to the next, by which time the line has been evicted.

The prefetcher widens the gap further. Hardware detects sequential access and fetches ahead, so the row-major loop's misses are largely hidden, while a large stride defeats detection and every miss is paid in full.

The general lesson is that the constant factor in memory access is not a constant at all — it ranges from about one nanosecond in L1 to eighty in RAM — so layout decides performance once the data is larger than cache. This is why an array of structs beats a linked list for iteration despite identical asymptotics, why column-oriented storage exists for analytics, and why the honest answer to "which data structure is fastest" is that it depends on the access pattern, not the complexity class.

A cache line is the unit of transfer between memory and cache, 64 bytes on current hardware, and coherence between cores is maintained per line rather than per byte. False sharing is the pathology that follows: two threads writing to different variables that happen to occupy the same line force that line to bounce between cores, because each write invalidates the other core's copy. The threads share nothing logically and contend severely in practice, and the symptom is a parallel loop that gets slower as you add threads. The fix is padding — placing per-thread counters on separate lines — which is why concurrent data structures contain fields whose only purpose is to occupy space.

The code reads correctly line by line. The bug only exists in the ordering.

balance = 100. Two threads each withdraw 60.

Thread A                      Thread B                      balance
--------------------------    --------------------------    -------
read balance -> 100                                            100
                              read balance -> 100              100
check 100 >= 60, ok                                            100
                              check 100 >= 60, ok              100
write 100 - 60 = 40                                             40
                              write 100 - 60 = 40               40

Both withdrawals reported success. 120 was paid out. 40 remains.

The check and the write are separate operations with a window between them, and the other thread's read lands in that window. Nothing is atomic here: even balance -= 60 compiles to a load, a subtract and a store, so it has the same hole even when it looks like one statement.

Two properties make these bugs expensive. They are timing-dependent, so the interleaving that fails may occur once in ten million and never on the developer's machine; and they are invisible in a code review that reads each thread in isolation, because each thread is individually correct.

The fix must make the read-modify-write a single indivisible unit. That is a lock around the whole sequence, a compare-and-swap retry loop, or pushing the invariant into a store that can enforce it — a database constraint that the balance may not go negative, or a conditional update whose WHERE clause repeats the check. Guarding only the write, which is the common half-fix, leaves the window exactly where it was.

That an operation is indivisible from the point of view of other threads: they observe the state before it or the state after it, never a partial result. It is not the same as thread-safe and not the same as fast. Hardware provides atomic read-modify-write instructions — compare-and-swap, fetch-and-add — and everything above is built from them. Two traps follow. An atomic increment does not make a sequence of two atomic increments atomic, so atomicity does not compose. And atomicity says nothing about visibility ordering of other variables, which is what memory models and barriers govern, so a correctly incremented counter can still be read alongside stale data it was meant to describe.

A mutex protects a critical section: exactly one thread holds it, it has an owner, and only that owner may release it — which is what lets the runtime detect misuse and support recursion or priority inheritance. A counting semaphore is a permit pool with no ownership, so it models a resource with N instances or acts as a signalling mechanism between threads where one signals and another waits. A binary semaphore resembles a mutex and is not one, because any thread can release it. Use a mutex for mutual exclusion and a semaphore for capacity limiting or signalling; conflating them produces locks released by threads that never took them.

Waiting for a predicate to become true without busy-polling. A thread holding a mutex discovers the condition it needs is not yet met, so it waits on the condition variable, which atomically releases the mutex and sleeps; another thread changes the state and signals, and the waiter reacquires the mutex before returning. The atomic release-and-sleep is the entire point, because checking and then sleeping as two steps loses a signal arriving in between. The rule that follows is that a wait must always sit inside a loop re-checking the predicate, since spurious wakeups are permitted and a signalled thread may find another thread got there first.

Two threads, two locks, and an ordering that only occurs under load.

Thread A                              Thread B
lock(accounts[1])                     lock(accounts[2])
  ... begin transfer 1 -> 2             ... begin transfer 2 -> 1
lock(accounts[2])  <- blocks          lock(accounts[1])  <- blocks

Coffman conditions, all four required, all four present:
  1 mutual exclusion  each lock is held by exactly one thread
  2 hold and wait     A holds lock 1 while waiting for lock 2
  3 no pre-emption    nothing can take lock 1 away from A
  4 circular wait     A waits on B, which waits on A

Deadlock requires all four simultaneously, which is why the conditions are worth memorising as a set: each one is a place to attack. Breaking any single condition makes deadlock impossible.

Circular wait is the one you break in practice, by imposing a global ordering on lock acquisition. Here that means always locking the lower account identifier first, so both threads take lock 1 then lock 2 and one simply waits. It costs nothing at runtime and it is a discipline rather than a mechanism, which is its weakness — it holds only while every code path obeys it.

Hold-and-wait can be broken by acquiring all locks at once or by using a timed try-lock that releases everything and retries on failure, which converts deadlock into livelock unless the retry is randomised. No-pre-emption is what a database breaks: it detects the cycle in its wait-for graph and kills one transaction with a deadlock error, which is why application code talking to a database must be prepared to retry rather than treating that error as fatal.

The detail candidates omit is that the two threads' code is symmetric and looks correct. The bug is not in either function; it is in the relationship between them, which is why deadlocks survive code review and appear first under production concurrency.

By breaking one of the four conditions deliberately rather than hoping. The cheapest is a global lock ordering, so cycles cannot form; the second is holding one lock at a time, which often means restructuring so the second resource is not needed while the first is held. Timed acquisition with full release and a randomised retry works where ordering is impossible. Lock-free structures avoid the question. What does not work is reducing the window and testing harder, because the window never closes. The related discipline is never calling out to unknown code — a callback, a remote service — while holding a lock, since you have no idea what it will try to acquire.

Starvation is a thread that is runnable but never scheduled or never granted the lock it wants, usually because a priority scheme or an unfair lock keeps favouring others. Livelock is worse to diagnose: threads are actively executing and making no progress, because each keeps reacting to the other — two threads that detect contention, both back off, and both retry in lockstep forever. The distinction from deadlock is that nothing is blocked, so CPU is at a hundred per cent and every thread looks healthy. Randomised backoff is the standard cure for livelock, and fair queueing for starvation, at the cost of throughput.

Compilers and CPUs reorder reads and writes to hide latency, and that reordering is invisible in single-threaded code because the result is unchanged. Across threads it is very visible: one thread can observe writes in a different order than they were issued, so a flag set after data is prepared may be seen before the data. A memory model is the contract stating which reorderings are observable, and synchronisation primitives insert barriers that constrain them. This is why a correctly locked program needs no reasoning about reordering — the lock implies the barriers — and why a hand-rolled lock-free structure using plain variables is almost always wrong even when it passes every test.

Four of the seven, and it is worth being blunt about it. Layer 3, the network layer, is IP: addressing and routing between networks, best-effort and connectionless. Layer 4, transport, is TCP or UDP: ports, and whether you get reliability. Layer 7, application, is HTTP, DNS, TLS-wrapped protocols and everything you write. Layer 2 matters when you care about the local segment — MAC addresses, ARP, switches, VLANs. Layers 5 and 6 have no clean mapping to real protocols and the honest answer says so. The reason the model still earns its place is that it tells you where a symptom lives: name resolution failing is not the same problem as a connection refused.

TCP is connection-oriented and gives you an ordered, reliable, flow-controlled byte stream: it numbers bytes, retransmits what is not acknowledged, and slows down when the network signals congestion. UDP is a thin wrapper over IP that sends independent datagrams with a checksum and nothing else — no ordering, no retransmission, no connection setup, no congestion control. The trade is not "reliable versus unreliable" but latency versus completeness. TCP will delay delivering byte 100 until byte 99 arrives, which is correct for a file and wrong for a live voice call where a stale packet is worthless. UDP is also the base for protocols that want reliability with different rules, which is what QUIC is.

Three segments before a single byte of your data moves, and the sequence explains what connection setup costs.

sequenceDiagram
    participant C as Client
    participant S as Server
    C->>S: SYN, my sequence number is x
    S-->>C: SYN-ACK, my sequence is y, I acknowledge x+1
    C->>S: ACK, I acknowledge y+1
    C->>S: First byte of application data
    S-->>C: Response

Each side announces an initial sequence number and acknowledges the other's, which is what establishes that both directions work and lets either side detect loss from then on. Random initial sequence numbers also make it harder for an off-path attacker to inject data into the stream.

The cost is one full round trip before data flows, and it is paid in latency rather than bandwidth. Between London and Singapore a round trip is roughly 180 milliseconds, so the handshake alone delays the first byte by that much, regardless of how fast the link is.

Add TLS and it gets worse: TLS 1.2 needs two further round trips, TLS 1.3 needs one, so an HTTPS request over a fresh connection is two to three round trips of pure setup. That is the entire reason for connection pooling, HTTP keep-alive and HTTP/2 multiplexing — not to save bytes, but to amortise setup. A service that opens a new connection per request on a high-latency path spends most of its time in handshakes, and QUIC exists partly to collapse the transport and TLS handshakes into one round trip.

Two further details answer the usual follow-ups. Slow start means a fresh connection also begins with a small congestion window, so early throughput is low even after the handshake completes. And the server allocates state on receiving the SYN, which is the basis of the SYN-flood attack and the reason SYN cookies exist.

Reliability comes from sequence numbers, cumulative acknowledgements, retransmission on timeout or on duplicate acknowledgements, and a checksum. Flow control protects the receiver: the advertised window says how much unread data its buffer can still hold, so a fast sender cannot overrun a slow reader. Congestion control protects the network between them, inferring available capacity from loss and delay because no router tells it directly — slow start ramps up exponentially, then congestion avoidance grows linearly, and a loss signal cuts the window. Conflating the two is the common error: the effective send rate is the minimum of both windows, and diagnosing a throughput problem means knowing which one is the constraint.

The resolver walks a hierarchy. Your stub resolver asks a recursive resolver, which answers from cache if it can; otherwise it asks a root server for the top-level domain's nameservers, asks those for the domain's nameservers, and asks those for the record. Each step is a referral rather than a lookup on your behalf, which is what makes the system scale. Caching is what makes it fast, governed by each record's TTL, and it is also what makes DNS changes slow to take effect — resolvers keep the old answer until the TTL expires, and some ignore short TTLs. Hence lowering the TTL before a planned cutover, hours ahead of the change.

Network address translation lets many hosts behind one public address share it, by rewriting source addresses and ports on outbound packets and keeping a table to reverse the mapping on the way back. It is why IPv4 survived address exhaustion. What it breaks is inbound connections and address symmetry: nothing outside can initiate a connection to a host inside without an explicit forward, a host does not know its own public address, and protocols that embed addresses in their payload need rewriting help. It also makes the mapping stateful and time-limited, so an idle connection is silently dropped — which is why long-lived connections need keepalives.

A kernel object representing one endpoint of a communication channel, exposed to your process as a file descriptor so it can be read and written like a file. For TCP it is identified by the four-tuple of source address, source port, destination address and destination port, which is what allows one server port to hold thousands of distinct connections at once. A listening socket is a different thing from a connected one: accept returns a new socket per connection while the listener keeps listening. The kernel owns the send and receive buffers, which is why a write can succeed with nothing yet on the wire, and why "the write returned" is not "the peer received it".

After closing, the side that closed first holds the connection in TIME_WAIT for roughly twice the maximum segment lifetime — a minute or so. Two reasons: a delayed duplicate of an old segment must not be delivered into a new connection reusing the same four-tuple, and the final acknowledgement may be lost, so the peer's retransmitted FIN needs somewhere to land. The operational consequence is that a client making very many short connections exhausts its ephemeral port range and fails to connect while thousands of sockets sit in TIME_WAIT. The right fix is connection reuse, not shortening the timer, because the timer is protecting correctness.

A representation of signed integers where the top bit carries negative weight, so an n-bit value spans -2^(n-1) to 2^(n-1)-1. It is used because it makes signed addition and subtraction identical to the unsigned operations: the same adder circuit works for both, and the carry out is simply discarded. The alternatives — sign-and-magnitude, or one's complement — both produce two representations of zero and need special-case handling for arithmetic. Two's complement has exactly one zero, and the asymmetry it pays for that is one extra negative value with no positive counterpart, which is where the abs-of-the-minimum bug comes from.

Eight bits is enough to see every property that matters.

   0000 0101   =    5
   1111 1011   =   -5     invert 0000 0101 -> 1111 1010, then add 1
   1111 1111   =   -1     all ones is always -1
   1000 0000   = -128     the negative with no positive counterpart
   0111 1111   =  127     the largest positive

Addition needs no sign handling.  -5 + 5:
     1111 1011
   + 0000 0101
   = 1 0000 0000   -> carry discarded -> 0000 0000 = 0

Overflow is silent, and wraps:
     0111 1111  ( 127)
   + 0000 0001  (   1)
   = 1000 0000  (-128)

And the classic:
     abs(-128) -> negate 1000 0000 -> invert 0111 1111, add 1 -> 1000 0000
     abs of the most negative value is itself, still negative

The single adder is the whole justification. Negation is invert-and-increment, and subtraction is addition of the negation, so hardware needs one circuit rather than sign-comparison logic.

The overflow behaviour is the part with production consequences. It is silent — no flag your code reads unless you check — and in C signed overflow is undefined behaviour rather than merely wrapping, which means the compiler may optimise on the assumption that it cannot happen. That is how a bounds check written as if (i + n > limit) gets removed entirely.

Two follow-ups are common. Right-shifting a negative number is arithmetic, not logical, in most languages, so the sign bit is copied and the result is not division-by-two-rounding-toward-zero for negatives. And the asymmetric range is why parsing the string "-2147483648" works while negating the parsed positive does not, and why timestamp and identifier columns should be sized with the signed maximum in mind rather than the unsigned one.

As a sign bit, a biased exponent and a fraction, giving a value of roughly sign times 1.fraction times two to the exponent. A double has 11 exponent bits and 52 fraction bits, so it spans an enormous range with about 15-17 significant decimal digits of precision anywhere in that range. The consequence is that the representable values are not evenly spaced: they are dense near zero and sparse at large magnitudes, so adding 1 to a large double may change nothing at all. Special encodings carry infinities and NaN, and NaN is not equal to itself, which breaks sorting and equality in ways that surface as a comparator exception.

The bug is not in the addition. Neither operand exists in the first place.

0.1 as an IEEE 754 double
  sign 0   exponent 01111111011   fraction 1001100110011001...0011010
  exact stored value
    0.1000000000000000055511151231257827021181583404541015625

0.2 stored exactly as
    0.200000000000000011102230246251565404236316680908203125

Their sum, rounded to the nearest double
    0.3000000000000000444089209850062616169452667236328125
0.3 stored as
    0.299999999999999988897769753748434595763683319091796875

  >>> 0.1 + 0.2
  0.30000000000000004
  >>> 0.1 + 0.2 == 0.3
  False
  >>> 0.3 - 0.1 - 0.2
  -2.7755575615628914e-17

Binary fractions can represent only sums of powers of one half, and one tenth is not such a sum, exactly as one third is not representable in decimal. So 0.1 is stored as the nearest double, which is slightly above one tenth, and the error is present before any arithmetic happens. Printing usually hides it, because most languages print the shortest decimal that round-trips to the same double.

Two consequences matter. Equality comparison on floats is meaningless: compare with a tolerance appropriate to the magnitude, or do not compare at all. And error accumulates — summing a million small floats in a different order gives a different answer, so floating-point addition is not associative and a parallel reduction is not bit-identical to a serial one.

The fix for money is not a bigger float. It is an integer count of the smallest unit, or a decimal type with declared precision, because the requirement is exact representation of decimal fractions and no float provides that. The related interview trap is a float or double money column in a schema, which produces totals that disagree with the sum of their parts by a penny and an accountant who cannot be argued with.

A character set — Unicode — maps characters to abstract numbers called code points, saying that U+00E9 is a small e with acute. An encoding says how a code point becomes bytes: UTF-8, UTF-16 and UTF-32 all encode the same Unicode differently. Confusing the two is the origin of mojibake, because bytes written in one encoding and read as another produce plausible-looking wrong characters rather than an error. The rule that follows is that a string has no meaningful byte length until you name an encoding, and every boundary — file, socket, database column, HTTP header — needs the encoding declared rather than assumed.

The design is the answer to why it won, so the bit patterns are worth knowing.

code point range        bytes  layout
----------------------  -----  -----------------------------------------
U+0000  - U+007F          1    0xxxxxxx
U+0080  - U+07FF          2    110xxxxx 10xxxxxx
U+0800  - U+FFFF          3    1110xxxx 10xxxxxx 10xxxxxx
U+10000 - U+10FFFF        4    11110xxx 10xxxxxx 10xxxxxx 10xxxxxx

'A'   U+0041   ->  41
'£'   U+00A3   ->  C2 A3
'€'   U+20AC   ->  E2 82 AC
'😀'  U+1F600  ->  F0 9F 98 80

so len in code points 4, len in UTF-8 bytes 10, len in UTF-16 units 5

Three properties fall out of that table. ASCII is unchanged, so every existing ASCII file is already valid UTF-8 and byte-oriented code that searches for a slash or a newline keeps working. No multi-byte sequence contains a byte below 0x80, so an ASCII character can never appear inside another character — which is what makes naive delimiter scanning safe.

And the encoding is self-synchronising: leading bytes start 11 and continuation bytes start 10, so from any position you can find the start of the current character by scanning backwards a few bytes. That is why a truncated UTF-8 stream recovers rather than being garbage from the truncation point onward.

The cost is that indexing is not constant time. Byte offset and character offset differ, so "the fifth character" requires a scan, and slicing by byte index can split a character in half. This is the source of the reversed-string bug, where reversing bytes or even code points mangles combining characters and emoji sequences, and it is why a careful answer distinguishes bytes, code points and user-perceived characters as three different lengths.

The order in which the bytes of a multi-byte value are stored. Little-endian puts the least significant byte at the lowest address, which is what x86 and ARM generally do; big-endian is the reverse and is the convention on the wire, which is why the network byte order is big-endian. It bites at boundaries: reading a binary file or protocol written by a machine of the other order, casting a byte buffer to an integer type, or memory-mapping a struct. Within one process it never matters. The discipline is to serialise explicitly with a declared byte order rather than dumping memory, which also removes struct padding surprises.

The growth rate of a cost — usually time or space — as input size grows, in the limit, ignoring constant factors and lower-order terms. That is its power and its limitation: it tells you how an algorithm scales, and deliberately says nothing about how fast it is on your data. It is also an upper bound, which is why theta and omega exist and why saying an algorithm "is O(n squared)" is technically compatible with it being linear. In an interview the important precision is naming which case you mean — worst, average or amortised — and which variable n refers to, since a graph algorithm has two.

Assume a billion simple operations a second, which is roughly one modern core.

                n = 1,000        n = 1,000,000      n = 1,000,000,000
--------------  ---------------  -----------------  ---------------------
O(log n)        10 ops           20 ops             30 ops
                under 1 us       under 1 us         under 1 us

O(n)            1e3              1e6                1e9
                1 us             1 ms               1 second

O(n log n)      1e4              2e7                3e10
                10 us            20 ms              30 seconds

O(n^2)          1e6              1e12               1e18
                1 ms             ~17 minutes        ~32 years

O(2^n)          n = 50 is 1e15 ops, ~13 days.  n = 100 exceeds the age
                of the universe.

Read the middle column first, because a million records is an ordinary size for a production job. Linear and n-log-n are both fine there; quadratic has already become a job you cannot run inside a deployment window; exponential was never an option.

The row that changes behaviour is n squared. It is invisible in testing at n in the hundreds, where a millisecond is a millisecond, and catastrophic at a million. That is exactly the shape of the nested-loop bug that ships: a lookup inside a loop over the same collection, correct and fast on the developer's fixture and fatal on real data.

Two refinements are worth adding unprompted. The billion-operations assumption is generous once memory is involved, because a cache miss is worth roughly a hundred arithmetic operations, so an algorithm with poor locality can lose to one with a worse complexity class at realistic sizes. And log n is effectively a constant around 20-30 for any input that fits on a machine, which is why binary search, balanced trees and heaps are treated as free.

Because real inputs are finite and often small, and the constant can be three orders of magnitude. Linear search beats a hash table for a handful of elements, since the hash and the indirection cost more than a few comparisons over contiguous memory. Insertion sort beats quicksort below about a dozen items, which is why every production sort switches to it for small partitions. Matrix multiplication algorithms with better exponents are slower than the naive one at any size you will ever multiply. The rule is that complexity tells you which algorithm wins eventually, and measurement tells you whether your n is past the crossover.

Amortised complexity is the cost per operation averaged over a worst-case sequence, so it is a guarantee rather than a probability. A dynamic array's push is amortised O(1): most pushes are constant and an occasional one copies everything, but doubling the capacity means the copies total O(n) across n pushes. Average case, by contrast, is over a distribution of inputs and offers no promise about any particular sequence — quicksort's O(n log n) is average case, and adversarial input still gives quadratic. The distinction has a real consequence: an amortised structure can still miss a latency target, because one push in a thousand takes a hundred times as long.

P is the class of decision problems solvable in polynomial time. NP is the class whose solutions can be verified in polynomial time — so sudoku is easy to check and apparently hard to solve. The open question is whether the two are the same; nobody has proved they differ, and the consensus is that they do. NP-complete problems are the hardest in NP, in the precise sense that any NP problem reduces to them in polynomial time, so a polynomial algorithm for one would settle the question for all. The common error is calling NP problems "unsolvable" or "exponential"; NP is about verification, and undecidability is a different thing entirely.

Recognise it, then stop looking for an exact efficient algorithm and choose which requirement to relax. Approximate: accept a solution provably within some factor of optimal, which is how bin packing and set cover are handled in practice. Use a heuristic with no guarantee but good behaviour on real instances — simulated annealing, or a solver that prunes aggressively. Restrict the input, because many hard problems are easy on trees, on planar graphs, or when a parameter is small. Or reduce the instance size until brute force fits. Naming the problem is itself valuable, because it converts an open-ended engineering effort into a known trade-off.

A hash function for a table must be fast, distribute keys uniformly so buckets fill evenly, and be deterministic and consistent with equality — equal objects must hash equally, or lookups fail silently. It need not be hard to invert. A cryptographic hash adds collision resistance, preimage resistance and the avalanche property, and is deliberately slower. Using the wrong one has real costs: a fast non-cryptographic hash on attacker-controlled keys enables a collision attack that turns every lookup linear, which is why runtimes randomise their hash seed per process, and a cryptographic hash in a hot inner loop is pure waste.

Collisions are not an edge case; with 23 keys in 365 buckets one is already more likely than not.

table size 8, hash(k) = k mod 8, insert 12, 20, 4  -> all hash to bucket 4

Separate chaining
  bucket:  0    1    2    3    4         5    6    7
                               [12]->[20]->[4]
  lookup 4:  hash once, walk three links
  load factor may exceed 1; lookup degrades to O(chain length)
  cost: a pointer per entry, and a cache miss per link

Open addressing, linear probing
  index:   0    1    2    3    4    5    6    7
                              12   20    4
  lookup 4:  probe 4 -> 12 no, 5 -> 20 no, 6 -> 4 found
  lookup 13: probe 5, 6, 7 -> empty slot -> absent
  delete 12: blanking slot 4 would end the probe run and hide 20 and 4
             -> write a tombstone instead

Chaining keeps the invariant simple and tolerates a high load factor, at the cost of an allocation and a pointer chase per entry. Open addressing stores everything in one contiguous array, so a probe run is usually within a cache line or two and it is markedly faster in practice at moderate load — which is why several modern standard libraries use it, including Python's dict, Rust's HashMap and Go's maps. It is not universal: Java's HashMap chains and treeifies a long bucket, and C++ requires std::unordered_map to chain.

Open addressing's price is the deletion problem shown above and its sensitivity to load factor. Linear probing suffers clustering: a run of occupied slots grows and absorbs new insertions, so performance falls off sharply above roughly seventy per cent occupancy, and tombstones accumulate until a rehash clears them.

The property both share is that the worst case is O(n), not O(1). If every key collides — because the hash is poor, or because an attacker chose the keys — the table becomes a list. That is the honest answer to "what is the complexity of a hash lookup": constant expected, linear worst case, and the gap between them is a denial-of-service vector rather than a theoretical curiosity.

Symmetric encryption uses one shared key for both directions, is fast enough to encrypt bulk data at gigabytes per second with hardware support, and leaves you with the problem of getting the key to the other party. Asymmetric encryption uses a keypair where the public key encrypts and only the private key decrypts, which solves key distribution and is orders of magnitude slower, so it is never used for bulk data. Every real protocol combines them: asymmetric operations establish a shared symmetric key, and everything after that is symmetric. That hybrid structure is the answer to "how does TLS work" in one sentence.

Encoding changes representation with no secret involved — base64, URL encoding, UTF-8 — and is reversible by anyone, so it provides exactly zero security. Encryption is reversible with a key and is for confidentiality. Hashing is one-way by design, produces a fixed-size digest, and is for integrity and identification rather than secrecy. The interview trap is treating base64 as obfuscation, which appears in real systems as credentials "encrypted" in a config file. The second trap is hashing when you need to recover the value, or encrypting a password when you should hash it, since nothing should ever be able to decrypt a stored password.

Because the threat is offline brute force, and speed helps the attacker. A general-purpose hash like SHA-256 is designed to be fast, so a GPU tries billions of candidates a second against a stolen digest. A password hash — bcrypt, scrypt, Argon2 — is deliberately slow and, in the better ones, memory-hard, so parallel hardware gains little. Each password also gets a unique random salt, stored alongside, which defeats precomputed rainbow tables and ensures two users with the same password get different digests. A pepper, a secret not stored with the data, adds a layer that survives a database-only breach.

That the holder of a specific private key saw this exact message. It is produced by hashing the message and applying a signing operation with the private key, verified by anyone with the public key. For RSA that operation resembles encrypting the digest, which is where the common "encrypt with the private key" shorthand comes from, but ECDSA and EdDSA encrypt nothing and have no corresponding decryption. So it gives integrity — any change to the message breaks verification — and authenticity, and non-repudiation, since only the keyholder could have produced it. What it does not give is confidentiality: a signed message is still plaintext. Two limits matter. It proves nothing about who holds the key, which is what certificates are for, and it proves nothing about freshness, so a replayed signed message is still valid without a timestamp or nonce.

The structure is the hybrid argument made concrete: asymmetric to agree a key, symmetric for everything after.

sequenceDiagram
    participant C as Client
    participant S as Server
    C->>S: ClientHello, supported ciphers and a key share
    S-->>C: ServerHello, key share and certificate chain
    C->>C: Verify chain to a trusted root, check name and dates
    C->>S: Finished, encrypted from this point
    S-->>C: Finished
    C->>S: Application data under the derived session key

Both sides send an ephemeral key share and derive the same shared secret without transmitting it — that is Diffie-Hellman, and using a fresh keypair per connection is what gives forward secrecy: recovering the server's long-term private key later does not decrypt recorded traffic, because that key never encrypted the session secret.

The certificate is where the server's identity enters. It binds a public key to a name, signed by an authority, and the server proves it holds the matching private key by signing handshake data. Without the verification step in the middle, everything else still works and you have a perfectly encrypted channel to an attacker — which is exactly what disabling certificate validation to make a client work achieves.

The cost is round trips. TLS 1.3 completes in one, TLS 1.2 in two, on top of TCP's one, which is why the first request on a new connection is dominated by setup and why session resumption and connection reuse matter more than cipher choice.

The detail candidates leave out is what TLS does not protect. It secures the channel, not the endpoints: data is plaintext at both ends, the certificate says nothing about whether the server is trustworthy, and the hostname you asked for is visible in the handshake and in DNS.

Trust is not in the certificate you are shown. It is in what that certificate can be traced back to.

leaf          CN = api.example.com
              signed by:  R3 Intermediate
              SAN: api.example.com, example.com
              valid 2026-05-01 to 2026-07-30

intermediate  CN = R3
              signed by:  Root X1
              basicConstraints: CA TRUE, pathlen 0

root          CN = Root X1
              self-signed
              present in the OS or browser trust store

verification, working upward from the leaf
  1  leaf's signature verifies under R3's public key
  2  R3's signature verifies under Root X1's public key
  3  Root X1 is in the local trust store -> stop, chain anchored
  4  requested hostname matches a SAN entry
  5  every certificate is within its validity window
  6  none appears in a revocation list or fails an OCSP staple

The root is trusted because it was shipped with your operating system or browser, not because of anything cryptographic — that is the one axiom in the system, and it is a social fact rather than a mathematical one. Everything else is derived by signature verification.

Intermediates exist so the root's private key can stay offline in a vault and be used only rarely. The trade is that a server must send the full chain: a misconfiguration where only the leaf is sent works in browsers that have cached the intermediate and fails in every other client, which is the classic "works on my laptop, fails in the container" TLS bug.

Each check in the list corresponds to a real failure. A name mismatch is why a certificate for the apex domain fails on a subdomain. Expiry is the outage that takes down a service on a date nobody diaried, which is the entire argument for automated renewal. And revocation is the weakest link, because checking it is slow and often skipped, which is why certificate lifetimes have been shortened instead — a short-lived certificate is its own revocation mechanism.

Authentication establishes who the caller is; authorisation decides what that identity may do. They fail differently and are enforced in different places, which is why conflating them produces real vulnerabilities. A system that authenticates well and authorises by trusting a client-supplied identifier has the most common web vulnerability there is: any logged-in user can read another's record by changing a number in the URL. The rule is that authorisation must be checked server-side on every request, against the authenticated identity, at the point where the resource is loaded — not in the UI, which merely hides options, and not once at the session boundary.

All three exist to stop identical inputs producing identical outputs, and they are not interchangeable. A salt is per-password random data stored with the hash, which makes precomputation useless and stops two identical passwords sharing a digest. An initialisation vector randomises a block cipher's first block so encrypting the same plaintext twice gives different ciphertext; it must be unpredictable but need not be secret. A nonce is a number used once, and its requirement is uniqueness rather than randomness — reusing a nonce in a mode like GCM is catastrophic, leaking the authentication key rather than merely revealing that two messages match.

Because it is a slogan that answers nothing the interviewer wants to know. The question behind the question is what is shared and what is private, since that is what determines every practical consequence: threads share the heap and open files, so communication is free and corruption is contagious; each has its own stack and registers, so locals are safe and stack size multiplies with thread count. A strong answer names the sharing, then draws the conclusions — synchronisation is required, a crash takes the whole process, a switch is cheaper but not free. The slogan states a relative cost while omitting the cause of it.

They describe it as a way to use disk as extra memory, which was one motivation in 1965 and is the least important one now, when servers commonly run with swap disabled entirely. The two things they omit are the ones that matter every day: isolation, since a process can only name what has been mapped for it, and indirection, which is what makes shared libraries, memory-mapped files and copy-on-write after fork possible. A strong answer also knows where the cost lives — a translation on every access, cached in the TLB — because that is what connects the concept to a performance problem you can actually observe.

Reciting a class without saying what n is or which case it describes. A graph algorithm has vertices and edges, so O(n squared) is ambiguous; a string algorithm has pattern length and text length. The second mistake is ignoring space, which is often the binding constraint — an O(n) auxiliary structure is free at a thousand elements and impossible at a billion. The third is treating big-O as a performance claim, which leads to defending an asymptotically better algorithm that is slower on every input the system will ever see, when the answer wanted was that constants and cache behaviour decide the crossover.

Because it names a channel guarantee and calls it a security posture. TLS protects data in transit against an observer or a tamperer on the path, and that is all. It does nothing about data at rest, nothing about authorisation, nothing about injection, nothing about a compromised endpoint, and nothing about the fact that your logs may contain what the channel just protected. It also assumes certificate validation is actually enforced, which client code frequently disables. A strong answer says what threat TLS addresses, then names the ones it leaves open — which is the difference between having configured something and understanding what it bought.

"You have a program that is slower than it should be. Walk me from the symptom to the cause." It works because it cannot be answered from memorised definitions and because every layer on this sheet is a possible answer. A strong response establishes what resource is saturated before theorising — CPU, memory, I/O or lock contention — and reasons about which is plausible: near-zero CPU with high I/O wait points at page faults or disk, a hundred per cent CPU with no progress suggests livelock or a spin, and a parallel loop that gets slower with more threads points at contention or false sharing. It names the tool that would confirm each guess, and it distinguishes an algorithmic problem, where the fix is a different complexity class, from a locality problem, where the fix is a different memory layout. A weak answer starts optimising immediately, usually by adding threads or a cache, and never establishes what the machine was actually waiting for.