Phỏng vấn: Tìm 1 triệu số nhỏ nhất trong 1 tỷ số
Câu hỏi
Cho 1 tỷ số thực, tìm 1 triệu số nhỏ nhất trong 1 tỷ số đấy.
Phân tích
Cách giải đơn giản nhất là sắp xếp từ bé đến lớn 1 tỷ số đầu vào, sau đó chọn ra 1 triệu số đầu tiên. Độ phức tạp của …
Articles
Phỏng vấn: Số nhân viên cấp dưới
Câu hỏi
Cho một từ điển từ chuỗi sang chuỗi, khoá là tên nhân viên, và giá trị là tên của người quản lý. Nhân viên cấp cao nhất báo cáo cho chính họ. Tìm số nhân viên cấp dưới của một nhân viên nào đó.
Ví dụ: Trong từ …
Phỏng vấn: Cộng chuỗi ít tốn nhất
Câu hỏi
Cho n chuỗi, tìm cách cộng các chuỗi này lại theo một thứ tự nào đó sao cho ít tốn bộ nhớ nhất.
Ví dụ: Cho chuỗi A=abc, B=wxyz, C=g, và xét hai cách cộng chuỗi sau:
- Cộng A và B trước, sau đó cộng …
Phỏng vấn: In ra phần tử nhỏ thứ n trong cây nhị phân
Câu hỏi
Cho một cây nhị phân tìm kiếm (binary search tree), in ra phần tử nhỏ thứ n trong cây này.
Ví dụ: Với cây nhị phân như sau:
7
5 9
3 6 10
Phần tử nhỏ nhất (n=1) là 3, phần tử nhỏ thứ 2 là …
Phỏng vấn: Tìm các từ cùng bộ ký tự
Câu hỏi
Cho một quyển từ điển D, và một từ W trong từ điển, yêu cầu xuất ra tất cả các từ có trong từ điển với cùng bộ ký tự như từ W.
Ví dụ từ mary có bộ ký tự là một chữ m, một chữ a …
Phỏng vấn: Số lượng số chính phương ít nhất để có tổng là n
Câu hỏi
Cho một số nguyên dương n, tìm số lượng số chính phương ít nhất có tổng là n.
Ví dụ: Với n là 9, thì đáp án là 1 (vì 9 là số chính phương), với n là 10 thì đáp án là 2 (9 + 1), với n …
Phỏng vấn: Cài đặt "ngăn xếp" với thao tác "min/max"
Câu hỏi
Cài đặt cấu trúc dữ liệu ngăn xếp với thao tác trả về phần tử nhỏ (hay lớn) nhất hiện tại của ngăn xếp.
Phân tích
Ngăn xếp (stack) là cấu trúc dữ liệu vào sau ra trước (Last In, First Out). Nói đến ngăn xếp ta phải …
Phỏng vấn: Tìm tích của mọi phần tử trừ phần tử hiện tại
Câu hỏi
Cho một danh sách các số thực A, trả về một danh sách trong đó phần tử tại vị trí i có giá trị là tích của các phần tử không phải ở vị trí i trong danh sách A.
Phân tích
Trường hợp ngoại lệ
Nếu A …
Phỏng vấn: Cách mua và bán lời nhất
Câu hỏi
Giả sử như bạn có thông tin về giá của một món hàng trong một khoảng thời gian nào đó. Tìm ngày bạn sẽ mua, và ngày bạn sẽ bán món hàng đó để đạt được lợi nhuận cao nhất.
Đầu vào: một danh sách các giá trị …
Thuật toán đẹp: Tìm chuỗi Boyer-Moore-Horspool
Mục đích
Tìm chính xác (exact match) chuỗi con (substring) trong một chuỗi dài hơn.
Ý tưởng chính
Gọi chuỗi cần tìm là P (pattern), và chuỗi dài là T (text).
So sánh ngược P trong T, nghĩa là ta sẽ so sánh ký tự cuối của P trước, sau …