CS Fundamentals

A process is an isolated running program with its own address space, file descriptors, and resources. A thread is a unit of execution inside a process; threads share that process’s memory and open files. Creating a process is expensive (new address space); creating a thread is cheap. Shared memory is why threads need locks — two threads writing the same variable without synchronization is a race.

A process moves through a small set of states: new (created), ready (waiting for CPU), running (on a core), waiting/blocked (I/O or a lock), and terminated. The scheduler picks from ready; a blocking syscall moves running → waiting; I/O completion moves waiting → ready. Interviewers want the transitions, not a memorized diagram.

A context switch is the OS saving one thread/process’s CPU state (registers, program counter, stack pointer) and loading another’s so it can run. It happens on timer interrupts, blocking syscalls, and preemption. It is expensive because of register save/restore, cache/TLB disruption, and (for processes) address-space switches. Threads in the same process are cheaper to switch than processes.

The CPU scheduler decides which ready process runs next. FCFS is fair but can convoy (a long job blocks short ones). SJF/SRTF minimize average wait but need burst estimates and can starve long jobs. Round Robin gives each a time slice — good for interactive work. Priority scheduling can starve unless you age waiting jobs. Know when each fails, not just the names.

A mutex is a lock that only one thread can hold at a time, protecting a critical section. The thread that locks it must unlock it — unlike a semaphore, you cannot “unlock” on behalf of someone else. If you forget to unlock (or throw before unlock), other threads wait forever. Use it when the invariant is “only one thread may touch this data.”

A semaphore is a counter with wait (P/down) and signal (V/up). A binary semaphore is 0/1 and looks like a lock, but any thread may signal — so it is not a mutex. A counting semaphore tracks N resources (buffer slots, connections). Classic use: producer-consumer, where empty/full counts wake the other side. Interview distinction: mutex has an owner; semaphore does not.

A race condition is when the result depends on which thread wins the timing — typically two threads read-modify-write the same variable without a lock, and one update is lost. Races are bugs you cannot reliably reproduce. Locks, atomics, and not sharing data are the fixes. If two threads can see the same memory, assume you need a story for how it stays consistent.

Deadlock is when threads wait forever because each holds a lock the other needs. Four Coffman conditions must all hold: mutual exclusion, hold-and-wait, no preemption, circular wait. Break any one (lock ordering is the usual fix) and deadlock cannot happen. Prevention designs the system so a condition cannot hold; avoidance (Banker’s) is rarely used in apps; detection finds cycles and aborts. Interviewers want an example, the four conditions, and lock ordering.

Virtual memory gives each process its own address space: pointers in your program are virtual addresses that the MMU translates to physical RAM (or disk). The OS can overcommit, isolate processes, and map the same library into many processes. A process cannot read another’s memory by guessing addresses. Page tables and the TLB are how translation stays fast.

Paging splits virtual memory into fixed-size pages and physical RAM into frames of the same size. A page table maps page → frame (or “not in RAM”). The TLB caches recent translations so you do not walk the page table on every load/store. Internal fragmentation is at most almost one page per mapping. Demand paging loads a page only when you first touch it.

A page fault is a trap when the CPU accesses a virtual page that is not currently mapped the way the process needs. A minor fault is cheap (page is already in RAM — maybe shared or not yet mapped). A major fault must read from disk (or the swap file) — that is why “thrashing” kills performance. The OS finds a free frame, loads the page, updates the page table, and restarts the instruction.

The stack holds function frames: locals, arguments, return addresses. It grows and shrinks with calls; allocation is a pointer bump, and it is per-thread. The heap is for data whose lifetime is not a single call — malloc/new, objects in Java. Heap allocation is slower and can fragment; forgetting to free (C++) or holding references (Java) leaks. Recursion depth is limited by stack size; large objects belong on the heap.

CPUs run in privilege levels. User mode is where your app runs: it cannot change page tables, talk to devices, or halt the machine. Kernel mode is where the OS runs those privileged operations. A syscall or interrupt is the controlled switch into kernel mode. This split is why a crashing app should not take down the whole system.

A system call is the API from user space to the kernel: open a file, read, fork, mmap, send a packet. The process traps (syscall instruction), the kernel validates arguments, does the work, and returns. Library functions like printf often wrap syscalls (write). You cannot implement true isolation or I/O in pure user code — that is the point of the boundary.

A primary key uniquely identifies every row and cannot be NULL. A table has at most one. It is the default target for foreign keys and the clustered index in many engines (MySQL InnoDB). Prefer a stable key (often a surrogate id) so updates do not cascade through the schema. Uniqueness without “the” primary key is a unique constraint or candidate key.

A foreign key is a column (or set) that must match a candidate/primary key in another table — or be NULL if allowed. That is referential integrity: you cannot orphan a child row pointing at a missing parent. ON DELETE RESTRICT/NO ACTION refuses to delete a parent with children; CASCADE deletes children too; SET NULL clears the pointer. Pick CASCADE only when the child has no meaning without the parent.

A candidate key is a minimal set of columns that uniquely identifies a row — drop any column and uniqueness breaks. A table can have several (email and user_id). You pick one as the primary key; the others stay as unique constraints. Superkeys include extra columns and are not minimal.

Normalization is splitting tables so each fact is stored once, which prevents update/insert/delete anomalies. 1NF: atomic cells, no repeating groups. 2NF: no partial dependency on a composite key. 3NF: no transitive dependency (non-key → non-key). BCNF is a stricter 3NF. You denormalize later for read performance — know why you are doing it, not as a default.

A transaction is a group of reads/writes that must succeed or fail together. BEGIN starts it, COMMIT makes it durable and visible (per isolation), ROLLBACK undoes it. If the process crashes mid-transaction, the database restores the previous committed state. Use a transaction whenever “half of this update” would leave the data wrong (transfer money, place an order and decrement stock).

ACID is the contract for transactions. Atomicity: all statements commit or none do (transfer both accounts). Consistency: constraints and invariants hold after commit (FK, checks). Isolation: concurrent transactions do not see each other’s dirty work (level-dependent). Durability: after COMMIT, a crash does not lose the write (WAL). Interviewers want a one-line example for each letter, not the acronym only.

Isolation levels trade consistency for concurrency. Read uncommitted can dirty-read. Read committed (Postgres default) sees only committed data but non-repeatable reads and phantoms are possible. Repeatable read freezes the snapshot of rows you already read (Postgres also prevents phantoms via snapshots). Serializable behaves as if transactions ran one after another — may abort with serialization failures you must retry. Name the anomalies each level still allows.

A dirty read is seeing another transaction’s uncommitted write. If that transaction rolls back, you acted on data that never existed. Read uncommitted allows this; higher levels do not. This is why production databases almost never use read uncommitted.

A non-repeatable read is when you SELECT the same row twice in one transaction and get different committed values because another transaction committed an UPDATE in between. Read committed allows this; repeatable read and serializable do not (you keep your snapshot of that row). Distinct from dirty reads (uncommitted) and phantoms (new rows).

A phantom is when a second query in the same transaction sees new rows that match your WHERE clause because another transaction committed an INSERT. You did not re-read a changed row — the set of rows grew. Range locks or snapshot isolation are how engines prevent this. Interviewers pair this with non-repeatable reads to see if you know the difference.

Databases lock rows (or keys/pages) so concurrent transactions do not corrupt data. Shared (read) locks can coexist; exclusive (write) locks do not. Deadlocks happen when A waits for B’s lock and B waits for A’s — the engine aborts one victim. Keep transactions short, lock in a consistent order, and do not hold locks while calling slow external APIs.

An index is extra structure (usually a B+ tree) that lets the engine find rows without scanning the table. Reads and ORDER BY/JOIN can get much faster; every INSERT/UPDATE/DELETE must maintain the index, so writes get slower. Index columns you filter and join on; skip low-selectivity columns (boolean flags) and tables that are tiny. Too many indexes is a real production problem.

A B-tree keeps keys in a wide, balanced tree so lookups are O(log n) disk I/Os, which matters because disks are slow. A B+ tree stores all row pointers in the leaf level and links leaves, so range scans (WHERE x BETWEEN) walk sequentially. That is why default indexes are B+ trees, not binary trees in RAM. Hash indexes only help equality, not ranges.

A clustered index is the table itself sorted by the key (InnoDB primary key): one clustered index per table. A secondary/non-clustered index is a separate tree that points to rows (by PK in InnoDB, by heap tid in Postgres). Postgres tables are heaps; all indexes are secondary. The interview point: clustered defines physical order; you cannot have two clustered indexes.

A join combines rows from two tables using a condition. INNER keeps matches only. LEFT keeps all left rows (NULL-padded if no match). RIGHT is the mirror. FULL keeps both sides. CROSS is every combination. Engines pick nested loop (good if one side is tiny or indexed) or hash join (build a hash of the smaller side). Write the join you mean; do not filter a LEFT JOIN in WHERE so it accidentally becomes INNER.

A view is a named SELECT stored in the catalog. Querying it runs that SQL (or a rewritten plan). Views simplify APIs and hide columns; they are not a copy of the data unless you materialize them. Simple views can be updatable; joins and aggregates usually are not. Use views for a stable interface, not as a substitute for indexes.

SELECT lists the columns (or expressions) you want — projection. FROM is the source; without WHERE you get every row. DISTINCT removes duplicate result rows after projection. Aliases (AS) name expressions for the client and for ORDER BY. SELECT * is fine while exploring; in production, name columns so schema changes do not surprise you.

WHERE filters rows before grouping. AND/OR combine predicates; IN tests a set; LIKE is pattern match. NULL is not equal to anything — use IS NULL / IS NOT NULL, never = NULL. WHERE cannot see aliases defined in the same SELECT list in most engines. Put row filters here; put aggregate filters in HAVING.

GROUP BY collapses rows that share the same key into one output row. Every selected column must be in the GROUP BY or inside an aggregate (COUNT, SUM, …). That rule is the usual interview gotcha. Grouping happens after WHERE. Use it to answer “per customer / per day / per category” questions.

HAVING filters groups after aggregation. WHERE cannot use COUNT(*) because rows are not grouped yet. Example: customers with more than 5 orders — GROUP BY customer_id HAVING COUNT(*) > 5. You can still use WHERE to drop rows before they enter a group. Interview line: WHERE filters rows, HAVING filters groups.

ORDER BY sorts the result set; without it, row order is undefined. You can sort by multiple columns (priority, then name) and choose ASC/DESC. NULLs sort first or last depending on the engine — Postgres lets you say NULLS LAST. Sorting large results is expensive; indexes that match the ORDER BY can avoid a filesort.

In SQL, JOIN is how you combine related tables in one query instead of looping in application code. Start from the table that defines the grain of the answer, then INNER/LEFT join lookup tables on keys. Draw the tables and the key first; then write the ON clause. Most interview SQL is “join these tables, then group.” Practice until you do not freeze on LEFT vs INNER.

A subquery is a SELECT nested in another statement. Scalar subqueries return one value; IN / EXISTS test a set. A correlated subquery references the outer row and runs logically per row — powerful and easy to make slow. EXISTS stops at the first match; prefer it over IN when you only care about existence. Many subqueries rewrite as joins; pick the form you can still explain.

A CTE (WITH name AS (SELECT …)) names a subquery so the main query stays readable and you can reference it more than once. It is the same result as nesting, not a magic performance boost (Postgres can inline it). Use CTEs to break “top customers last month who also …” into steps. Recursive CTEs walk trees/graphs — know they exist; you rarely need them in a fresher round.

A window function computes over related rows without collapsing them like GROUP BY. OVER (PARTITION BY … ORDER BY …) defines the window. ROW_NUMBER() unique-ranks; RANK() ties leave gaps; SUM() OVER running totals. Classic use: “latest row per user” (ROW_NUMBER = 1) and running totals. You keep every input row, with extra columns — that is the difference from GROUP BY.

Aggregates collapse many rows into one value: COUNT, SUM, AVG, MIN, MAX. COUNT(*) counts rows; COUNT(col) skips NULLs in that column — a frequent trick question. Aggregates ignore NULLs except COUNT(*). Combine with GROUP BY for per-group stats. AVG of integers may truncate depending on the engine; CAST if you need a decimal.

OSI is a seven-layer teaching model: Physical, Data Link, Network, Transport, Session, Presentation, Application. Real networks run TCP/IP, so map OSI to what you actually use: IP is network, TCP/UDP transport, HTTP application. Interviewers want “which layer is IP / TCP / HTTP / Ethernet,” not a recitation of all seven names with nothing attached.

TCP/IP (the Internet model) is four layers: Link, Internet (IP), Transport (TCP/UDP), Application (HTTP, DNS, …). It is what packets on the public internet actually follow. OSI Session/Presentation are folded into the application layer here. When someone says “layer 4 vs layer 7 load balancer,” they are mixing OSI numbering with this stack — L4 is TCP/UDP, L7 is HTTP.

TCP is a connection-oriented byte stream: handshake, ordered delivery, retransmission, congestion control. UDP is datagrams with no connection and no delivery guarantee — just send. Use TCP for files, HTTP, databases. Use UDP when latency matters more than a lost packet (video, games) or when the app implements retry (DNS). “Reliable” means TCP’s contract, not that the network never fails.

To open a TCP connection both sides must agree on initial sequence numbers. Client sends SYN, server replies SYN-ACK, client sends ACK — three segments. Two is not enough: the last ACK proves the client received the server’s sequence number. After this, data can flow both ways. Interviewers often ask why not two-way and what a SYN flood is (half-open connections).

TCP close is four-way because each direction of the byte stream is shut down separately: FIN, ACK, FIN, ACK. TIME_WAIT keeps the closer’s port reserved so delayed packets from the old connection are not applied to a new one with the same 4-tuple. That is why you sometimes see many sockets in TIME_WAIT after a busy client. Half-close (FIN one way, still sending the other) is allowed.

HTTP is a request/response protocol: method, path, headers, optional body in; status, headers, body out. The server does not remember you between requests unless you send cookies or tokens — that is “stateless.” HTTP/1.1 runs on TCP; browsers reuse connections. Know that headers are metadata (Content-Type, Authorization) and that caching/proxies reason about methods and headers.

HTTPS is HTTP inside a TLS tunnel: the bytes on the wire are encrypted and authenticated, and the client checks the server’s certificate. Plain HTTP can be read or altered by anyone on the path (Wi-Fi, ISP). HTTPS does not hide that you talked to a host (SNI/DNS still leak) but it hides paths, cookies, and bodies. Port 443 vs 80 is the usual split.

Methods declare intent. GET reads and should be safe (no side effects) and idempotent. POST creates or triggers work and is not idempotent by default. PUT replaces a resource at a URL (idempotent). PATCH partial-updates. DELETE removes (idempotent). Idempotent means repeating the same request leaves the same server state. Interviewers use this to see if you will retry GET vs POST blindly.

Status codes tell the client what happened. 2xx success (200 OK, 201 created, 204 no body). 3xx redirect (301 permanent). 4xx the client was wrong (400 bad request, 401 unauthenticated, 403 authenticated but forbidden, 404 missing, 409 conflict, 429 rate limit). 5xx the server failed (500). Do not return 200 with an error JSON if you can use the right class — load balancers and clients branch on the code.

DNS maps names to data: A/AAAA to IPs, CNAME to another name, MX to mail hosts. Your stub resolver asks a recursive resolver, which walks the hierarchy (root → TLD → authoritative) if the answer is not cached. TTL is how long a record may be cached — low TTL means faster updates, more queries. Without DNS, browsers would need raw IPs. Interview story: type a URL → DNS lookup before any TCP.

IP is the internet’s addressing and routing layer. IPv4 is 32-bit addresses; IPv6 is 128-bit. Private ranges (10/8, 192.168/16, …) are not routed on the public internet; NAT lets many devices share one public IPv4 address by rewriting ports. Packets are routed hop-by-hop toward the destination IP. TCP/UDP sit on top and add ports so many apps share one host.

A port is a 16-bit number that multiplexes connections on one IP. Servers listen on well-known ports (80 HTTP, 443 HTTPS, 22 SSH, 5432 Postgres). Clients use ephemeral ports allocated by the OS for the source side of a connection. A TCP connection is a 4-tuple: src IP, src port, dst IP, dst port. Firewalls and security groups allow or deny by port.

Cookies are small key-value data the server sends with Set-Cookie and the browser returns on later requests to that site. HttpOnly blocks JavaScript access (helps against XSS stealing sessions). Secure sends only over HTTPS. SameSite (Lax/Strict/None) controls cross-site sending and is the main CSRF lever today. Cookies are how classic server sessions remember you on a stateless protocol.

After login, the server must recognize you on the next request. A server-side session stores user id in Redis/DB and gives the browser an opaque cookie. A JWT puts claims in a signed token the client sends (often Authorization header) — the server verifies the signature and may not look up a session. Sessions are easy to revoke; JWTs need short expiry or a blocklist. “How does login work?” is cookie or token plus a secret the client cannot forge.

REST is a style: URLs name resources (nouns), HTTP methods are the verbs, status codes report outcome, and the server stays stateless between requests. /users/42 plus GET/PATCH/DELETE is the usual shape. You do not store client conversation in server memory; you send enough in the request (auth, ids). Real APIs bend the rules; interviewers still want resource-oriented design vs one RPC dump at /api.

TLS (successor of SSL) encrypts a TCP connection and authenticates the server with a certificate issued by a CA the client trusts. The handshake agrees on keys; then HTTP (or other) runs inside. The padlock means “this TLS session looks valid,” not “the site is honest.” Certificate expiry and hostname mismatch are why browsers scream. HTTPS is HTTP + TLS.

The browser parses the URL, checks cache, then DNS-resolves google.com to an IP. It opens a TCP connection to 443, completes a TLS handshake, and sends an HTTP GET. The server responds with HTML; the browser parses it, fetches CSS/JS/images (more DNS/TCP/TLS as needed), runs JS, and paints. Mention HSTS, HTTP/2 multiplexing, and CDN anycast if you have time — the spine is DNS, TCP, TLS, HTTP, render.

A class is the blueprint: fields (state) and methods (behavior). An object is a live instance with its own field values. new Car() creates an object of type Car. Interviewers want this split before inheritance and SOLID. In Java, a class also defines a type; in JS, prototypes play a similar role.

Encapsulation hides internal state and exposes a small API so invariants stay true. Private fields plus public methods (getters that do not leak mutability, operations that keep balances non-negative) are the usual form. It is not “make everything private for the sake of it” — it is so callers cannot break the object’s rules. LLD interviews fail when every field is public.

Abstraction means showing what something does, not how. A List add() contract does not mention arrays vs linked nodes. Interfaces and abstract classes are the language tools. Good abstraction lets you swap implementations (file logger vs network logger) without rewriting callers. Too much abstraction too early is also a smell — start from the real types in the problem.

Inheritance is IS-A: a subclass reuses and specializes a superclass. It helps when the subtype truly is that type and you want polymorphism. It hurts when you inherit just to reuse code (fragile base class, wrong taxonomy). Prefer a shallow hierarchy. Interview contrast: inheritance vs composition — if it is HAS-A, do not extend.

Polymorphism means the same message can run different code. Runtime polymorphism is overriding: a Vehicle reference calling start() hits Car or Bike. Compile-time polymorphism is overloading: same name, different parameter types, resolved at compile time. LLD uses runtime polymorphism so you can add a new subtype without rewriting the loop that calls the interface.

Composition is HAS-A: a Car has an Engine. You reuse by delegating, not by extending. Inheritance couples you to the parent’s internals and lifecycle. Default to composition; inherit only for true IS-A with a stable parent. “Favour composition over inheritance” is the line interviewers want, with one example of each.

An interface is a contract of methods a type must implement. A class can implement many interfaces (multiple inheritance of type, not of state). Callers depend on the interface so you can swap implementations. Java default methods add shared behavior without a class hierarchy. Use interfaces at boundaries (PaymentProvider, FeeStrategy); do not make an interface for every class.

An abstract class can hold fields and some implemented methods, and cannot be instantiated. Subclasses fill in the abstract parts. Use it when implementations share state or a template of steps (template method). Use an interface when you only need a contract and may mix several. Java: one superclass, many interfaces — that often decides the design.

Overloading is several methods with the same name and different parameter lists in one class. The compiler picks which one based on the argument types. Return type alone cannot distinguish overloads. It is convenience (print(int) vs print(String)), not runtime dispatch. Do not confuse it with overriding.

Overriding replaces a parent method in a subclass with the same signature. Calls on a parent-typed reference run the subclass version (virtual dispatch). @Override catches signature mistakes. super.method() calls the parent version. Access cannot be more restrictive; in Java, you cannot override static or private methods in the polymorphic sense.

SOLID is five design checks. SRP: one reason to change. OCP: add behavior by extension, not by editing a switch forever. LSP: subtypes must honor the parent contract (no Square that breaks Rectangle). ISP: small interfaces, not one fat one. DIP: depend on abstractions (FeeStrategy), not on a concrete UPI class. Quote one sentence and one example per letter in LLD rounds.

Exceptions are a control path for failures. try/catch handles them; finally (or try-with-resources) always cleans up. Java checked exceptions must be declared or caught; unchecked (RuntimeException) are for programming bugs. Do not catch and ignore — log, translate, or retry with a policy. Catch the specific type you can handle; let the rest bubble to a boundary.

Generics parameterize types: List<String> is a list the compiler knows holds String, so you avoid casts and ClassCastException. The type parameter is erased at runtime on the JVM, which is why you cannot new T() easily. Wildcards (? extends / super) appear in APIs. Raw List is the pre-generics hole — do not use it in new code.

The collections library is the default data structures: List (ordered, duplicates), Set (unique), Map (key → value). ArrayList is a resizable array — random access O(1), insert in the middle O(n). LinkedList is rarely the right default. HashMap is average O(1) get/put, unordered; TreeMap is sorted keys, O(log n). Pick by access pattern. This is asked in every Java interview and shows up in LLD as “what does this class store?”