IRInterview Ready

CS Fundamentals

A condensed, interview-focused checklist of core computer science theory — complexity analysis, operating systems, networking, databases, and essential data structures. Inspired by jwasham/coding-interview-university.

Complexity Analysis

Big-O, Omega, Theta Notation

Asymptotic bounds describe how runtime/space scale with input size n. Big-O (upper bound) is most common in interviews; Omega (lower bound) and Theta (tight bound) appear in more formal discussions.

▾
Key points:
  • O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!) — memorize this ladder.
  • Drop constants and lower-order terms: O(2n + 5) → O(n), O(n² + n) → O(n²).
  • Multiplication for nested loops (O(n) inside O(m) → O(n·m)), addition for sequential blocks (O(n) then O(m) → O(n + m)).
  • Space complexity counts extra memory used beyond input — recursive call stack, hash maps, auxiliary arrays.
  • Big-Omega (Ω) is best-case lower bound, Theta (Θ) is tight bound when upper and lower match.
Common interview questions:
  • What's the time/space complexity of your solution?
  • Can you do better than O(n²)?
  • Why is quicksort O(n log n) on average but O(n²) worst-case?
Complexity Analysis

Amortized Analysis

Amortized complexity averages the cost of operations over a sequence — a single operation may be expensive, but the average cost per operation remains low.

▾
Key points:
  • Classic example: dynamic array append is O(1) amortized despite occasional O(n) resize — most appends are cheap, resizes are rare.
  • Three methods: aggregate (total cost / num operations), accounting (bank credits/debits), potential (energy function).
  • Union-Find with path compression + union by rank: O(α(n)) amortized per operation, where α is the inverse Ackermann function (effectively constant).
  • Splay trees: O(log n) amortized per operation despite O(n) worst-case for a single op.
Common interview questions:
  • Why is appending to a dynamic array O(1) amortized?
  • Explain Union-Find amortized complexity.
Operating Systems

Processes vs. Threads

Processes are independent execution contexts with isolated memory; threads are lightweight execution units within a process that share memory.

▾
Key points:
  • Process: separate address space, heavyweight context switch, IPC via pipes/sockets/shared memory.
  • Thread: shared address space, lighter context switch (no memory map reload), cheaper to spawn.
  • Context switch overhead: saving/restoring CPU registers, switching address space (for processes), cache invalidation.
  • User-space threads (green threads) are scheduled by the runtime (e.g. Go goroutines), not the OS kernel — lighter than kernel threads but can't exploit true parallelism unless multiplexed onto kernel threads.
Common interview questions:
  • When would you use threads vs. processes?
  • What happens during a context switch?
  • Why are threads cheaper than processes?
Operating Systems

Concurrency, Locks, & Deadlock

Concurrency primitives (mutexes, semaphores, condition variables) coordinate access to shared state; improper usage leads to race conditions, deadlocks, or starvation.

▾
Key points:
  • Mutex (mutual exclusion): only one thread holds the lock at a time. Use for critical sections.
  • Semaphore: generalized counter allowing N threads (N=1 is a mutex). Use for resource pools (e.g. DB connection limit).
  • Deadlock conditions (all four must hold): mutual exclusion, hold-and-wait, no preemption, circular wait.
  • Deadlock prevention: order locks globally (always acquire lock A before B), use timeouts, or design lock-free algorithms.
  • Race condition: outcome depends on non-deterministic thread interleaving. Fix with locks or atomic operations.
  • Condition variable: threads sleep until another thread signals a state change — avoids busy-waiting.
Common interview questions:
  • Explain deadlock and how to prevent it.
  • What's the difference between a mutex and a semaphore?
  • How would you debug a race condition?
Operating Systems

Memory Management & Virtual Memory

OS abstracts physical RAM via virtual memory (paging), giving each process an isolated address space and enabling swap to disk when RAM is full.

▾
Key points:
  • Virtual memory maps logical addresses (used by programs) to physical RAM via page tables; pages are typically 4KB.
  • Page fault: requested page isn't in RAM → OS loads it from disk (slow), possibly evicting another page (LRU, FIFO, etc.).
  • TLB (translation lookaside buffer): hardware cache of recent virtual→physical mappings — avoids expensive page table walk.
  • Stack vs. heap: stack grows down (function calls, local vars), heap grows up (malloc/new). Stack overflow happens when recursion is too deep or locals are too large.
  • Segmentation fault: program accesses unmapped or protected memory (null pointer dereference, buffer overflow).
Common interview questions:
  • What's a page fault and when does it happen?
  • Explain virtual memory.
  • Stack vs. heap — when do you use each?
Operating Systems

CPU Scheduling Algorithms

OS scheduler decides which process/thread runs next on the CPU — balancing fairness, throughput, and response time.

▾
Key points:
  • FCFS (First-Come, First-Served): simple, but long tasks block short ones (convoy effect).
  • Round-robin: each process gets a time slice (quantum), good for interactive systems but higher context-switch overhead.
  • Priority scheduling: highest-priority task runs first; risk of starvation for low-priority tasks unless you use aging.
  • Multi-level feedback queue (MLFQ): processes start in high-priority queue; if they use too much CPU, they're demoted — balances I/O-bound and CPU-bound workloads.
  • Real-time scheduling (EDF, RM): guarantees deadlines for hard real-time systems.
Common interview questions:
  • Explain round-robin scheduling.
  • What causes priority inversion?
Networking

TCP vs. UDP

TCP is reliable, ordered, connection-oriented (3-way handshake); UDP is unreliable, connectionless, lower latency — choose based on whether you need guarantees or speed.

▾
Key points:
  • TCP: 3-way handshake (SYN, SYN-ACK, ACK) to establish connection; retransmits lost packets; guarantees in-order delivery.
  • UDP: no handshake, no retransmissions, no ordering guarantee — just fire-and-forget datagrams.
  • TCP overhead: header is 20+ bytes, congestion control slows you down; UDP header is 8 bytes.
  • Use TCP for: HTTP, file transfer, anything where data loss is unacceptable.
  • Use UDP for: DNS, video streaming (can tolerate some packet loss), gaming (latency-sensitive).
Common interview questions:
  • When would you choose UDP over TCP?
  • Explain the TCP 3-way handshake.
  • What's TCP congestion control?
Networking

HTTP, HTTPS, & TLS

HTTP is the stateless request-response protocol powering the web; HTTPS adds TLS encryption on top to ensure confidentiality and integrity.

▾
Key points:
  • HTTP request: method (GET/POST/PUT/DELETE), URL, headers, optional body.
  • HTTP response: status code (2xx success, 3xx redirect, 4xx client error, 5xx server error), headers, body.
  • Stateless: server doesn't remember past requests by default; use cookies/tokens/sessions for state.
  • HTTPS = HTTP over TLS: encrypts payload, authenticates server (via certificate), prevents MITM attacks.
  • TLS handshake: client/server negotiate cipher suite, exchange keys, verify cert — adds 1-2 RTT latency.
  • HTTP/2: multiplexing (multiple requests per connection), server push, header compression (HPACK).
Common interview questions:
  • What's the difference between HTTP and HTTPS?
  • Explain a GET vs. POST request.
  • What are HTTP status codes 200, 404, 500?
Networking

DNS Resolution

DNS translates human-readable domain names (google.com) into IP addresses (142.250.80.46) via a hierarchical lookup chain.

▾
Key points:
  • Lookup flow: browser cache → OS cache → recursive resolver (ISP or 8.8.8.8) → root server → TLD server (.com) → authoritative nameserver → IP returned.
  • Record types: A (IPv4), AAAA (IPv6), CNAME (alias), MX (mail server), TXT (SPF, domain verification).
  • TTL (time to live): how long to cache the DNS result before re-querying.
  • DNS is UDP on port 53 by default (occasionally TCP for large responses or zone transfers).
Common interview questions:
  • Walk me through what happens when you type google.com in your browser (DNS is step 1).
  • What's the difference between A and CNAME records?
Networking

What Happens When You Type a URL

End-to-end browser flow: DNS lookup → TCP handshake → TLS handshake → HTTP request → server processing → HTTP response → HTML parse → render.

▾
Key points:
  • 1. DNS resolution: domain name → IP address.
  • 2. TCP 3-way handshake: establish connection with server.
  • 3. TLS handshake (if HTTPS): establish encrypted channel.
  • 4. HTTP request: browser sends GET /path with headers (User-Agent, cookies).
  • 5. Server processing: route request, query DB, generate HTML.
  • 6. HTTP response: server sends back HTML, status code, headers (Content-Type, Cache-Control).
  • 7. Browser parses HTML → constructs DOM → fetches CSS/JS/images (more requests) → paints pixels.
Common interview questions:
  • Walk me through what happens when you type a URL and hit Enter.
Networking

Load Balancing Basics

Load balancers distribute incoming traffic across multiple backend servers — improving availability, reliability, and throughput.

▾
Key points:
  • Algorithms: round-robin (cycle through servers), least connections (send to server with fewest active conns), IP hash (sticky sessions based on client IP).
  • Layer 4 (transport): routes based on IP/port, no visibility into HTTP — fast but dumb.
  • Layer 7 (application): routes based on HTTP path, headers, cookies — slower but smarter (can route /api → backend-api, /static → CDN).
  • Health checks: LB periodically pings backends; if a server fails checks, LB stops routing traffic to it.
  • Sticky sessions: pin a user to the same backend (via cookie or IP hash) — needed when servers hold session state, but hurts load distribution.
Common interview questions:
  • What's the difference between Layer 4 and Layer 7 load balancing?
  • Why would you use sticky sessions?
Databases

SQL vs. NoSQL Trade-offs

SQL (relational) enforces schema and ACID; NoSQL (document, key-value, wide-column, graph) trades consistency for flexibility and horizontal scalability.

▾
Key points:
  • SQL: structured schema, joins, ACID transactions, vertical scaling (harder to shard). Use for: banking, orders, structured data with complex queries.
  • NoSQL: schema-less or flexible schema, no joins (denormalize), eventual consistency (often), horizontal scaling (easy). Use for: logs, user profiles, high write throughput, semi-structured data.
  • Document stores (MongoDB): store JSON-like docs, query by nested fields.
  • Key-value (Redis, DynamoDB): O(1) lookups by key, no complex queries.
  • Wide-column (Cassandra, Bigtable): optimized for writes, partition key + sort key, eventual consistency.
  • Graph (Neo4j): model relationships as first-class citizens, traverse edges efficiently.
Common interview questions:
  • When would you use SQL vs. NoSQL?
  • Explain CAP theorem (Consistency, Availability, Partition-tolerance — pick 2).
Databases

Database Indexing

Indexes speed up queries (O(log n) via B-tree or O(1) via hash) at the cost of slower writes and extra storage.

▾
Key points:
  • B-tree index (default in Postgres, MySQL): ordered, supports range queries (BETWEEN, <, >), O(log n) lookups.
  • Hash index: O(1) exact-match lookups, no range support.
  • Composite index: index on (A, B) helps WHERE A=x AND B=y or WHERE A=x, but NOT WHERE B=y alone (leftmost prefix rule).
  • Covering index: index contains all columns in the query → no table lookup needed.
  • Trade-off: indexes speed reads but slow writes (every INSERT/UPDATE must also update the index) and use disk space.
Common interview questions:
  • Explain how a B-tree index works.
  • Why might adding an index slow down writes?
  • What's a covering index?
Databases

ACID Transactions

ACID guarantees ensure database transactions are reliable even in the face of crashes, concurrency, or errors.

▾
Key points:
  • Atomicity: all-or-nothing — if any part of the transaction fails, the whole thing rolls back.
  • Consistency: transaction moves DB from one valid state to another (constraints, foreign keys, triggers all respected).
  • Isolation: concurrent transactions don't interfere with each other. Levels: Read Uncommitted < Read Committed < Repeatable Read < Serializable.
  • Durability: once a transaction commits, it survives crashes (written to disk, replicated, or in WAL).
  • Isolation anomalies: dirty read (read uncommitted data), non-repeatable read (same row changes mid-transaction), phantom read (new rows appear mid-transaction).
Common interview questions:
  • Explain ACID.
  • What's the difference between isolation levels?
  • What's a dirty read?
Databases

Normalization vs. Denormalization

Normalization reduces redundancy by splitting data into related tables (joins required); denormalization duplicates data to avoid joins and speed up reads.

▾
Key points:
  • Normalization (1NF, 2NF, 3NF, BCNF): eliminate duplicate data, rely on foreign keys and joins. Pro: data integrity, disk savings. Con: slower reads (join overhead).
  • Denormalization: duplicate frequently-queried data to avoid joins. Pro: faster reads, simpler queries. Con: update anomalies (must update multiple places), more storage.
  • 3NF in practice: every non-key column depends only on the primary key, not on other non-key columns.
  • When to denormalize: read-heavy workloads (analytics, caches), data rarely changes, or you're already using NoSQL (which doesn't support joins).
Common interview questions:
  • What's database normalization?
  • When would you denormalize a schema?
Data Structures & Algorithms

Arrays & Linked Lists

Core linear structures: arrays for random access, linked lists for efficient insertion/deletion.

▾
Key points:
  • Array: O(1) random access, O(n) insert/delete (must shift elements), contiguous memory (cache-friendly).
  • Linked list: O(n) access (must traverse), O(1) insert/delete if you have the pointer, extra memory for pointers.
  • Dynamic array (vector, ArrayList): amortized O(1) append, occasional O(n) resize.
  • Use array when: random access, iteration speed, known/bounded size. Use linked list when: frequent insert/delete, unknown size, no need for random access.
Common interview questions:
  • When would you use a linked list over an array?
Data Structures & Algorithms

Hash Tables

O(1) average-case insert/lookup via hashing; collision handling (chaining or open addressing) keeps performance degradation bounded.

▾
Key points:
  • Hash function maps key → integer → array index. Good hash: deterministic, uniform distribution, fast.
  • Collision resolution: chaining (linked list at each bucket) or open addressing (linear probing, quadratic probing).
  • Load factor = n/m (items/buckets). Rehash (resize + re-insert all keys) when load factor exceeds threshold (~0.75).
  • Worst-case O(n) if all keys collide (bad hash or adversarial input), but amortized O(1) with good hash and rehashing.
Common interview questions:
  • How does a hash table work?
  • What happens when two keys collide?
Data Structures & Algorithms

Trees (BST, AVL, Red-Black, Heaps)

Trees organize hierarchical data; balanced trees guarantee O(log n) ops, heaps give O(log n) insert/delete-min.

▾
Key points:
  • Binary search tree (BST): left < parent < right. O(log n) search/insert/delete if balanced, O(n) if skewed.
  • AVL tree: self-balancing via rotations, height difference ≤1 for every node. Strict balance → faster reads, slower writes.
  • Red-black tree: looser balance rules (black-height property), faster writes than AVL. Used in C++ std::map, Linux kernel.
  • Heap: complete binary tree, parent ≥ children (max-heap) or parent ≤ children (min-heap). O(log n) insert/delete-min, O(1) peek-min. Used for priority queues.
  • Trie: prefix tree for strings, O(m) insert/lookup where m = key length. Use for autocomplete, prefix matching.
Common interview questions:
  • Explain a binary search tree.
  • What's the difference between AVL and red-black trees?
  • How does a heap work?
Data Structures & Algorithms

Graphs (Representation & Traversal)

Graphs model relationships; adjacency list (space-efficient for sparse graphs) vs. adjacency matrix (fast edge lookup).

▾
Key points:
  • Adjacency list: map each node → list of neighbors. Space O(V + E), check if edge exists O(degree(v)).
  • Adjacency matrix: 2D array, matrix[u][v] = 1 if edge exists. Space O(V²), check edge O(1).
  • DFS (depth-first search): explore as far as possible before backtracking. Use stack (or recursion). Good for: pathfinding, cycle detection, topological sort.
  • BFS (breadth-first search): explore neighbors level by level. Use queue. Good for: shortest path (unweighted), level-order traversal.
  • Dijkstra: shortest path in weighted graph (non-negative weights), O((V + E) log V) with min-heap.
Common interview questions:
  • Explain BFS vs. DFS.
  • How would you detect a cycle in a graph?
Data Structures & Algorithms

Sorting Algorithms

Know comparison-based sorts (O(n log n) lower bound) vs. linear-time sorts (counting, radix) and when to use each.

▾
Key points:
  • Quicksort: O(n log n) average, O(n²) worst-case (bad pivot), in-place, unstable. Default in many stdlib implementations.
  • Mergesort: O(n log n) guaranteed, O(n) extra space, stable. Use when stability or worst-case guarantee matters.
  • Heapsort: O(n log n) guaranteed, in-place, unstable. Less cache-friendly than quicksort.
  • Counting sort: O(n + k) where k = range of input values. Use when keys are small integers.
  • Radix sort: O(d(n + k)) where d = num digits. Use for fixed-length strings or integers.
Common interview questions:
  • Explain quicksort. Why is it O(n²) worst-case?
  • When would you use merge sort over quicksort?