Đang nạp Cẩm nang Phỏng vấn...
Đang nạp Cẩm nang Phỏng vấn...
Hệ thống hóa toàn bộ 49 tài liệu cốt lõi từ yangshun/tech-interview-handbook (110k+ ⭐): 20 Cheatsheet cấu trúc dữ liệu, cẩm nang chiến lược phòng thi, ngân hàng câu hỏi hành vi STAR kèm rubrics chấm điểm, và 10 nguyên tắc vàng đàm phán Total Comp.
Cấu trúc dữ liệu nền tảng nhất. Bộ nhớ liên tục cho phép truy cập ngẫu nhiên O(1). Trọng tâm phỏng vấn là Two Pointers, Sliding Window và Prefix Sum.
Two Pointers (Hai con trỏ): Duyệt từ 2 đầu mảng đã sắp xếp hoặc con trỏ nhanh/chậm
Tương tự như mảng nhưng bất biến (immutable) trong Python và Java. Chú ý các phép biến đổi chuỗi con, so khớp mẫu và bảng mã ký tự.
Frequency Array: Dùng mảng int[26] hoặc int[128] thay vì Map để đếm tần suất nhanh hơn
Cấu trúc dữ liệu ánh xạ key-value quan trọng nhất trong lập trình. Cho phép tra cứu, thêm và xóa trong thời gian trung bình O(1). Chú ý cơ chế xử lý va chạm (Chaining vs Open Addressing).
Đếm tần suất (Frequency Counter): Kiểm tra Anagram hoặc phần tử chiếm đa số
Cấu trúc dữ liệu Last-In-First-Out. Cực kỳ đắc lực cho các bài toán ghép cặp ngoặc, duyệt cây/đồ thị dạng DFS và kỹ thuật Monotonic Stack tìm phần tử lớn hơn kế tiếp.
Ghép cặp ngoặc (Matching Pairs): Đẩy ngoặc mở vào stack, gặp ngoặc đóng thì pop kiểm tra
Cấu trúc First-In-First-Out. Trụ cột của thuật toán duyệt đồ thị theo chiều rộng (BFS), mô phỏng hàng đợi tin nhắn và kỹ thuật Monotonic Deque cho cửa sổ trượt.
Breadth-First Search (BFS): Duyệt theo từng lớp (level-order) tìm đường đi ngắn nhất đồ thị không trọng số
Tìm kiếm nhị phân chia đôi không gian tìm kiếm O(log n). Thao tác bit (Bit manipulation) tối ưu bộ nhớ và tính toán chỉ trong 1 chu kỳ xung nhịp CPU.
Binary Search trên không gian đáp án (Binary Search on Answer): Khi hàm kiểm tra có tính đơn điệu
Phương pháp giải quyết bài toán tối ưu có các bài toán con chồng lấn (overlapping subproblems) và cấu trúc con tối ưu (optimal substructure).
Xác định rõ ý nghĩa trạng thái DP[i] hoặc DP[i][j]
Tập hợp các đỉnh (Vertices) và cạnh (Edges). Mô hình hóa mạng xã hội, bản đồ giao thông và hệ thống phân tán. Trọng tâm là BFS, DFS, Dijkstra và Topological Sort.
BFS: Tìm đường đi ngắn nhất trên đồ thị không trọng số
Tập hợp các nút chứa giá trị và con trỏ trỏ đến nút kế tiếp. Thêm/xóa O(1) khi đã có con trỏ nhưng truy cập ngẫu nhiên tốn O(n).
Dummy / Sentinel Node: Nút giả đứng trước head giúp đồng nhất logic thêm/xóa mà không cần kiểm tra if(head == null)
Đồ thị có hướng vô hướng phi chu trình đặc biệt. Trọng tâm phỏng vấn là Binary Tree Traversals (In-order, Pre-order, Post-order, Level-order) và tính chất BST.
Duyệt đệ quy DFS (Pre-order, In-order, Post-order): Thuộc lòng cấu trúc đệ quy cơ sở
Cây nhị phân gần hoàn chỉnh duy trì phần tử nhỏ nhất (Min-Heap) hoặc lớn nhất (Max-Heap) ở gốc. Tối ưu cho các bài toán tìm Top K phần tử hoặc ghép K danh sách.
Top K Elements: Dùng Min-Heap kích thước K để tìm K phần tử lớn nhất trong luồng dữ liệu
Các bài toán thao tác trên các khoảng [start, end]. Trọng tâm là hợp nhất các khoảng chồng lấn (Merge Intervals), tìm điểm chèn và lập lịch phòng họp.
Sắp xếp theo start time: 90% bài toán interval bắt đầu bằng việc sort theo mốc bắt đầu