DSA Studio

Probabilistic Structures

Trace fresh cases, diagnose a failed invariant, then revisit the linked explanation and implementation.

Get every question correct to pass this checkpoint. You can review feedback, revise your answers, and submit again.

1. A Bloom filter has eight bits, all clear. One key sets positions 1,4,4. How many distinct bits become set? Answer with the integer only.
2. Every queried bit for a never-inserted key is set. What may the filter conclude?

Select one answer.

3. An ordinary Bloom filter clears all bits belonging to a deleted key. What can go wrong?

Select one answer.

4. Under the usual insert-only, consistent-hash assumptions, how many false negatives should a Bloom filter produce for inserted keys?
5. A Bloom-filter hit guards an authorization decision. What should follow?

Select one answer.

6. For m=8, double hashing has step h2=0 modulo 8. Increasing k from 2 to 6 does what to this key’s positions?

Select one answer.

Join Discord