Các câu hỏi phỏng vấn [33]
Ngô Quang Hưng | 13 tháng 01, 2010 | 
Bản để in
Cảm ơn bác Vũ Hà Văn cho câu hỏi số 90 rất dễ thương. Câu 91 là một sinh viên của tôi vừa phỏng vấn ở Google được/bị hỏi. Câu 92 chôm từ chùa THT, do bác Đàm Thanh Sơn truyền bá từ quyển sách thú vị của Mark Levi.
- Có 10 con kiến trên một que 1 mét. Từng con kiến bắt đầu bò sang trái hoặc phải tùy hỉ, dọc theo que, với tốc độ 1 mét/giờ. Khi hai con kiến đụng đầu nhau chúng sẽ đổi hướng. Khi một con bò đến đầu que thì nó rới xuống đất. Hỏi: khi nào thì tất cả kiến rơi xuống đất?
- Cho n dãy ký tự, mỗi dãy có n ký tự. Tìm dãy con chung lớn nhất của tất cả n dãy trong thời gian càng nhanh càng tốt. Ví dụ, ba dãy
abcxyz, xabcfb, xyzabccó dãy conabcchung. - Một người đi xe đạp hai bánh trong sân. Vết bánh trước và bánh sau tạo thành hai đường cong trơn khép kín không giao nhau. Chứng minh rằng diện tích hình vành khăn nằm giữa hai đường cong khép kín này là một hăng số chỉ phụ thuộc vào cái xe đạp, không phụ thuộc gì vào cơ bắp hay nghệ thuật của người đi.
Cho em hỏi là với câu hỏi số 91 có phải ta sẽ tìm được trong O(n) với suffix tree đúng ko a?
90 : 1h.
Hòa Thượng: 1h đúng là chặn trên tốt nhất có thể có nếu không còn thông tin nào khác.
Tuy nhiên ta có thể có câu trả lời chính xác luôn nếu cho cả vị trí từng con và chiều (trái/phải) mà từng con kiến chọn. Trong trường hợp đó, bọn kiến có thể rơi trước 1 h.
Để PB thử trả lời câu 90 xem nhá:
Nếu các chú kiến đi cùng chiều thì không quá 1h các chú sẽ rơi xuống hết. Bây giờ xét 1 chú kiến đi ngược chiều với các chú còn lại. Khi chú này gặp chú đi ngước chiều đâu tiên, theo đề bài hai chú này sẽ đổi chiều. Giả sử kiến A đi từ bên trái qua bên phải, kiến B đi từ bên phải qua bên trái, thế thì khi gặp nhau A về bên trái, B về bên phải. Tuy nhiên về bản chất hai chú kiến là không phân biệt nếu ta thêm giả sử ở thời điểm gặp nhau ta không nhìn thấy chúng đụng độ, A vẫn đi tới đầu bên phải, B vẫn đi tới đầu bên trái. Tương tự xét cho một chú kiến bất kỳ trong đoàn ta thấy không quá 1 h tất cả sẽ rơi xuống đất.
PB xin phép đưa thêm câu hỏi phụ, trong trường hợp có đụng độ hỏi có tối đa bao nhiêu đụng độ có thể xảy ra
?
Bác Văn cấp cho mỗi con kiến một cái mũ đánh số từ 1 đến mười. Khi hai con kiến đụng độ nhau, thay vì đổi hướng, hai con kiến sẽ đổi mũ cho nhau. Trong bài toán mới này, hiển nhiên sau một giờ, cả mười con Kiến đều rơi vào mồm bác Văn đã há sẵn. Nếu có đo đạc trước, bác Văn còn có thể há mồm đúng lúc chúng rụng, khỏi bị bệnh há miệng mắc quai. Bài toán này dễ hơn bài cũ vì kiến chỉ đổi mũ, không đổi hướng. Để tìm lại bài cũ, ta chỉ cần xác định hoán vị đổi mũ. Hoán vị này còn được phân tích thành tích của các chuyển vị (transposition) tương ứng với các vụ đụng độ. Độ dài tối đa của một hoán vị là n(n-1)/2 trong trường hợp có n con kiến. Nhưng trong bài toán này, vì có một số kiến đi sang phải, một số đi sang trái, trong mỗi nhóm không chuyển vị với nhau, nên số lần đụng độ tối đa sẽ là $latex n^2/4$ nếu số kiến n là chẵn, và $latex (n^2-1)/4$ nếu n lẻ. Bác Văn thì không quan tâm lắm đến hoán vị, miễn là cả đàn kiến chui vào mồm là được.
90:
Tối thiều là tồng chiều dài của 10 con kiến (m) chia cho 1 (h) .
Ví dụ: chiều dài một con kiến ~ 0.001 (m) x 10 con kiến ~ 0.01 (m) / 1 h ~ 0.01 (h).
Tối đa là gần một giờ ~ 1 (h).
@Duy: độ dài các con kiến bằng … 0
@Pandabear & Hòa Thượng: câu trả lời của PB và bác Hòa Thượng dĩ nhiên là chính xác. Quan sát mấu chốt là chỉ cần đổi tên kiến khi 2 con đụng nhau.
Câu hỏi thêm rất hay của PB thì Hòa Thượng đã cho câu trả lời vừa rất đại số vừa rất tổ hợp, thật thú vị. Cảm ơn!
@Hòa thượng: chắc bác muốn nói “chuyển vị kề” (adjacent transpositions), hay là tôi nhớ thuật ngữ không chuẩn.
@Hưng: độ dài các con kiến có thể xem bằng 0 nếu như cái que dài hơn 1m gấp nhiều lần. Vì có nhiều loại kiến mà chiều dài của nó có thể lên đến 3-5cm!
http://www.bbc.co.uk/nature/wildfacts/factfiles/3086.shtml
Kiến ở New England này trung bình là 1cm
91: Lý thuyết thì dễ nhưng thực tế thì khó hơn nhiều khi mà chiều dài của chuỗi tăng lên đáng kể.
Có một bài tương tự trên TopCoder cách đây vài năm (StringSearch)
http://www.topcoder.com/longcontest/?module=ViewProblemStatement&rd=9958&pm=6164
Có nhiều lời giải thực tế (practical approaches) thảo lụân khá hay:
http://forums.topcoder.com/?module=Thread&threadID=510371&start=0
Cảm ơn anh Duy cho mấy cái links về bài String Search rất hay.
92. Neu dung` loai xe freestyle, truc banh xe truoc co the vuong goc voi truc than xe. Dieu nay tao ra vet xe banh truoc la 1 vong tron va banh sau la mot diem. Vay it’ nhat thi dien tich can tim phai phu thuoc vao khoang cach cua 2 cai tam cua 2 banh xe –> phu thuoc vao` khung cua xe dap.
ở đây có rất nhiều bài toán/lời giải để practice. xin lỗi vì nó ko liên quan gì đến 3 bài toán ở trên
http://code.google.com/codejam/
Theo tôi thì bài toán 91 là bài toán classical được biết đến với tên gọi là Longest Common Subsequence có thể Google để tìm thấy một số tài liệu nói về độ phức tạp của bài toán này và phương pháp dynamic programming để giải nó. Tôi thích bài toán 90 nhất vì nó phù hợp với các cuộc phỏng vấn kiểm tra trí tuệ hơn là kiến thức.