Loading page…
Master the fundamental concepts of build a simple key-value store through this focused micro-challenge.
You have read the whole brief, and the concepts above stay free on every task. Writing and running the code needs a plan.
Three hints are available for this task, revealed one at a time inside the code workspace so you can struggle productively before seeing them.
Every task includes starter code, theory, and hidden tests so you can implement and verify locally in the browser.
How it worksBloom filters sit in SSTable metadata to answer "key definitely not in this file" without disk reads. A negative lookup saves an I/O; a positive lookup must still check the data block because false positives are allowed.
Hash key with k independent functions into m bits. Insert sets bits; query requires all k bits set.
cLoading…
Keep the relevant documentation open while you implement. When your output disagrees with the reference, trace one failing case by hand before changing random lines.
You will implement a Bloom filter with configurable bit array and hash count. This exercise asks you to report false positive rate on a provided key set.
An LSM tree keeps a Bloom filter per SSTable so a lookup can skip files that certainly do not hold the key. Implement a 64-bit Bloom filter with two hash functions:
cLoading…
add K sets bits hash1(K) and hash2(K).check K answers MAYBE when both bits are set and NO otherwise. A NO is always right; a MAYBE can be a false positive when other keys happened to set both bits.One command per line, add K or check K, with 0 <= K <= 1000000. The filter starts empty.
For each check: key=K MAYBE or key=K NO. add prints nothing.