Interviews are upon us and, after a short holiday break, I’ve begun the requisite preparation for coding interviews. It’s easy to find valuable question resources online, but the majority of explanations are mathematical. I’ve found that a practical explanation works for me, as well as coding the solution in my own words so as to better internalize the methodology.
It’s tempting to become frustrated with these types of interview questions, prompting one to ask questions about the interview process itself.
If I’m not going to bit twiddle in my actual job, then why are these things tested in the interview process?
The first good reason is that the interviewer has a limited amount of time in which to test each applicant, so these shorter format questions are suitable for whiteboarding, without having to spend a few days getting to know a real code base.
Another reason is that it’s more interesting to test in a conversational format, as opposed to a Q&A. Rather than telling an interviewer what you know about the size and format of integers, bit twiddling can be used to demonstrate your knowledge of space efficiency, operating systems, and logical data structures.
I’ve encountered this type of question in a real, live interview. Suppose that you have a file composed of character data and you want to find out which characters are present.
The brute force solution for this is to create an external data structure, such as a hashtable/dictionary where each ascii character code is a key and each value is a boolean. If you’ve worked with Java and other object-oriented languages, where space is usually a non-issue, easily understood external structures are the norm, especially where readability is a concern.
Suppose that space is the most important concern here. Say that the server only has room for a single integer because the character file is enormous. An elegant solution is to use this integer as a bit vector/array, where each bit is interpreted as a 0/1 boolean value. We can then navigate the array using a bit mask together with a bit shift operation. Each cell, or bit position in the integer, represents an ascii character code. (Note that a 32-bit integer system works for all lower case characters, while a 64-bit integer accommodates both lower and upper case. You will need to clarify details about the OS with the interviewer and show off your knowledge of systems.)
My suggestion for interview preparation is to first sketch the code out on paper. Then write the code up and test it out as you’ve written it. Being able to write compilable code on paper is a valuable skill for whiteboard interviews.
A great resource: https://graphics.stanford.edu/~seander/bithacks.html