Bàn về câu hỏi phỏng vấn trong bài viết của giaosucan

Minh Hoang TO viết ngày 19/03/2019

Lâu lắm rồi mới quay lại viết bài trên Kipalog, trong bài viết mới này tôi muốn bàn về 1 câu hỏi trong bài của Giaosucan

https://kipalog.com/posts/Toi-da-phong-van-o-Sillicon-valley-nhu-the-nao

Cho số dương integer n, tìm số cách để để chia n thành 5 số dương nhỏ hơn sao cho cộng lại thì vẫn là n

1. Hỏi câu hỏi kiểu đó làm gì?

Mặc dù từng là người học chuyên toán và kiến thức toán giúp tôi khá nhiều trong hình thành tư duy lập trình, cá nhân tôi thấy các câu hỏi kiểu này không có giá trị gì cho việc phỏng vấn tuyển dụng các vị trí thuần engineering. Ngày còn là sinh viên ngành toán tôi làm mấy cái bài kiểu này nhanh hơn, nhưng lập trình chắc chắn dốt hơn bây giờ nhiều

Các bạn nghĩ thế nào thì comment bên dưới nhé

2. Tại sao cần nghĩ về hướng đi trước khi bắt đầu lập trình?

Trước hết xin minh hoạ một lời giải kiểu cắm đầu cắm cổ vào code với kết quả là complexity là O(n^5)

int findNumWays(int n) {
    int count = 0;
    int i, j, k, l,m = 0;
    for (i = 1; i < n; i++)  
        for (j = i; j < n; j++)  
            for (k = j; k < n; k++)  
                for (l = k; l < n; l++) 
                   for (m = l; m < n; m++)  
                        if (i + j + k + l + m == n)  
                            count++;
    return count;
  }

Với câu hỏi này thì có thể thấy ngay con số 5 chỉ là con số cụ thể và hướng suy nghĩ hợp lý là tìm một công thức truy hồi trên:

F(k, n): Số các bộ gồm k số nguyên dương không tính thứ tự (i.e 2 bộ số là hoán vị của nhau chỉ tính là 1) có tổng bằng n

Với công thức truy hồi dạng tuyến tính (nếu có thể tìm được), ta có thể hạ bớt bậc của complexity.

Có thể thấy rằng nếu a_1, a_2, ..., a_k là k số dương có tổng bằng n thì ta có

0 < a_1 < a_1 + a_2 < a_1 + a_2 + a_3 < ... < a_1 + a_2 + ... + a_(k-1) < n

Dễ thấy với điều kiện tổng k số bằng n thì tương ứng {a_1,..., a_k} -> {a_1, a_1 + a_2, ..., a_1 + a_2 + ...+ a_(k-1) } là tương ứng 1-1

Do đó F(k, n) = Số các bộ (k-1) số nguyên dương phân biệt nhỏ hơn n.

Theo công thức truy hồi quen thuộc của tổ hợp chập k của n phần tử thì

https://en.wikipedia.org/wiki/Combination

F(k, n) = F(k, n-1) + F(k-1, n-1)

Với công thức này ta có thể lập trình với complexity là O(n), và nó cũng minh hoạ cho việc tại sao cần nghĩ về hướng giải pháp trước thay vì cắm đầu cắm cổ vào code