Recentemente ho partecipato a Microsoft Interview.Come implementare l'elenco collegato con 1 milione di nodi?
Mi è stato chiesto di implementare l'elenco collegato con 1 milione di nodi? Come accederai al 999999 nodo?
Qual è la strategia di progettazione ottimale e l'implementazione per tale domanda?
Una lista concatenata ha poche varianti, perché molta variazione significa che sarebbe qualcosa di diverso da una lista collegata.
È possibile modificarlo con collegamenti singoli o doppi. Il collegamento singolo è il punto in cui si ha un puntatore alla testa (il primo nodo, A dire) che punta a B che punta a C, ecc. Per trasformarlo in un doppio elenco collegato si aggiunge anche un collegamento da C a B e B A.
Se si dispone di un doppio elenco collegato, è significativo mantenere un puntatore alla coda dell'elenco (l'ultimo nodo) e alla testa, il che significa che l'accesso all'ultimo elemento è economico e gli elementi vicini alla fine sono più economici, perché puoi lavorare a ritroso o in avanti ... MA ... dovresti sapere cosa vuoi alla fine della lista ... E alla fine della giornata una lista collegata è ancora solo quella, e se diventerà molto grande e questo è un problema a causa della natura del suo caso d'uso, probabilmente dovrebbe essere scelta una struttura di archiviazione diversa da una lista collegata.
Ovviamente è possibile ibridare l'elenco collegato, quindi è possibile indicizzarlo o qualcosa, ad esempio, e in teoria non c'è nulla di male, ma se si indicizzano TUTTI i nodi, la natura dell'elenco collegato non ha più molto valore e se indicizzi solo alcuni, allora i nodi tra i nodi indicizzati devono essere ordinati o qualcosa in modo da poter trovare un nodo vicino e lavorare verso un nodo di destinazione ... probabilmente questo non sarebbe mai ottimale e una migliore struttura di dati dovrebbe essere scelto.
In realtà è necessario utilizzare un elenco collegato quando non si desidera eseguire operazioni come ottenere un nodo specifico, ma si desidera eseguire l'iterazione dei nodi indipendentemente.
E probabilmente questo tipo di ragionamento era quello che l'intervistatore si aspettava, più di una chiara soluzione al problema – Trompa
Sono d'accordo, ho intervistato molte persone e non riesco a pensare a nessun altro tipo di risposta Potevo aspettarmi da un candidato, dovevo chiedere loro una domanda del genere. – Michael
Vale anche la pena menzionare Skip List se si sta tentando di mantenere gli articoli memorizzati in ordine (ordine ordinato, ordine di inserimento, ecc.), Che è spesso il caso di serie di dati molto grandi. Gli SkipList sono come liste concatenate ma sono multi-livello con i livelli più alti che saltano metà dei nodi (in media) rispetto alla lista concatenata di livello inferiore. – Tuxdude
ho idea di quello che sto per dire, ma, ecco qui:
Si potrebbe conceptually dividere la lista in sqrt(1000000)blocchi, in modo tale che si avrebbe "puntatori di riferimento" ogni 1000 elementi.
Si consideri come con 1000 linked lists ciascuno con 1000 elements che rappresenta il proprio elenco con 1000000 elements.
Questo è quello che viene in mente!
Generalizza questo concetto e ottieni un [elenco salti] (https://en.wikipedia.org/wiki/Skip_list). –
Fantastico !! Non sapevo questo :) –
Come Michael ha detto che dovresti presentare prima le due varianti classiche dell'elenco collegato. La prossima cosa che dovresti fare è chiedere degli schemi di inserimento, ricerca e cancellazione.
Questi motivi ti guideranno verso una struttura dati più adatta, perché nessuno desidera un elenco semplice o doppio con un milione di nodi.
Non posso fare a meno di pensare immediatamente "dipende, perché?". Non rispondere a questo in un'intervista, però. Ad ogni modo, stai chiedendo una soluzione "ottimale", quindi ... Dipende. Per un'intervista, è molto più una scommessa per ciò che l'intervistatore si aspetta per la posizione, piuttosto che un problema SO ... –
Probabilmente mi interromperò l'uso di una lista collegata per una raccolta di un milione di nodi e non riuscirò a colloquio perché questo è Microsoft stiamo parlando.detto che il caso peggiore dell'elenco adiacente quando si implementa un grafico è un singolo elenco collegato – UmNyobe