## Thursday, August 10, 2017

### FizzBuzz Analysis

Recently I was asked this kind of question. As I was told not to worry too much about it and I got many other questions to answer within short time, I did not pay attention to much on it and just scribbled it on a piece of paper, no time to mentally test the algorithm.

At home I realized I did not complete the answer (blame that to the recruiter).  Anyway, the fizz buzz interview question is to ask interviewee to write a code to print number from 1 to 100, but for every multiplication of 3 to print string "FIZZ" (or something), for every multiplication of 5 to print string "BUZZ", and for every multiplication of 3 and 5 (which is another way to say multiplication of 15) to print "FIZZBUZZ".

Here's my working code in C++:

#include <iostream>

using namespace std;

const static char *s1 = "FIZZ";
const static char *s2 = "BUZZ";

int main()
{
for(int i=1; i<=100; i++)
{
if (i% 3*5==0)
{
cout << s1 << s2 << endl;
continue;
}
if (i % 3 == 0)
{
cout << s1 << endl;
continue;
}
if (i % 5 == 0)
{
cout << s2 << endl;
continue;
}

cout << i << endl;
}
}

No matter whay you do, the optimal solution is always O(n) (unless you're crazy enough to just print manually without loop, such as cout << "1\n2\FIZZ\n4\BUZZ\n...|").

Some silly optimization can be performed in printing the string, though.

#include <iostream>

using namespace std;

const static string s = "FizzBuzz";

int main()
{
for(int i=1; i<=100; i++)
{
if (i%15==0)
{
cout << s << endl;
continue;
}
if (i % 3 == 0)
{
cout << s.substr(0,3) << endl;
continue;
}
if (i % 5 == 0)
{
cout << s.substr(4) << endl;
continue;
}

cout << i << endl;
}
}

Another thought is to eliminate mod 15.  For example:

#include <iostream>

using namespace std;

const static string s = "FizzBuzz";

int main()
{
int m;
for(int i=1; i<=100; i++)
{
m = 0;
if (i%3==0)
{
cout << s.substr(0,3);
m++;
}
if (i % 5 == 0)
{
cout << s.substr(4);
m++;
}
if (m > 0)
cout << endl;
else
cout << i << endl;
}
}

When I tested it (upper limit set to 1000 and perform "time <program>", the last algorithm shows some speedup.

The last few lines can be optimized to be:

if (m == 0)
cout << i;
cout << endl;

Another tiny optimization is instead of doing post increment (i++), we do preincrement (++i).  This saves tiny bit (no copy to extra variable internally).

Last, we can write it down in Assembly if we want.  The following is suitable for embedded device:

main:
leal 4(%esp), %ecx
andl    \$-16, %esp
pushl -4(%ecx)
pushl %ebp
movl %esp, %ebp
pushl %edi
pushl %esi
pushl %ebx
pushl %ecx

subl \$8, %esp
movl \$1, %ebx         ; EBX=1
movl \$3, %esi         ; ESI=3
movl \$5, %edi         ; EDI=5
jmp CHECK_FIZZ

FOR_I_NEXT:
movl %ebx, %eax       ; eax stores current value of i
cltd
idivl %edi             ; i / 5, result in eax and mod in edx
testl %edx, %edx       ; i % 5
jne PRINT_I          ; i % 5 != 0 -> jump to PRINT_I

CHECK_FUZZ:
subl \$8, %esp
pushl stdout
pushl 'f'
call _IO_putc
popl %edx
popl %ecx
pushl stdout
pushl 'i'
call _IO_putc
popl %eax
popl %edx
pushl stdout
pushl 'z'
call _IO_putc
popl %ecx
popl %eax
pushl stdout
pushl 'z'
call _IO_putc

PRINT_CR:
subl   \$8, %esp
pushl stdout
pushl '\n'
call _IO_putc
incl %ebx
cmpl \$101, %ebx           ; i == 101 ?
je MAIN_EXIT            ; if (i ==101) goto MAIN_EXIT

CHECK_FIZZ:
movl %ebx, %eax
cltd
idivl %esi
testl %edx, %edx           ; i % 3 == 0
jne FOR_I_NEXT
subl \$8, %esp             ; if (i%3==0):
pushl stdout
pushl 'b'
call _IO_putc
popl %eax
popl %edx
pushl stdout
pushl 'u'
call _IO_putc
popl %ecx
popl %eax
pushl stdout
pushl 'z'
call _IO_putc
popl %eax
popl %edx
pushl stdout
pushl 'z'
call _IO_putc
movl %ebx, %eax
cltd
idivl %edi
testl %edx, %edx
jne PRINT_CR
jmp CHECK_FUZZ

PRINT_I:
pushl %eax
pushl %ebx
pushl \$.LC0
pushl \$1
call __printf_chk
jmp PRINT_CR
MAIN_EXIT:
xorl   %eax, %eax
leal -16(%ebp), %esp
popl %ecx
popl %ebx
popl %esi
popl %edi
popl %ebp
leal -4(%ecx), %esp
ret