Esplorazione di domande e risposte da un colloquio di lavoro per una posizione di sviluppatore Java. Parte 9

Essere un programmatore non è facile. C'è sempre qualcosa di nuovo da imparare. E, come in ogni altra impresa, la cosa più difficile è iniziare, fare il primo passo verso il proprio obiettivo. Ma poiché sei già qui e stai leggendo questo articolo, hai completato il primo passaggio. Ciò significa che ora devi muoverti deliberatamente verso il tuo obiettivo, senza rallentare o deviare di lato. Presumo che il tuo obiettivo sia diventare uno sviluppatore Java o rafforzare le tue conoscenze se sei già uno sviluppatore. Se è così, continuiamo ad affrontare un ampio elenco di domande sul colloquio per sviluppatori Java. Continuiamo!

Collezioni

84. Parlaci degli iteratori e di come vengono utilizzati

Le raccolte sono l'argomento preferito in qualsiasi intervista agli sviluppatori Java. Quando rispondono alle domande sulla gerarchia della raccolta, i candidati spesso dicono che tutto inizia con l' interfaccia della raccolta . Ma non è così. C'è un'altra interfaccia un livello sopra: Iterable . Questa interfaccia è costituita dal metodo iterator() , che consente di accedere all'oggetto Iterator per la raccolta corrente. E cos'è esattamente questo oggetto Iterator ? L' oggetto Iterator offre la possibilità di spostarsi all'interno di una raccolta ed eseguire l'iterazione sui suoi elementi e non è necessario che l'utente conosca i dettagli di implementazione specifici della raccolta. In altre parole, è una sorta di puntatore agli elementi della collezione, come se si sbirciasse all'interno di uno di essi. L'iteratore ha metodi come:

• hasNext() — restituisce true se l'iterazione ha un altro elemento (questo metodo ti consente di sapere quando hai raggiunto la fine della raccolta);

• next() — restituisce l'elemento successivo nell'iterazione. Se non ce n'è uno, viene lanciata una NoSuchElementException . Ciò significa che prima di utilizzare questo metodo, è meglio utilizzare il metodo hasNext() per assicurarsi che esista un elemento successivo;

• rimuovi() — rimuove dalla raccolta l'ultimo elemento ricevuto utilizzando il metodo next() . Se next() non è mai stato chiamato, la chiamata a delete() causerà la generazione di un'eccezione IllegalStateException ;

• forEachRemaining(<Consumer>) — esegue l'azione passata su ciascun elemento della raccolta (questo metodo è apparso in Java 8).

Ecco un piccolo esempio di iterazione di un elenco e rimozione di tutti i suoi elementi utilizzando i vari metodi di iterazione che abbiamo esaminato:

List<String> list = new ArrayList<>();
list.add("Hello ");
list.add("World, ");
list.add("It's ");
list.add("Amigo!");
Iterator iterator = list.iterator();
 
while(iterator.hasNext()) {
   iterator.next();
   iterator.remove();
}
System.out.println(list.size());

La console visualizzerà quanto segue: Ciò significa che gli elementi sono stati rimossi con successo. Una volta ottenuto un iteratore, puoi utilizzare un metodo per visualizzare tutti gli elementi sullo schermo:

iterator.forEachRemaining(x -> System.out.print(x));

Ma una volta fatto questo, l'iteratore diventa inadatto per un ulteriore utilizzo: ha attraversato l'intero elenco e un iteratore ordinario non ha metodi per eseguire l'iterazione all'indietro. E questo costituisce un bel passaggio alla discussione su LinkedList , in particolare sul suo metodo listIterator() , che restituisce un tipo avanzato di iteratore: ListIterator . Oltre ai metodi di un iteratore regolare (standard), questo tipo ha quanto segue:

• add(<Element>) — aggiunge un nuovo elemento alla lista;

• hasPrevious() — restituisce true se c'è un elemento situato prima dell'elemento successivo (se c'è un elemento precedente);

• nextIndex() — restituisce l'indice dell'elemento successivo;

• previous() — restituisce l'elemento precedente (quello prima dell'elemento successivo);

• previousIndex restituisce l'indice dell'elemento precedente.

• set(<Element>) — sostituisce l'ultimo elemento restituito da next() o previous() .

Come puoi vedere, questo iteratore ha funzionalità molto più interessanti: ti consente di camminare in entrambe le direzioni e offre una notevole libertà quando lavori con gli elementi. Dovresti anche sapere che quando le persone parlano di iteratori, a volte intendono il modello di progettazione stesso.

85. Quale gerarchia di raccolte esiste nel Java Collection Framework?

Esistono due gerarchie di raccolte in Java. La prima gerarchia è la gerarchia della Collezione, che ha la seguente struttura: È divisa nelle seguenti sottoraccolte:

• Set è un'interfaccia che descrive un set, una struttura dati che contiene elementi univoci (non ripetitivi) non ordinati. Questa interfaccia ha alcune implementazioni standard: TreeSet , HashSet e LinkedHashSet .

• List è un'interfaccia che descrive una struttura dati che memorizza una sequenza ordinata di oggetti. Gli oggetti in un elenco possono essere inseriti e rimossi tramite il loro indice nell'elenco (come un array, ma con ridimensionamento dinamico). Questa interfaccia ha anche alcune implementazioni standard: ArrayList , Vector ( deprecato e non attualmente utilizzato ) e LinkedList .

• La coda è un'interfaccia che descrive una struttura dati che memorizza gli elementi in una coda FIFO (First In First Out) . Questa interfaccia ha le seguenti implementazioni standard: LinkedList (esatto, implementa anche Queue ) e PriotityQueue .

La seconda gerarchia di raccolte è la gerarchia Map , che ha la seguente struttura: Questa gerarchia di raccolte non ha divisioni in sottoraccolte (poiché la gerarchia Map stessa è una sorta di sottoraccolta che si distingue da sola). Le implementazioni standard della mappa sono Hashtable (deprecato), LinkedHashMap e TreeMap . In pratica, quando le persone chiedono informazioni sulle Collezioni , di solito intendono entrambe le gerarchie.

86. Qual è la struttura interna di un ArrayList?

Un ArrayList è come un array, ma può espandersi dinamicamente. Che cosa significa? Dietro le quinte, ArrayList utilizza un array ordinario, ovvero memorizza i suoi elementi in un array interno la cui dimensione predefinita è 10 celle. Una volta che l'array interno è pieno, viene creato un nuovo array. La dimensione del nuovo array è determinata da questa formula:

 <size of the current array> * 3 / 2 + 1

Quindi, se la dimensione del nostro array è 10, la dimensione di quello nuovo sarà: 10 * 3 / 2 + 1 = 16. Quindi tutti i valori dell'array originale (vecchio) verranno copiati al suo interno utilizzando il metodo integrato System.arraycopy() e l'array originale viene eliminato. In poche parole, è così che ArrayList implementa il ridimensionamento dinamico. Consideriamo i metodi ArrayList più popolari : 1. add(<Element>) — aggiunge un elemento alla fine dell'array (nell'ultima cella vuota), dopo aver prima controllato se c'è una cella disponibile nell'array. In caso contrario, viene creato un nuovo array e gli elementi vengono copiati al suo interno. La complessità temporale di questa operazione è O(1). Esiste un metodo add(<Index>, <Elelement>) simile . Aggiunge un elemento non alla fine dell'elenco (array), ma alla cella specifica indicata dall'indice inserito come argomento. In questo caso, la complessità temporale varierà a seconda di dove aggiungi:

• se l'aggiunta è vicina all'inizio della lista, allora la complessità temporale sarà prossima a O(N), perché tutti gli elementi situati a destra di quello nuovo dovranno essere spostati di una cella a destra;
• se l'elemento è inserito al centro, allora sarà O(N/2), poiché dobbiamo solo spostare metà degli elementi dell'elenco di una cella a destra.

Cioè, la complessità temporale di questo metodo varia da O(1) a O(N), a seconda di dove è inserito l'elemento. 2. set(<Indice>, <Elemento>) — scrive un elemento nella posizione specificata nell'elenco. Se un elemento è già presente in quella posizione, il metodo lo sovrascrive. La complessità temporale di questa operazione è O(1), perché non prevede alcuna operazione di shift: usiamo semplicemente l'indice per calcolare l'indirizzo della cella nell'array, che ha complessità O(1), e poi scriviamo il nuovo elemento . 3. rimuovi(<indice>) — rimuove un elemento in base al suo indice nell'array interno. Quando si rimuove un elemento che non si trova alla fine dell'elenco, tutti gli elementi a destra di quello eliminato devono essere spostati di una cella a sinistra per colmare il vuoto risultante dall'eliminazione. Di conseguenza, la complessità temporale sarà la stessa di add(<Indice>, <Elemento>) quando un elemento viene aggiunto nel mezzo: O(N/2). Dopotutto, devi spostare metà degli elementi di una cella a sinistra. E se parliamo dell'inizio, allora O(N). Oppure se alla fine, allora O(1), poiché non è necessario spostare nulla.

87. Qual è la struttura interna di una LinkedList?

Un ArrayList contiene elementi nell'array interno, ma un LinkedList li memorizza in un elenco doppiamente collegato. Ciò significa che ogni elemento contiene un collegamento all'elemento precedente e all'elemento successivo . Il primo elemento non si collega a un elemento precedente (dopotutto è il primo). È anche considerato l'inizio della lista e l' oggetto LinkedList ha un riferimento diretto ad esso. Allo stesso modo, l'ultimo elemento non ha l'elemento successivo, poiché è la coda della lista. Anche l' oggetto LinkedList fa riferimento direttamente ad esso. Ciò significa che la complessità temporale dell'accesso alla testa o alla coda di una lista è O(1). In ArrayList , se l'elenco cresce, cresce anche l'array interno. Qui tutto è più semplice: aggiungere un riferimento è semplice come cambiare un paio di link. Diamo un'occhiata ad alcuni dei metodi LinkedList più utilizzati : 1. add(<Element>) — aggiunge un elemento alla fine della lista, ovvero dopo l'ultimo elemento (5), verrà aggiunto un collegamento al nuovo elemento come successivo . Il riferimento precedente nel nuovo elemento punterà all'elemento (5) che ora lo precede nell'elenco. La complessità temporale di questa operazione è O(1), poiché abbiamo bisogno solo del collegamento all'ultimo elemento e, come ricorderai, l'oggetto LinkedList ha un riferimento diretto alla coda e l'accesso ad esso ha una complessità temporale costante minima. 2. add(<Index>, <Element>) — aggiunge un elemento per indice. Quando si aggiunge un elemento, diciamo, al centro di un elenco, questo metodo prima esegue l'iterazione sugli elementi dalla testa e dalla coda (in entrambe le direzioni) finché non viene trovata la posizione desiderata. Se aggiungiamo un elemento tra il terzo e il quarto elemento (nell'immagine sopra), il collegamento successivo del terzo elemento punterà al nuovo elemento. E il precedente dell'elemento appena aggiunto punterà al terzo. A sua volta, il collegamento precedente del vecchio quarto elemento ora punterà al nuovo elemento, e il collegamento successivo del nuovo elemento punterà al nuovo quarto elemento: La complessità temporale di questo metodo dipende dall'indice del nuovo elemento:

• se è vicino alla testa o alla coda, l'operazione si avvicinerà a O(1), poiché in realtà non sarà necessario iterare sugli elementi;
• se è vicino al centro, allora avremo O(N/2), poiché il metodo cercherà contemporaneamente dalla testa e dalla coda finché non verrà trovato l'elemento desiderato.

3. set(<Indice>, <Elemento>) — scrive un elemento nella posizione specificata nell'elenco. La complessità temporale di questa operazione varierà da O(1) a O(N/2), sempre a seconda di quanto il nuovo elemento è vicino alla testa, alla coda o al centro. 4. delete(<index>) — rimuove un elemento dall'elenco facendo in modo che l'elemento prima di quello eliminato ( previous ) ora si riferisca all'elemento successivo a quello eliminato ( next ). E viceversa, cioè l'elemento dopo quello cancellato ora si riferisce a quello prima di quello cancellato: questo processo è l'opposto dell'aggiunta per indice ( add(<Index>, <Element>) ).

88. Qual è la struttura interna di una HashMap?

Questa potrebbe essere una delle domande più popolari da porre ai candidati sviluppatori Java durante il colloquio. Una HashMap funziona con coppie chiave-valore . Come vengono archiviati all'interno della HashMap stessa? Una HashMap ha un array interno di nodi:

Node<K,V>[] table

Per impostazione predefinita, la dimensione dell'array è 16 e raddoppia ogni volta che viene riempita di elementi (ovvero, quando viene raggiunto LOAD_FACTOR ; specifica la soglia per quanto può essere pieno l'array - per impostazione predefinita, è 0.75 ) . Ciascuno dei nodi memorizza un hash della chiave, la chiave, un valore e un riferimento all'elemento successivo: in questo caso, il "riferimento all'elemento successivo" significa che abbiamo a che fare con una lista concatenata singolarmente, dove ogni elemento contiene un collegamento al successivo. In altre parole, una HashMap memorizza i suoi dati in una serie di elenchi collegati singolarmente. Ma lasciatemi dire subito che quando una cella dell'array della tabella ha un elenco concatenato composto da più di un elemento, ciò non va bene. Questo fenomeno è chiamato collisione . Ma prima le cose principali. Vediamo come viene salvata una nuova coppia utilizzando il metodo put . Innanzitutto, il metodo ottiene l' hashCode() della chiave . Ciò implica che affinché una HashMap funzioni correttamente, le chiavi utilizzate devono essere classi che sovrascrivono questo metodo. Questo codice hash viene quindi utilizzato nel metodo hash() interno per determinare un indice di alcune celle all'interno dell'array della tabella. L'indice risultante ci consente di accedere a una cella specifica dell'array della tabella. Qui abbiamo due casi:

1. La cella è vuota: in questo caso, al suo interno viene memorizzato il nuovo valore del nodo .
2. La cella non è vuota: in questo caso vengono confrontati i valori delle chiavi. Se sono uguali, il nuovo valore Nodo sovrascrive quello vecchio; se non è uguale, si accede al successivo e la sua chiave viene confrontata... E così via, finché il nuovo valore non sovrascrive qualche vecchio valore o si raggiunge la fine dell'elenco collegato singolarmente e quindi si memorizza lì il nuovo valore come ultimo elemento.

Quando si cerca un elemento per chiave (utilizzando il metodo get(<key>) ), viene calcolato l'hashCode() della chiave , quindi il suo indice all'interno dell'array viene calcolato utilizzando hash() . Il numero risultante è l'indice di una cella nell'array della tabella , che poi cerchiamo iterando sui nodi e confrontando la chiave del nodo desiderato con la chiave del nodo corrente. Idealmente, le operazioni Map hanno una complessità algoritmica di O(1), perché stiamo accedendo a un array e, come ricorderete, è O(1), indipendentemente dal numero di elementi che contiene. Ma non siamo di fronte al caso ideale. Quando la cella non è vuota (2) e memorizza già alcuni nodi, allora la complessità algoritmica diventa O(N) (lineare), perché ora è necessario iterare sugli elementi prima di trovare il posto giusto. Non posso fare a meno di menzionare che a partire da Java 8, se un nodo sotto forma di elenco collegato singolarmente ha più di 8 elementi (collisioni), viene convertito in un albero binario. In questo caso, la complessità algoritmica non è più O(N), ma O(log(N)) — e questa è tutta un'altra questione, no? HashMap è un argomento importante e le persone adorano porre domande al riguardo durante i colloqui di lavoro. Quindi, ti suggerisco di conoscerlo come il palmo della tua mano. Personalmente non ho mai avuto un colloquio che non includesse domande su HashMap . È tutto per oggi. Continua...