Phỏng vấn: trên dân Matching

Question

Tôi thấy câu hỏi phỏng vấn này thời gian gần đây cho một công ty mà nói:

Nhóm của mọi người, bạn có thể gọi Know(i, j) hỏi nếu i người thứ biết thứ j, giá trị trả về là true (i biết j) hoặc false (i không biết j). Tìm người mà mọi người khác biết anh ta nhưng anh ấy không biết ai cả.

Tôi có thể nghĩ đến việc triển khai O(N^2) sao cho bạn vừa đối sánh mọi người với phương pháp với mọi người khác, loại bỏ bất kỳ ai thực sự biết ai đó. Tuy nhiên tôi không thể nghĩ ra việc triển khai nhanh hơn thế này.

Có ai có thể giúp hoặc đưa ra gợi ý không?

Answer 1

Chúng ta có thể làm điều này theo thời gian tuyến tính với một thuật toán đơn giản. Trong hai lần tra cứu, chúng tôi có thể loại bỏ ít nhất một ứng cử viên - chọn hai người và xóa người i với Know(i,j) hoặc ~Know(j,i).

Answer 2

Tất cả chúng ta phải làm là -

1. Tìm hiểu một người không biết bất cứ ai khác
2. Và sau đó kiểm tra mọi người đều biết người đó

Bước 1: Tìm ra một người không biết ai khác. Ban đầu mỗi người là ứng viên của chúng tôi. Vì vậy, hãy bắt đầu với bất kỳ một i như nút hiện tại. Lặp lại tất cả các ứng cử viên j. Nếu Knows (i, j) là false. Sau đó, j không thể là ứng cử viên của chúng tôi. Vì vậy, loại bỏ j từ các ứng cử viên. Nếu Knows (i, j) là true cho bất kỳ j, thì tôi không thể là ứng cử viên của chúng ta, do đó, nút hiện tại sẽ được cập nhật thành j và loại bỏ nút i. Lặp lại điều này cho đến khi chúng tôi không thể cập nhật nút hiện tại. Nút hiện tại cuối cùng là ứng cử viên cuối cùng của chúng tôi. Điều này sẽ thực sự là O (N) vì tại mỗi bước chúng ta thực sự loại bỏ một nút, hoặc là i hoặc j.

Bước 2: Chúng tôi đã tìm thấy một người không biết bất kỳ ai khác. Nhưng chúng tôi phải xác minh rằng mọi người đều biết anh ấy. Những gì chúng ta có thể làm là lặp qua tất cả các nút và kiểm tra, đó là O (N). Nếu chúng tôi thấy rằng đây không phải là nút của chúng tôi, thì không có giải pháp nào như vậy. Bởi vì không thể có một nút k khác, đó là giải pháp, vì tôi không biết k.

Chúng tôi có thể sử dụng danh sách liên kết để lưu trữ danh sách ứng cử viên để xóa ứng viên sẽ là O (1).

Answer 3

while there are at least two candidate people remaining: 
    if Know(i, j) then 
     i is not the solution - remove from list of candidates 
    else 
     j is not the solution - remove from list of candidates 

cuối cùng (wo) người đàn ông đứng sự là giải pháp ....

Nếu cấu trúc dữ liệu được sử dụng không làm cho nó rõ ràng làm thế nào để "loại bỏ" một ứng cử viên, một vòng trên một mảng có thể được sử dụng:

int candidate = 0; 
for (int i = 1; i < n; ++i) 
    if (know(candidate, i)) 
     candidate = i; 
// candidate now holds the solution...