Интервью: о людях, соответствующих

Question

Я недавно видел этот вопрос для фирмы, которая сказала:

Группа людей, вы можете позвонить Know(i, j) и спросить, знает ли i th человек j th, возвращаемое значение true (i знает j) или false (i не знает j). Найдите человека, которого все остальные знают, но он никого не знает.

Я могу представить себе реализацию O(N^2), в которой вы просто сопоставляете каждого человека с методом с любым другим человеком, исключая любого, кто действительно кого-то знает. Однако я не могу придумать более быстрой реализации, чем эта.

Может кто-нибудь помочь или дать подсказки?

Answer 1

Мы можем сделать это за линейное время с помощью простого алгоритма. В двух поисках мы можем исключить хотя бы одного кандидата - выбрать двух человек и удалить человека i с помощью Know(i,j) или ~Know(j,i).

Answer 2

Все, что нам нужно сделать, это -

1. Узнайте человека, который никого не знает
2. А затем проверьте, что все знают этого человека

Шаг 1: Найдите человека, который больше никого не знает. Изначально каждый является нашим кандидатом. Итак, давайте начнем с любого я в качестве текущего узла. Перебрать всех кандидатов j. Если Знает (я, J) является ложным. Тогда j не может быть нашим кандидатом. Так что уберите j из кандидатов. Если Knows (i, j) имеет значение true для любого j, то я не могу быть нашим кандидатом, поэтому текущий узел будет обновлен до j, и удалит узел i. Повторяйте это, пока мы не сможем обновить текущий узел. Последний текущий узел - наш последний кандидат. Это будет фактически O (N), потому что на каждом шаге мы фактически удаляем один узел, i или j.

Шаг 2: Мы нашли человека, который больше никого не знает. Но мы должны убедиться, что все его знают. Что мы можем просто сделать, так это перебрать все узлы и проверить, что O (N). Если мы обнаружили, что это не наш узел, то такого решения не существует. Потому что не может быть другого узла k, который является решением, так как я не знаю k.

Мы можем использовать список ссылок для хранения списка кандидатов, так что удаление кандидата будет 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

последний (горе) человек, стоящий - это решение ....

Если используемые структуры данных не дают понять, как «удалить» кандидата, можно использовать цикл над массивом:

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