A better solution to the FizzBuzz interview problem
Wednesday, July 2nd, 2008Many 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);
}
}
}
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!
