Articles

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:

  1. Cộng AB trước, sau đó cộng …
➟ Read more


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 …

➟ Read more




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ị …

➟ Read more

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 …

➟ Read more

Thuật toán đẹp: Partition (ngăn)

Mục đích

Chia một mảng ra thành hai cụm: một cụm thỏa điều kiện, và cụm còn lại.

Cài đặt

Sử dụng mảng phụ

def partition(a, pred):
  head = [x for x in a if pred(x)]
  tail = [x for x in a if not pred(x)]
  return head + tail …
➟ Read more

Thuật toán đẹp: Tìm nhị phân

Mục đích

Tìm phần tử X trong một mảng đã được sắp xếp.

Ý tưởng chính

Chia mảng ra thành 3 cụm: cụm bên trái, phần tử ở giữa, và cụm bên phải. So sánh X với phần tử ở giữa. Nếu X bằng với phần tử ở giữa thì …

➟ Read more