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

Binary Search - Khi việc tìm kiếm cần nhanh hơn

by @ToanBui Mình thường thấy các bạn luôn sử dụng việc tìm kiếm tuyến tính (Linear Search) như một thói quen cho tất cả các trường hợp, nhưng việc này chỉ đúng khi tìm trong một mảng không được sắp xếp. Ví dụ rằng khi có một list sản phẩm, thường lúc này các sản phẩm sẽ được sắp xếp theo ID khi được trả ra, vậy nên khi tìm các sản phẩm trong list sử dụng Binary Search code của các bạn sẽ được tối ưu đáng kể từ O(n) xuống còn O(logn). Để mình đưa ra một ví dụ minh họa dễ tưởng tượng hơn. Một q

Transaction trong Store Procedure: Vấn đề gì xảy ra khi quên ROLLBACK?

By Đức Hiếu Store Procedure: Vũ khí hai lưỡi trong tối ưu hóa performance Trong quá trình phát triển phần mềm, chúng ta thường tin rằng Store Procedure là công cụ mạnh mẽ để tối ưu hiệu suất hệ thống. Tuy nhiên, qua trải nghiệm thực tế, mình nhận ra rằng nếu không sử dụng đúng cách, chúng có thể gây ra những vấn đề nghiêm trọng về hiệu năng. Bài viết này chia sẻ một bài học quý giá về trường hợp Store Procedure có thể trở thành nguyên nhân làm chậm hệ thống nếu không được xử lý lỗi đúng cách.

Cache strategies - Lựa chọn chiến lược nào cho dự án của bạn?

I. Giới thiệu Bạn hẳn đã quen thuộc với khái niệm cache rồi nhỉ? Khi ứng dụng chạy chậm, giải pháp thường nghĩ đến là dùng cache – nghe có vẻ đơn giản. Nhưng triển khai cache như thế nào để vừa đạt hiệu quả cao, vừa đảm bảo tính chính xác của dữ liệu lại là một bài toán không hề dễ. Trong bài viết này, chúng ta sẽ cùng tìm hiểu 5 chiến lược caching phổ biến, phân tích ưu nhược điểm của từng chiến lược và khám phá cách áp dụng chúng vào các tình huống thực tế để tối ưu hiệu suất hệ thống nhé.

Lost Update: Tồn kho còn 1, nhiều người cùng order thì xử lý thế nào?

by @HieuHocCode I. Giới thiệu Hãy tưởng tượng bạn đang xây dựng một sàn thương mại điện tử và gặp phải tình huống sản phẩm chỉ còn 1, nhưng có đến 2 khách hàng đặt hàng cùng lúc. Làm thế nào để hệ thống xử lý tình huống này một cách chính xác, tránh sai sót? Đây chính là một thách thức phổ biến khi xử lý nhiều transaction đồng thời. Vấn đề này thường liên quan đến khái niệm race condition, trong đó các giao dịch song song sẽ tranh chấp quyền thao tác trên dữ liệu, dẫn đến những tình trạng sa

Distributed Lock Là Gì? Tại Sao Nó Quan Trọng và Cách Triển Khai Với Redis

by @ AnhDH Mục lục 1. Đặt vấn đề 2. Distributed Lock 3. Triển khai Distributed Lock với Redis 4. Best practice 5. Tổng kết 6. Tham khảo Trong các hệ thống phân tán, việc đảm bảo tính nhất quán của dữ liệu (data consistency) và ngăn chặn tranh chấp tài nguyên (race condition) là một thách thức lớn, đặc biệt khi nhiều tiến trình hoặc service truy cập đồng thời vào các tài nguyên dùng chung. Một trong những giải pháp quan trọng để giải quyết vấn đề này chính là sử dụng distributed lock (k

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