Các câu hỏi phỏng vấn [1]
Ngô Quang Hưng | 23 tháng 06, 2005 | 
Bản để in
Microsoft nổi tiếng là có các câu hỏi phỏng vấn nhân viên mới mang tính kỹ thuật theo dạng đố “mẹo” (đa số là về thuật toán hoặc lập trình C/C++). Có nhiều bộ sưu tập các câu hỏi dạng này đã từng được hỏi ở các cuộc phỏng vấn ở Microsoft. Gần đây Google cũng phỏng vấn theo kiểu tương tự. Mỗi câu trả lời chỉ được cho khoảng 5-10 phút suy nghĩ. Đôi khi người ta quan tâm đến quá trình suy nghĩ của bạn hơn là bản thân câu trả lời.
Trong chuỗi bài này tôi sẽ nêu chọn lọc một số câu hỏi tôi thích nhất. Các câu hỏi được chọn không nhất thiết là khó nhất, tiêu chuẩn là gọn gàng và đẹp.
- Cho một danh sách liên kết đơn (simple linked list) hữu hạn. Có hai trường hợp: một là cuối danh sách trỏ về NULL, hai là trỏ về một phần tử đã gặp - tạo nên một vòng tròn trong danh sách.
Ví dụ trường hợp 1: A –> B –> C –> D –> NULL.
Ví dụ trường hợp 2: A –> B –> C –> D –> E –> F –> C.
Cho trước một con trỏ vào một danh sách liên kết đơn L nào đó, hữu hạn nhưng có thể có độ dài tùy ý. Làm thế nào để kiểm tra nhanh nhất nếu danh sách L thuộc trường hợp 1 hay trường hợp 2, với điều kiện là ta chỉ được dùng vài chục bytes bộ nhớ. - Cho một chuỗi ký tự s bao gồm nhiều từ. Viết một đoạn chương trình C đảo thứ tự các từ.
Ví dụ: với input là “this is a nice blog” thì output là “blog nice a is this“. - Cho hai dãy số đã xếp thứ tự tăng dần A và B, mỗi dãy có n phần tử. Xét tập hợp sau:
S = { A[i] + B[j] | 1 < = i, j <= n }.Chú ý rằng S có thể có đến n2 phần tử. Viết một chương trình in ra n số lớn nhất trong S. Chương trình phải chạy trong thời gian O(n).
Hôm nay em được biết đến các câu hỏi phỏng vấn này, suy nghĩ mãi xin nêu ra cách giải tạm chấp nhận được cho bài 1:
Lưu lại vị trí bắt đầu Linked List, sau đó duyệt list, khi duyệt tới node nào thì đảo chiều liên kết của nó lại: A->B thì B->A
nếu node của chúng ta là null –> Linked List loại 1
nếu node của chúng ta trở về vị trí bắt đầu: Linked List loại 2, lúc này ta lại duyệt Linked List 1 lần nữa theo cách duyệt như vậy sẽ cho trở lại Linked List ban đầu
Mong anh Hưng và các bạn chỉ bảo cách nhanh nhất để thực hiện yêu cầu trên
Chào Hùng,
Cách giải rất hay! Về asymptotic thì không có cách nào nhanh hơn (đều cần O(n) bước). Nhưng, có cách không cần phải “sửa” bất kỳ link nào trong link list cả.