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

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é :smile:

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 :smile:

Bình luận


White
{{ comment.user.name }}
Bỏ hay Hay
{{comment.like_count}}
Male avatar
{{ comment_error }}
Hủy
   

Hiển thị thử

Chỉnh sửa

White

Minh Hoang TO

5 bài viết.
12 người follow
Kipalog
{{userFollowed ? 'Following' : 'Follow'}}
Cùng một tác giả
White
10 0
Bài viết này trình bày một giải pháp buildfromscratch cho bài toán khá phổ biến sau Tôi có một ứng dụng A, tôi đang liên kết với các đối tác {C_1,...
Minh Hoang TO viết 3 năm trước
10 0
White
7 1
Bài viết này trình bày cách thiết lập cơ chế build CI thông qua Jenkins cho các Android project (libraries hoặc applications) được quản lý bằng (Li...
Minh Hoang TO viết 3 năm trước
7 1
White
6 0
Trước hết xin nhắc lại mục đích của bài viết này là đưa ra giải pháp buildfromscratch cho bài toán sau: Tôi có một ứng dụng A, tôi đang liên kết v...
Minh Hoang TO viết 3 năm trước
6 0
{{like_count}}

kipalog

{{ comment_count }}

bình luận

{{liked ? "Đã kipalog" : "Kipalog"}}


White
{{userFollowed ? 'Following' : 'Follow'}}
5 bài viết.
12 người follow

 Đầu mục bài viết

Vẫn còn nữa! x

Kipalog vẫn còn rất nhiều bài viết hay và chủ đề thú vị chờ bạn khám phá!