Matt Godbolt's recent blog entry about using the population count instruction to count bits made the rounds on HN recently and I was reminded of an interview where I was asked to write the code to count bits and I didn't quite flunk it but failed anyway.
This is my interview experience from almost ~30+ years ago when I had "only" ~2+ years of coding in C under my belt - but it included writing a compiler for a subset of Pascal as part of my Masters and coding Unix drivers at work (in addition to reviewing code written in SPARC assembly).
I was interviewing at a hardware shop for a firmware position and I was told it was a 3 person "funnel" interview which meant that if the earlier ones in the list of interviewers didn't find me to be a good fit, the interview ended right then and there without the remaining interviewers having to talk to me. The first person to interview me looked like a relatively senior guy who informed me that he had been there at the same company for about a decade. He started with a coding test asking me to write the code for "getbit" and "setbit" where an array of bytes was passed in as the argument. I dashed this off on the whiteboard starting with "getbit" since he asked me to do that first:
int getbit(unsigned char *a, int i)
{
int loc = i/8;
int bit = i%8;
return ((a[loc] & (1 << bit)) >> bit);
}
He was happy with that code and asked me to move on to "setbit" for which I wrote this:
void setbit(unsigned char *a, int i)
{
int loc = i/8;
int bit = i%8;
if (getbit(a, i) == 0)
a[loc] |= (1 << bit);
/* else already set */
}
Next he asked for a function called "countbits" to count all the bits and this was coded easily enough:
int countbits(unsigned char *a, int n)
{
int i, j, c=0;
for (i=0; i<n; i++) {
for (j=0; j<8; j++) {
c += getbit(a, i*8+j);
}
}
}
After looking it over, he tactfully pointed out to me that the code had a bug and after giving it a quick review, I figured out easily enough that it was missing just the return statement:
return c;
So far so good - I'd managed to squeak through that close call but that bug was enough to leave me a bit shook up - I knew that my palms were starting to sweat a bit since the whiteboard marker I was using felt slippery in my hand.
At this point the interviewer changed tack a bit and asked me how I would count the bits if it was an int instead of an array. Feeling confident but sensing a trick question and hoping to show off my knowledge of the SPARC instruction set I replied that if it could be coded in SPARC assembly, we could just use the "popcnt" instruction. He replied that he just wanted C code and asked me to code it as "countbits_int"
So I wrote:
int countbits_int(unsigned int n)
{
int i, j, c=0;
for (i=0; i<4; i++) {
for (j=0; j<8; j++) {
c += getbit(n, i*8+j);
}
}
return c;
}
Since this was on a whiteboard, I didn't have to write the entire thing over again, I just had to erase and rewrite the parts that changed from the previous code - shown here with the corrected/additional return statement.
He again pointed out that there was a bug and asked me if I could see it. Reviewing the code on the whiteboard I was again, quickly enough, able to figure out the "copy-pasta" bug: since 'a' was an address and 'n' was now passed by value, I'd have to make a copy of it in a new variable (say 'v') and pass it with an additional '&' so that it could be used as an address.
I was feeling pretty pleased with myself for having found the bug when he asked something that caught me by surprise: "what if the int is not 32 bits?"
For whatever reason, my mind went blank and I couldn't for the life of me think about how to answer that - other than to chicken out and suggest passing the length in as an additional parameter. He made up his mind fairly quickly after that and regretfully informed me that he would have to terminate the interview and walked me out to the office entrance (from where he had initially picked me up).
As I slowly made my way back to where I'd parked my car, I was crestfallen rueing the fact that I had failed an interview for the first time in my life - and in the very first round, no less - without making it to round #3 since I was initially scheduled to talk to two more people after that.
As I reached my car, "sizeof" suddenly popped back into my head, unbidden. I almost turned around to walk back to the office to see if I could tell him my answer, but I could see that the doors with their badge enabled locks had already swung shut.
With hindsight and in all fairness to his judgement, I can see that the two bugs that were in my code probably counted as 2 strikes and not using "sizeof()" must have counted as the third and final strike and thus, I was out.
I'm writing this blog entry as "anecdata" - that our whole "fizz buzz" coding interview process tends to be a fairly unscientific approach to hiring and also as a reminder to myself about the fickle nature of our memories - I took copious notes after that interview, which is why it is showing up in blog form almost 30 years later.
This was my failed interview #1, the very first time that I wasn't selected in an interview. I may add more of these "failed interview" anecdotes as time permits.
My personal conclusion from that experience is that interviewing is at best a hit or miss proposition. As Dan Luu points out, the entire interviewing process is a fairly unscientific approach to hiring at best and it does give me the occasional imposter syndrome about whether I'm a lemon myself despite having worked in the industry for over 3 decades.
I sometimes wonder how my life would have turned out if my memory hadn't failed me at that critical juncture - a fork in the road of a multiverse that I'll never get to experience. For the people involved, there can be no controlled experiment that can go both ways, exploring both forks of the road.
As luck would have it, all of my interviews at the other places I interviewed at including Sun Microsystems went fine and I guess I have no regrets at all about how my life turned out. I haven't heard any complaints about my C coding skills either except for one goof up in the way I coded up a doubly linked list that happened in a change that I made to the NFS server in the Solaris kernel code base while I was working at Sun, but that's a story for another day.