Intervista Google: trova la distanza pazzesca tra le stringhe

Question

Questa domanda mi è stata posta nell'intervista di Google. Potrei farlo O (n * n) ... Posso farlo in tempo migliore. Una stringa può essere costituito solo da 1 e 0.

Definizione:

X & Y sono stringhe formato da 0 o 1

D(X,Y) = Rimuovere le cose comuni all'inizio sia X & Y Quindi aggiungere le lunghezze rimanenti da entrambe le corde.

Ad es.

D(1111, 1000) = Solo il primo alfabeto è comune. Quindi la stringa rimanente è 111 & 000. Quindi il risultato length("111") & length("000") = 3 + 3 = 6

D(101, 1100) Solo = primi due alfabeti sono comuni. Quindi la stringa rimanente è 01 & 100. Quindi il risultato è length("01")length("100") = 2 + 3 = 5

È abbastanza ovvio che scoprire una distanza così folle sarà lineare. O (m).

Ora la domanda è

data di ingresso n, dicono come

1111 
1000 
101 
1100 

Ottieni la massima distanza possibile pazza.

n è il numero di stringhe di input. m è la lunghezza massima di qualsiasi stringa di input.

La soluzione di O (n * m) è piuttosto semplice. Può essere fatto in un modo migliore? Supponiamo che m sia corretto. Possiamo farlo in meglio di O (n^2)?

Answer 1

Mettere le stringhe su un albero, dove 0 significa andare a sinistra e 1 significa andare a destra. Così, per esempio

1111 
1000 
101 
1100 

si tradurrebbe in un albero come

 Root 
      1 
      0  1 
     0 1* 0 1 
     0* 0* 1* 

in cui si intende il * che un elemento finisce lì. La costruzione di questo albero richiede chiaramente lo O(n m).

Ora dobbiamo trovare lo diameter of the tree (il percorso più lungo tra due nodi, che è la stessa cosa della "distanza folle"). L'algoritmo ottimizzato presentato lì colpisce ogni nodo nell'albero una volta. Ci sono al massimo min(n m, 2^m) tali nodi.

Quindi se n m < 2^m, l'algoritmo è O(n m).

Se n m > 2^m (e abbiamo necessariamente input ripetuti), l'algoritmo è ancora O(n m) dal primo passaggio.

Questo funziona anche per le stringhe con un alfabeto generale; per un alfabeto con le lettere k creare un albero-albero k, nel qual caso il runtime è ancora O (n m) con lo stesso ragionamento, anche se richiede una quantità di memoria pari a k volte.

Answer 2

Penso che sia possibile in O (nm) tempo creando un albero binario dove ogni bit in una stringa codifica il percorso (0 a sinistra, 1 a destra). Quindi trovare la massima distanza tra i nodi dell'albero which can be done in O(n) time.

Answer 3

Questa è la mia soluzione, penso che funziona:

1. Creare un albero binario da tutte le stringhe. L'albero sarà costruito in questo modo: ad ogni giro, selezionare una stringa e aggiungerla all'albero. così per il tuo esempio, l'albero sarà:

       <root> 
         <1>   <empty> 
   <1>   <0> 
   

   < 1> < 0> < 1> < 0> < 1> < 0> < 0>

Così ogni percorso da la radice di una foglia rappresenterà una stringa.

1. Ora la distanza tra le due foglie corrisponde alla distanza tra due corde. Per trovare la distanza folle, devi trovare il diametro di questo grafico, che puoi farlo facilmente con dfs o bfs.

La complessità totale di questo algoritmo è: O (n * m) + O (n * m) = O (n * m).

Answer 4

Per ottenere una risposta in O (nm) basta scorrere i caratteri di tutte le stringhe (questa è un'operazione O (n)). Confronteremo al massimo m caratteri, quindi questo sarà fatto O (m). Questo dà un totale di O (nm). Ecco una soluzione C++:

int max_distance(char** strings, int numstrings, int &distance) { 
    distance = 0; 
    // loop O(n) for initialization 
    for (int i=0; i<numstrings; i++) 
     distance += strlen(strings[i]); 

    int max_prefix = 0; 
    bool done = false; 
    // loop max O(m) 
    while (!done) { 
     int c = -1; 
     // loop O(n) 
     for (int i=0; i<numstrings; i++) { 
      if (strings[i][max_prefix] == 0) { 
       done = true; // it is enough to reach the end of one string to be done 
       break; 
      } 

      int new_element = strings[i][max_prefix] - '0'; 
      if (-1 == c) 
       c = new_element; 
      else { 
       if (c != new_element) { 
        done = true; // mismatch 
        break; 
       } 
      } 
     } 
     if (!done) { 
      max_prefix++; 
      distance -= numstrings; 
     } 
    } 

    return max_prefix; 
} 


void test_misc() { 
    char* strings[] = { 
     "10100", 
     "10101110", 
     "101011", 
     "101" 
    }; 

    std::cout << std::endl; 
    int distance = 0; 
    std::cout << "max_prefix = " << max_distance(strings, sizeof(strings)/sizeof(strings[0]), distance) << std::endl; 
} 

Answer 5

Penso che questo problema è qualcosa di simile a "trovare prefisso per due stringhe", è possibile utilizzare trie (http://en.wikipedia.org/wiki/Trie) per accerlate ricerca

Ho un colloquio telefonico google 3 giorni prima , ma forse non sono riuscito ...

Miglior fortuna a voi

Answer 6

Non certo perché uso alberi quando iterazione ti dà la stessa grande O complessità computazionale, senza la complessità del codice. comunque qui è la mia versione di esso in javascript O (mn)

var len = process.argv.length -2; // in node first 2 arguments are node and program file 
var input = process.argv.splice(2); 
var current; 
var currentCount = 0; 
var currentCharLoc = 0; 
var totalCount = 0; 
var totalComplete = 0; 
var same = true; 
while (totalComplete < len) { 
     current = null; 
     currentCount = 0; 
     for (var loc = 0 ; loc < len ; loc++) { 
       if (input[loc].length === currentCharLoc) { 
         totalComplete++; 
         same = false; 
       } else if (input[loc].length > currentCharLoc) { 
         currentCount++; 
         if (same) { 
           if (current === null) { 
             current = input[loc][currentCharLoc]; 
           } else { 
             if (current !== input[loc][currentCharLoc]) { 
               same = false; 
             } 
           } 
         } 
       } 
     } 
     if (!same) { 
       totalCount += currentCount; 
     } 
     currentCharLoc++; 
} 

console.log(totalCount);