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
addl $16, %esp
PRINT_CR:
subl $8, %esp
pushl stdout
pushl '\n'
call _IO_putc
incl %ebx
addl $16, %esp
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
addl $16, %esp
testl %edx, %edx
jne PRINT_CR
jmp CHECK_FUZZ
PRINT_I:
pushl %eax
pushl %ebx
pushl $.LC0
pushl $1
call __printf_chk
addl $16, %esp
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
