FizzBuzz

Q: Độ phức tạp thời gian của FizzBuzz là gì?

Trả lời cho một số có độ phức tạp O(1) : số lần kiểm tra phần dư cố định và chuyển đổi một số có tối đa 10 chữ số. In dãy số từ 1 đến n có độ phức tạp O(n) .

Người mớiToán và mô phỏng

+10

Trong trò chơi đếm FizzBuzz, người chơi đếm từ 1 trở lên và thay một số con số bằng từ ngữ. Với số lượt n, hãy trả về nội dung người chơi nói ở lượt đó: "FizzBuzz" nếu n chia hết cho cả 3 và 5, "Fizz" nếu chỉ chia hết cho 3, "Buzz" nếu chỉ chia hết cho 5, còn lại là chính n dưới dạng chuỗi, chẳng hạn như "7".

Hàm

fizzBuzz(n: integer) → string

ninteger: số thứ tự lượt, một số nguyên dương
Trả vềstring: từ hoặc số được nói ở lượt n, dưới dạng chuỗi

Ràng buộc

1 ≤ n ≤ 10⁹
Câu trả lời luôn là một chuỗi, kể cả khi đó là chính con số ấy. ĐỊNH DẠNG ĐẦU RA BẮT BUỘC:

Ví dụ

Đầu vào: n = 15
Đầu ra: "FizzBuzz"
Giải thích: 15 chia cho 3 bằng 5 và 15 chia cho 5 bằng 3, cả hai phép chia đều không có số dư, nên lượt 15 là "FizzBuzz".

Đầu vào: n = 7
Đầu ra: "7"
Giải thích: 7 chia 3 dư 1 và chia 5 dư 2, nên không có từ nào phù hợp và bạn trả về số đó dưới dạng văn bản, "7".

Câu hỏi mở rộng

Một quy tắc mới biến các bội số của 7 thành "Bazz", ghép các từ theo thứ tự, nên 105 là "FizzBuzzBazz". Bạn có thể thêm quy tắc này mà không cần viết một trường hợp cho từng tổ hợp bằng cách nào?

Gợi ý

Mở từng gợi ý một. Mỗi gợi ý tiết lộ thêm một chút.

Đã mở 0/3

Lời giải

Mỗi quy tắc là một phép kiểm tra số dư. Điểm dễ mắc lỗi nằm ở thứ tự: 15 chia hết cho 3, vì vậy hàm kiểm tra 3 trước rồi trả về ngay sẽ cho kết quả "Fizz" với 15. Hãy kiểm tra trường hợp kết hợp trước hoặc tạo câu trả lời từ cả hai phép kiểm tra.

Tạo từ này từ cả hai điều kiện kiểm tra

Ý tưởng

Bắt đầu với một từ rỗng. Nếu 3 chia hết cho n, hãy thêm "Fizz"; nếu 5 chia hết cho n, hãy thêm "Buzz". Cả hai phép kiểm tra luôn chạy, nên bội số của 15 nhận được cả hai phần theo đúng thứ tự và trở thành "FizzBuzz" mà không cần trường hợp đặc biệt. Nếu từ đó vẫn rỗng, nghĩa là không có quy tắc nào được áp dụng, và bạn trả về số dưới dạng chuỗi.

Thuật toán

Gán word thành chuỗi rỗng.
Nếu n % 3 == 0, nối thêm "Fizz".
Nếu n % 5 == 0, nối thêm "Buzz".
Nếu word rỗng, trả về n đã chuyển thành chuỗi.
Nếu không, trả về word.

def fizzBuzz(n):
    word = ""
    if n % 3 == 0:
        word += "Fizz"
    if n % 5 == 0:
        word += "Buzz"
    # An empty word means neither 3 nor 5 divides n.
    if word == "":
        return str(n)
    return word

Kiểm tra 15, sau đó 3, rồi 5

Ý tưởng

Một số chia hết cho cả 3 và 5 cũng chính là số chia hết cho 15, vì 3 và 5 không có ước chung nào khác 1. Vì vậy, quy tắc kết hợp chỉ cần một lần kiểm tra, n % 15 == 0, và cần kiểm tra quy tắc này trước. Nếu không thỏa mãn, số chia hết cho 3 nghĩa là chỉ chia hết cho 3, còn số chia hết cho 5 nghĩa là chỉ chia hết cho 5. Mỗi lần kiểm tra sẽ trả về ngay, nếu không có trường hợp nào khớp thì trả về số đó dưới dạng chuỗi.

Thuật toán

Nếu n % 15 == 0, trả về "FizzBuzz".
Nếu n % 3 == 0, trả về "Fizz".
Nếu n % 5 == 0, trả về "Buzz".
Nếu không, chuyển n thành chuỗi, viết đầy đủ từng chữ số.

def fizzBuzz(n):
    if n % 15 == 0:
        return "FizzBuzz"
    if n % 3 == 0:
        return "Fizz"
    if n % 5 == 0:
        return "Buzz"
    return str(n)

Lỗi thường gặp và trường hợp biên

Kiểm tra 3 hoặc 5 trước 15 rồi trả về ngay: 15, 30 và 45 cho kết quả "Fizz".
Trả về số thay vì chuỗi. Lượt 7 là "7".
Chuyển số lớn sang dạng ký hiệu khoa học. Trong R, chuyển đổi thông thường in 10^9 thành 1e+09; hãy dùng format(n, scientific = FALSE).
In đáp án ra thay vì trả về.

Câu hỏi thường gặp3

Vì sao FizzBuzz thường xuất hiện trong các buổi phỏng vấn lập trình?

Bài này kiểm tra khả năng chuyển một bộ quy tắc ngắn thành code hoạt động: kiểm tra số dư, sắp xếp điều kiện đúng thứ tự và dùng đúng kiểu dữ liệu trả về. Người thường xuyên viết code chỉ mất vài phút, nên bài này phù hợp để kiểm tra nhanh trước khi làm các câu hỏi khó hơn.

Bạn có thể giải bài toán FizzBuzz mà không dùng toán tử modulo không?

Có. Hãy chia lấy phần nguyên (integer division), nhân thương với số chia rồi so sánh kết quả với n: chúng chỉ bằng nhau khi không còn dư. Khi in cả dãy, bạn cũng có thể dùng hai bộ đếm (counter), một bộ đếm đặt lại về 3 và bộ còn lại đặt lại về 5.

Độ phức tạp thời gian của FizzBuzz là gì?

Trả lời cho một số có độ phức tạp O(1): số lần kiểm tra phần dư cố định và chuyển đổi một số có tối đa 10 chữ số. In dãy số từ 1 đến n có độ phức tạp O(n).

def fizzBuzz(n):
    # Viết code ở đây

Kiểm thử #1

Kiểm thử #2

Đối số

n = 15

Đầu ra mong đợi

"FizzBuzz"