Các câu hỏi phỏng vấn [14]
- Có bao nhiêu số nguyên tố có dạng thập phân hoán chuyển giữa 0 và 1, bắt đầu và kết thúc bằng 1 (nghĩa là dạng 1010…101)?
- Có n người, mỗi người có một bí mật riêng. Họ gọi điện thoại lẫn nhau, mỗi lần gọi thì hai đối tượng trao đổi tất cả các bí mật mà hai đối tượng biết. Cần ít nhất bao nhiêu cuộc gọi để mọi người biết mọi bí mật?
- Tìm số nguyên có dạng ABCDEFGHIJ, trong đó A là tổng số chữ số 0 trong số nguyên này, B là tổng số chữ số 1, vân vân.
Chủ đề : Dành cho du học sinh, Vui - Giải Trí. Bookmark the
permalink. Trackbacks are closed, but you can .
4 Comments
Anh Hưng, em nghĩ câu số 41 thì chính là thuật toán Breadth-First Search, cũng chính là cách mà Distance Vector routing protocol áp dụng. Thuật toán (chưa optimized) này dừng trong O(diameter) rounds và số lượng message là O(diameter * E) với E là tổng số cạnh. Ở đây nếu giả sử tất cả liên thông thì E = n * (n – 1) / 2.
41. Em chưa có nhiều kiến thức về mấy cái thuật toán nên mấy cái twoask nói em ko hiểu, chỉ biết đó là đồ thị thôi
. Không biết E=n*(n-1)/2 có phải là số lượng cuộc gọi ít nhất của cái anh nói ko? Em có nghĩ cách nói chuyện nói theo kiểu vòng tròn, như thế số lượng cuộc gọi là 2n-3.
Bài này hao hao như distance vector routing, nhưng không phải. Nó gọi là bài toán gossip (gossip problem), đã được giải độc lập bởi nhiều người (ít nhất 5 bài báo khác nhau) từ hồi thập niên 70. Câu trả lời là f(1)=0, f(2)=1, f(3)=3, và f(n)=2n-4 với n>=4. Tìm cách đạt được 2n-4 không khó, chứng minh 2n-4 là cách tốt nhất thì khó hơn một chút, nhưng cũng không phải quá đáng, có thể dùng làm bài tập lớp graph theory.
42. Đó là số 6210001000.