Để trở thành một lập trình viên giỏi, bạn không thể thiếu kỹ năng này

Kỹ sư phần mềm đang trở thành một ngành nghề được giới trẻ ưa thích do nhu cầu việc làm ngày càng lớn và mức lương hậu hĩnh. Tuy nhiên, trong một thế giới công nghệ thay đổi, lập trình viên cũng cần luôn tự làm mới mình và trau dồi thêm các kỹ năng mới. Với kinh nghiệm của mình, trong bài viết này, tôi sẽ trình bày về một kỹ năng tôi cho là tối quan trọng cho mọi lập trình viên hiện nay.

Lập trình - một nghề viết lách lương cao

Vâng, đó là chính là kỹ năng lập trình.

Đến đây có lẽ các bạn đã lờ mờ nhận ra bài viết này chẳng liên quan gì tới việc phát triển bản thân cả, và tiêu đề của bài viết này chỉ nhằm mục đích câu view mà thôi (nhưng mà lương 9 chữ số là thật hihi). Tôi viết bài viết này sau khi đã đọc khá nhiều bài viết (theo tôi là) hơi fancy về nghề lập trình. Trong quan điểm của tôi, việc lập trình bản chất chính là giải quyết vấn đề (problem solving), và điều quan trọng nhất chính là cách mà chúng ta giải quyết vấn đề - hay chúng ta gọi đó là thuật toán. Tôi cũng vừa hoàn thành 1 task ở công ty bằng một thuật toán thú vị, vì thế muốn viết một bài viết ngắn về các thuật toán mà tôi yêu thích và ứng dụng của chúng trong các vấn đề thực tiễn của đời sống. Trong mỗi phần, tôi sẽ đầu tiên đưa ra bài toán, sau đó trình bày các góc nhìn thông thường để giải quyết bài toán cũng như cách tiếp cận sử dụng tư duy của thuật toán mà tôi muốn trình bày. Ok, let's start!

Thuật toán phân tập (partitioning)

Có 1000 người đang đứng xếp hàng để tiêm vacxin pfizer, nhưng theo quy định chỉ có những người có tên trong danh sách mới được tiêm. Vì thế, các y tá cần sắp xếp lại hàng với những người có tên trong danh sách sẽ được ưu tiên đứng ở phía trước, còn người không được ưu tiên sẽ đứng ở phía sau hàng. Nếu bạn là người y tá thì bạn sẽ làm thế nào để tối thiểu hoá việc sử dụng diện tích?

Cách đơn giản và tiện lợi nhất là bạn sẽ tạo một hàng mới, sau đó đi từ đầu hàng tới cuối hàng và kiểm tra từng người. Nếu người nào không có tên trong danh sách, bạn sẽ đưa người đó ra khỏi hàng cũ và xếp vào hàng mới. Cuối cùng ghép 2 hàng với nhau. Nhược điểm của phương pháp này là bạn cần chỗ trống để tạo một hàng mới. Trong việc lập trình, nó tương tự như việc bạn phải tạo ra một biến mới để chứa dữ liệu cũ, và sẽ gây ra lãng phí tài nguyên (cụ thể là bộ nhớ).

Cách làm đầu tiên: tạo hàng mới - đơn giản nhưng lãng phí bộ nhớ

Nếu không muốn tạo thêm hàng mới, các y tá có thể sắp xếp lại hàng ngay tại chỗ như sau: đi từ đầu hàng tới cuối hàng và kiểm tra từng người, nếu ai không có tên trong danh sách thì mời họ đi xuống cuối hàng giống như trong hình vẽ sau.

Cách làm có thể tốt hơn: đưa những người không có trong danh sách ra phía sau của hàng đợi

Có thể dễ dàng thấy rằng phương pháp này vẫn có hạn chế là dù không phải tạo thêm hàng mới nhưng vẫn cần có chỗ trống ở phía sau hàng cũ để xếp thêm người. Chúng ta có thể khắc phục nhược điểm này bằng cách dồn hàng ngay khi chuyển một người về cuối hàng, tuy nhiên nó lại gây ra rất nhiều việc di chuyển (cụ thể là dịch lên) trong hàng. Trong việc lập trình, đôi khi việc di chuyển một phần tử cũng tốn kém không khác gì việc tạo ra một phần tử mới.

Thực tế là thuật toán phân tập mà các lập trình viên có kinh nghiệm sử dụng sẽ không di chuyển các phần tử mà chỉ đơn giản hoán đổi vị trí của các phần tử ở trong hàng để tạo ra phân tập mong muốn. Các bạn có thể hình dung việc hoán đổi trong bài toán ban đầu bằng hình dưới đây.

Phân tập bằng cách hoán đổi trong lập trình: hình mũi tên thể hiện sự hoán đổi vị trí của 2 phần tử. Có một nhược điểm của phương pháp này được thể hiện trên hình, theo bạn đó là gì?

Tôi sẽ không trình bày thuật toán cụ thể (mặc dù thuật toán rất đơn giản và đẹp) vì có quá nhiều tính kỹ thuật và những người không với các khải niệm trong lập trình sẽ khó để hiểu. Các bạn có thể tìm hiểu cách triển khai thuật toán này tại đây. Việc phân tập theo cách này được ứng dụng rộng rãi trong các thuật toán sắp xếp hoặc thuật toán lọc phần tử.

Thuật toán đếm phiếu (Boyer-Moore majority voting algorithm)

Địa phận thành phố Z được chia thành 3 vùng: đỏ, vàng, và xanh. Người dân ở mỗi vùng thì sẽ có màu tóc tương ứng: người dân vùng đỏ có tóc đỏ, người vùng vàng có tóc vàng, và vùng xanh có tóc xanh. Trong cuộc họp hội đồng nhân dân thành phố, vị chủ tịch muốn biết vùng nào có quá bán (nhiều hơn một nửa) số đại biểu trong hội đồng. Tuy nhiên ông không có danh sách check-in, cũng như không thể đếm từng người do mắt kém. Bạn sẽ làm gì nếu là vị chủ tịch kia?

Việc xác định phần tử xuất hiện quá bán trong một tập hợp là một bài toán rất phổ biến trong cả lập trình và đời sống (việc đếm phiếu đại cử tri trong bầu cử tổng thống Mỹ chẳng hạn). Cách đơn giản nhất là đếm số lượng xuất hiện của từng phần tử một, sau đó tìm xem phần tử nào có lượt đếm nhiều nhất. Tuy nhiên, để đếm được thì chúng ta cần có công cụ để đếm và lưu trữ kết quả. Đôi khi để tối ưu về mặt tài nguyên (trong lập trình, tài nguyên cụ thể chính là bộ nhớ của máy tính), chúng ta không muốn đếm. Vậy có cách nào để làm tốt hơn là đếm không?

Bẩu cử Mỹ là một ví dụ quen thuộc cho bài toán tìm phần tử quá bán. Có tổng cộng 538 phiếu đại cử tri, nếu ứng viên nào có quá bán số phiếu bầu (>=270) thì sẽ chiến thắng (credit ảnh: BBC).

Trở lại bài toán ban đầu. Vị chủ tịch nọ vốn là một tay chính trị gia lão làng và nắm rất rõ rằng giữa các vùng với nhau luôn có sự hiềm khích không hề nhỏ. Vì vậy, ông đứng lên và phát biểu một câu như sau “Chính những người ở các vùng khác, ở đây và ngay bây giờ, đang lấy mất quyền lợi của vùng của các vị”. Bị kích động, cả hội trường lao vào ẩu đả. Mỗi vị đại biểu lại tìm một người gần nhất có màu tóc khác mình và cùng lao vào động thủ. Với giả thuyết rằng hai đại biểu sẽ đánh tay đôi tới khi cả 2 cùng gục, chỉ khoảng 5 phút sau, gần như cả hội trường đều nằm dưới đất. Tuy nhiên, điều ngạc nhiên hơn cả là, người ta thấy rằng những người không nằm xuống đều có chung một màu tóc đỏ. Vị chủ tịch tên Xuân mỉm cười đắc thắng: có lẽ một nhiệm kỳ nữa là nằm trong tầm tay của ông.

Sau khi ghép cặp các phần tử khác nhau, nếu tồn tại một phần tử xuất hiện quá bán thì phần tử đó phải bị chừa ra.

Câu chuyện ở trên chính là một cách lý giải đơn giản cho thuật toán đếm phiếu của Boyer và Moore. Logic rất đơn giản: nếu tồn tại một phần tử xuất hiện quá bán trong một tập hợp, nếu chúng ta ghép cặp tương ứng 1-1 giữa những phần tử khác nhau thì những phần tử chừa ra chính là phần tử xuất hiện quá bán. Việc triển khai thuật toán này rất đơn giản và không yêu cầu công cụ để lưu trữ kết quả đếm (các bạn có thể tham khảo ở link trên).

Cần chú ý rằng thuật toán Boyer-Moore có giới hạn: nếu tồn tại phần tử xuất hiện quá bán, thuật toán luôn trả về chính xác phần tử đó, tuy nhiên nếu không tồn tại phần tử xuất hiện quá bán, thuật toán sẽ trả về một phần tử bất kỳ.

Thuật toán tìm kiếm nhị phân (Binary search)

Nồng độ virus covid-19 trong hơi thở một người ở trong khoảng từ 0 tới 100, trong đó có một ngưỡng X mà nếu nồng độ virus từ X trở lên thì kết quả xét nghiệm của người đó sẽ là dương tính. Nếu là nhà một nhà nghiên cứu với kinh phí hạn hẹp bạn sẽ làm thế nào để tìm ra X mà sử dụng ít xét nghiệm nhất có thể?

Nếu sử dụng tư duy thông thường như làm xét nghiệm lần lượt với nồng độ từ thấp lên cao hoặc từ cao xuống thấp, số lượng test trong tường hợp tốt nhất là 1, xấu nhất là 100, và trung bình là 50. Con số này là quá lớn chỉ để tìm ra một giá trị. Ngoài ra chúng ta đã bỏ qua một lợi thế rất quan trọng: nếu chúng ta làm test ở ngưỡng Y mà kết quả là âm tính, vậy chắc chắn nếu làm test ở dưới ngưỡng Y thì kết quả cũng sẽ là âm tính! Việc làm test với mọi giá trị trong khoảng từ 1-100 là không cần thiết, và đó chính là tư duy của phương pháp tìm kiếm nhị phân - binary search.

Giả sử ngưỡng X chúng ta cần tìm là X=65, nếu sử dụng thuật toán tìm kiếm nhị phân thì quy trình thực hiện sẽ được thể hiện như hình minh hoạ sau.

Phương pháp xét nghiệm để tìm ngưỡng dương tính theo thuật toán tìm kiếm nhị phân

Đầu tiên, chúng ta biết là X ở khoảng từ 1-100, vì thế chúng ta làm test ở 50 (số trung bình - median) và nhận được kết quả âm tính, do đó chúng ta biết rằng X sẽ ở khoảng từ 51-100. Tiếp tục lặp lại quá trình trên, chúng ta thu hẹp khoảng của X lần lượt về 51-75, 64-75, 64-69, 64-66, 64-65, và cuối cùng là 65-65. Với cách xét nghiệm này, chúng ta cần tối đa khoảng 7 test cho mọi giá trị của X - một con số nhỏ hơn nhiều so với 50 test của cách làm thông thường.

Thuật toán lấy mẫu Reservoir (Reservoir sampling)

Khi công ty X bắt đầu mở cửa văn phòng trở lại, lãnh đạo công ty được yêu cầu mỗi ngày phải lấy ngẫu nhiên một người trong số những người đi làm để xét nghiệm covid-19. Công ty X không có lịch làm việc tại văn phòng cụ thể nên dù có danh sách nhân viên nhưng cũng không có cách nào để chọn ngẫu nhiên từ danh sách sẵn có. Nếu bạn là giám đốc của công ty, bạn sẽ làm thế nào để chọn ra ngẫu nhiên một người trong số những người đến công ty? Biết rằng để tuân thủ quy định, văn phòng công ty chỉ mở một cửa và nhân viên chỉ có thể vào văn phòng thông qua cửa đó vào mỗi buổi sáng từ 6h-9h?

Có lẽ chúng ta đã nghe rất nhiều về tầm quan trọng của dữ liệu trong thời đại ngày nay. Tuy nhiên, dữ liệu thì quá nhiều mà khả năng xử lý của con người (và cả máy tính) là có hạn. Chính vì vậy, việc lấy mẫu dữ liệu là điều tất yếu. Tuy nhiên, việc lấy mẫu không hề đơn giản như chúng ta tưởng tượng, đặc biệt khi chúng ta thậm chí không cả biết rằng có bao nhiêu mẫu dữ liệu. Chúng ta có thể tưởng tượng bài toán chọn người để xét nghiệm ở trên giống như việc bài toán kỹ thuật sau: có rất nhiều dữ liệu đang tới (mà chúng ta không biết chính xác là có bao nhiêu), và bạn chỉ được giữ lại một mẫu dữ liệu, tuy nhiên phải đảm bảo rằng tất cả các mẫu dữ liệu đều có xác xuất được giữ lại như nhau!

Một ứng dụng của việc lấy mẫu ngẫu nhiên trong hệ thống gợi ý video

Rõ ràng, nếu chỉ chọn một người và dừng lại thì không thể là ngẫu nhiên được, vì chúng ta đã bỏ qua tất cả những người khác có thể sẽ đến trong tương lai. Thuật toán lấy mẫu Reservoir giải quyết vấn đề này như sau. Đầu tiên, khởi tạo một biến số cnt := 0 để đếm tổng số người đã tới công ty. Sau đó, với mỗi nhân viên tới công ty, chúng ta sẽ chọn nhân viên đó để làm người đi xét nghiệm với xác suất 1/cnt (người được chọn sau sẽ thay thế cho người được chọn trước). Sau 9h, người cuối cùng được chọn sẽ là người đi xét nghiệm.

Hãy hình dung nếu chúng ta có tổng cộng N người tới công ty trong ngày hôm đó, thì phương pháp trên sẽ là ngẫu nhiên nếu mỗi người có xác suất phải xét nghiệm là 1/N. Với người đầu tiên tới công ty, anh ta sẽ phải xét nghiệm nếu cả 2 điều kiện sau xảy ra: (1) anh ta được chọn trong lượt của mình (luôn đúng vì khi đó, cnt=1), và (2) không có ai được chọn sau anh ta. Nếu gọi Q(i) là xác suất người thứ i tới công ty phải xét nghiệm và P(i) là xác suất người thứ i tới công ty được chọn để xét nghiệm, thì xác suất để người đầu tiên phải xét nghiệm là:

Q(1) = P(1) x (1-P(2)) x (1-P(3)) x ... x (1-P(N))

Ta biết P(i) = 1/i, do đó biểu thức trên được rút gọn thành:

Q(1) = 1 x (1-1/2) x (1-1/3) x ... x (1-1/N) = 1 x 1/2 x 2/3 x ... x (N-1)/N = 1/N

Với suy luận tương tự, có thể dễ dàng thấy mỗi người đến công ty ngày hôm đó đều có xác xuất phải xét nghiệm như nhau!

Thuật toán xét nghiệm mẫu gộp (Pooled testing)

Tổ dân phố bạn có 100 người cần xét nghiệm covid-19; tuy nhiên chỉ được phát 20 kít xét nghiệm. Cho rằng tỷ lệ nhiễm covid-19 ở cộng đồng là khoảng 1%, tức là có nhiều nhất 1 người trong tổ dân phố bị nhiễm bệnh. Nếu là tổ trưởng tổ dân phố, bạn sẽ làm thế nào để tìm ra người nhiễm bệnh nhanh nhất?

Trước đây, tôi chỉ từng gặp bài toán này khi phỏng vấn cho coding interview. Tới đầu năm 2020 nó lại trở thành bài toán bài toán rất thực tế, khi nguồn cung cấp kit xét nghiệm covid-19 còn hạn chế. Chúng ta đã nghe rất nhiều tới việc xét nghiệm mẫu gộp 5, gộp 10. Về cơ bản, cách xét nghiệm này dựa trên lý thuyết rằng nếu mẫu gộp là âm tính thì tất cả mọi người trong mẫu gộp đó đều âm tính, còn nếu dương tính thì sẽ làm xét nghiệm riêng cho từng người để khẳng định kết quả. Nếu tỷ lệ âm tính trong cộng đồng cao thì xét nghiệm mẫu gộp sẽ tiết kiệm được rất nhiều test kit. Về lý thuyết là vậy, tuy nhiên cách làm có lẽ không hoàn toàn giống nhiều người trong chúng ta vẫn nghĩ.

Cơ sở của phương pháp xét nghiệm mẫu gộp. Nếu tỷ lệ dương tính thấp, cách xét nghiệm này tiết kiệm rất nhiều test kit so với việc xét nghiệm từng mẫu đơn.

Trở lại bài toán bên trên, giả sử chúng ta sử dụng phương pháp xét nghiệm mẫu gộp-10 thì cách làm sẽ như sau: đầu tiên, chúng ta chia 100 người thành 10 nhóm và sử dụng 10 test kit để xét nghiệm mẫu gộp-10 cho từng nhóm. Với giả thuyết chỉ 1% người nhiễm bệnh, sẽ chỉ có 1 mẫu gộp-10 là dương tính. Sau khi khoanh vùng được 10 người có khả năng dương tính, chúng ta có thể dùng 10 test kit còn lại để kiểm tra cho từng người. Với cách làm như thế này, chúng ta mất 20 test kit và 2 ngày để xác định 1 F0 (cho rằng việc xét nghiệm PRC thông thường sẽ mất 1 ngày).

Cách làm như trên không phải cách nhanh nhất. Thực tế thì cũng với 20 test kit ấy, tổ dân phố hàng xóm phía Bắc chỉ mất 1 ngày để xác định được F0. Cách họ làm như sau: xếp 100 người thành 1 ma trận 10x10, sau đó lấy mẫu gộp theo từng hàng và từng cột - tổng cộng 20 mẫu - và thực hiện xét nghiệm 1 lần. Với giả thuyết chỉ có 1 người bị nhiễm, sẽ có chính xác 1 mẫu gộp hàng và 1 mẫu gộp cột ra kết quả dương tính. Từ vị trí của các mẫu này trên trục của ma trận, chúng ta có thể tìm ra vị trí của mẫu dương tính.

Xét nghiệm gộp theo phương pháp nhóm ma trận 2-D: vị trí mẫu dương tính được xác định bằng vị trí của nó ở trên hàng và trên cột của ma trận.

Để hình dung ra lợi ích của cách làm này, hãy tưởng tượng tình huống có 1000 người thay vì 100 người, và chỉ có 1 người nhiễm bệnh. Bằng cách xếp 1000 người thành 1 ma trận 10x10x10, chúng ta có thể sử dụng 30 test kit và xét nghiệm mẫu gộp-100 để xác định ra F0 chỉ trong một ngày (với giả thuyết tỷ lệ nhiễm bệnh chỉ là 0.1%).

Nhược điểm của cách làm trên là khi tỷ lệ nhiễm bệnh tăng lên, nó không còn cho kết quả chính xác nữa. Giả sử như trong 100 người, có 2 người dương tính, thì cách xếp mẫu theo ma trận 10x10 có thể cho ra tới 4 người có khả năng dương tính, và chúng ta vẫn cần xét nghiệm khẳng định. Thực tế là khi tỷ lệ dương tính tăng lên, chúng ta cần các phương pháp phức tạp hơn là nhóm mẫu theo các ma trận hình khối . Chính vì vậy các bạn rất hay nghe người ta nói đến tỷ lệ dương tính trong cộng đồng trên báo, bởi tỷ lệ dương tính sẽ ảnh hưởng tới cách test và tốc độ test. Bạn nào quan tâm về vấn đề này có thể google thử từ khoá “pooled testing algorithm” và đọc thêm các bài báo khoa học.

Khi xuất hiện 2 mẫu đơn dương tính trên một đường chéo, nó sẽ tạo ra 4 mẫu đơn có khả năng dương tính giả, do đó cần làm lại xét nghiệm khẳng định cho 4 mẫu trên. Theo các bạn, cần làm bao nhiêu xét nghiệm khẳng định?

Kết bài

Việc lập trình bản chất chính là việc giải quyết vấn đề - problem solving. Các bài toán ví dụ tôi lấy ở trên mục đích chính là để các bạn thấy các vấn đề trong việc lập trình thực tế rất gần gũi với đời sống. Nếu bạn đang theo đuổi đam mê trở thành một lập trình viên, tôi nghĩ điều quan trọng nhất chính là rèn luyện cách tư duy để: (1) giải thích vấn đề, và (2) giải quyết vấn đề (pls, avoid buzz words in your CV and complex and meaningless figures in your reports - post in on Linkedin instead). Với 5 thuật toán tôi trình bày ở trên, hy vọng đem đến cho các bạn một cái nhìn khác về công việc lập trình cũng như tạo cảm hứng để bạn bắt tay vào việc trở thành một lập trình viên.

P/S: Công ty tôi (unicorn - văn phòng tại Singapore) đang tuyển fresh graduate, bạn nào muốn tôi refer thì có thể contact qua Linkedin trong profile).