Docs

Giải thuật phỏng vấn

Các bài toán hay gặp khi phỏng vấn, giải bằng C# và Python, kèm tình huống trong game.

1. 01Độ phức tạp Big-O: đo tốc độ thuật toánBig-O là cách đo thuật toán chậm đi bao nhiêu khi dữ liệu lớn lên. Học O(1), O(n), O(n²), O(log n) và cách đếm vòng lặp, ví dụ bằng C# và Python.
2. 02Two Sum: tìm hai số có tổng bằng mục tiêuTwo Sum, bài phỏng vấn kinh điển nhất: từ cách thử hết mọi cặp O(n²) tới cách dùng bảng băm O(n), giải bằng C# và Python.
3. 03Contains Duplicate: kiểm tra mảng có phần tử trùngKiểm tra một mảng có giá trị nào xuất hiện từ hai lần trở lên: từ hai vòng lặp O(n²) tới HashSet O(n), giải bằng C# và Python.
4. 04Valid Anagram: hai chuỗi có cùng bộ chữ cái khôngKiểm tra hai chuỗi có phải là hoán vị chữ cái của nhau hay không: từ cách sắp xếp O(n log n) tới đếm ký tự O(n), giải bằng C# và Python.
5. 05Valid Parentheses: kiểm tra ngoặc đóng mở hợp lệKiểm tra chuỗi ngoặc (), [], {} có đóng mở đúng thứ tự không: từ cách xóa lặp O(n²) tới dùng stack O(n), giải bằng C# và Python.
6. 06Valid Palindrome: kiểm tra chuỗi đối xứng bằng hai con trỏKiểm tra một câu có đọc xuôi ngược như nhau khi bỏ dấu câu và khoảng trắng: từ tạo chuỗi đảo O(n) bộ nhớ tới hai con trỏ O(1), giải bằng C# và Python.
7. 07Binary Search: tìm nhị phân trong mảng đã sắp xếpTìm một số trong mảng đã sắp xếp bằng cách chia đôi mỗi bước: từ tìm tuần tự O(n) tới tìm nhị phân O(log n), kèm hai lỗi kinh điển, giải bằng C# và Python.
8. 08Best Time to Buy and Sell Stock: mua một lần, bán một lần lời nhấtChọn ngày mua và ngày bán để lời nhiều nhất: từ thử mọi cặp ngày O(n²) tới giữ giá thấp nhất đã gặp O(n), giải bằng C# và Python.
9. 09Maximum Subarray: đoạn con có tổng lớn nhất với KadaneTìm đoạn liên tiếp có tổng lớn nhất trong mảng có cả số âm: từ thử mọi đoạn O(n²) tới thuật toán Kadane O(n), giải bằng C# và Python.
10. 10Merge Sorted Arrays: gộp hai mảng đã sắp xếpGộp hai mảng đã sắp xếp thành một mảng vẫn sắp xếp: từ nối rồi sắp xếp lại O((n+m) log(n+m)) tới hai con trỏ O(n+m), giải bằng C# và Python.
11. 11Move Zeroes: dồn số 0 về cuối mảng tại chỗDồn mọi số 0 về cuối mảng mà vẫn giữ thứ tự các số còn lại, không tạo mảng mới: dùng hai con trỏ đọc và ghi O(n), giải bằng C# và Python.
12. 12Group Anagrams: nhóm các từ cùng bộ chữ cáiGom các từ là anagram của nhau vào cùng một nhóm: từ so từng cặp tới dùng Dictionary với key là chuỗi đã sắp xếp, giải bằng C# và Python.
13. 13Fibonacci: đệ quy, ghi nhớ và vòng lặpTính số Fibonacci thứ n theo ba cách: đệ quy thuần O(2^n), đệ quy có ghi nhớ (memo) và vòng lặp O(n). Bài mở đầu cho quy hoạch động, giải bằng C# và Python.
14. 14Climbing Stairs: đếm số cách leo cầu thangLeo n bậc, mỗi lần 1 hoặc 2 bậc, có bao nhiêu cách? Cách tìm công thức truy hồi, dựng bảng dp và rút gọn còn hai biến, giải bằng C# và Python.
15. 15Coin Change: đổi tiền bằng ít đồng xu nhấtTìm số đồng xu ít nhất để ghép đúng một số tiền: vì sao cách tham lam sai, cách dựng bảng dp và xử lý trường hợp không đổi được, giải bằng C# và Python.
16. 16Reverse Linked List: đảo ngược danh sách liên kếtĐảo chiều một danh sách liên kết đơn bằng ba con trỏ prev, cur, next trong O(n) thời gian và O(1) bộ nhớ, có định nghĩa ListNode, giải bằng C# và Python.
17. 17Linked List Cycle: phát hiện vòng lặp bằng rùa và thỏKiểm tra danh sách liên kết có vòng hay không: cách dùng HashSet O(n) bộ nhớ và cách rùa và thỏ (Floyd) chỉ tốn O(1) bộ nhớ, giải bằng C# và Python.
18. 18Longest Substring Without Repeating Characters: chuỗi con dài nhất không lặp ký tựTìm độ dài chuỗi con liên tiếp dài nhất không có ký tự nào lặp lại: từ cách thử mọi điểm bắt đầu O(n²) tới cửa sổ trượt O(n), giải bằng C# và Python.
19. 19BFS: tìm đường ngắn nhất trên bản đồ lướiTìm số bước ít nhất để quái đuổi tới người chơi trên bản đồ ô vuông có tường, dùng BFS với hàng đợi và mảng đánh dấu, giải bằng C# và Python.
20. 20Number of Islands: đếm đảo và tô vùng (flood fill)Đếm số vùng đất liền trên lưới bằng flood fill, viết theo DFS đệ quy và BFS dùng hàng đợi, kèm lỗi tràn stack khi đệ quy quá sâu, giải bằng C# và Python.
21. 21Binary Tree Traversal: bốn cách duyệt cây nhị phânDuyệt cây nhị phân theo preorder, inorder, postorder bằng đệ quy và theo từng tầng (level order) bằng hàng đợi, có định nghĩa TreeNode, giải bằng C# và Python.
22. 22Sorting: bubble sort, merge sort, quick sort và hàm sắp xếp có sẵnÝ tưởng và code ngắn của bubble sort, merge sort, quick sort, bảng so sánh độ phức tạp, và khi nào nên dùng Array.Sort hay sorted, giải bằng C# và Python.
23. 23Top K Frequent Elements: k phần tử xuất hiện nhiều nhấtTìm k phần tử xuất hiện nhiều nhất: đếm bằng Dictionary rồi sắp xếp O(n log n), hoặc chia vào các giỏ theo số lần xuất hiện để được O(n), giải bằng C# và Python.