Phỏng vấn 2: BST, heap và top-k

Giới thiệu

Bạn luyện bài cây và heap. Vẽ hình heap khi dry-run.

Kiến thức cần nhớ

Duyệt và biến đổi BST

• BST là trái nhỏ hơn gốc, phải lớn hơn gốc.
• Hay gặp: liệt kê trong khoảng, tìm tổ tiên chung.
• Ví dụ đời thường: giống tìm sách trong kệ xếp theo tên.
• Cắt tỉa bỏ nhánh ngoài khoảng cho nhanh.

Kiểm tra BST hợp lệ

• So cha con thôi là chưa đủ.
• Phải dùng khoảng chặn từ gốc truyền xuống.
• Ví dụ đời thường: giống kiểm tra cả dòng họ, không chỉ cha con.
• Nút sai ở tầng sâu dễ lọt nếu chỉ so gần.

Heap và top-k

• Heap lấy lớn nhất hoặc nhỏ nhất rất nhanh.
• Heapify biến mảng thành heap trong $O(n)$.
• Ví dụ đời thường: heap như xếp hàng ưu tiên.
• Top-k trên stream chỉ giữ k món, không giữ hết.

# top-k nhỏ nhất bằng heap
import heapq  # thư viện heap sẵn
def topk(a, k):
    h = []  # heap giữ k món
    for x in a:  # duyệt từng món
        heapq.heappush(h, x)  # đẩy vào heap
        if len(h) > k:  # quá k món
            heapq.heappop(h)  # bỏ món nhỏ nhất
    return sorted(h)  # trả k món lớn nhất

Ví dụ

• Cây 7 nút, khoảng hẹp trúng 2 -> chỉ thăm đường cần thiết.
• Stream 100 số, k = 3 -> chỉ giữ 3 số lớn nhất.

💻 Bài tập

Luyện phỏng vấn, mỗi bài 25 phút. Nộp vào day-162/, mỗi bài 1 file có test và comment độ phức tạp.

Bài 1: BST

1a: [5, 1, 4, null, null, 3, 6] -> false (3 nằm bên phải 5)
1b: BST [3,1,4,null,2], k=1 -> 1
1d: [10,5,15,3,7,null,18], lo=7, hi=15 -> 32

Bài 2: Heap

2a: [3,2,1,5,6,4], k=2 -> 5
2c: add 1, add 2 -> 1.5; add 3 -> 2

Bài 3: Kết hợp (nâng cao)

1. k điểm gần gốc tọa độ nhất trong $10^6$ điểm, $O(n \log k)$.
2. Lập lịch CPU: các task có thời điểm đến và thời gian chạy. Luôn chạy task ngắn nhất đang chờ. In thứ tự hoàn thành.
3. Iterator duyệt BST theo thứ tự, next() $O(1)$ trung bình, bộ nhớ $O(h)$.

✅ Tiêu chí hoàn thành

• 12 bài có test gồm ca biên.
• isValidBST bắt được lỗi ở cháu.
• Trung vị luồng có test 10^5 số ngẫu nhiên so với sắp xếp.
• Bảng thời gian thực tế mỗi bài.

❓ Câu hỏi ôn tập

1. Quy tắc trái phải của BST là gì?
2. Vì sao so cha con chưa đủ?
3. Heapify tốn bao nhiêu?
4. Top-k giữ mấy món trong heap?

🌕 Bạn đã hoàn thành ngày 162. Làm hết bài tập phía trên rồi sang ngày tiếp theo.