Các câu hỏi phỏng vấn [13]
Ngô Quang Hưng | 31 tháng 05, 2006 | 
Bản để in
Một sinh viên của tôi vừa phỏng vấn với Google và Yahoo. Ba câu hỏi sau đây còn “nóng hổi”:
- Cho một linked list (danh sách liên kết) và pointer đến đầu linked list. Ta không biết trước tổng số phần tử trong list là bao nhiêu. Viết một function trả về pointer đến một phần tử ngẫu nhiên trong list (uniform distribution), mà chỉ được duyệt qua linked list 1 lần. (Nghĩa là không được đếm tổng số phần tử n, chọn ngẫu nhiên từ 1 đến n, rồi duyệt lần 2 để trả về con trỏ ngẫu nhiên.)
- Cho một array A các ký tự trong một bộ ký tự nào đó, và một tập S của vài ký tự. Viết một function chạy trong thời gian tuyến tính, trả về sub-array nhỏ nhất của A chứa tất cả các ký tự trong S.
- Cho một ma trận m hàng n cột. Các con số trên các hàng đều tăng dần từ trái sang phải, và trên các cột đều tăng dần từ trên xuống dưới. Viết một thủ tục tìm một số xem nó có trong ma trận không? Thời gian chạy là bao nhiêu? (Lưu ý: đây là phiên bản 2-D của binary search.)
37. Đi từ đầu danh sách, lưu lại phần tử đầu tiên làm kết quả tạm thời. Đi đến phần tử thứ 2 và chọn phần tử này làm kết quả với xác suất 1/2… Tại phần tử thứ i chọn phần tử này với xác suất làm kết quả với xác suất 1/i.
Giả sử danh sách có n phần tử, xác suất để phần tử thứ i được chọn sẽ là 1/i * i/(i+1) * … * (n-1)/n = 1/n
38. Với mỗi i ( 1
Các bạn đọc lại cái này khi post lời bình. Có vẻ post của bạn resvictory bị cắt.
Em xin được post lại phần bị cắt:
38. Với mỗi i ( 1<= i <= n = length(A) ) gọi f(i) là giá trị nhỏ nhất thoả mãn đoạn A[i..f(i)] chứa S (trường hợp A[i..n] không chứa S ta coi f(i) = infinity). Ta thấy f(1) <= f(2) <= … f(n). Để giải bài toán trong thời gian tuyến tính ta quét A từ trái qua phải:
(1)best = infinity;
(2)for i = 1 to n do
(3){
(4) f(i) = f(i-1);
(5) while ( A[ i..f(i) ] chưa chứa S) f(i)++;
(6) best = min( best, f(i) - i + 1);
(7)}
Việc kiểm tra tại (5) được thực hiện bằng một mảng đánh dấu để đảm bảo độ phức tạp O(n).
39. Thực hiện tìm kiếm trong 2-D sorted array có thể được thực hiện trong thời gian O(m + n).
Gọi ma trận cần tìm là a(i, j). Thực hiện tìm kiếm từ dưới lên trên (i giảm dần) và từ trái qua phải j tăng dần.
bool search(k) {
j = 1;
for i=m to 1 do {
while (a[i,j] < k) j++;
if ( a[i, j] = k)
return true;
}
return false
}
Hình như vẫn còn khoảng trống. Để tôi sửa lại xem sao. Đúng rồi, khi dùng & #60; thay cho < đừng để khoảng trống giữa & và #60;
Câu số 39 độ phức tạp là O (logm + logn) thui. Làm tương tự như binary search trên mảng 1 chiều:
[code]
bool search (value, r1, c1, r2, c2) {
if (r1 > r2 || c1 > c2) return false;
r_mid = (r1 + r2 + 1) / 2;
c_mid = (c1 + c2 + 1) / 2;
if (A [r_mid][c_mid] == value) return true;
if (A [r_mid][c_mid]
Câu số 39 độ phức tạp là O (logm + logn) thui. Làm tương tự như binary search trên mảng 1 chiều:
bool search (value, r1, c1, r2, c2) {
if (r1 > r2 || c1 > c2) return false;
r_mid = (r1 + r2 + 1) / 2;
c_mid = (c1 + c2 + 1) / 2;
if (A [r_mid][c_mid] == value) return true;
if (value > A [r_mid][c_mid])
return
search (value, r_mid + 1, c1, r2, c_mid) ||
search (value, r1, c_mid + 1, r_mid, c2) ||
search (value, r_mid + 1, c_mid + 1, r2, c2);
else
return
search (value, r_mid, c1, r2, c_mid - 1) ||
search (value, r1, c_mid, r_mid - 1, c2) ||
search (value, r1, c1, r_mid, c_mid);
}
(ủa, cái này ko có preview ạ ?)
hic, hi vọng lần này ko bị lỗi nữa :-w
1. Good idea, to^i se~ ti`m mo^.t comment preview plugin. DDi.nh update le^n Wordpress 2.0.3 ma` chu+a co’ tho+`i gian
2. Thay vi` [code], ba.n du`ng <code> … </code>