Table of Contents
1. Lời nói đầu
Mình không có background gì quá nổi trội khi không tham gia vào các kỳ thi lập trình lớn của sinh viên như ICPC hay Olympic Tin học do tiếp xúc với lập trình thi đấu khá muộn, nhưng mình có một niềm đam mê lớn đối với cấu trúc dữ liệu & giải thuật (CTDL & GT) cũng như việc rèn luyện phát triển bản thân để trở thành một kỹ sư giỏi.
Ở độ tuổi còn trẻ trong sự nghiệp, mình luôn muốn phát triển và cập nhật các kiến thức mới về công nghệ để chạy theo xu hướng thị trường, tuy nhiên sẽ có những thứ mà mình coi là bất biến, là gốc rễ và đóng góp thầm lặng vào việc phát triển năng lực của một lập trình viên bền vững trong tương lai.
Và mình tin rằng CTDL & GT cũng là một trong những kiến thức nền tảng đó! Việc học cũng như luyện tập nó ở các mức độ vừa phải (không cần ở các dạng quá cao siêu) sẽ giúp các bạn software engineer đạt được các lợi ích:
- Trau dồi khả năng tư duy logic, problem solving - từ việc phân tích đề, đưa ra các giải pháp, cài đặt, kiểm thử, review code và tìm cách tối ưu hơn nếu có,...
- Là nền tảng để hiểu sâu hơn về các kiến thức khác, ví dụ như index trong database, cơ chế xử lý Rate Limit, leader election trong Kafka,... giúp nâng tầm trình độ lên một level mới, từ việc chỉ biết cách sử dụng đơn thuần, cho đến việc giải thích được lý do tại sao sử dụng nó, so sánh được pros and cons là gì,...
- Cuối cùng nó cũng là một kỹ năng hiệu quả để giúp pass được các round interview ở những công ty top tier hiện nay, khi mà vòng CTDL & GT là một thước đo nhanh chóng với sai số tạm chấp nhận được để có thể lọc được những ứng viên phù hợp nhất. Và nó là một kỹ năng quan trọng nếu bạn muốn có một mức lương ổn cũng như tự tin có thể luôn tồn tại trong thị trường khắc nghiệt như hiện nay.
Đó chính là lý do mình cho ra đời một chuỗi các bài viết về CTDL & GT từ lý thuyết cho đến các dạng bài tập Leetcode đang được các công ty sử dụng khá phổ biến để phỏng vấn. Mục đích chính vẫn là để giúp bản thân mình ôn luyện cũng như hệ thống lại kiến thức một cách hiệu quả hơn, nếu có gì sai sót mong các bạn có thể góp ý để bài viết thêm chất lượng và tiếp cận được với những người thật sự cần nó.
2. Cấu trúc dữ liệu là gì?
Cấu trúc dữ liệu là cấu trúc dùng để lưu trữ dữ liệu, mỗi cấu trúc khác nhau sẽ có điểm mạnh yếu khác nhau và phù hợp với một số giải thuật nhất định. Phù hợp ở đây có nghĩa là giải thuật này sẽ phát huy được hết sức mạnh của nó khi đi với cấu trúc dữ liệu này, chứ không có nghĩa là gắn liền với nhau.
Đối với các dạng bài toán thường gặp, nếu chúng ta muốn nhanh thì phải hi sinh về bộ nhớ lưu trữ và ngược lại nếu muốn tiết kiệm bộ nhớ thì phải hi sinh về mặt thời gian. Đó là tính chất "Trade Off" luôn luôn phải nhớ, bạn sẽ gặp rất nhiều khó khăn nếu muốn giải thuật của mình vừa nhanh mà vừa tiết kiệm bộ nhớ! Chính vì vậy nếu muốn tối ưu mặt nào hay suy nghĩ về việc hi sinh mặt còn lại nếu có thể.
Trong series này, mình sẽ đi qua từng cấu trúc dữ liệu cụ thể kèm theo những dạng bài toán và giải thuật hay gặp, từ đó giúp ta hiểu rõ hơn về sự liên kết giữa chúng.
3. Giải thuật là gì?
Theo geeksforgeeks, giải thuật hay thuật toán nghĩa là "Một tập hợp các bước hữu hạn và có thứ tự cần tuân theo" để đạt được output từ input đã cho. Hay nói một cách đơn giản và gần gũi trong thực tế, đó có thể là các công thức nấu ăn, hay việc sắp xếp các cuốn sách theo thứ tự từ điển,...
Chỉ đơn giản như vậy thôi, nhưng việc tìm ra các bước để giải quyết một vấn đề nào đó thật sự đòi hỏi rất nhiều kỹ năng và thời gian luyện tập.
- Ở các mức độ cơ bản nhất, yêu cầu tối thiểu là cần phải nhận dạng được bài toán và các hướng giải quyết tương ứng.
- Ở mức độ nâng cao hơn, ta cần cố gắng chia nhỏ bài toán lớn thành những bài toán con có thể giải quyết được và liên kết chúng lại với nhau.
-> Và đối với mình, phương pháp học hiệu quả không chỉ là ghi nhớ như vậy, mà còn là cách suy luận để đưa ra được từng lời giải cụ thể, giải thích được tại sao lại sử dụng giải thuật đó và so sánh được ưu nhược điểm của nó đối với những cách làm khác. Vì có như vậy thì bạn mới rèn được khả năng phân tích & giải quyết vấn đề thực thụ thay vì chỉ ghi nhớ và học vẹt, trong khi trí nhớ chúng ta thì có hạn...
4. Các tính chất của giải thuật
Thường thì mình cũng không thích tập trung vào các tính chất này vì nó đạt được một cách mặc định thông qua các tư duy suy luận đúng đắn theo thời gian, tuy nhiên cũng nên giới thiệu qua để biết nó là gì và tránh gặp phải các lỗi cơ bản khi lập trình:
- Tính rõ ràng (Unambiguous): Mỗi bước trong giải thuật phải được định nghĩa rõ ràng và không gây nhầm lẫn, đảm bảo rằng mỗi bước đều dẫn đến một kết quả cụ thể.
- Tính hữu hạn (Finiteness): Giải thuật phải kết thúc sau một số bước hữu hạn để có thể hoàn thành và đưa ra kết quả cuối cùng.
- Tính đầu vào (Input) và tính đầu ra (Output): Một giải thuật phải có 0 hoặc nhiều hơn một đầu vào xác định rõ, và phải có ít nhất một đầu ra xác định, khớp với kết quả mong muốn của bài toán.
- Tính hiệu quả (Feasibility/Efficiency): Giải thuật phải khả thi, có nghĩa là có thể được thực hiện với các nguồn lực có sẵn và giải quyết vấn đề hiệu quả trong thời gian và tài nguyên cho phép.
- Tính độc lập (Independent): Giải thuật không phụ thuộc vào bất kỳ ngôn ngữ lập trình cụ thể nào, có thể được triển khai trên nhiều ngôn ngữ khác nhau mà không cần thay đổi bản chất của nó.
5. Các bước để thiết kế giải thuật
Tương tự thì khi giải một bài toán nào đó, chúng ta đang làm theo một cách bản năng nhất, tuy nhiên việc biết rõ các bước nên làm sẽ giúp chúng ta hệ thống lại theo một quy trình cụ thể, để từ đó có thể giải thích và truyền đạt được đến nhiều người khác một cách hiệu quả hơn.
5.1. Phân tích yêu cầu
Khi còn đi học, chúng ta hay được dạy cần phải "đọc kỹ đề", ở mức độ cơ bản, thì đó là việc:
- Đọc rõ các constraints của bài toán, bao gồm input, output
- Tóm tắt đề, và đọc kỹ các ví dụ cho sẵn để bước đầu hình dung về yêu cầu của bài toán
- Đặt những câu hỏi để làm rõ hơn về yêu cầu, cố gắng tìm ra các edge cases, ví dụ nếu input là 1 String thì có thể đặt các câu hỏi sau: Output sẽ như thế nào nếu input là null hoặc empty? Nếu String là 1 palindrome thì sẽ ra sao?....
5.2. Đề xuất giải pháp
Bước này thường là thể hiện rõ nhất của "Tính độc lập" đã nêu, nó không nên gắn liền với một ngôn ngữ nào cả, chúng ta cần phải đưa ra được 1 hoặc 1 vài giải pháp ở mức độ high-level, ví dụ như dùng flow-chart hay pseudocode, phân tích độ phức tạp của giải thuật đó và so sánh chúng với nhau để tìm ra giải thuật tối ưu nhất nếu có thể.
5.3. Cài đặt
Chỉ đơn giản là bước implement lại giải pháp đã đề xuất bằng một ngôn ngữ quen thuộc nào đó, có thể là C, C++, Java,... Tuy nhiên đối với môi trường đi làm, việc cài đặt sẽ được xem xét thêm các yếu tố khác đặc biệt là "Clean Code": đặt tên hàm, biến, có dễ mở rộng hay không,... Nó giống như là một thói quen tốt, giúp bạn đem vào chính công việc sau này.
5.4. Kiểm thử
Kiểm tra lại syntax hay code logic bằng việc dò nhanh lại từng dòng và chạy chay "dry run" chương trình với các ví dụ cho sẵn, cộng với các edge cases suy nghĩ ra được. Mục đích chính là cố gắng tìm được nhiều "bug" nhất có thể, luyện tập tính cẩn thận trước khi submit code. Khi đi làm thì bước này chính là việc viết các tests (unit test or integration test) để cover được nhiều case nhất có thể.
5.5. Đánh giá & cải tiến
Sau khi solution đã pass hết tất các test cases thì mọi chuyện chưa phải kết thúc, các bước ở phía trên chỉ mang tính chất cá nhân và chủ quan là chính, chúng ta nên so sánh lời giải hiện tại với các lời giải mẫu hoặc các lời giải từ người khác để có thêm nhiều góc nhìn khác nhau, từ đó có thể biết được mình đang ở level nào và cải thiện được solution hiện tại để nó tốt hơn.
6. Tổng kết
"Practice makes perfect" - Việc tìm hiểu lý thuyết là tốt và cần thiết, nhưng để có thể biến những điều trên thành bản năng, bạn cần luyện tập nhuần nhuyễn nhiều dạng bài tập khác nhau và tự suy ngẫm cũng như rút ra được bài học cho riêng mình.
Trên hết, cần phải đặt câu hỏi tại sao cần phải học algorithm? Vì mục đích gì? Vì với mỗi người, có thể sẽ có những mục tiêu khác nhau, và cũng có vô số cách để chạm được đính đến đó, quan trọng là hãy chọn một con đường phù hợp và tận hưởng nó, chứ đừng nên chạy theo số đông mà lại mất thời gian và không hiệu quả chút nào, thân chúc các bạn thành công với lựa chọn của mình!
