CAP theorem
~11 minTwo data centres hold the same data. The link between them breaks. Each must now answer from its own copy, or refuse. CAP is the proof that there is no third way.
Answer the computer science fundamentals round by explaining why, not reciting definitions. Covers data structures and algorithms, computation theory, concurrency and memory, databases, and distributed systems.
3197 of 3197 questions in your plan: 0 known, 0 in progress, 0 due, 0 skipped, 3197 new. 0 cut, outside your plan.
Outside early-career hiring, fundamentals rarely get a round of their own. New-graduate loops often open with a screen of short theory questions; elsewhere the subject is spread across the rounds that exist anyway: the coding round is graded on structures and cost, the design round leans on replication and caching, and a backend conversation reaches for threads, transactions and the network. One prompt crosses all of them, what happens between typing an address and the page appearing, because it goes as deep as the candidate can take it: the DNS lookup, the TCP and TLS handshakes, the HTTP exchange, the work behind the server. Level shows less in the question than in where the follow-ups stop. That a hash table finds a key in constant time is an entry-level answer; the next question is what that average assumes, and the one after it is what an attacker who picks colliding keys does to the table, which is why Python randomizes its string hashes per process and Java's `HashMap` turns an overlong bucket into a tree. The same descent runs through the plan, from why a database index is a B-tree rather than a binary search tree (one page read per level, not per comparison) to which direction a reduction must run to show a new problem NP-hard. Credit goes to a guarantee stated at its true strength, with the input that breaks it.
The plan opens on mathematics, the language most later modules argue in. [Discrete mathematics](/topics/found-discrete-math) supplies induction, counting and the vocabulary of graphs, and [probability](/topics/found-math-statistics-probability) the expected-case reasoning behind hashing and randomized pivots; modular arithmetic from the first module returns near the end, under public-key cryptography. Data structures start where memory is contiguous. [Arrays](/topics/found-dsa-arrays-strings) explain why a scan is fast, and most of what follows either links nodes by pointer or reads an array differently, as a heap does; [hash tables](/topics/found-dsa-hash-tables) use both, and [graphs](/topics/found-dsa-graphs) close the stretch by reusing the stack and the queue in their traversals. Only then does the plan stop to measure: [complexity analysis](/topics/found-dsa-complexity) arrives with structures in hand to cost and goes straight to work on sorting and binary search. Recursion is induction run as code, which is where the first module pays off again; the two ways of taming it follow, [dynamic programming](/topics/found-dsa-dynamic-programming), which caches overlapping subproblems, and greedy choice, which works only when the locally best step never has to be undone. Then the question changes from how fast to whether at all. [Automata and languages](/topics/found-automata-languages) rank machines by what they can recognize, and [complexity classes](/topics/found-complexity-classes) rank problems the same way, ending on how to cope with a hard one using the paradigms just covered. [Information theory](/topics/found-information-theory) sets the floor on how small data can get, and [serialization](/topics/found-serialization) turns that into bytes crossing a process boundary, where the plan leaves pure theory. From there it describes a running system from one process outward. [Concurrency](/topics/found-concurrency) and memory management cover threads sharing a heap and who reclaims it. Databases follow because [transactions and isolation](/topics/db-relational-transactions) are concurrency control with durability added, and their indexes are the disk-oriented trees met earlier. The network stretch goes from the layer model through the protocols a request touches, [TCP](/topics/proto-tcp) first, to how a server pushes to a browser. [Distributed systems](/topics/found-distributed-systems-core-theory) join the database and the network, taking consensus, clocks and delivery semantics before the building blocks a design round draws. The close steps back from the machine. [Cryptography](/topics/found-appsec-cryptography) follows the network because TLS is where its primitives meet a connection, and software design ends the plan: how code is organized rather than what it computes.
Where to open the plan depends on how you came to it. A recent graduate has met most of the first half in coursework and tends to lose points in the second, on what lectures seldom reached, such as the isolation level a transaction actually ran at. Begin at Processes & Memory and return to the structures only to drill. A developer who learned on the job has the reverse profile: the math, analysis and theory at the top are the gap, and they build on one another closely enough that by topics, not by frequency, is the order to read them in. If asymptotic notation is not yet automatic, read complexity analysis before the structures, even though the plan places it after them. With days rather than weeks before a fundamentals screen, narrow level so that it stops at the band you are interviewing at: the upper levels here ask which guarantee a design depends on, not what a structure costs, and a short screen rarely gets that far. Importance narrowed to must know does the rest. The craft of the coding round sits outside this plan: it has no module on the recurring problem patterns those rounds are built from, or on working a problem aloud from its first minute, and [Data Structures & Algorithms](/roadmaps/datastructures-and-algorithms) is the roadmap built around exactly that. The plan's distributed stretch also stops at the building blocks; assembling them under an open-ended prompt is the subject of the [System Design roadmap](/roadmaps/system-design).
Two data centres hold the same data. The link between them breaks. Each must now answer from its own copy, or refuse. CAP is the proof that there is no third way.
Outside early-career hiring, fundamentals rarely get a round of their own. New-graduate loops often open with a screen of short theory questions; elsewhere the subject is spread across the rounds that exist anyway: the coding round is graded on structures and cost, the design round leans on replication and caching, and a backend conversation reaches for threads, transactions and the network. One prompt crosses all of them, what happens between typing an address and the page appearing, because it goes as deep as the candidate can take it: the DNS lookup, the TCP and TLS handshakes, the HTTP exchange, the work behind the server.
Level shows less in the question than in where the follow-ups stop. That a hash table finds a key in constant time is an entry-level answer; the next question is what that average assumes, and the one after it is what an attacker who picks colliding keys does to the table, which is why Python randomizes its string hashes per process and Java's HashMap turns an overlong bucket into a tree. The same descent runs through the plan, from why a database index is a B-tree rather than a binary search tree (one page read per level, not per comparison) to which direction a reduction must run to show a new problem NP-hard. Credit goes to a guarantee stated at its true strength, with the input that breaks it.
The plan opens on mathematics, the language most later modules argue in. Discrete mathematics supplies induction, counting and the vocabulary of graphs, and probability the expected-case reasoning behind hashing and randomized pivots; modular arithmetic from the first module returns near the end, under public-key cryptography.
Data structures start where memory is contiguous. Arrays explain why a scan is fast, and most of what follows either links nodes by pointer or reads an array differently, as a heap does; hash tables use both, and graphs close the stretch by reusing the stack and the queue in their traversals. Only then does the plan stop to measure: complexity analysis arrives with structures in hand to cost and goes straight to work on sorting and binary search. Recursion is induction run as code, which is where the first module pays off again; the two ways of taming it follow, dynamic programming, which caches overlapping subproblems, and greedy choice, which works only when the locally best step never has to be undone.
Then the question changes from how fast to whether at all. Automata and languages rank machines by what they can recognize, and complexity classes rank problems the same way, ending on how to cope with a hard one using the paradigms just covered. Information theory sets the floor on how small data can get, and serialization turns that into bytes crossing a process boundary, where the plan leaves pure theory.
From there it describes a running system from one process outward. Concurrency and memory management cover threads sharing a heap and who reclaims it. Databases follow because transactions and isolation are concurrency control with durability added, and their indexes are the disk-oriented trees met earlier. The network stretch goes from the layer model through the protocols a request touches, TCP first, to how a server pushes to a browser. Distributed systems join the database and the network, taking consensus, clocks and delivery semantics before the building blocks a design round draws.
The close steps back from the machine. Cryptography follows the network because TLS is where its primitives meet a connection, and software design ends the plan: how code is organized rather than what it computes.
Where to open the plan depends on how you came to it. A recent graduate has met most of the first half in coursework and tends to lose points in the second, on what lectures seldom reached, such as the isolation level a transaction actually ran at. Begin at Processes & Memory and return to the structures only to drill. A developer who learned on the job has the reverse profile: the math, analysis and theory at the top are the gap, and they build on one another closely enough that by topics, not by frequency, is the order to read them in. If asymptotic notation is not yet automatic, read complexity analysis before the structures, even though the plan places it after them.
With days rather than weeks before a fundamentals screen, narrow level so that it stops at the band you are interviewing at: the upper levels here ask which guarantee a design depends on, not what a structure costs, and a short screen rarely gets that far. Importance narrowed to must know does the rest.
The craft of the coding round sits outside this plan: it has no module on the recurring problem patterns those rounds are built from, or on working a problem aloud from its first minute, and Data Structures & Algorithms is the roadmap built around exactly that. The plan's distributed stretch also stops at the building blocks; assembling them under an open-ended prompt is the subject of the System Design roadmap.