Using The FizzBuzz Problem to Explain the Goals of Algorithms

#algorithms #go #interview #programming

In this article, you will gain some insights required to write algorithms that ace job interviews.

The major aim of the article is to explain the five common goals of an algorithm.
In the course of the article, I will explain the simple FizzBuzz algorithm, and implement it in Golang. Additionally, I use two methods to explain the importance of writing clean, readable code.

Introduction

Algorithms are mathematical and computational procedures in solving problems.
Problems are binary relations of inputs and outputs. In a typical coding challenge or job interview, you have a set of input, and are looking to produce a set of possible output.

An algorithmic or computational problem is specified by describing the complete set of instances it must work on and of its output after running on one of these instances.
The first goal, therefore, of an algorithm is to Solve Problems.

Solving Fizz and Buzz with a Simple Sorting Algorithm

You must have heard of the FizzBuzz algorithm before, especially if you have an experience in data structures and algorithms. It can be spelt as Fizz Buzz, FizzBuzz, or Fizz-Buzz. Whichever one you prefer, it remains a common question in technical job interviews.

Imagine a set of numbers from 1 to 10.

x = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

Fizz and Buzz refer to all number that's a multiple of 3 and 5 respectively. In other words, if a number is divisible by 3, it is categorized as fizz; if a number is divisible by 5, it is categorized as buzz.

fizz(x) = {3, 6, 9}
buzz(x) = {5, 10}

If a number is simultaneously a multiple of 3 AND 5, the number is replaced with "fizz buzz." In essence, it emulates the famous children game "fizz buzz."

In writing the algorithm for solving this computational problem, iterate through the array and check which numbers are fizz and which are buzz. To do this, create a for loop to iterate through the set of numbers from 1-10:

for x := 1; x <=10; x++ {
   if x % 3 ==  0 {
          fmt.Println("Fizz", x)
   } else if x % 5 == 0 {
          fmt.Println("Buzz", x)
   }
   fmt.Println(x)
}

You can run this code in the Go Playground.

You see the output as exactly the fizz(x) and buzz(x) values.

It is not enough. FizzBuzz refer to cases where elements of the set are both divisors of fizz and buzz i.e., 3 and 5.
What makes a computational solution an algorithm is if it can perform efficiently for both large and small area of data. Expert algorists will argue that an algorithm should perform better with larger data sets than smaller.
The second goal of an algorithm is to Argue Efficiency.

The FizzBuzz (in Confusing Code)

The FizzBuzz Algorithm can be improved to a series of if else statements: popular for sorting algorithms. This, however, requires a larger dataset.

func main() {
    for i := 1; i <= 100; i++ {
        if i%3 == 0 {
            if i%5 == 0 {
                fmt.Println("FizzBuzz at", i)
            } else {
                fmt.Println("Fizz")
            }
            if i%5 == 0 {
                fmt.Println("Buzz")
            } else {
                fmt.Println(i)
            }

        }
    }
}

You can run this code in the Go Playground.

You see the expected output, but there's a trade-off here:

Go’s motto is in favor of clean, readable code. Hence, avoid writing nested code of if, else if and else statements.
The third goal of an algorithm is to Communicate Ideas. I know an algorist who got his offer with only pseudocodes. If you ever get stuck in writing an algorithm, switch to pseudocode or draw a flowchart.

The FizzBuzz (in Clean Code)

Instead of writing nested code that might confuse your interviewer, you can use if and continue to make code cleaner.

func main() {
    for i := 1; i <= 100; i++ {
        if i%3 == 0 && i%5 == 0 {
            fmt.Println("FizzBuzz at", i)
            continue
        }
        if i%3 == 0 {
            fmt.Println("Fizz")
            continue
        }
        if i%5 == 0 {
            fmt.Println("Buzz")
            continue
        }
        fmt.Println(i)
    }
}

You can run this code in the Go Playground.

The continue keyword skips an iteration and moves to the next.
The output confirms the fourth goal of an algorithm: to Prove Correctness.

Algorithmic Thinking

The fifth and grandest goal of an algorithm is to correctly Optimize Runtime.
As the range of the dataset increases to 1-100, you have to think carefully for ways to reduce the runtime.

Given, the compiler will check each number to determine whether it is divisible by 3 or 5. It will then run through the numbers again to check if the numbers are divisible by 3 and 5. The code would essentially have to run through each number in the array twice — it would have to runs the numbers by 3 first and then run it by 5. This reduces the speed or time complexity of the algorithm in a sense.

To speed up the process, you can simply divide the numbers by 15 directly, since the smallest FizzBuzz is the product of fizz and buzz i.e. 3 x 5 = 15.

func main() {
    for i := 1; i <= 100; i++ {
        if i%15 == 0 {
            fmt.Println("FizzBuzz at ", i)
        } else if i%3 == 0 {
            fmt.Println("Fizz")
        } else if i%5 == 0 {
            fmt.Println("Buzz")
        } else {
            fmt.Println(i)
        }
    }
}

You can run this code in the Go Playground.

Conclusion

In this article, you learned the definition of several concepts. Moreover, you saw use cases of control structures in Go. You also learned how nested loops make code confusing, and a good way to solve this.
More importantly, you learnt about the five common goals of an algorithm and what they mean. You also leart how to use a simple sorting algorithm to solve the FizzBuzz problem.
Finally, you learnt the need and benefits of thinking algorithmically i.e. of how to optimize the runtime of your algorithm. In a competitive setting, this gives you an edge.