I’ve talked about interviews from one perspective or another on several occasions, you might even say it is a pet subject of mine. It’s fascinating because most people are no good at interviews and when it comes to developer interviews – well; let’s just say there is a whole new dimension for us to suck at with coding questions, whiteboards and whatnot. Of course, the other side of the equation is not pristine here, the interviewer can be just as much to blame for a terrible interview, either through lack of training, empathy, preparation or a host of other reasons, but that’s a whole separate discussion. So, why are we so bad at interviews? You can probably think of quite a few reasons straight away:

• it is a high pressure situation, you were nervous
• you just didn’t “click” with the interviewer
• you were asked all the “wrong” questions
• sometimes you just have a bad day

Infact, you can often work yourself into a self-righteous frenzy after a bad interview, thinking how every circumstance seemed to conspire against you, it was beyond your control, there was nothing you could do – hell, you didn’t even want to work for that stupid company anyway! But, deep down, we all know that those excuses are just so much bullshit. The truth is there were many things we could have done, but by the time the interview started it was much too late. I’ll use a story to demonstrate.

The least stressful exam I’ve ever had was a computing theory exam in the second year of my computer science degree. I never really got “into it” during the semester, but a few weeks before exam time – for some inexplicable reason – I suddenly found the subject fascinating. I spent hours reading and hours more playing with grammars and automata. Long story short, when exam time rolled around I knew the material backwards – I groked it. There was some anxiety (you can’t eliminate it fully), but I went into the exam reasonably confident I’d blitz it (which I did). Practice and preparation made all the difference. Of course, this is hardly a revelation, everyone knows that if you study and practice you’ll do well (your parents wouldn’t shut up about it for years :)). Interviews are no different from any other skill/subject in this respect, preparation and practice are key.

Can You Wing It?

The one difference with interviews is that they are an occasional skill, almost meaningless most of the time, but of paramount importance once in a long while. It just doesn’t seem like it’s worth the effort to get good at them, especially if you happen to already have a job at the time (who knows, you may not need those skills for years). There are plenty of other subjects clamouring for your attention and anyway every interview is different, you can never predict what’s gonna happen so it would be stupid to waste your time trying. No – good communication skills and decent software development knowledge will see you through, right? Except, they don’t and it won’t. Sure, you might be able to stave off total disaster, but without preparation and practice, you’re mostly relying on luck. Things “click”; you get asked the “right” questions and are able to think of decent answers just in time. This is how most people get hired. As soon as the process gets a little more rigorous/scientific, so many candidates get weeded out that companies like Google, Facebook, Twitter etc. find themselves trying to steal people from each other since they know that those that have passed the rigorous interview processes of their competitors must be alright. The interesting thing is that the rejected candidates are not necessarily worse; they are often simply a lot less prepared and a little less lucky.

Over the last few years presentation skills have seen quite a lot of press. Many a blog post and much literature has come out (_e.g. Presentation Zen and Confessions of a Public Speaker are both great books_). Many people have decent knowledge of their subject area and have good communication skills, they think they are excellent presenters – they are wrong. They put together some slides in a few hours and think their innate abilities will carry them through, but inevitably their presentations end up disjointed, mistargeted, boring or amateurish. Sometimes they sail through on luck, circumstances conspire and the presentation works, but these situations are not common. Malcolm Gladwell is a master presenter, he is one of the most highly sought after and highly paid speakers in the world (_and has written a bunch of awesome books to boot_) – this is not by chance. Without doubt he knows his stuff and has better communication skills than the majority of speakers out there and yet all his talks are rigorously prepared for and practiced. To my mind, the situation with interviews is similar to that of presentations, except the deluge of literature about interviews goes almost unnoticed since they are old-hat. The digital world hasn’t changed the interview process too significantly (unlike the public speaking process), except the internet age brings all the old advice together in one place for us and all of that advice is still surprisingly relevant.

The Old-School Advice

Everyone (and I mean everyone) always says that you should research the company you’ll be interviewing with beforehand. You would think people would have this one down by now, especially developers cause we’re smart, right? Nope, no such luck, just about everyone who rocks up for an interview knows next to nothing about the company they are trying to get a job at, unless the company is famous, in which case people are just full of hearsay. But hearsay is no substitute for a bit of research and it is so easy, I am reminded of an article Shoemoney wrote about getting press (well worth a read by the way, if you’re trying to promote a product/service) – there is a tremendous amount of info you can find out about a person by trawling the web for a bit and it is just as easy to learn something about a company. I mean, we do work in software, so any company you may want to work for should have a web presence and a half. And even if web info is sparse there is your social network or picking up the phone and seeing if someone will trade a coffee for some info. Yeah, you go to a bit of trouble but the fact that you did will be apparent in an interview, I mean, there is a reason why I work where I work and I’d prefer to work with other people who give a shit (everyone would) – you savvy? Of course if you do go to the trouble to find out what skills/tech/knowledge/processes a company is looking for/values you may be able to anticipate where an interview might head, the value there should be self-evident.

Which leads me to interview questions. When it comes to developers, there are three types of questions we struggle with/despise:

• the behavioural/culture fit
• the coding question
• the Mount Fuji question

With a bit of practice you can blitz all of these. The Fujis are the hardest, but even they can be prepared for, but I’ll get back to those shortly.

Behavioural Questions

The behavioural questions seem annoyingly difficult but are actually the easiest. You know the ones “Give me an example of a time when you demonstrated leadership/communication skills/problem solving/conflict resolution”. It is always the same question, with a different attribute of yours that you have to spruik. Being in essence the same question you can address all of them with what amounts to the same answer, once again substituting a different attribute. These are actually difficult to handle on the spot, but if you have something prepared it is a breeze. Example:

“There was a time, when Bill the developer was being an obstinate bastard and wouldn’t buy in to the awesome that the rest of us were peddling, but I took charge of the situation and was able to convince Bill blah, blah ….” – leadership

“Bill the contrary developer just wouldn’t agree with the way we were dishing out the awesome, but I took Bill out for coffee and we hashed it out one on one blah, blah …” – communication

“There was insufficient awesome to go around and Bill and Joe just couldn’t share it and were coming to blows, but I stepped in and took them both to a whiteboard, we had a long chat blah, blah …” – conflict resolution

As long as you think up a situation beforehand you can adapt it to answer any behavioural question, the situation can even be a fictitious, but you do need to think through it carefully for 10-15 minutes to be able to come up with something coherent. You will never have time to frame a coherent reply in the interview itself. Of course, it is best to have a few situations prepared just so you can change it up a bit, variety never hurt anyone. If the company you’re interviewing with is enlightened they won’t ask you these questions, but will instead focus on your dev skills, but there are many companies and few are enlightened, might as well prepare for the worst case and be pleasantly surprised if the best case happens.

Coding Questions

Talking about dev skills, the one thing that just about every company that hires developers will do, would be to ask a coding question at some stage. These usually take the form of a sandbox question or what I call a Uni question. You know the ones, “Reverse a list”, “Implement a linked list” it’s as if they are under the impression you studied computer science at some point, go figure :). People struggle here, because you just don’t come across this kind of question in your day-to-day work. If they asked you to implement a Twitter or Facebook clone, you could really show them your chops, but balancing a binary tree – who the hell remembers how to do that? And that’s the rub, you probably could dredge the information from the depths of your grey matter, but by the time you do the interview will have been long over. Because you don’t do this kind of question daily, you brain has dumped the info you need to tape and sent it to Switzerland (cause backups should be kept off-premises). The answer is simple; you gotta practice these questions well in advance of the interview. Preparation baby, that’s the ticket. Preferably you should be doing them regularly regardless of your employment status cause those questions are fun and bite-sized and give your brain a bit of a workout – you’ll be a better developer for it. The most interesting thing though is this, you do enough of them and you won’t really encounter anything new in an interview. There are really not so many themes when it comes to these questions, it will be the same formulae you’ll just need to plug in different numbers (a simplification but not too far from reality). I really gotta follow my own advice here. If you seriously want a leg up, there are books specifically about this, I prefer Cracking the Coding Interview but there is also Programming Interviews Exposed – read them, do the questions.

Puzzles

Mount Fuji questions are the most controversial, but regardless of whether you hate them or not, even they can be practiced. Yeah, alright, maybe you’re willing to walk out if any company ever dares to ask you about manhole covers, but I’d much rather answer the questions and then walk out in self-righteous satisfaction rejecting the offers they’ll be throwing at my feet, than storm out in self-righteous anger knowing deep down that I was a wuss for doing so. And anyway, I’d like to think that I’ve already demonstrated that not all Mount Fuji questions are created equal, some are coding problems, others deal with concurrency, others still might be back-of-the-envelope questions (the story of how these originated is actually pretty interesting, I am writing it up as we speak). The subset of questions that are simply a useless puzzle are a lot smaller than you might think. Doing these kinds of questions in your spare time is just another way to build your skills with a side benefit that you become an interview-proof individual. Of course, many people also enjoy an occasional puzzle – I’m just saying.

There is still lots more to say, I haven’t even begun to talk about attitude, but this is already a tl;dr candidate, so I’ll leave that discussion for another time. Let’s sum up, if you feel that you suck at interviews, it’s because you didn’t prepare well enough and haven’t had enough practice – it is that simple. As an interviewer it is most disheartening to see an unprepared candidate, there are just so many of them, on the other hand a person who is clearly on the ball is just awesome. And I am well aware that practicing interviews is hard, there is no Toastmasters equivalent for that particular skill, but thorough preparation can significantly mitigate that issue. Even a few minutes of preparation will put you head and shoulders above most other people since the vast majority don’t bother at all. So, take the time to practice/prepare if you have an interview on the horizon, be smart about it and it is bound to pay off, not to mention a better experience for the interviewer as well, more fun and less stress for everyone.

Images by Caro Wallis and louisvolant

For a few years now, I’ve been meaning to read Peter Norvig’s old book, “Paradigms of Artificial Intelligence Programming: Case Studies in Common Lisp”, but every time I started I’d inevitably get lost in the code due to my poor Lisp skills. For some reason I just couldn’t absorb the introductory Lisp chapters at the beginning of the book. So a little while ago I decided to “begin at the beginning” and slowly started making my way through Peter Seibel’s “Practical Common Lisp”.

Inevitably, one of the first things I learned about was the “format” function. Format, is essentially the Lisp equivalent of printf, so you kinda need it to produce the old “Hello World”. Just like printf and its ilk, format supports string interpolation via embedded directives. For example if you wanted to print two strings side by side but separate them by a specific number of spaces you could do something like this:

CL-USER> (format t "~a~40t~a~%" "abc" "123")
abc                                     123
NIL

One of the most interesting format directives is ~r which will take an integer and produce its English representation e.g.:

CL-USER> (format nil "~r" 123456)
"one hundred twenty-three thousand four hundred fifty-six"

I found this little gem in one of the footnotes, the lesson here being – always read the footnotes. Anyway, I don’t know about you, but I thought that was pretty awesome, which immediately got me thinking about how hard it would be to implement a stand-alone integer to English translation function. I would have loved to try my hand at doing this in Lisp, but I don’t think I am sufficiently Jedi for that as yet (I will however give it a go as soon as I am ready, you will not want to miss that :)), so instead I decided to have a go at implementing it in Ruby.

A Totally Unrelated Musical Trivia Interlude

Speaking of Jedi, I’ve recently been a little obsessed with the “Good Morning” song from “Singing In The Rain”, you know the one I mean. I blame “Family Guy” for this, it all started after I watched the episode where they perform this song in one of their postmodern flashes of randomness. Anyway, it’s just such a nice and happy song, it’s kinda quaint how 1:30 used to be considered “late” in those days and I dig the whole synchronized tap dancing thing that they do (just imagine how much they had to practice to get it right).

Now, here is the trivia, the girl in the song/movie is a 20 year old Debbie Reynolds (did you know that before “Singing In The Rain” she didn’t even know how to dance) who went on to marry singer Eddie Fisher. A few years later she gave birth to a daughter named Carrie (i.e. Carrie Fisher) who, in turn, went on to play Princess Leia in “Star Wars”. That’s how all of this relates to Jedi, and you thought I was going off on a random tangent – now you know better :). Time to get back to some Ruby code.

A Ruby Based Integer To English Converter

It turns out writing it was somewhat harder than I expected because the English language is a little insane when it comes to naming numbers. Everything was going well at the start; it was obvious that we need some kind of lookup table to convert digits to words. The lookup table must contain all the uniquely named numbers that we are likely to encounter.

• all number between 1 and 10 (e.g. one, two, five etc.)
• all number between 11 and 20 (e.g. eleven, twelve, sixteen etc.)
• all multiples of 10 between 20 and 100 (e.g. thirty, forty etc.)
• all uniquely named powers of 2 over 100 (e.g. hundred, thousand, million, billion etc.)

Here is a cut-down version:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

{
1 => "one",
2 => "two",
3 => "three",
...
19 => "nineteen",
20 => "twenty",
...
90 => "ninety",
100 => "hundred",
1000 => "thousand",
1000000 => "million",
...
}

We don’t really think about it, since we are so used to it, but that is actually a lot more unique numbers than strictly necessary. You can easily identify all possible numbers using just 1 through 9 as well as all the named powers of 10, such as ten, hundred, thousand etc (we’ll explore this thought further shortly). Doing it this way would be pretty logical, instead the English speaking world decided that we needed nine special words to represent numbers between 11 and 19 as well as eight more similar, but still unique, words for the multiples of 10 between 20 and 100. As much as we take it for granted this causes all sorts of pain when we try to implement out integer to words converter.

Consider this, we’re given an integer several digits long, let’s say 12.

• to get a word representation we start looking at the digits of the integer in reverse order (we have to start with the least significant digit first):
  • digits = 21
• we use the look-up table to find the word that represents the first digit and add it to an accumulator (which is a list that will contain all the words in the English representation of our integer):
  • digits = 21, accumulator = [two]

But as soon as we move on to the second digit, we’re already in trouble. If this digit is a one, we know we have a number between 11 and 19, so we have to do the following:

• backtrack the previous digit from the accumulator:
  • digits = 21, accumulator = []
• get the current digit along with the previous digit and reverse them to get our actual number:
  • digits = 12, accumulator = []
• do a lookup to get the new word representation and put the new representation in the accumulator:
  • digits = 12, accumulator = [twelve]

The story is similar if the second digit is 2 through 9, we still have to backtrack, then we need to do a lookup on the second digit multiplied by 10 (i.e. 20, 30 etc), combine the result with the word representation of the previous digit and put that back in the accumulator. So if the number is 20, we need to look up 20, combine that with 5 and get twenty five which ends up in the accumulator.

When the number is big enough, this patters comes up again and again every few digits. For example, numbers such as 11000, 23000, 134000 need to be represented as eleven thousand, twenty three thousand and one hundred and thirty four thousand (see what I mean). Luckily it is a pattern so we can handle all occurrences of it as a special case, but it’s a pattern that need not be. And talking about patterns that need not be, what is our obsession with the word hundred:

• three hundred and fifty
• one hundred and twenty thousand three hundred and fifty
• one hundred and twenty five million three hundred and twenty thousand five hundred and six

We have the word hundred appearing 3 times in that last one, we’re used to it and it feels comfortable, but is it strictly necessary? We have to handle that one as a special case as well. Needless to say, the code ends up being long and ugly, you can have a look at the full source here, but the main chunk of it is something along the following lines:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

def convert(number)
    return "zero" if number == 0
    word_representation_accumulator = []
    number_digits_reversed = number.to_s.reverse
    digit_count = 0
    number_digits_reversed.chars.each_with_index do |digit, index|
      digit_as_number = Integer(digit)
      skip_zero(digit_as_number) do
        if digit_count == 0
          word_representation_accumulator << "#{NTW[digit_as_number]}"
        elsif ten_to_twenty?(digit_as_number, digit_count)
          backtrack word_representation_accumulator
          actual_number = Integer("#{digit}#{number_digits_reversed[index - 1]}")
          multiplier = (digit_count > 1 ? 10**(digit_count - 1) : nil)
          word_representation = "#{NTW[actual_number]}"
          word_representation += " #{NTW[multiplier]}" if multiplier
          word_representation += " and" if word_representation_accumulator.size == 1
          word_representation_accumulator << word_representation
        elsif twenty_to_one_hundred?(digit_count)
          backtrack word_representation_accumulator
          multiplier = (digit_count > 1 ? 10**(digit_count - 1) : nil)
          lookup_number = digit_as_number * 10
          word_representation = "#{NTW[lookup_number]}"
          word_representation += " #{NTW[Integer(number_digits_reversed[index - 1])]}"
          word_representation += " #{NTW[multiplier]}" if multiplier
          word_representation += " and" if word_representation_accumulator.size == 1
          word_representation_accumulator << word_representation
        elsif digit_count == 2 || digit_count % 3  == 2
          multiplier = 10**2
          word_representation = "#{NTW[digit_as_number]} #{NTW[multiplier]}"
          word_representation += " and" if word_representation_accumulator.size != 0
          word_representation_accumulator << word_representation
        else
          multiplier = 10**digit_count
          word_representation = "#{NTW[digit_as_number]} #{NTW[multiplier]}"
          word_representation += " and" if word_representation_accumulator.size == 1
          word_representation_accumulator << word_representation
        end
      end
      digit_count += 1
    end
    word_representation_accumulator.reverse.join(" ")
  end

You can have a go at running it, but don’t forget, I only took the lookup table up to trillions, so if you want to try numbers bigger than that you will need to add more named powers of ten (such as quadrillion, quintillion etc.) to the table. Here is some sample output:

315119 - three hundred and fifteen thousand one hundred and nineteen
1000001 - one million and one 
1315119 - one million three hundred and fifteen thousand one hundred and nineteen
11315119 - eleven million three hundred and fifteen thousand one hundred and nineteen

Using Code To Derive The English That Should Have Been

Even though my code was producing reasonable output, I wasn’t entirely happy, the arbitrary nature of the English language made my code uglier than it could have been. Since I’ve taken liberties with the English language before I decided this was a good time to do it again. What if we were to remove all the extraneous words that English had for numbers. Surely, the numbers 1 through 9 are more than sufficient? This would be the simplest possible case e.g.:

135 - one three five
3619 - three six one nine

Unfortunately it just doesn’t cut it. Firstly we would have to introduce 0 as a non-silent number e.g.:

609 - six zero nine

Currently, zero is completely silent in all numbers unless it is by itself e.g.:

609 - six hundred and nine (see, zero is silent)

But even if this wasn’t an issue, it turns out we actually need the named powers of ten to make English representations of integers meaningful. One five six two three, tells us almost nothing, but fifteen thousand six hundred and twenty three gives us a lot of information instantly. Even when we haven’t processed the number fully, we know straight away that it is approximately 15 thousand and a few hundred. The bigger the number gets, the more pronounced this “estimation” effect is. So, we need numbers one through nine as well as named powers of 10. This allows us to cut our lookup table down to the following:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

NTW = {
  1 => "one",
  2 => "two",
  3 => "three",
  4 => "four",
  5 => "five",
  6 => "six",
  7 => "seven",
  8 => "eight",
  9 => "nine",
  10 => "ten",
  100 => "hundred",
  1000 => "thousand",
  1000000 => "million",
  1000000000 => "billion",
  1000000000000 => "trillion"
  }

We can use this table to write code that is much more intuitive than our previous attempt. Infact, we don’t even need to know exactly what we’re trying to achieve, instead we let the code guide us to the “correct” solution. We’re using code to derive the requirements for the real world which is the opposite of the usual scenario. The full implementation I came up with is in this gist, but here is the main bit:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

def convert(number)
    return "zero" if number == 0
    word_representation_accumulator = []
    number_digits_reversed = number.to_s.reverse
    digit_count = 0
    number_digits_reversed.chars.each_with_index do |digit, index|
      digit_as_number = Integer(digit)
      skip_zero(digit_as_number) do
        multiplier = 10**digit_count
        word_representation = "#{NTW[digit_as_number]}"
        word_representation += " #{NTW[multiplier]}" if multiplier > 1 && NTW[multiplier]
        word_representation_accumulator << word_representation
      end
      digit_count += 1
    end
    word_representation_accumulator.reverse.join(" ")
  end

You have to admit, it’s much shorter and nicer looking and here is some of the output produced:

0 - zero
1 - one
3 - three
5 - five
11 - one ten one
15 - one ten five
25 - two ten five
71 - seven ten one
40 - four ten
100 - one hundred
101 - one hundred one
112 - one hundred one ten two
123 - one hundred two ten three
457 - four hundred five ten seven
999 - nine hundred nine ten nine
1000 - one thousand
1001 - one thousand one
1010 - one thousand one ten
1011 - one thousand one ten one
2117 - two thousand one hundred one ten seven
3001 - three thousand one
13101 - one three thousand one hundred one
14001 - one four thousand one
16000 - one six thousand
25119 - two five thousand one hundred one ten nine
65009 - six five thousand nine
315119 - three one five thousand one hundred one ten nine
1000001 - one million one
1315119 - one million three one five thousand one hundred one ten nine
11315119 - one one million three one five thousand one hundred one ten nine
74315119 - seven four million three one five thousand one hundred one ten nine
174315119 - one seven four million three one five thousand one hundred one ten nine
1174315119 - one billion one seven four million three one five thousand one hundred one ten nine
15174315119 - one five billion one seven four million three one five thousand one hundred one ten nine
35174315119 - three five billion one seven four million three one five thousand one hundred one ten nine
935174315119 - nine three five billion one seven four million three one five thousand one hundred one ten nine
2935174315119 - two trillion nine three five billion one seven four million three one five thousand one hundred one ten nine

As you can see, all the named powers of ten are now treated in exactly the same way i.e.:

• 10 is ten to the power of 1
• 100 is ten to the power of 2
• etc.

So 101 is one hundred one and 11 is one ten one, 203 is two hundred three, while 23 is two ten three – logical isn’t it? There is no longer any need for any specially named numbers between 10 and 100 since we can represent all of them just as efficiently with this notation; this means no more special cases for numbers under 100. The other one we had was all the extra usages of the word hundred. We simply eliminate them all together (except for when we are talking about numbers between 100 and 1000), three one five thousand conveys the same amount of information as three hundred and fifteen thousand – the word hundred is totally redundant. Now, every named power of 10 appears only once in the English representation of the integer which allows us to still retain the ability to “estimate” the magnitude instantly without any extraneous information:

one million three one five thousand one hundred one ten nine

Short, consistent and to the point. It does seem a little awkward at first, but after a few minutes it starts to grow on you – after all, it is much more logical than the system we have now. There you go, deriving “better” English through some Ruby code. Not only do we get superior language but it is also easier, faster and less error prone to code it – FTW brothers, FTW :)!!!

Image by plindberg

One of my friends always asks that question when interviewing developers. Apparently it’s quite ambiguous and many people misunderstand – which is curious since I thought it was rather straight forward, but that’s not what this story is about.

When he first told me about this question my brain immediately went ahead and tried to solve it, as your brain probably did as soon as you read the title of this post, if you’re a developer :). After thinking about it for a couple of minutes I said that people should get “extra points” if their function uses bit hackery to solve the problem. I later realised that the most interesting thing about this was how I arrived at that conclusion.

The First Thing I Thought Of Was…

Something along the lines of the following:

1
2
3
4
5
6
7
8

def power_of_2?(number)
 return false if number == 0
 while(number % 2  == 0)
   number = number / 2
 end
 return false if number > 1
 true
end

Of course it didn’t spring forth out of my head fully formed like that, but the general gist was the same. This code solves the problem and, as you can see it is an iterative solution. The first programming language I learned was Java, the second was C, so you might say I was weaned on the “iterative approach”. So, whenever I am presented with a new problem, my mind always gropes for the iterative solution first. You might say I find it the most “natural” way to solve a problem.

The Second Thing I Though Of Was…

Something that looked like this:

ruby def power_of_2?(number) return true if number == 1 return false if number == 0 || number % 2 != 0 power_of_2?(number / 2) end

Once again, it solves the problem, but this time recursively. Since those early days of Java and C, I’ve played around with a whole bunch of languages, some just as imperative, but others were functional or had functional capabilities. In such languages, recursion is the norm or at least a lot more prevalent. I find that I really like recursive solutions, it is often a very elegant way to get around some ugly code. Even though it is not the first stop my brain makes when it comes to solving programming problems, I find that these days I almost always consider if there might be a recursive way to approach a problem. I don’t yet always instinctively feel if a problem has a recursive answer, but in many cases (like this one) it is fairly simple. As long as you can divide the initial problem into two smaller parts which are “equivalent” to the original problem, you can solve it recursively (like when you split a tree you get two smaller trees).

I do wonder if programmers who were “weaned” on functional languages would go for the recursive solution first and if they find one do they bother to consider an iterative one at all? If you’re such a developer, please share how you think.

The Next Thing I Thought Of Wasn’t Code

It is only recently that I have started to give bit hacking the attention it deserves. It always used to seem like it wasn’t worth the trouble, but since I’ve learned a bit more about Bloom Filters (I’ll write it up one of these days, hopefully make it a bit easier to grok) and finally got my hands on a copy of “Programming Pearls”, I’ve become a bit of a convert. So, whenever I hear “power of 2” or anything similar these days, I always think that there is surely some bit hacking to be done :), which is exactly what my brain latched on to after the iterative and recursive approaches.

Consider that any number that is a power of 2 has exactly one bit set in its binary representation e.g.:

2    =  00000010 
4    =  00000100 
8    =  00001000 
16   =  00010000 
256  = 100000000

If we subtract 1 from any of these numbers we get the following:

2 - 1 = 1 = 00000001 
4 - 1 = 3 = 00000011 
8 - 1 = 7 = 00000111

Every bit that was less significant than the original interesting bit (the one that was set), is now set while the original bit is unset. If we now do a bitwise and (& operator) on the original number and the number which results when 1 is subtracted, we always get zero:

2 & 1 = 00000010 & 00000001 = 0 
8 & 7 = 00001000 & 00000111 = 0

This will only happen if a number is a power of two. Therefore we can write the following code:

ruby def power_of_2?(number) number != 0 && number & (number - 1) == 0 end

This is apparently a pretty well known way to determine if a number is a power of 2. In the olden days when computing resources were scarce, every programmer probably knew about this shortcut and others like it, these days – not so much. But, you have to admit it is by far the cleanest solution of the three, even the need to treat zero separately makes it only marginally less elegant. Definitely a handy thing to remember (it does still come up occasionally in the real world).

I do wonder though, is anyone’s brain sufficiently indoctrinated into bit hackery that they would jump to this solution first without even considering an iterative or a recursive one? Anyone?

If Someone Ever Actually Asks You This In An Interview…

The first thing to do would be to write (or at least mention) some tests. They don’t have to be proper unit tests in this case (although for more complex questions it may be warranted), but you will never go wrong if you show that you’re aware of testing. In this case something along the lines of this is probably fine:

ruby puts "fail 2" if !power_of_2? 2 puts "fail 4" if !power_of_2? 4 puts "fail 1024" if !power_of_2? 1024 puts "fail 1" if !power_of_2? 1 puts "fail 1025" if power_of_2? 1025 puts "fail 0" if power_of_2? 0 puts "fail 3" if power_of_2? 3

0,1,2 and 3 are the cases where our function is likeliest to break the rest are included for completeness. The other thing that may be worth mentioning is the fact that the behaviour of the function for negative integers or floats is undefined, you can of course handle those cases, but it adds extra complexity and I think simply showing that you’re aware of them is enough.

After this you can go ahead and write your function, remember – bit hackery means extra points (as far as I am concerned anyway :)).

Image by .m for matthijs