by @ToanBui

Các bài toán mang tư tưởng đếm xuất hiện phần lớn ở các bài phỏng vấn thuật toán của các công ty, các bài này thường ở mức dễ để xử lý.

Một mẫu đề bài ví dụ là cho một chuỗi kí tự và trả về kí tự có số lượng xuất hiện nhiều thứ 2 trong chuỗi.

Để bắt đầu với điều này, hãy trở về quá khứ tại thời điểm bản thân bắt đầu học đếm. Phần lớn mọi người đều biết tới que tính với rất nhiều màu sắc (lục, đỏ, xanh, vàng,…). Mình có một chuỗi ví dụ đơn giản là “abacca”, mình sẽ lấy kí tự “a” với que tính đỏ, “b” là que tính vàng và “c” là que tính lục. Lúc này mình có số lượng que tính đỏ là 3, vàng là 1 và cuối cùng lục là 2. Việc còn lại là mình sẽ tìm lại số que có số lượng nhiều thứ 2 trong đó là lục tương đương với kí tự “c”.

Trở lại với bài toán lập trình, hẳn mọi người nghĩ ngay tới việc tạo một hash table có các cặp key-value để xử lý bài toán với các key là một kí tự trong chuỗi, và value sẽ là số lần xuất hiện của các kí tự. Việc này hoàn toàn khả thi nhưng theo mình nghĩ không cần quá phức tạp như vậy.

Mình hoàn toàn có thể xử lý với một array gồm 26 vị trí tương đương với 26 kí tự trong bảng chữ cái. Sau đó, mình sẽ áp dụng mã của một kí tự theo bảng mã ASCII và trừ đi cho mã của kí tự đầu tiên trong bảng chữ cái là kí tự “a” với mã trên bảng mã ASCII là 97 lúc đó ta sẽ có COUNTING_ARR[97-97]++ (tăng lên khi kí tự xuất hiện trong chuỗi). Lúc này việc còn lại chỉ là tìm kí tự xuất hiện nhiều thứ hai.

Với việc sử dụng array mình tin chắc mọi người sẽ ăn điểm với nhà tuyển dụng về việc xử lý array.

✏️ System Design VN: https://fb.com/groups/systemdesign.vn
📚 Đọc thêm tài liệu khác: https://roninhub.com/tai-lieu
🎬 Youtube: https://youtube.com/@ronin-engineer