Stockroom Quorum Read
A hardware shop keeps the stock count for each item on 3 replicas. Every write carries a version number one higher than the last, and a write counts as done once 2 replicas have stored it (W = 2). A read asks all 3 and waits for the first 2 answers (R = 2). Because 2 + 2 > 3, the replicas that answer a read always include at least one that stored the latest completed write, so the newest version among the answers is at least that fresh. A replica that is slow or down simply never answers.
This is the quorum read used by leaderless key-value stores (see Replication and Design a Key-Value Store). It only works if the read picks the newest answer, not the first one.
Your task
Write quorumRead(replies, r). replies lists what each replica sent, in the order the replies arrive. Each entry is [version, value], or null for a replica that timed out.
The coordinator takes the first r entries that are not null, and ignores everything after them, even a newer version, because it has already answered. Return [version, value] for the highest version among those r replies. If fewer than r replicas answered, the read fails: return an empty list.
Two replies with the same version always carry the same value.
quorumRead(replies: int[][], r: int) → int[]
Examples
replies = [[4, 12], null, [5, 9]] r = 2
[5, 9]
The first reply is version 4 (12 in stock). The second replica timed out, so the coordinator keeps waiting. The third reply is version 5 (9 in stock). That makes 2 replies, and version 5 is newer, so the answer is 9. Returning the first reply, 12, would show stock that was already sold.
replies = [[7, 30], [6, 31], [8, 29]] r = 2
[7, 30]
The first two replies, versions 7 and 6, already make a quorum of 2, so the coordinator answers with version 7. Version 8 arrives too late to be seen. That is allowed: R + W > N only promises that the read sees the latest write that had finished, and a write still on its way to its second replica has not finished.
replies = [null, [3, 5], null] r = 2
[]
Only one replica answered, and the read needs 2. Returning version 3 anyway would drop the overlap guarantee, so the read fails and the caller can retry.
Constraints
- 1 ≤ replies.length ≤ 7
- 1 ≤ r ≤ replies.length
- 1 ≤ version ≤ 1,000,000,000
- −1,000,000 ≤ value ≤ 1,000,000
Start with brute force
A tempting shortcut is to return the highest version in the whole list. That is wrong, not slow: the coordinator answers as soon as it has r replies, so replies after that never reach it (the second example).
Another is to return the first reply that is not null. That is a read with R = 1, and with W = 2 on 3 replicas it can miss the latest write entirely (the first example).
Hints
0 of 4 shown- Hint 1
Which replies does the coordinator actually look at? What happens to a reply that arrives after it already has
ranswers? - Hint 2
Walk the replies in order, skip the
nulls, and stop as soon as you have countedrreal replies. - Hint 3
While you walk, remember the reply with the highest version so far. Do not sort the whole list: the order of arrival is part of the input.
- Hint 4
If the walk ends with fewer than
rreplies counted, return[]. Otherwise return the remembered[version, value].
Walkthrough and solution
Unlocks when you pass every test. Stuck for a while? Looking is fine too, as long as you then close it and write the code yourself.
How to solve it
Simulate the coordinator: read replies in arrival order, skip timeouts, keep the newest so far, and answer the moment the count reaches r.
Trace the first example, r = 2:
[4, 12]: best is version 4, counted 1.null: skipped, still 1.[5, 9]: 5 > 4, so best is version 5. Counted 2 = r: return[5, 9].
Know what this does not give you. R + W > N makes a read see the latest completed write, as long as both quorums are drawn from the same N replicas. It does not order concurrent writes, and a read that overlaps an unfinished write may see it while a later read does not. Real stores narrow that gap with read repair: the coordinator sends the newest value back to the stale replicas it heard from.
function quorumRead(replies, r) {
let best = null, counted = 0;
for (const reply of replies) {
if (reply === null) continue; // timed out: never answered
if (best === null || reply[0] > best[0]) best = reply;
counted++;
if (counted === r) return [best[0], best[1]]; // quorum reached: answer now
}
return []; // fewer than r replicas answered
}def quorum_read(replies, r):
best, counted = None, 0
for reply in replies:
if reply is None: # timed out: never answered
continue
if best is None or reply[0] > best[0]:
best = reply
counted += 1
if counted == r: # quorum reached: answer now
return [best[0], best[1]]
return [] # fewer than r replicas answeredRun your code to see results here. Run checks the examples. Submit checks every test, including hidden edge cases.