Intervista: il people corrispondenti

Question

ho visto questa domanda intervista di recente per una ditta che ha detto:

Gruppo di persone, è possibile chiamare Know(i, j) per chiedere se i ° persona sa j °, il valore di ritorno è true (i conosce j) o false (i non sa j). Trova la persona che tutti gli conoscono, ma non conosce nessuno.

Posso pensare a un'implementazione di O(N^2) in modo da abbinare ogni persona con il metodo a ogni altra persona, eliminando chiunque conosca davvero qualcuno. Non riesco tuttavia a pensare a un'implementazione più veloce di questa.

Qualcuno può aiutare o dare suggerimenti?

Answer 1

Possiamo farlo in tempo lineare con un semplice algoritmo. In due ricerche, possiamo eliminare almeno un candidato: scegliere due persone e rimuovere la persona i con Know(i,j) o ~Know(j,i).

Answer 2

Tutto ciò che dobbiamo fare è -

1. trovare una persona che non conosce nessun altro
2. e quindi controllare tutti sanno che persona

Fase 1: Trova fuori una persona che non conosce nessun altro. Inizialmente ognuno è il nostro candidato. Quindi iniziamo con uno qualsiasi come nodo corrente. Iterate su tutti i candidati j. Se Knows (i, j) è falso. Quindi j non può essere il nostro candidato. Quindi rimuovi j dai candidati. Se Knows (i, j) è vero per qualsiasi j, quindi non posso essere il nostro candidato, quindi il nodo corrente verrà aggiornato a j e rimuoverà il nodo i. Ripeti fino a quando non possiamo aggiornare il nodo corrente. L'ultimo nodo corrente è il nostro candidato finale. Questo sarà in realtà O (N) perché ad ogni passo stiamo effettivamente rimuovendo un nodo, io o j.

Passaggio 2: Abbiamo trovato una persona che non conosce nessun altro. Ma dobbiamo verificare che tutti gli altri lo conoscano. Quello che possiamo fare è iterare su tutti i nodi e controllare, che è O (N). Se abbiamo scoperto che questo non è il nostro nodo, allora non esiste una soluzione del genere. Perché non può esserci un altro nodo k, che è la soluzione, poiché non lo so k.

Possiamo utilizzare un elenco di collegamenti per memorizzare l'elenco di candidati in modo che la rimozione di un candidato sia 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 

scorso (wo) man in piedi è la soluzione ....

Se le strutture di dati in uso non rendono chiaro come a "rimuovere" un candidato, un ciclo su un array può essere utilizzato:

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