Day 2 — Categorization & Top K Elements

Learning Objectives

• Làm chủ kỹ thuật Phân nhóm (Categorization) dữ liệu bằng cách sử dụng HashMap.
• Sử dụng Mảng tĩnh (Static Array) làm Key cho HashMap để tối ưu hóa từ O(k log k) xuống O(k).
• Hiểu và áp dụng kỹ thuật Bucket Sort để giải quyết các bài toán về tần suất (Top K) trong thời gian tuyến tính O(n).

Key Concepts & Glossary

Các thuật ngữ quan trọng:

• Entry API: Một tính năng mạnh mẽ của Rust giúp thực hiện thao tác "kiểm tra và cập nhật" (Check-and-update) trên HashMap chỉ với một lần tìm kiếm (Single-lookup).
• Bucket Sort: Kỹ thuật phân phối các phần tử vào các "xô" dựa trên tần suất xuất hiện của chúng để tìm Top K mà không cần sắp xếp toàn bộ mảng.
• Frequency Map: Một HashMap dùng để đếm số lần xuất hiện của từng phần tử.

Example Implementation

Cargo.toml

[package]
name = "algo02_categorization"
version = "0.1.0"
edition = "2024"

[dependencies]
# Standard library is sufficient

src/main.rs

use std::collections::HashMap;

fn main() {
    let strs = vec![
        "eat".to_string(), "tea".to_string(), "tan".to_string(), 
        "ate".to_string(), "nat".to_string(), "bat".to_string()
    ];
    
    // Task: Group Anagrams (LeetCode 49)
    let grouped = group_anagrams(strs);
    println!("Grouped Anagrams: {:?}", grouped);
}

/// O(n * k) time complexity where n is number of strings and k is max length
fn group_anagrams(strs: Vec<String>) -> Vec<Vec<String>> {
    // Key is a frequency array of 26 lowercase letters
    let mut map: HashMap<[u8; 26], Vec<String>> = HashMap::new();

    for s in strs {
        let mut count = [0u8; 26];
        for &b in s.as_bytes() {
            count[(b - b'a') as usize] += 1;
        }

        // Using Entry API for efficient insertion
        // If the key doesn't exist, it creates a new Vec
        map.entry(count).or_insert(Vec::new()).push(s);
    }

    // Transform map values into the final result vector
    map.into_values().collect()
}

Hands-on Exercises

1. top_k_frequent(nums: Vec, k: i32) -> Vec Tìm K phần tử xuất hiện nhiều nhất trong mảng. Hãy thử giải bằng Bucket Sort để đạt O(n) thay vì O(n log n). Ví dụ: nums = [1,1,1,2,2,3], k = 2 -> [1, 2].
2. product_except_self(nums: Vec) -> Vec Trả về mảng kết quả sao cho mỗi phần tử tại i bằng tích của tất cả các số khác trừ nums[i]. Không được dùng phép chia. Ví dụ: [1, 2, 3, 4] -> [24, 12, 8, 6].
3. longest_consecutive(nums: Vec) -> i32 Tìm độ dài của dãy số liên tiếp dài nhất (không cần đúng thứ tự trong mảng). Phải đạt độ phức tạp O(n). Ví dụ: [100, 4, 200, 1, 3, 2] -> Dãy [1, 2, 3, 4] có độ dài 4.

Common Pitfalls & Debugging Tips

Q&A — Common Questions

Q1. Khi nào nên dùng HashMap và khi nào nên dùng BTreeMap?

• Dùng HashMap khi bạn chỉ cần truy cập nhanh (O(1)) và không quan tâm đến thứ tự của các Key.
• Dùng BTreeMap khi bạn cần các Key luôn được sắp xếp (ví dụ: để in ra báo cáo theo thứ tự bảng chữ cái), đổi lại tốc độ truy cập sẽ chậm hơn (O(log n)).

Q2. Làm sao để xử lý Key có chứa ký tự ngoài bảng chữ cái tiếng Anh?

• Nếu đầu vào chứa ký tự Unicode, bạn không thể dùng [u8; 26]. Lúc này, hãy dùng chính chuỗi đã được chuẩn hóa (ví dụ: s.chars().sorted().collect()) làm Key của HashMap<String, Vec<String>>.

Wisdom Note