Using Bits as a way to Encode Preference[Technique Tuesdays]
Referncing an excellent blog by Vimeo. Booleans, Bit Functions, Algebra, Encoding
Happy Last Day of May my reader,
For this extra special day, I will be covering this amazing blog post by Vimeo engineers: A *bit* about content ratings
Using a very clever technique and math, they drastically cut down the storage requirements for their user content preferences. How much you ask. Imagine if a user can have k preferences about their content. Then the traditional, “use a boolean for every option”, the method will require O(k) space. Using their technique cuts it down to O(1) time. That is two orders of magnitude lower. They also achieved a significant reduction in time requirements, making their solution better overall. Imagine how good you’ll look in front of the interviewer if you can do that.
This post will cover some of the ideas expressed in the blog post. For more details, I would suggest reading the post. I will simply summarize the post here.
Summary of the Post
Vimeo has different content filters that keep track of things like nudity, violence, drugs, explicit language, etc. The traditional way for this would be expensive, as we have already discussed.
They keep track of these using a bit field data structure, where each bit represents a specific content filter flag (nudity, violence, etc.).
The entire bit field can fit in a single integer, so comparing bit fields can be done in O(1) - constant time. This makes it incredibly memory and time-efficient.
Thus, I was pleasantly surprised to learn that bitwise operators and bit fields, a concept my college professors barely grazed over during perhaps a single lecture, had an extremely applicable use case on something I was working on. Bit fields offer an optimal solution to a data structure that would otherwise consist of sometimes dozens of boolean values.
-From the Blog. This is why Math Mondays are so crucial. Make sure you show up to them.
Every user on the Vimeo platform will also have their own bit field that keeps track of their viewing preferences. If a user is okay with watching videos with nudity, then that corresponding nudity bit will be set to 1. If they flag nudity as something they want to avoid, then that bit will be set to 0.
Then, when Vimeo wants to check if a user can watch a video, the backend just has to do a bitwise AND operation between the video’s bit field and the user’s bit field.
All the 1s in the user’s bit field represent filters that the user is okay with watching, so the AND operation between the video’s bit field and the user’s bit field should result in 1s for all the matching 1 bits and 0s for all the mismatching bits or matching 0 bits.
Therefore, the result of the AND operation between the user’s bit field and the video’s bit field will be equal to the video’s bit field if the user has allowed all the content filters that the video is flagged for.
If the result of the AND operation is not equal to the video’s bit field, then that means the user has filters set to avoid the video.
In the example above, the video clip’s bit field is 1010010, or 82 in base 10. Radhika and David are two Vimeo users who have their own viewing preferences encoded in bit fields.
Running the AND operation between Radhika’s bit field and the video’s bit field will indicate that the video clip has a 1 set in a bit where Radhika has a 0 set, so Vimeo can filter out that video for Radhika.
David has 1s set for all the fields where the video clip has a 1, so he’s eligible to watch the video.
This AND operation can be done in constant time, so it’s far quicker than having a hashmap or array keep track of content ratings and doing an O(n) comparison every time you need to check if a user can watch the video.
Before proceeding, if you have enjoyed this post so far, please make sure you like it (the little heart button in the email/post). I also have a special request for you.
***Special Request***
This newsletter has received a lot of love. If you haven’t already, I would really appreciate it if you could take 5 seconds to let Substack know that they should feature this publication on their pages. This will allow more people to see the newsletter.
There is a simple form in Substack that you can fill up for it. Here it is. Thank you.
https://docs.google.com/forms/d/e/1FAIpQLScs-yyToUvWUXIUuIfxz17dmZfzpNp5g7Gw7JUgzbFEhSxsvw/viewform
To get your Substack URL, follow the following steps-
Open - https://substack.com/
If you haven’t already, log in with your email.
In the top right corner, you will see your icon. Click on it. You will see the drop-down. Click on your name/profile. That will show you the link.
You will be redirected to your URL. Please put that in to the survey. Appreciate your help.
In the comments below, share what topic you want to focus on next. I’d be interested in learning and will cover them. To learn more about the newsletter, check our detailed About Page + FAQs
If you liked this post, make sure you fill out this survey. It’s anonymous and will take 2 minutes of your time. It will help me understand you better, allowing for better content.
https://forms.gle/XfTXSjnC8W2wR9qT9
Happy Prep. I’ll see you at your dream job.
Go kill all you tricky technician,
Devansh <3
To make sure you get the most out of Technique Tuesdays, make sure you’re checking in the rest of the days as well. Leverage all the techniques I have discovered through my successful tutoring to easily succeed in your interviews and save your time and energy by joining the premium subscribers down below. Get a discount (for a whole year) using the button below
Reach out to me on:
Instagram: https://www.instagram.com/iseethings404/
Message me on Twitter: https://twitter.com/Machine01776819
My LinkedIn: https://www.linkedin.com/in/devansh-devansh-516004168/
My content:
Read my articles: https://rb.gy/zn1aiu
My YouTube: https://rb.gy/88iwdd
Get a free stock on Robinhood. No risk to you, so not using the link is losing free money: https://join.robinhood.com/fnud75