logo

Lộ trình

Khóa học

Tài liệu

Mock Interview

Liên hệ

Quay lại
  • Trang chủ

    /

  • Tài liệu

    /

  • Counting - Dạng bài phỏng vấn thuật toán phổ biến của các công ty
Tài liệu

Counting - Dạng bài phỏng vấn thuật toán phổ biến của các công ty

Ronin Engineer

14 Tháng 6 2025

<p>by @ToanBui</p><p>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ý.</p><p>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.</p><figure class="kg-card kg-image-card kg-width-full"><img src="https://roninhub.com/content/images/2025/06/io_counting-1.png" class="kg-image" alt="" loading="lazy" width="519" height="238"></figure><p>Để 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”.</p><figure class="kg-card kg-image-card kg-width-full"><img src="https://roninhub.com/content/images/2025/06/example_counting.png" class="kg-image" alt="" loading="lazy" width="540" height="378"></figure><p>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.</p><p>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.</p><figure class="kg-card kg-image-card"><img src="https://roninhub.com/content/images/2025/06/logic_flow_counting.png" class="kg-image" alt="" loading="lazy" width="1128" height="647" srcset="https://roninhub.com/content/images/size/w600/2025/06/logic_flow_counting.png 600w, https://roninhub.com/content/images/size/w1000/2025/06/logic_flow_counting.png 1000w, https://roninhub.com/content/images/2025/06/logic_flow_counting.png 1128w" sizes="(min-width: 720px) 720px"></figure><p>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.</p><hr><p>✏️ System Design VN: <a href="https://fb.com/groups/systemdesign.vn%5C?ref=roninhub.com">https://fb.com/groups/systemdesign.vn</a><br>📚 Đọc thêm tài liệu khác: <a href="https://roninhub.com/tai-lieu%5C">https://roninhub.com/tai-lieu</a><br>🎬 Youtube: <a href="https://youtube.com/@ronin-engineer?ref=roninhub.com">https://youtube.com/@ronin-engineer</a></p>

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

beginner
dsa
buiductoan

Bài viết liên quan

Stack & Queue - Khi array không chỉ để lưu trữ

Stack & Queue là hai cấu trúc dữ liệu cơ bản và phổ biến trong con đường của một lập trình viên, hẳn rằng những lập trình viên có kinh nghiệm đều đã nghe, đã biết đến cấu trúc dữ liệu này, vậy cuối cùng thì, Stack & Queue là gì và nó có tác dụng thế nào? QUEUE - HÀNG ĐỢI Để bắt đầu nhẹ nhàng, chúng ta bắt đầu với Queue trước. Trước tiên thì Queue là một cấu trúc dữ liệu có dạng FIFO (First In Frist Out) tức là vào trước thì ra trước. Một ví dụ dễ thấy trong cuộc sống hàng ngày là việc xếp

Materialized view với PostgreSQL

Khái niệm view trong relational database chắc hẳn đã quá quen thuộc với anh em dev. View chỉ lưu trữ câu lệnh truy vấn, không lưu kết quả truy vấn và thực hiện truy vấn trên (các) bảng gốc mỗi khi view được truy cập. Vậy nếu truy vấn của view là một truy vấn phức tạp cho thống kế, cần JOIN nhiều bảng, nhiều điều kiện FILTER, tập dữ liệu ở bảng gốc lớn, có nhiều phép tổng hợp như SUM, AVG… Thì các bạn có đoán được vấn đề gì sẽ xuất hiện không? Nếu câu trả lời của các bạn là “hiệu suất của truy

DFS & BFS - Khi dữ liệu không được lưu trữ một cách tuyến tính

By Bùi Đức Toàn “Muốn tìm trân châu nơi đáy biển, ắt phải lặn sâu. Muốn nhìn toàn cảnh rừng xanh, phải leo lên đỉnh núi.” - Cổ nhân. Từ thuở khai hoang, con người khi thì đào sâu xuống lòng đất để tìm vàng, khi thì lại lần theo dòng sông để biết nó chảy về đâu. Trong thế giới khoa học máy tính, tinh thần khai hoang đó được tái hiện qua hai chiến lược kinh điển trong việc duyệt đồ thị là: 1. Tìm kiếm theo chiều sâu (Depth-First Search – DFS). 2. Tìm kiếm theo chiều rộng (Breadth-First Search

Connection Pool: Tối ưu hiệu suất kết nối Database trong hệ thống Backend

By Đức Hiếu 1. Connection Pool là gì? Connection Pool là một cơ chế quản lý kết nối giữa các ứng dụng đến cơ sở dữ liệu (Database Server), trong đó một tập hợp các kết nối được khởi tạo trước và duy trì sẵn sàng để sử dụng. Thay vì phải thiết lập kết nối mới mỗi khi cần truy vấn dữ liệu. Database Client (thường là Backend App) có thể "mượn" một kết nối có sẵn từ pool, sử dụng xong và trả lại pool để tái sử dụng. 1.1. Vấn đề với phương pháp kết nối truyền thống Trong mô hình kết nối truyền

HTTP/1.1 vs HTTP/2 : Tại sao HTTP/2 lại nhanh hơn?

By @VietDuc HTTP (Hypertext Transfer Protocol) là giao thức truyền tải tài nguyên cho Web theo mô hình Client-Server (hoặc Request-Response). Ví dụ khi bạn truy cập https://roninhub.com/ . Trình duyệt sẽ tạo các HTTP request đến Server lấy các file HTML, Ảnh, Text… hiển thị lên như ảnh bên dưới. HTTP hoạt động thế nào? Khi một Client (thường là trình duyệt) gửi một HTTP request, quá trình giao tiếp giữa Client và Server thường diễn ra qua các bước sau: * Thiết lập kết nối TCP: Client

Tất cả bài viết
logo

HỘ KINH DOANH LẬP VƯƠNG

Giấy chứng nhận đăng ký doanh nghiệp số: 8656162915-001. Cấp ngày 21/02/2024. Nơi cấp: Sở Kế hoạch và Đầu tư TP. Hà Nội

PHƯƠNG THỨC THANH TOÁN

vnpay

LIÊN HỆ

roninengineer88@gmail.com

0362228388

26 ngõ 156 Hồng Mai, Hai Bà Trưng, Hà Nội

THEO DÕI CHÚNG TÔI

Facebook

Youtube

Tiktok

CHÍNH SÁCH

Chính sách bảo mật

Chính sách thanh toán

Đổi trả/Hoàn tiền

Hướng dẫn thanh toán VNPAY

PHƯƠNG THỨC THANH TOÁN

vnpay

Ronin Engineer 2024