Bit Twiddling and Bit Vectors

unique ascii

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.

Good luck!

A great resource: https://graphics.stanford.edu/~seander/bithacks.html

An Apple a Day

apple

I love learning about organizational methodologies. There’s a lot out there too – TedTalks, 99u.com, Steven Covey and Brian Tracey audiobooks, the pomodoro technique. I’ve started to filter through conflicting statements (successful people stay up late vs. get enough sleep or risk brain damage) to distill some simple ideas that have worked for me throughout my professional and academic career.

The Case for Hard Work

The most important aspect to consider is hard work. No organizational strategy can get around this one. I can plan my project to the 10 minute iteration, and timebox like Father Christmas, but unexpected issues will arise. So, I’m going to put aside my lower priority tasks in favour of my most important ones. I may even have to stay up a bit past my bedtime! (I schedule a rest day after important deadlines for this very reason.) This same rule applies to my coding career as much as it did in my music career. How do you get to Carnegie Hall?

The Case for Mono-Tasking

I used to be a big fan of the insane multi-tasking. I would code, write emails, text, listen to a Coursera lecture, chat with colleagues, update my portfolio, memorize French vocab…all at once. I felt like a super productive person but in reality my main task suffered from a lack of focused attention. There are two reasons why I don’t do this anymore; 1) I want my estimates to be somewhat predictable, and 2) I want to make time for downtime. All that my multi-tasking achieved was to stretch the main task until it took over everything else, leading to an imbalance.

The Case for Balance

Everything you’re currently doing is important to you. This realization hit me in the gut. It’s to say that browsing imgur with breakfast is important to me, really?

For 3 months, I diligently tracked my activities, then I examined the distribution of categories based on my high level goals. (What can I say, I’m really into data!) No fancy app here – a scrap of paper was all I needed. Our most important goals are memorized, aren’t they?

Try logging your hours by category – time spent on Facebook, imgur, honing your yogi skills, perfecting that recipe, finishing a course – all real and imagined tasks. Then, track the actual hours spent on these categories. Broad strokes are enough. Colour code the categories (eg. Health, Work, Learning, Friends and Family). If these things are balanced, you’ll end up with a nice rainbow!

Weekly Rainbow

My task list rainbow for this week: Green = health activities, Blue = Career Enhancement, Purple = Academics, Red = Work, Pink = Fun time

Zen of Python

zenofpython

My Directed Studies project this summer is written entirely in Python … a powerful language that I’m still learning. This afternoon I attempted to map two dictionaries to a lambda function. Silly considering that the Dictionary data structure is meant to be unsorted given that it has O(1) for most operations. I think I was carried away by its awesome power. At any rate, I did learn about the Zen of Python and had a refresher on data structures.