## A better solution to the FizzBuzz interview problem

Many months ago, I wrote about a simple programming problem that I was administering to interviewees at work to assess their programming skills. The basic problem is this: loop through a range of integers, outputting different strings depending on whether each integer is divisible by one given number, by another given number, by both given numbers, or by neither. It’s a very basic weed-out problem that can be solved easily by any applicant with a basic understanding of control structures and modular arithmetic.

Last week, the comments section on that post erupted with new activity. I posted my own solution, which I was then criticized for because it used more than two division operations per integer (and as you should know, division is by far the most expensive basic arithmetic operation on a computer). So I got to brainstorming and I quickly came up with a solution that uses two divisions *total*, no matter how large the range is. I’m pretty convinced that my solution is very close to optimal (minus some minor fudging regarding how the if-statements are laid out and how the modular incrementing is handled). Here’s the solution in Java, simply because Java is the language most job applicants seemed to want to solve the problem in:

public class FizzBuzz {

// I got lazy and coded in the parameters as constants instead of as arguments.

static final int x = 3; // The first integer to test divisibility on

static final int y = 5; // The second integer to test divisibility on

static final int a = 27; // The starting number in the range to process

static final int b = 74; // The ending number in the range to process

public static void main(String[] args) {

int x1 = a % x; // These are our only

int y1 = a % y; // two divides!!

for (int i = a; i <= b; i++) {
if (x1 == 0) System.out.print("Fizz");
if (y1 == 0) System.out.print("Buzz");
if (x1 != 0 && y1 != 0) System.out.print(i);
System.out.println("");
x1 = ( x1 == x - 1 ? 0 : x1 + 1);
y1 = ( y1 == y - 1 ? 0 : y1 + 1);
}
}
}
[/code]
Pretty nifty, eh? Instead of having to perform expensive division operations on each integer in the loop, we're simply incrementing two modular counters. This solution immediately suggests a good part two for the FizzBuzz interview question. After the applicant demonstrates basic familiarity with how programming works by writing up the naive solution, test their analytical abilities by asking them to come up with a more efficient version of the same program. If they don't know it already, explain that division operations are expensive, and then ask them to minimize the total number of division operations necessary.
There will be a fair number of people who can get through the first part of the problem but won't be able to get through the second part of the problem without a lot of hints. It's these people that you may want to avoid hiring, because being able to improve on the naive algorithm and find more optimized ways of doing things is *very* important in programming. So, if you happen to be in a hiring position at a programming company, do try this problem out, and let me know how it goes!

July 9th, 2008 at 09:47

Why not use 1 divide. In C:

int xy = x * y;

int x1 = a % xy;

int array = new int[xy];

for (int i = 0; i < xy; i++)

{

array[i] = 0;

}

for (int i = 0; i < xy; i+=x)

{

array[i] += 1;

}

for (int i = 0; i < xy; i+=y)

{

array[i] += 2;

}

for (int i = a; i <= b; i++) { int j = array[x1++]; if (x1 == xy) x1 = 0; if (j == 3) printf(”FizzBuzz\n”); else if (j == 1) printf(”Fizz\n”); else if (j == 2) printf(”Buzz\n”); else printf(”%d\n”, i); }

July 9th, 2008 at 10:53

Interesting, but I think that the extra memory allocation of the array (and the subsequent iteration over it and modification of it) makes it more expensive in all situations. Especially as x and y grow larger; my solution is nearly as fast when x and y are numbers in the millions, whereas the size of the array necessary in your solution would need to hold trillions of integers. Divisions are expensive, sure, but they are still a simple arithmetic operation, and will always be faster than having to call an OS function to allocate memory for an array.

My solution only uses two integers in addition to all of the input parameters. I wonder if anything better is possible?

October 19th, 2009 at 13:49

Is this kind of stuff really still relevant to modern programming? It’s very useful as an exercise and to see how the candidate performs under pressure, and they should be able to get to the end of it (including your extension to avoid division) but it’s not really very relevant to the majority of modern data-shovelling applications.

I am not a JIT compiler. Nor am I processor designer. I have absolutely no idea, without measuring, whether division is expensive or whether some other aspect of the algorithm will overshadow the division. The correct way to do modern programming, in my opinion, is to write readable code and then measure whether it’s fast enough. One single database hit in the same piece of functionality that’s doing all these “unnecessary” divisions would totally overshadow the division.

This is a great little programming exercise, it’s just miles away from real world programming. Anyone who tells you otherwise is either working on one of the extreme minority of situations where algorithmic performance actually matters, or they’re wasting time and money optimizing for the sake of it. Premature optimization is the root of all evil.

October 17th, 2012 at 11:13

I gotta favorite this website it seems extremely helpful

invaluable