Exploring Fizz Buzz

Posted by

Nowadays, most developer candidate will face an algorithmic based puzzle at their hiring technical interviews. One of the favorite exercise of recruiters is the Fizz Buzz exercise.

The first time a colleague of mine introduce this exercise to me, I thought it was a dumb exercise. Then he showed me how to do it. And I realized I was wrong. There is something beautiful about a problem that can be bent in almost any direction, depending on where the candidate goes.

Today’s post is about describing this exercise, and how it typically goes with a candidate. Through this journey, I hope to show you what makes Fizz-Buzz such a fantastic exercise.

Let us start by defining the problem.

 

Fizz buzz (Basic Problem)


The candidate is asked to write a function that takes as input an positive integer N and returns a string. The string should be equal to:

  • “fizz” if the number is divisible by 3
  • “buzz” if the number is divisible by 5
  • “fizzbuzz” if the number is divisible by both 3 and 5
  • The number N converted to a string otherwise (“11” for 11)

There is a trick here: to get rid of duplicated conditionals, the candidate usually struggles with a potential “else” and where to insert it. But most candidate do not get stuck very long, and come up with an answer that usually looks like this:

string fizz_buzz(int i)
{
   string out;
   if (i % 3 == 0)  out += "fizz";
   if (i % 5 == 0)  out += "buzz";
   return out.empty() ? to_string(i) : out;
}

 
Done? Not quite.

This is where the “fun part” begins. The recruiter will keep making the problem more complex to check how the candidate adapts to these growing requirements.

 

Fizz Buzz Tweet Flour…


One of the most common enhancement asked by the recruiter is to add more rules. The purpose is to mimic the unavoidable law of software: a happy customer is a needy customer.

The recruiter might add the following additional rules:

  • “tweet” if the number is divisible by 7
  • “flour” if the number is divisible by 10
  • “fizzbuzztweet” if the number is divisible by 3, 5 and 7
  • … (insert all combinations there) …

The goal is obviously to check how the candidate reacts to these growing requirements. Specifically, how much time the candidate takes to realize there is something more to do that just stacking up if-statements in the body of the function.

Let us say the candidate reached the following point:

string fizz_buzz(int i)
{
   string out;
   if (i % 3 == 0)  out += "fizz";
   if (i % 5 == 0)  out += "buzz";
   if (i % 7 == 0)  out += "tweet";
   if (i % 10 == 0) out += "flour";
   return out.empty() ? to_string(i) : out;
}

 
At this point, a good candidate should have seen the pattern appear. Most brilliant candidates will see it before they start writing code.

Here is a typical first attempt at factorization I saw a lot:

const char* apply_rule(int i, int divisor, const char* outcome)
{
   return i % divisor == 0 ? outcome : "";
}

string fizz_buzz(int i)
{
   string out;
   out += apply_rule(i, 3, "fizz");
   out += apply_rule(i, 5, "buzz");
   out += apply_rule(i, 7, "tweet");
   out += apply_rule(i, 10, "flour");
   return out.empty() ? to_string(i) : out;
}

 
Although it has the advantage of putting a name on what we do (a bit of abstraction is always welcomed), it does not solve the fundamental problem of the overall approach: the function will keep growing.

 

Loops and Data Structures


The solution is to realize there is a loop somewhere here, and modify the code to take advantage of that loop. It also means introducing a collection to contain those rules (typically given as input to the function).

You should expect something like this:

string fizz_buzz(vector<pair<int, string>> const& rules, int i)
{
   string out;
   for (auto const& rule : rules)
   {
      if (i % rule.first == 0)
         out += rule.second;
   }
   return out.empty() ? to_string(i) : out;
}

 
The test driver code should look like this:

vector<pair<int, string>> rules = { { 3, "fizz" }, { 5, "buzz" } };
fizz_buzz_generic(rules, 3);

 
There are obviously many different possible answers here:

  • Some will create a class “Rule” to contain the divisor and the outcome
  • Some think in terms of interfaces or functions (from integer to strings)

The one interesting pitfall is when the candidate tries to introduce a hash map or ordered map. Because using an associative container will mess up the ordering, this solution does not produce the right output.

But still, a lot of candidate will think in terms of key-value pairs and immediately jump to a hash map. This makes for a usually interesting question to the candidate.

 

Conclusion


We have seen what Fizz Buzz is, and how this exercise usually goes with a candidate, when we make it more complex.

I hope I have convinced you of how good this small problem really is: it is small, proceeds by steps, tests different skills, introduces the concept of growing requirements in software and tests how the candidate reacts to these new requirements.

One comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s