1. Arrays and Graphs

Xác Định Tổng Của Ba Số Nguyên

Bài toán: Tìm ba số nguyên trong mảng sao cho tổng của chúng bằng một giá trị cho trước.

Phương pháp: Sắp xếp mảng, sử dụng hai con trỏ để tìm tổng phù hợp.

Độ phức tạp: O(n²).

Hợp Nhất Các Khoảng Thời Gian Chồng Chéo

Bài toán: Hợp nhất các khoảng thời gian chồng lên nhau trong một danh sách.

Phương pháp: Sắp xếp theo timestamp, sau đó hợp nhất các khoảng thời gian.

Độ phức tạp: O(n).

Sao Chép Một Đồ Thị Có Hướng

Bài toán: Tạo bản sao sâu (deep copy) của một đồ thị có hướng.

Phương pháp: Sử dụng bảng băm để theo dõi các node đã được duyệt.

Độ phức tạp: O(n).

2. Linked List

Cộng Hai Số Nguyên Dưới Dạng Danh Sách Liên Kết

Bài toán: Thực hiện phép cộng hai số nguyên được biểu diễn dưới dạng danh sách liên kết.

Phương pháp: Duyệt từng node của danh sách, cộng từng phần tương ứng.

Độ phức tạp: O(n).

Hợp Nhất Hai Danh Sách Liên Kết Đã Sắp Xếp

Bài toán: Hợp nhất hai danh sách liên kết đã được sắp xếp.

Phương pháp: Duyệt từng node và kết hợp chúng.

Độ phức tạp: O(m + n), với m và n là độ dài của hai danh sách.

3. Trees

Kiểm Tra Hai Cây Nhị Phân Có Giống Hệt Nhau Không

Bài toán: Kiểm tra xem hai cây nhị phân có hoàn toàn giống nhau hay không.

Phương pháp: Dùng đệ quy để so sánh từng node trong cây.

Độ phức tạp: O(n), với n là số node trong cây.

Hoán Đổi Các Node Của Cây Nhị Phân

Bài toán: Hoán đổi node trái và phải của một cây nhị phân.

Phương pháp: Duyệt theo thứ tự sau (post-order traversal).

Độ phức tạp: O(n).

4. Strings

Tìm Tất Cả Các Chuỗi Palindrome

Bài toán: Tìm tất cả các chuỗi con là palindrome trong một chuỗi cho trước.

Phương pháp: Mở rộng từ giữa mỗi ký tự trong chuỗi để tìm palindrome.

Độ phức tạp: O(n²).

Đảo Ngược Các Từ Trong Câu

Bài toán: Đảo ngược thứ tự các từ trong một câu.

Phương pháp: Đảo ngược toàn bộ chuỗi rồi đảo ngược lại từng từ.

Độ phức tạp: O(n), với n là chiều dài chuỗi.

5. Dynamic Programming

Tìm Mảng Con Có Tổng Lớn Nhất

Bài toán: Tìm mảng con có tổng lớn nhất trong một mảng cho trước.

Phương pháp: Sử dụng thuật toán Kadane.

Độ phức tạp: O(n).

Lũy Thừa Của Một Số

Bài toán: Tính lũy thừa của một số nguyên.

Phương pháp: Dùng phương pháp chia để trị (divide and conquer).

Độ phức tạp: O(logn).

Tìm Tất Cả Các Tổ Hợp Tổng Bằng Một Số Cho Trước

Bài toán: Tìm tất cả các tổ hợp có tổng bằng một số cho trước.

Phương pháp: Đệ quy kết hợp với thuật toán backtracking.

Độ phức tạp: O(2ⁿ), với n là số phần tử.

6. Searching and Design

Tìm Kiếm Trong Mảng Xoay

Bài toán: Tìm kiếm một số trong mảng xoay đã được sắp xếp.

Phương pháp: Sử dụng thuật toán tìm kiếm nhị phân, điều chỉnh để xử lý mảng xoay.

Độ phức tạp: O(logn).

Cài Đặt Bộ Nhớ Đệm LRU

Bài toán: Cài đặt bộ nhớ đệm Least Recently Used (LRU).

Phương pháp: Sử dụng hashmap kết hợp với danh sách liên kết đôi (doubly linked list).

Độ phức tạp: O(1) cho các thao tác get và set.

7. Bonus

Vấn Đề Các Triết Gia Ăn Uống

Bài toán: Xử lý tình huống các triết gia ăn uống sao cho không bị bế tắc.

Phương pháp: Sử dụng semaphore hoặc tổ chức thứ tự ưu tiên trong việc truy cập các tài nguyên.

Độ phức tạp: Phụ thuộc vào cách triển khai giải pháp.

Kết luận: Những câu hỏi này không chỉ giúp bạn chuẩn bị tốt cho các cuộc phỏng vấn tại Apple mà còn giúp rèn luyện kỹ năng giải quyết các vấn đề thuật toán phức tạp. Thực hành các bài toán này sẽ nâng cao khả năng tư duy logic và chuẩn bị cho những thử thách trong môi trường làm việc công nghệ cao.