There's only one thing worse than setting development screening tests and having to mark them, and that is being required to sit a screening test yourself which happens to contain a typical question that you yourself set in a past test. Well... I guess that should be a good thing (you say), since you've had the opportunity to think hard about it. Perhaps ... if you happen to have done that recently.
I'm presently interviewing for local work in Adelaide, Australia, the home of green hills, Alpacas and good wine. With interviews come tests, and so far I've had to write a variety of IKM tests and at least one home grown test. One of the questions in the latter was FizzBuzz:
"Players generally sit in a circle. The player designated to go first says the number "1", and each player thenceforth counts one number in turn. However, any number divisible by three is replaced by the word fizz and any divisible by five by the word buzz. Numbers divisible by both become fizz buzz. A player who hesitates or makes a mistake is eliminated from the game."
In C#, a naïve implementation:
for (var i=1; i <= 10000000; i++) {
var dividedBy3 = i / 3;
var dividedBy5 = i / 5;
if (i-(dividedBy3*3) == 0 && i-(dividedBy5*5) == 0)
Console.WriteLine("FizzBuzz");
else if (i-(dividedBy3*3) == 0)
Console.WriteLine("Fizz");
else if (i-(dividedBy5*5) == 0)
Console.WriteLine("Buzz");
else
Console.WriteLine(i);
}
Ten million iterations executes in a little over six seconds:
$ time (csharp content/code/fb-naive.cs > /dev/null)
( csharp content/code/fb-naive.cs > /dev/null; ) 6,45s user 3,55s system 99% cpu 10,024 total
If we use the mod operator, we would expect things to be a little faster:
for (var i=1; i <= 10000000; i++) {
var m3 = i % 3;
var m5 = i % 5;
if (m3 == 0 && m5 == 0)
Console.WriteLine("FizzBuzz");
else if (m3 == 0)
Console.WriteLine("Fizz");
else if (m5 == 0)
Console.WriteLine("Buzz");
else
Console.WriteLine(i);
}
Surprisingly though, this isn't the case:
$ time (csharp content/code/fb-a-little-better.cs > /dev/null)
( csharp content/code/fb-a-little-better.cs > /dev/null; ) 6,52s user 3,53s system 99% cpu 10,071 total
The interview that I did was for a hands-on position working on a piece of software that is performance sensitive, so ... let's see if doing the integer comparison no more than we need to will help any:
for (var i=1; i <= 10000000; i++) {
var m3 = i % 3 == 0;
var m5 = i % 5 == 0;
if (m3 && m5)
Console.WriteLine("FizzBuzz");
else if (m3)
Console.WriteLine("Fizz");
else if (m5)
Console.WriteLine("Buzz");
else
Console.WriteLine(i);
}
As a sanity check, is this still producing what we expect?
$ csharp content/code/fb-hopefully-better.cs | head -20
1
2
Fizz
4
Buzz
Fizz
7
8
Fizz
Buzz
11
Fizz
13
14
FizzBuzz
16
17
Fizz
19
Buzz
The corresponding times for this (hopefully) better version:
$ time (csharp content/code/fb-hopefully-better.cs > /dev/null)
( csharp content/code/fb-hopefully-better.cs > /dev/null; ) 6,45s user 3,58s system 99% cpu 10,081 total
At this point it's becoming fairly clear that I've succumbed to mistaking precision for accuracy.
Clearly, the vast majority of time is spent on I/O, so let's eliminate that as a factor whilst preserving the ability to easily verify that the results are correct:
var firstFifteen = new[] { "1", "2", "Fizz", "4", "Buzz", "Fizz", "7", "8", "Fizz", "Buzz",
"11", "Fizz", "13", "14", "FizzBuzz" };
Func<int,string> buzzer = i => {
string fb;
var m3 = i % 3 == 0;
var m5 = i % 5 == 0;
if (m3 && m5)
fb = "FizzBuzz";
else if (m3)
fb = "Fizz";
else if (m5)
fb = "Buzz";
else
fb = i.ToString();
return fb;
}
for (var i=1; i <= 100000000; i++) {
string fb;
if (i <= 15 && firstFifteen[i-1] != (fb = buzzer(i)))
throw new ApplicationException(string.Format(
"{0} does not match expected {1}", fb, firstFifteen[i-1]));
}
As expected, even after bumping up the number of iterations by 10, this is now much faster than the previous version:
$ time (csharp content/code/fb-verify.cs > /dev/null)
( csharp content/code/fb-verify.cs > /dev/null; ) 0,36s user 0,05s system 96% cpu 0,421 total
Now, let's concentrate on making this a little DRY er (note that I've bumped the number of iterations up again by a factor of 10, bringing it to a trillion [thousand million]):
var firstFifteen = new[] { "1", "2", "Fizz", "4", "Buzz", "Fizz", "7", "8", "Fizz", "Buzz",
"11", "Fizz", "13", "14", "FizzBuzz" };
Func<int,string> buzzer = i => {
string fb = string.Empty;
var m3 = i % 3 == 0;
var m5 = i % 5 == 0;
if (m3)
fb = "Fizz";
if (m5)
fb += "Buzz";
if (!(m3 || m5))
fb = i.ToString();
return fb;
}
for (var i=1; i <= 1000000000; i++) {
string fb;
if (i <= 15 && firstFifteen[i-1] != (fb = buzzer(i)))
throw new ApplicationException(string.Format(
"{0} does not match expected {1}", fb, firstFifteen[i-1]));
}
Corresponding timings:
$ time (csharp content/code/fb-dry.cs > /dev/null)
( csharp content/code/fb-dry.cs > /dev/null; ) 0,94s user 0,06s system 99% cpu 1,000 total
Compared to the (trillion iterations) version of the non-DRY FizzBuzzer:
$ time (csharp content/code/fb-verify-moreits.cs > /dev/null)
( csharp content/code/fb-verify-moreits.cs > /dev/null; ) 0,92s user 0,06s system 98% cpu 0,995 total
What does this do for us? Absolutely zilch IMO; that is, other than: If you want to measure things, follow these golden rules:
- Don't ever make assumptions about where performance issues lie; you'll almost always be wrong (despite your beliefs to the contrary);
- Always make sure that what you're measuring is related to the problem you're trying to solve.
As a spicey ending to another inconsequental post: FizzBuzz in one line of C#:
Console.WriteLine(string.Join("\n", Enumerable.Range(1,20)
.Select(n => new Tuple<int,bool,bool>(n, n % 3 == 0, n % 5 == 0))
.Select(t => (t.Item2 ? "Fizz" : string.Empty) +
(t.Item3 ? "Buzz" : string.Empty) +
((t.Item2 || t.Item3) ? string.Empty : t.Item1.ToString()))));
$ csharp content/code/fb-1line.cs
1
2
Fizz
4
Buzz
Fizz
7
8
Fizz
Buzz
11
Fizz
13
14
FizzBuzz
16
17
Fizz
19
Buzz
Comments !