python-213Bước 1Cơ bản
Kiểm tra mảng đã sắp xếp tăng dần
Trước khi chạy tìm kiếm nhị phân hay trộn mảng, ta phải kiểm tra dữ liệu đã sắp xếp chưa. Chỉ cần một lượt duyệt so sánh các cặp kề nhau là đủ — không cần sắp xếp rồi so sánh.
CHUYÊN ĐỀ PYTHON THỰC CHIẾN
Bài tập Mảng, Kỹ thuật hai con trỏ & Tìm kiếm nhị phân Python
Các kỹ thuật kinh điển giúp giảm độ phức tạp thuật toán từ O(N²) xuống O(N) hoặc O(log N). Phục vụ đắc lực cho phỏng vấn lập trình và giải bài toán dữ liệu lớn.
18
bài tập có chấm code
Bài tập theo chuyên đề, có đề bài, ví dụ và starter code riêng.
7
cơ bản
Củng cố nền tảng và làm quen với kỹ thuật cốt lõi.
10
trung bình
Kết hợp nhiều bước suy luận để vận dụng kiến thức.
1
nâng cao
Thử thách tối ưu, cấu trúc dữ liệu và thuật toán chuyên sâu.
Lộ trình thực hành đề xuất
Bước 1
Kỹ thuật Hai con trỏ
Duyệt mảng từ hai đầu hoặc cùng chiều để tìm cặp phần tử thỏa mãn điều kiện.
Bước 2
Mảng cộng dồn (Prefix Sum)
Tính trước tổng mảng để trả lời truy vấn tổng đoạn trong thời gian O(1).
Bước 3
Cửa sổ trượt (Sliding Window)
Duy trì trạng thái của dãy con liên tiếp độ dài cố định hoặc thay đổi.
Bước 4
Binary Search
Cài đặt tìm kiếm nhị phân và chặt nhị phân trên tập kết quả tối ưu.
Lỗi thường gặp & Cách phòng tránh
•
Quên cập nhật con trỏ trong vòng lặp while dẫn đến vòng lặp vô tận.
•
Lỗi tràn chỉ số (IndexError) hoặc xét thiếu trường hợp biên ở Binary Search.
Danh sách bài tập thực hành (18 bài)
Trong mỗi mức độ, bài tập được xếp từ dễ nhất đến khó nhất — hãy đi theo số bước.
Cơ bản 7 bài
Khởi động
Nhập xuất, biến, rẽ nhánh và các bước suy luận đơn giản.
python-206Bước 2Cơ bản
Phần tử lớn thứ hai trong mảng
Tìm giá trị lớn nhất thì dễ, nhưng giá trị lớn thứ hai lại là câu hỏi phỏng vấn phổ biến vì rất dễ sai khi mảng toàn số âm. Cách tốt là duyệt một lượt và giữ đồng thời hai giá trị…
python-161Bước 3Cơ bản
Tìm Kiếm Tuyến Tính Vị Trí Đầu Tiên
Trong phân tích dữ liệu và lập trình ứng dụng, việc tìm kiếm phần tử đầu tiên thỏa mãn điều kiện là thao tác cơ bản nhất. Thuật toán tìm kiếm tuyến tính (Linear Search) duyệt tuần…
python-214Bước 4Cơ bản
Xoay mảng sang trái k vị trí
Xoay mảng là thao tác chuẩn bị dữ liệu cho cửa sổ trượt, hàng đợi vòng và mã hoá. Điểm quan trọng là k có thể lớn hơn N, nên phải lấy phần dư trước khi tách mảng.
Làm quen
Vòng lặp, mảng một chiều, chuỗi và hàm ở mức cơ bản.
python-236Bước 5Cơ bản
Trung bình cộng của mảng
Trung bình cộng là chỉ số thống kê cơ bản nhất, nhưng cũng là nơi hay sai định dạng đầu ra và sai kiểu phép chia. Bài này luyện cả hai: tính đúng và in đúng định dạng số thực.
python-207Bước 6Cơ bản
Loại bỏ phần tử trùng, giữ thứ tự xuất hiện
Trong xử lý nhật ký, danh sách khách truy cập hay mã sản phẩm, ta thường phải khử trùng nhưng vẫn giữ nguyên thứ tự xuất hiện ban đầu. Dùng set cho tốc độ O(1) mỗi phần tử, kết hợp…
python-205Bước 7Cơ bản
Đếm số lần hoán đổi của sắp xếp nổi bọt
Sắp xếp nổi bọt so sánh từng cặp kề nhau và hoán đổi khi sai thứ tự. Số lần hoán đổi nó thực hiện đúng bằng số cặp nghịch thế của mảng — một thước đo mức độ lộn xộn của dữ liệu, th…
Trung bình 10 bài
Vận dụng
Dùng một kỹ thuật quen thuộc: sắp xếp, tìm kiếm, đếm, ngăn xếp.
python-235Bước 1Trung bình
Phần tử xuất hiện nhiều nhất
Đếm tần suất là phép phân tích cốt lõi: tìm sản phẩm bán chạy, phát hiện bất thường, hoặc chọn nhãn chiếm đa số. Bảng băm cho phép đếm trong O(N) thay vì duyệt lồng nhau O(N2).
python-209Bước 2Trung bình
Mảng cộng dồn (Prefix Sum)
Mảng cộng dồn cho phép trả lời câu hỏi “tổng đoạn [l, r]” trong O(1) sau O(N) chuẩn bị. Đây là kỹ thuật nền tảng cho thống kê theo khoảng thời gian, phân tích nhật ký và nhiều bài…
python-068Bước 3Trung bình
Tìm kiếm nhị phân trên mảng đã xoay (Rotated Sorted Array)
Một mảng số nguyên được sắp xếp tăng dần gồm các phần tử phân biệt bị xoay tại một trục ẩn (ví dụ: [0, 1, 2, 4, 5, 6, 7] xoay thành [4, 5, 6, 7, 0, 1, 2]).
python-012Bước 4Trung bình
Cửa sổ trượt tìm dãy con cố định có tổng lớn nhất
Hệ thống phân tích giao dịch tại AI Empire Academy cần tìm khoảng thời gian cao điểm liên tục gồm k phút có tổng số lượng request gửi về máy chủ là lớn nhất.
python-014Bước 5Trung bình
Tìm kiếm nhị phân phần nguyên căn bậc hai
Trong hệ thống tính toán số học chính xác cao của AI Empire Academy, cần tính phần nguyên căn bậc hai $⌊ √(x)
Kết hợp kỹ thuật
Phối hợp hai kỹ thuật trong cùng một lời giải.
python-204Bước 6Trung bình
Tìm kiếm nhị phân trên mảng đã sắp xếp
Tìm kiếm tuyến tính quét cả mảng nên tốn O(N). Nếu dữ liệu đã sắp xếp, mỗi bước ta loại được một nửa không gian tìm kiếm và đưa chi phí xuống O(log N) — đây là nền tảng của tra cứ…
python-208Bước 7Trung bình
Trộn hai mảng đã sắp xếp
Trộn hai danh sách đã sắp xếp là bước lõi của sắp xếp trộn (merge sort) và của việc hợp nhất kết quả từ nhiều nguồn. Kỹ thuật hai con trỏ cho kết quả trong O(n+m) mà không cần sắp…
python-010Bước 8Trung bình
Mảng cộng dồn và truy vấn tổng đoạn O(1)
Hệ thống giám sát GPU cluster tại AI Empire Academy ghi lại lượng điện năng tiêu thụ (Watt-hour) của từng phút trong ngày thành một mảng số nguyên nums. Người quản trị cần thực hiệ…
python-011Bước 9Trung bình
Tìm cặp số có tổng bằng Target trên mảng đã sắp xếp
Trong bài toán ghép cặp tài nguyên máy chủ tại AI Empire Academy, ta có một danh sách numbers gồm các số nguyên đã được sắp xếp theo thứ tự tăng dần và một giá trị mục tiêu target.
python-069Bước 10Trung bình
Bài toán chứa nước mưa lớn nhất (Container With Most Water)
Cho mảng heights gồm N số nguyên không âm, mỗi phần tử biểu thị chiều cao của một cột thẳng đứng tại vị trí i. Hai cột bất kỳ cùng với trục hoành tạo thành một thùng chứa nước.
Nâng cao 1 bài
python-065Bước 1Nâng cao
Cửa sổ trượt tìm phần tử lớn nhất bằng Monotonic Deque O(N)
Cho mảng số nguyên nums và một số nguyên k đại diện cho kích thước cửa sổ trượt. Cửa sổ dịch chuyển từ đầu đến cuối mảng, mỗi lần sang phải 1 vị trí.