Top K Frequent Elements là câu thuật toán phỏng vấn rất hay gặp: sort toàn bộ là O(n log n), còn min-heap kích thước k chỉ O(n log k). Short này cho bạn quy tắc nhận ra bài heap trong vài giây.
▸ Bước 1: đếm tần suất bằng hash map (Dictionary trong C#), O(n)
▸ Đẩy từng phần tử vào min-heap, heap vượt k thì pop phần tử nhỏ nhất, heap chỉ tốn O(k) bộ nhớ
▸ Vì sao O(n log k) thắng sort: không tốn công sắp xếp những phần tử không bao giờ lọt top k
▸ Quy tắc nhận dạng: hỏi k lớn nhất thì dùng min-heap, hỏi k nhỏ nhất thì dùng max-heap
▸ C# PriorityQueue mặc định là min-heap, và bucket sort O(n) là phương án nên nhắc thêm với interviewer
Subscribe để luyện mỗi ngày một câu phỏng vấn thuật toán ngắn gọn, đúng trọng tâm.
🌐 Website:
ⓕ Fan Page:
ⓕ FB:
📩 Liên hệ hợp tác: duylinh191@gmail.com
#Shorts #TopKFrequentElements #MinHeap #PhongVanIT #ThuatToan #Heap #PriorityQueue #LeetCode #CodingInterview #DataStructures #CSharp #BigO
source
