Exercises

The following exercises provide you with the opportunity to practice with Bloom filters. The solutions to these exercises are found in the section .

1. You’re the lead engineer at the social media app HumbleBrag. This particular app requires users, upon sign-up, to choose a unique username. If a proposed username is already found to be taken, the user is asked to choose a different username.

   Now, you’ve gotten complaints that this process is too slow. Each time a user suggests a username, it takes a whopping four seconds (sheesh!) for the app to tell the user whether that username is available. You know that this is happening because the app, under the hood, is calling the database to search whether that username exists.

   How might you use a Bloom filter to help speed things up?

2. Thanks to your ingenuity in using the Bloom filter, you made HumbleBrag’s username validator much faster. Buoyed by this success, the rest of your engineering team got super excited to apply this technique to speed up other parts of the app.

   Another slow part of the HumbleBrag app is user login. Specifically, each time a user enters their password, the app needs to query the database to see if (an encrypted version of) that password is correct. The engineering team is suggesting storing encrypted passwords in a Bloom filter. This way, we could check the password using the super-quick Bloom filter rather than run a slow database lookup.

   Is this a good idea?

3. Use Python to create an instance of the “classic” BloomFilter class. Set it up to accommodate a set containing 1,000 values and to have a failure rate of 3 percent. Write code to help you answer the following questions:

   What does M come out to be?

   What does K come out to be?

   How many bytes does the underlying bit vector data take up when you call sys.getsizeof() on the bit vector’s underlying array?