Friday, October 17, 2008

Interview Question: FizzBuzz

Đây là 1 câu hỏi phỏng vấn dạng simple programming test (không dùng computer), nhằm loại bớt những người dự tuyển tuyên bố là thông thạo về 1 ngôn ngữ nào đó (nhưng thực tế rất ít viết code).

Theo tôi dạng phỏng vấn này khá hiệu quả, bởi nó cho thấy ứng viên có lập trình bằng ngôn ngữ này trong vòng 3 tháng gần đây, và cũng phần nào phản ánh suy nghĩ, phong cách lập trình của người viết.
Ít ra cũng không thuộc dạng stupid-interview-questions (cái này khi nào có dịp sẽ bàn kỹ hơn) .


Đề bài:
Write a program that prints the numbers from 1 to 100. But for multiples of three print "Fizz" instead of the number and for the multiples of five print "Buzz". For numbers which are multiples of both three and five print "FizzBuzz".
(Viết 1 chương trình in các con số từ 1 đến 100. Tuy nhiên ở những con số là bội số của 3 thì in ra "Fizz", bội số của 5 thì in ra "Buzz", bội số của cả 3 và 5 thì in ra "FizzBuzz" thay cho các con số đó.)


Dĩ nhiên là There's More Than One Way To Do It (TMTOWTDI, đọc là "tim-toady") , câu nói yêu thích của các lập trình viên Perl.


Ở đây tôi nêu lên vài cách giải mà theo tôi là ổn (if I were the interviewer) :

* Đơn giản: (KISS, YAGNI)
Code đơn giản không có nghĩa là code ngắn nhất, hay là phải dùng những phần tử cơ bản nhất, mà là dễ dàng đáp ứng ĐỦ yêu cầu (kết quả đúng ngay từ lần đầu chạy), trong khi trình bày ngắn gọn và dễ hiểu.

(Python)

for i in range(1, 100):
if (i % 3 == 0) and (i % 5 == 0):
print “FizzBuzz”
elif i % 3 == 0:
print “Fizz”
elif i % 5 == 0:
print “Buzz”
else:
print i

(Ruby)

1.upto(100) do |number|
if number % 15 == 0 then
puts 'FizzBuzz'
elsif number % 5 == 0 then
puts 'Fizz'
elsif number % 15 == 0 then
puts 'Buzz'
else
puts number
end
end

(Lisp)

(for (i 1 100)
(if
(= 0 (% i 15)) (set 'i "FizzBuzz")
(= 0 (% i 5)) (set 'i "Buzz")
(= 0 (% i 3)) (set 'i "Fizz"))
(println i))


* Dễ dùng lại và mở rộng: (DRY, DRW)
VD nếu như sửa Blah là bội của 4 (thay vì Fizz của 3), hoặc thêm vào FizzBuzzBlah là bội của 60 (3x4x5) , thì liệu code bạn viết lại có đỡ tốn công và vẫn giữ được các ưu điểm (dễ hiểu, chạy nhanh, ...) hay không?

(Ruby)

a = nil, 'fizz', 'buzz', 'fizzbuzz'
1.upto(100) { |a[0]| puts a[(a[0]%3 == 0 ? 1 : 0) + (a[0]%5 == 0 ? 2 : 0)] }

(Ruby - extended)
a = nil, 'Fizz', 'Buzz', 'FizzBuzz', 'Blah', 'FizzBlah', 'BlahBuzz', 'FizzBuzzBlah'
1.upto(100) { |a[0]| puts a[(a[0]%3 == 0 ? 1 : 0) + (a[0]%5 == 0 ? 2 : 0) + (a[0]%4 == 0 ? 4 : 0)] }



* Dễ nhìn, thanh thoát: (Refactoring, DRY)
Thường sau khi viết đạt yêu cầu KISS ta sẽ refactor code để củng cố YAGNI và DRY , cũng để code dễ nhìn và dễ hiểu hơn, mặc dù về performance hoặc line-of-code thì có thể không tối ưu lắm.

(Java - verbose)
public class FizzBuzz {
public static void main(String[] args) {

for(int i = 1; i <= 100; i++) {
if (((i % 3) == 0) && ((i % 5) == 0))
System.out.println("fizzbuzz");
else if ((i % 3) == 0)
System.out.println("fizz");
else if ((i % 5) == 0)
System.out.println("buzz");
else System.out.println(i);
}
//System.out.println();
}
}


(Java - shorter)

public class FizzBuzz {
public static void main(String[] args) {

for(int i = 1; i <= 100; i++) {
System.out.printf("%s\n",
i%15!=0?i%5!=0?i%3!=0 ? i :"Fizz":"Buzz":"FizzBuzz" );
}
}
}



CÒN VÀI KIỂU CODE KHÁC, THAM KHẢO CHO VUI:
(chứ phỏng vấn thiệt mà tìm tòi hướng này chắc là ít nhất cũng cả tiếng cho 1 bài cỡ FizzBuzz)

* Cực ngắn, gõ ít nhất: (one-liner, Perl-Golf)
Bạn phải đam mê lập trình thực sự mới tham gia được loại này. Cái kiểu one-liner này xuất phát từ Perl, do sự linh động, uyển chuyển và mạnh mẽ của Perl trong xử lý text của Perl. Bây giờ các lập trình viên ngôn ngữ hậu duệ của Perl (như Python, Ruby) cũng bắt đầu thích trò brainstorming này :D

(Python)
for i in range(1,101):print”FizzBuzz”[i*i%3*4:8–-i**4%5]or i

(Ruby)
1.upto(?d){|i|puts"FizzBuzz"[4&a=i*i%3*5,9-a-i**4%5]||i}

(Perl)
print$_%3?$_%5?$_:"":Fizz,$_%5?"":Buzz,"\n"for 1..100;



* Phức tạp hóa, làm rối rắm: (complicated, obfuscated)

(Csharp)
using System;

namespace FizzBuzz
{
internal class Program
{
private static void Main()
{
IFormatProvider formatProvider = new FizzBuzzFormatter();

for (int i = 1; i < = 100; i++)
Console.WriteLine(String.Format(formatProvider, “{0:FB}”, i));

Console.ReadLine();
}
}

internal class FizzBuzzFormatter : ICustomFormatter, IFormatProvider
{
public string Format(string format, object arg, IFormatProvider formatProvider)
{
if (format == null)
return String.Format(”{0}”, arg);

if (format.StartsWith(”FB”) && arg is int)
{
int val = (int) arg;
bool mod3 = val%3 == 0;
bool mod5 = val%5 == 0;

if (!mod3 && !mod5)
return arg.ToString();

string s = String.Empty;

if (mod3)
s += "Fizz";

if (mod5)
s += "Buzz";

return s;
}

return String.Format(”{0:” + format + “}”, arg);
}

public object GetFormat(Type formatType)
{
if (formatType == typeof (ICustomFormatter))
return this;
else
return null;
}
}
}


(Csharp - longer)
public abstract class Factory
{
public string ToString(char[] chars)
{
return new string(chars);
}
}

public class FizzFactory : Factory
{
private const char F = 'F';
private const char i = 'i';
private const char z = 'z';

public bool isFizz(int input)
{
if (input == 3) return true;
else if (input == 6) return true;
else if (input == 9) return true;
else if (input == 12) return true;
else if (input == 15) return true;
else if (input == 18) return true;
else if (input == 21) return true;
else if (input == 24) return true;
else if (input == 28) return true;
else if (input == 30) return true;
else if (input == 33) return true;
else if (input == 36) return true;
else if (input == 39) return true;
else if (input == 42) return true;
else if (input == 45) return true;
else if (input == 48) return true;
else if (input == 51) return true;
else if (input == 54) return true;
else if (input == 57) return true;
else if (input == 60) return true;
else if (input == 63) return true;
else if (input == 66) return true;
else if (input == 69) return true;
else if (input == 72) return true;
else if (input == 75) return true;
else if (input == 78) return true;
else if (input == 81) return true;
else if (input == 84) return true;
else if (input == 87) return true;
else if (input == 90) return true;
else if (input == 93) return true;
else if (input == 96) return true;
else if (input == 99) return true;
else return false;
}

public string GetFizz()
{
return base.ToString(new char[4] { F, i, z, z });
}
}

public class BuzzFactory : Factory
{
private const char B = 'B';
private const char u = 'u';
private const char z = 'z';

public bool isBuzz(int input)
{
if (input == 5) return true;
else if (input == 10) return true;
else if (input == 15) return true;
else if (input == 20) return true;
else if (input == 25) return true;
else if (input == 30) return true;
else if (input == 35) return true;
else if (input == 40) return true;
else if (input == 45) return true;
else if (input == 50) return true;
else if (input == 55) return true;
else if (input == 60) return true;
else if (input == 65) return true;
else if (input == 70) return true;
else if (input == 75) return true;
else if (input == 80) return true;
else if (input == 85) return true;
else if (input == 90) return true;
else if (input == 95) return true;
else if (input == 100) return true;
else return false;
}

public string GetBuzz()
{
return base.ToString(new char[4] { B, u, z, z });
}
}

public delegate void FizzBuzzWriter(string input);
public class Looper
{
private FizzFactory Fizz;
private BuzzFactory Buzz;
public event FizzBuzzWriter OnFizzBuzz;

public Looper(Factory fizzFact, Factory buzzFact)
{
Fizz = (FizzFactory) fizzFact;
Buzz = (BuzzFactory) buzzFact;
}

public void execute(int start, int finish)
{
for(int i = start; i<=finish; i++)
{
string val = String.Empty;
if (Fizz.isFizz(i)) val += Fizz.GetFizz();
if (Buzz.isBuzz(i)) val += Buzz.GetBuzz();
if (val == String.Empty) val = i.ToString();

if (OnFizzBuzz != null) OnFizzBuzz(val);
}
}

}

public class TheFizzBuzzProgram
{
public static void main(string[] args)
{
Looper l = new Looper(new FizzFactory(), new BuzzFactory());
l.OnFizzBuzz += new FizzBuzzWriter(l_OnFizzBuzz);
l.execute(1,100);
}

static void l_OnFizzBuzz(string input)
{
Console.Write(input + Environment.NewLine);
}
}



* Hiệu quả, chạy nhanh nhất: (performance, effectiveness)
Chưa test, ai có kết quả test vài trường hợp thì post lên thử nhé ^_^



Search vòng vòng Internet còn thấy thêm khá nhiều implementation với nhiều ngôn ngữ nữa, có thể kể JavaScript, ASP, Pascal, C++, VB, Groovy, Prolog, SmallTalk, Scheme, Haskell, Erlang, COBOL, bash, batch, ... thậm chí cả SQL (yay!), XSL (wow!), hợp ngữ IL (cool!), ASM86 trên Windows lẫn Linux (cooler!) , ASM51 (w00t!), etc ; nhưng nhìn chung mấy đoạn mã ở trên là đủ tiêu biểu rồi :D

Have fun !

1 comment:

jGuru said...

There should be some PHP snippet, too :)