01 Oct 2018

# Introduction

Fizz Buzz is a division game that is commonly used as a programming exercise. It is sometimes used as an interview problem.

There are those who debate whether this or any programming test is a fair or useful method for interviewing, but I personally like to use it in the interviews I conduct. If you are interested in the debate here are some links: 1, 2, 3

I see the test as an avenue for detailed discussion about code, which can be bypassed if the applicant has already provided some sort of portfolio we can discuss. I think it is critical to discuss both high-level and low-level aspects of code.

# Warming Up

I consider implementing the letter of the exercise to be just a warm up. I am fine with the applicant using any language and any online resources to complete this exercise. (Yes, someone has just Googled the solution for FizzBuzz before.) If the user has brought a laptop, she can use it; otherwise, she will use a laptop loaded with some mainstream languages like Java, node, Ruby, and Python. For this part of the interview, I just want to see that the task can be done. Here are the instructions as I’d typically give them:

Implement FizzBuzz for the numbers 1 through 100. Print the following for each number:

• If the number is a multiple of 3, print Fizz
• If the number is a multiple of 5, print Buzz
• If the number is a multiple of 3 and 5, print FizzBuzz
• Otherwise, print the number.

During implementation, I will answer any questions the applicant asks. We may also discuss implementation details and tradeoffs. Once the applicant says she is done, we talk about whether the program works. There are a number of valid interpretations of this problem. What I’m looking for in the end is some output like the following:

``````1
2
Fizz
4
Buzz
Fizz
7
8
Fizz
10
11
Fizz
13
14
FizzBuzz
...
``````

If the applicant has not separated the output with newlines, I will typically have them do that so the output is a little easier to read. There are also variations where the user starts at 0, ends at 101, or prints the number on each line. I will ignore these problems depending on the later results.

The “If/else ladder” and concatenation examples at Rosetta Code are representative of the type of solutions I will usually get from Java developers, which is obviously similar to the C# solutions I’ve seen.

Once we talk about the validity of the output, we will proceed to talk about implementation details. Here are some things to discuss with the applicant.

• What improvements can be made to the code?
• How can modulo be used? How can division?
• How can the input range parameterized?
• How can the program be made more maintainble?
• How can the program be made shorter?
• What is the level of familiarity with the language used?
• How can you output to stdout? How can you output to a file?
• How would you write a test for this?

At this point, I may decide to have the applicant try to implement one of the things we discussed, especially if they struggled with any of the discussion. If they implemented most of these things in their solution, I will skip to the next part of the interview.

# Performance

I segue the warm up into a discussion about performance. If I notice there are performance improvements possible, I ask the applicant to change the program to write the results to a file.

I ask the applicant whether she thinks the code is performant.

After this is done, I ask the applicant to run the program from 1 to 10 million. This typically exposes some issues, and we discuss how fast the program should be.

There are two common mistakes here:

• Attempting to keep everything in memory
• Not buffering/batching file I/O

For example, the If/else ladder example would be changed to something like:

``````import java.io.*;

public class FizzBuzz{
public static void main(String[] args) throws IOException {
try(BufferedWriter log = new BufferedWriter(new OutputStreamWriter(System.out))) {
for(int i= 1; i <= 10000000; i++){
if(i % 15 == 0){
log.write("FizzBuzz");
} else if(i % 3 == 0){
log.write("Fizz");
} else if(i % 5 == 0){
log.write("Buzz");
} else{
log.write(String.valueOf(i));
}
log.write('\n');
}
log.flush();
}
}
}
``````

And the Concatenation example might be changed to use StringBuilder and flush the output in batches (if there is memory pressure).

# Concurrency

After the performance part, I ask how the program can be made faster. This leads to a discussion about concurreny and parallel programming.

Some questions for discussion here:

• What are the concurrency primitives for the language?
• What are the tradeoffs between them?
• How would you implement this program to do parallel work?

If there is time, then we’ll attempt to implement a parallel solution. Here is a possible first attempt in Java.

``````import javafx.util.Pair;
import java.io.*;
import java.util.*;

public class FizzBuzz implements Runnable {
public long start;
public long end;
public String result;

public FizzBuzz(long start, long end) {
this.start = start;
this.end = end;
}

@Override
public void run() {
result = fizzbuzz(start, end);
}

public static fizzbuzz(long start, long end) {
StringBuilder sb = new StringBuilder();
for(long i= start; i < end; i++){
if(i % 15 == 0){
sb.append("FizzBuzz");
} else if(i % 3 == 0){
sb.append("Fizz");
} else if(i % 5 == 0){
sb.append("Buzz");
} else{
sb.append(i);
}
sb.append('\n');
}
return sb.toString();
}

public static void main(String[] args) throws IOException, InterruptedException {
long batchSize = 1000000;
long start = 1;
long end = 10000000 + 1;
List<Pair<FizzBuzz, Thread>> pairs = new ArrayList<>();

for(long i= start; i <= end; i+=batchSize){
FizzBuzz fb = new FizzBuzz(i, Math.min(i + batchSize, end));
}

try(BufferedWriter log = new BufferedWriter(new OutputStreamWriter(System.out))) {
for (Pair<FizzBuzz, Thread> pair : pairs) {
FizzBuzz fb = pair.getKey();
log.write(fb.result);
}
log.flush();
}
}
}
``````

There are a number of issues with this code that we could discuss including:

• Unconfigurable arguments for start and end
• If the arguments were configurable, unbounded execution of threads.
• There are alternatives to joining the threads that we could use. For example we could write each chunk to a file, and join the files later. Although writing to the filesystem would incur a higher IO penalty, it would reduce the memory pressure on the system, allowing the program to operate with less heap memory. This type of solution might be needed if we increase the upper bound above 1 billion.
Looking for more content? Check out other posts with the same tags: