Engineer Computer System cheat sheet

Amdahl's law: speedup = 1 / ((1 - f) + f/s), where f is the fraction enhanced and s the improvement factor; speedup is bounded by 1/(1 - f).

CPU performance: execution time = instruction count × CPI × clock cycle time; clock rate = 1 / cycle time, so halving CPI doubles throughput at fixed clock.

Classic five-stage pipeline: IF, ID, EX, MEM, WB; ideal CPI approaches 1, degraded by structural, data, and control hazards.

Data hazards are resolved by forwarding (bypassing) or stalling; load-use hazards typically require one bubble even with forwarding.

Cache hierarchy: L1 hit latency ~4 cycles, main memory ~100+ cycles; average access time = hit time + miss rate × miss penalty.

Three cache miss categories: compulsory (first reference), capacity (working set exceeds cache), conflict (mapping collisions in set-associative caches).

Write policies: write-through keeps memory coherent with higher traffic; write-back defers writes and needs a dirty bit per line.

Little's law: average number in system = arrival rate × average time in system; applies to queues, pipelines, and memory-level parallelism.

RISC vs CISC: RISC uses fixed-length instructions and load/store architecture; CISC allows memory operands and variable-length encoding.

Two's complement range for n bits: -2^(n-1) to 2^(n-1) - 1; negation is invert all bits then add 1.

IEEE 754 single precision: 1 sign bit, 8 exponent bits (bias 127), 23 fraction bits; value = (-1)^s × 1.f × 2^(e-127) for normalized numbers.

Floating point is not associative: (a + b) + c may differ from a + (b + c); never compare floats with ==, use an epsilon tolerance.

Unsigned n-bit addition overflows when a carry out of the MSB occurs; signed overflow occurs when two same-sign operands yield an opposite-sign result.

Boolean identities: De Morgan's laws (A·B)' = A' + B' and (A + B)' = A'·B'; XOR equals A'B + AB'.

Karnaugh maps group 1s in powers of two (1, 2, 4, 8); don't-care terms may be included to enlarge groups and simplify the expression.

Setup and hold constraints: data must be stable before the clock edge (setup) and after it (hold); the critical path sets maximum clock frequency.

A multiplexer with 2^k data inputs needs k select lines; an n-to-2^n decoder plus OR gates can implement any sum-of-products function.

Process states: new, ready, running, waiting, terminated; a context switch saves and restores PCB state and adds pure overhead.

Scheduling metrics: turnaround = completion - arrival; waiting = turnaround - burst; response = first-run - arrival.

SJF minimizes average waiting time but requires burst prediction; round robin bounds response time with a time quantum.

Deadlock's four Coffman conditions: mutual exclusion, hold and wait, no preemption, circular wait; removing any one prevents deadlock.

Banker's algorithm grants a request only if the resulting state is safe, i.e., some completion order satisfies all remaining needs.

Virtual memory translation: virtual address splits into page number and offset; the TLB caches page-table entries, and a miss costs a page-table walk.

Page replacement: FIFO can exhibit Belady's anomaly; LRU approximates optimal but needs reference tracking; OPT is unrealizable, used as a baseline.

Thrashing occurs when the sum of working sets exceeds physical frames; the fix is reducing multiprogramming degree, not adding pages blindly.

Interprocess communication: pipes are unidirectional byte streams; shared memory is fastest but needs explicit synchronization; message queues decouple sender and receiver.

Average complexities: hash table lookup O(1); balanced BST search O(log n); unsorted array search O(n); sorting comparison lower bound O(n log n).

Quicksort average O(n log n), worst O(n^2) on already-sorted input with a poor pivot; randomized or median-of-three pivots mitigate this.

Merge sort is stable and O(n log n) worst case but needs O(n) extra space; heapsort is in-place O(n log n) but not stable.

A binary heap supports insert and extract-min in O(log n) and peek in O(1); build-heap from n elements is O(n), not O(n log n).

BFS finds shortest paths in unweighted graphs; Dijkstra requires non-negative weights; Bellman-Ford handles negative edges in O(VE).

Minimum spanning tree: Kruskal sorts edges and uses union-find (near O(E log E)); Prim grows a tree from one vertex using a priority queue.

Dynamic programming requires optimal substructure and overlapping subproblems; memoization is top-down, tabulation is bottom-up.

Hash collisions: chaining stores colliding keys in lists, open addressing probes alternative slots; load factor above ~0.7 degrades performance sharply.

Red-black trees guarantee O(log n) height with at most two rotations per insertion; AVL trees are more strictly balanced and rotate more often.

SOLID: single responsibility, open/closed, Liskov substitution, interface segregation, dependency inversion.

Coupling should be low and cohesion high; a module should hide its representation behind a stable interface.

Test pyramid: many unit tests, fewer integration tests, fewest end-to-end tests; tests must be deterministic and independent of execution order.

TDD cycle: red (failing test), green (minimal code to pass), refactor; coverage percentage measures execution, not assertion quality.

Version control: a branch is a movable pointer to a commit; merge creates a merge commit, rebase rewrites history onto a new base.

Scrum roles are product owner, scrum master, and developers; sprint length is fixed and scope changes go to the backlog.

Code review checks correctness, readability, and design, not personal style; small pull requests review faster and find more defects.

Memory safety: dangling pointers reference freed memory, buffer overflows write past bounds; bounds checking and RAII prevent both classes.

ACID: atomicity (all or nothing), consistency (constraints preserved), isolation (concurrent transactions appear serial), durability (committed data survives failure).

Normalization: 1NF removes repeating groups, 2NF removes partial dependencies on a composite key, 3NF removes transitive dependencies, BCNF requires every determinant to be a candidate key.

Indexes speed reads but slow writes; a B+ tree index keeps all data in leaves linked for range scans, with height typically 3-4 for millions of rows.

SQL join semantics: INNER returns matches only, LEFT keeps all left rows with NULLs, FULL keeps unmatched rows from both sides.

A covering index contains all columns a query needs, so the engine answers from the index without touching the table (index-only scan).

Transaction isolation levels: read uncommitted allows dirty reads, read committed prevents them, repeatable read prevents non-repeatable reads, serializable prevents phantoms.

CAP theorem: under a network partition a distributed store chooses consistency or availability; PACELC extends this to latency trade-offs when no partition exists.

BASE (basically available, soft state, eventual consistency) is the common NoSQL alternative to ACID for horizontally scaled systems.

OSI seven layers: physical, data link, network, transport, session, presentation, application; TCP/IP collapses the top three into application.

TCP handshake is SYN, SYN-ACK, ACK; teardown uses FIN/ACK pairs; TCP guarantees ordered delivery, UDP does not and has lower overhead.

Subnetting: an IPv4 /n prefix leaves 32 - n host bits, giving 2^(32-n) addresses and 2^(32-n) - 2 usable hosts after network and broadcast.

DNS resolves names to addresses through recursive resolvers and authoritative servers; TTL controls caching duration.

TLS provides confidentiality, integrity, and server authentication using certificates; it does not by itself guarantee availability or hide traffic volume.

Symmetric encryption (AES) is fast for bulk data; asymmetric (RSA, ECC) solves key distribution; hybrid protocols use asymmetric to exchange a symmetric key.

Hashing (SHA-256) is one-way and detects tampering; salting and slow hashes (bcrypt, Argon2) defend stored passwords against rainbow tables.

OWASP-style defenses: parameterized queries stop SQL injection, output encoding stops XSS, CSRF tokens bind requests to a user session.

Defense in depth layers controls so a single failure is not fatal; least privilege limits blast radius; zero trust authenticates every request.

Availability in nines: 99.9% allows ~8.77 hours downtime per year, 99.99% ~52.6 minutes, 99.999% ~5.26 minutes.

Scalability: vertical scaling adds resources to one node, horizontal scaling adds nodes; horizontal needs stateless services or shared state management.

Load balancing algorithms: round robin, least connections, and consistent hashing, which minimizes key remapping when nodes join or leave.

Caching strategies: cache-aside reads on demand, write-through writes both layers, write-behind defers writes; every strategy must define invalidation.

Rate limiting protects services from overload; token bucket allows bursts, leaky bucket smooths output to a constant rate.

Reliability metrics: MTBF is mean time between failures, MTTR mean time to repair, availability = MTBF / (MTBF + MTTR).

Idempotency makes retries safe: GET, PUT, and DELETE are idempotent by HTTP semantics; POST is not unless a request key is used.

Queue-based load leveling absorbs spikes; backpressure signals producers to slow down rather than dropping work silently.

Observability rests on metrics, logs, and traces; percentiles (p95, p99) reveal tail latency that averages hide.

Software engineering codes of ethics (e.g., ACM/IEEE-CS) prioritize public safety, honesty about competence, and avoidance of conflicts of interest.

Intellectual property: copyright protects source code expression, patents protect novel processes, trade secrets protect confidential know-how; licenses govern reuse.

Open-source licenses: permissive (MIT, Apache-2.0) allow proprietary reuse; copyleft (GPL) requires derivative works to be distributed under the same terms.

Data protection principles (e.g., GDPR): lawfulness, purpose limitation, data minimization, accuracy, storage limitation, integrity, accountability.

Accessibility standards (WCAG) define conformance levels A, AA, AAA; level AA is the common legal and procurement baseline.

Quality standards: ISO/IEC 25010 defines product quality characteristics; ISO/IEC 12207 covers software life-cycle processes; ISO 9001 covers quality management.

Professional responsibility includes reporting safety-critical defects, documenting known risks, and refusing work beyond one's competence.

Audit and traceability: requirements should map to design, code, and tests so that changes and defects can be traced end to end.

Amdahl's law: speedup = 1 / ((1 - f) + f/s); the serial fraction 1 - f caps the maximum gain regardless of s.

Execution time = instruction count × CPI × clock cycle time; clock rate is the reciprocal of cycle time.

Five-stage pipeline (IF, ID, EX, MEM, WB) approaches CPI = 1; hazards are structural, data, and control.

Load-use data hazards need one stall even with forwarding; control hazards are reduced by branch prediction.

Average memory access time = hit time + miss rate × miss penalty, applied recursively down the cache hierarchy.

Miss classification: compulsory, capacity, and conflict; associativity reduces conflict misses without changing capacity misses.

Write-through vs write-back: write-back uses a dirty bit and lowers memory traffic; write-through simplifies coherence.

Little's law: L = λ × W, relating concurrency, arrival rate, and latency in queues and pipelines.

Two's complement n-bit range: -2^(n-1) to 2^(n-1) - 1; negation inverts all bits then adds one.

IEEE 754 single precision: 8 exponent bits with bias 127, 23 fraction bits; normalized value = (-1)^s × 1.f × 2^(e-127).

Floating-point addition is not associative; equality tests must use a tolerance epsilon rather than ==.

Signed overflow: adding two same-sign operands yields an opposite-sign result; unsigned overflow is a carry out of the MSB.

De Morgan: (A·B)' = A' + B' and (A + B)' = A'·B'; XOR = A'B + AB'.

Karnaugh maps group adjacent 1s in powers of two; don't-care cells may be included to enlarge groups.

Setup time requires data stable before the clock edge, hold time after it; the longest register-to-register path limits clock frequency.

A 2^k-input multiplexer needs k select lines; an n-to-2^n decoder with OR gates realizes any sum-of-products expression.

Turnaround = completion - arrival; waiting = turnaround - burst; response = first run - arrival.

SJF minimizes average waiting time; round robin bounds response time using a fixed time quantum.

Deadlock requires mutual exclusion, hold and wait, no preemption, and circular wait; breaking any condition prevents it.

Banker's algorithm admits a request only when a safe completion sequence exists for all processes.

Address translation splits a virtual address into page number and offset; the TLB caches translations and a miss triggers a page-table walk.

FIFO page replacement can show Belady's anomaly; LRU approximates optimal but needs reference bits or timestamps.

Thrashing means the working sets exceed available frames; the remedy is reducing the degree of multiprogramming.

Pipes are unidirectional byte streams; shared memory is fastest IPC but requires explicit synchronization.

Comparison sorting has an Ω(n log n) lower bound; quicksort averages O(n log n) but degrades to O(n^2) with poor pivots.

Merge sort is stable with O(n log n) worst case and O(n) extra space; heapsort is in place but unstable.

Building a binary heap from n elements is O(n); individual insert and extract-min are O(log n).

BFS gives shortest paths in unweighted graphs; Dijkstra needs non-negative weights; Bellman-Ford tolerates negative edges in O(VE).

Kruskal uses sorted edges plus union-find; Prim grows a tree from a start vertex using a priority queue.

Dynamic programming needs optimal substructure and overlapping subproblems; memoization is top-down, tabulation bottom-up.

Hash tables average O(1) but degrade as the load factor rises; chaining and open addressing are the two collision strategies.

Red-black and AVL trees both guarantee O(log n) height; AVL is stricter and rotates more frequently.

SOLID principles: single responsibility, open/closed, Liskov substitution, interface segregation, dependency inversion.

Aim for low coupling and high cohesion; hide representation behind a stable interface.

Test pyramid: many unit tests, fewer integration tests, fewest end-to-end tests; tests must be deterministic and order-independent.

TDD cycle: red, green, refactor; coverage measures executed code, not the strength of assertions.

Git: a branch is a movable pointer to a commit; merge preserves history with a merge commit, rebase rewrites commits onto a new base.

Scrum roles are product owner, scrum master, and developers; sprint length is fixed and new scope enters the backlog.

Code review targets correctness, readability, and design; small pull requests are reviewed faster and yield more defects.

Dangling pointers reference freed memory and buffer overflows write past bounds; RAII and bounds checking prevent both.

ACID: atomicity, consistency, isolation, durability; isolation makes concurrent transactions appear serial.

Normal forms: 1NF removes repeating groups, 2NF removes partial key dependencies, 3NF removes transitive dependencies, BCNF requires every determinant to be a candidate key.

B+ tree indexes keep all keys in linked leaves, making range scans efficient; height is typically 3-4 for millions of rows.

Join semantics: INNER returns matches, LEFT keeps all left rows with NULLs, FULL keeps unmatched rows from both sides.

A covering index holds every column a query needs, enabling an index-only scan without table access.

Isolation levels: read uncommitted permits dirty reads, read committed prevents them, repeatable read prevents non-repeatable reads, serializable prevents phantoms.

CAP theorem: during a network partition a distributed store trades consistency against availability.

BASE (basically available, soft state, eventual consistency) is the common NoSQL alternative to ACID.

OSI layers: physical, data link, network, transport, session, presentation, application; TCP/IP merges the top three.

TCP opens with SYN, SYN-ACK, ACK and closes with FIN/ACK pairs; UDP is connectionless with lower overhead.

An IPv4 /n prefix leaves 32 - n host bits: 2^(32-n) addresses and 2^(32-n) - 2 usable hosts.

DNS uses recursive resolvers and authoritative servers; record TTL controls caching duration.

TLS gives confidentiality, integrity, and server authentication via certificates; it does not guarantee availability.

AES is fast for bulk data; RSA and ECC solve key exchange; hybrid protocols use asymmetric cryptography to share a symmetric key.

SHA-256 is one-way and detects tampering; bcrypt and Argon2 slow down password guessing and require salts.

Parameterized queries stop SQL injection, output encoding stops XSS, and CSRF tokens bind requests to sessions.

Least privilege and defense in depth limit blast radius; zero trust authenticates every request regardless of network location.

99.9% availability permits about 8.77 hours of downtime per year; 99.99% about 52.6 minutes; 99.999% about 5.26 minutes.

Availability = MTBF / (MTBF + MTTR); reducing MTTR raises availability as effectively as lengthening MTBF.

Horizontal scaling adds nodes and needs stateless services; consistent hashing minimizes key remapping when nodes change.

Cache strategies: cache-aside, write-through, write-behind; each must define an invalidation rule.

Token bucket permits bursts up to bucket size; leaky bucket smooths output to a constant rate.

HTTP idempotency: GET, PUT, and DELETE are idempotent; POST is not unless a request key deduplicates retries.

Queue-based load leveling absorbs traffic spikes; backpressure slows producers instead of dropping work silently.

Observability uses metrics, logs, and traces; p95 and p99 expose tail latency hidden by averages.

Professional codes (ACM/IEEE-CS) prioritize public safety, honesty about competence, and disclosure of conflicts of interest.

Copyright protects code expression; patents protect novel processes; trade secrets protect confidential know-how.

Permissive licenses (MIT, Apache-2.0) allow proprietary reuse; copyleft (GPL) requires derivative works to carry the same terms.

GDPR principles: lawfulness, purpose limitation, data minimization, accuracy, storage limitation, integrity, accountability.

WCAG conformance levels are A, AA, and AAA; level AA is the usual legal and procurement baseline.

ISO/IEC 25010 defines product quality characteristics; ISO/IEC 12207 covers software life-cycle processes; ISO 9001 covers quality management.

Engineers must report safety-critical defects and decline work beyond their competence.

Traceability maps requirements to design, code, and tests so changes and defects can be followed end to end.