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

CIAO! Quante ore ci vogliono per diventare un maestro in qualcosa? Ho sentito spesso qualcosa del tipo: "Per diventare un maestro in qualsiasi cosa, devi dedicarci 10.000 ore". È un numero intimidatorio, non è vero? Eppure mi chiedo se sia vero. E cerco costantemente di capire quante ore ho già investito nel padroneggiare l'arte della programmazione. E quando supererò quella linea speciale delle 10.000 ore e diventerò un maestro, sentirò la differenza? Oppure ho già oltrepassato quel limite molto tempo fa senza rendermene conto? In ogni caso, non è necessario investire una quantità così grande di tempo per diventare un programmatore. L’importante è usare saggiamente il proprio tempo. Il tuo obiettivo principale è ottenere un colloquio. E nelle interviste, agli aspiranti sviluppatori di software viene prima chiesto della teoria, quindi questo deve essere un punto di forza. Infatti, mentre ti prepari per un colloquio, il tuo compito è scoprire tutte le lacune nella conoscenza della teoria di base di Java e poi colmarle. Oggi sono qui per aiutarti a fare proprio questo, poiché oggi continueremo la nostra rassegna delle domande più popolari da intervista. Bene, continuiamo!

89. In che modo un ArrayList è diverso da un LinkedList?

Questa è una delle domande più gettonate, insieme alla domanda sulla struttura interna di una HashMap . Nessuna intervista è completa senza di essa, quindi la tua risposta dovrebbe uscire facilmente dalla tua lingua. Oltre all'ovvio (hanno nomi diversi), differiscono nella loro struttura interna. In precedenza, abbiamo discusso la struttura interna sia di ArrayList che di LinkedList , quindi non entrerò nei dettagli della loro implementazione. Ti ricordo solo che ArrayList è implementato utilizzando un array interno la cui dimensione aumenta dinamicamente secondo questa formula:

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

Inoltre, l'implementazione di una LinkedList utilizza una lista interna doppiamente collegata, ovvero ogni elemento ha un riferimento all'elemento precedente e successivo, ad eccezione degli elementi all'inizio e alla fine della lista. Gli intervistatori adorano porre questa domanda in questo modo: "Che è meglio, ArrayList o LinkedList ?" sperando di prenderti. Dopotutto, se dici che è meglio l'uno o l'altro, hai dato la risposta sbagliata. Dovresti invece chiarire la situazione specifica di cui stai parlando: accesso agli elementi tramite indice o inserimento al centro della lista. Quindi, a seconda della loro risposta, puoi spiegare quale è la migliore. In precedenza ho descritto come funzionano ArrayList e LinkedList in ogni situazione. Riassumiamolo mettendoli in fila per il confronto: Aggiunta di un elemento (add)

1. Se non viene specificato un indice, verrà automaticamente aggiunto un nuovo elemento alla fine per entrambi i tipi di elenchi. In una LinkedList , il nuovo elemento diventerà la nuova coda (verranno riscritti solo una coppia di riferimenti, quindi la complessità algoritmica è O(1) ).

   Il metodo add aggiunge un elemento all'ultima cella vuota nell'array ( O(1) ).

2. Aggiungere un elemento tramite indice di solito significa inserirlo da qualche parte nel mezzo dell'elenco. In una LinkedList , il metodo cercherà prima la posizione desiderata eseguendo un'iterazione sugli elementi dalla coda e dalla testa ( O(n/2) ) e quindi inserirà il valore sovrascrivendo i riferimenti degli elementi su entrambi i lati di dove si trova il viene inserito un nuovo elemento ( O(1) ). La complessità algoritmica complessiva di questa operazione sarà O(n/2) .

   Nella stessa situazione (aggiunta per indice), un ArrayList trova la posizione desiderata ( O(1) ) e quindi sposta tutti gli elementi situati a destra (incluso l'elemento già memorizzato nell'indice specificato) a destra di uno (che potrebbe richiedere la creazione di un nuovo array interno e la copia degli elementi su di esso) ( O(n/2) ). La complessità complessiva è O(n/2) .

3. Aggiungere un elemento all'inizio di una LinkedList è simile ad aggiungere un elemento alla fine: il nuovo elemento diventa la nuova testa ( O(1) ). Ma per un ArrayList, tale operazione richiede lo spostamento di tutti gli elementi a destra ( O(n) ).

La conclusione è che per una LinkedList la complessità algoritmica varierà da O(1) a O(n/2) . Un'altra osservazione è che quanto più l'inserimento è vicino alla fine o all'inizio dell'elenco, tanto più veloce è. Per ArrayList , la complessità algoritmica varia da O(1) a O(n) e più l'inserimento è vicino alla fine dell'elenco, più veloce è. Impostazione di un elemento (set) Questa operazione scrive un elemento nella posizione specificata nell'elenco, sovrascrivendo qualsiasi elemento esistente. In una LinkedList , questa operazione è simile all'aggiunta, poiché la sfida più grande qui è trovare la posizione dell'elemento. L'elemento esistente viene sovrascritto aggiornando una coppia di riferimenti, quindi ancora una volta abbiamo una complessità algoritmica che varia da O(1) a O(n/2) , a seconda della distanza della posizione desiderata dalla fine o dall'inizio della lista. Ma per un ArrayList , questa operazione trova la cella desiderata in base all'indice e scrive lì il nuovo elemento. Come l'operazione sugli insiemi, la ricerca per indice ha una complessità algoritmica di O(1) . Ottenere un elemento tramite indice (get) Ottenere un elemento da una LinkedList segue lo stesso principio di ricerca utilizzato in altre operazioni. La complessità dipende dalla distanza dalla fine o dall'inizio, cioè varia da O(1) a O(n/2) . Come notato in precedenza, per un ArrayList , trovare un elemento tramite indice nell'array interno ha una complessità di O(1) . Rimuovere un elemento tramite indice (remove) Per LinkedList si applica ancora una volta lo stesso principio. Innanzitutto, l'elemento viene individuato, quindi i riferimenti vengono riscritti, gli elementi vicini dell'elemento eliminato ora si riferiscono tra loro, eliminando i riferimenti all'elemento eliminato, che verrà successivamente ripulito dal garbage collector. In altre parole, la complessità algoritmica è sempre la stessa: varia da O(1) a O(n/2) . Per ArrayList , questa operazione è più simile all'aggiunta di un nuovo elemento (add). Innanzitutto, il metodo trova l'elemento desiderato ( O(1) ), lo rimuove e quindi tutti gli elementi situati a destra vengono spostati di un passo a sinistra per colmare il divario creato dalla rimozione. La rimozione di un elemento ha la stessa complessità algoritmica dell'operazione di aggiunta: da O(1) a O(n). Quanto più l'elemento rimosso è vicino alla fine della lista, tanto minore sarà la complessità algoritmica di questa operazione. E ora abbiamo coperto tutte le operazioni principali. Lascia che ti ricordi che quando confronti questi due tipi di elenchi, devi chiarire la situazione specifica in cui vengono utilizzati. Solo allora puoi rispondere inequivocabilmente alla domanda dell'intervistatore.

90. In che cosa un ArrayList è diverso da un HashSet?

Se potessimo confrontare ArrayList e LinkedList operazione per operazione per determinare qual è il migliore, non troveremmo così facile fare un confronto del genere tra ArrayList e HashSet , perché sono raccolte completamente diverse. Puoi confrontare un dessert con un altro, ma confrontare un dessert e un piatto salato è una sfida: sono dolorosamente diversi. Cercherò comunque di evidenziare alcune delle differenze tra loro:

• ArrayList implementa l' interfaccia List mentre HashSet implementa l' interfaccia Set .

• ArrayList ti consente di accedere a un elemento tramite indice: l' operazione get ha una complessità algoritmica O(1) , ma HashSet ti consente di accedere solo all'elemento desiderato tramite iterazione, che produce una complessità algoritmica che va da O(1) a O(n) .

• ArrayList consente elementi duplicati. In un HashSet , tutti gli elementi sono unici: qualsiasi tentativo di aggiungere un elemento già presente in un HashSet fallirà (i duplicati vengono controllati tramite hashcode, da cui il nome di questa raccolta).

• ArrayList viene implementato utilizzando un array interno, ma HashSet viene implementato utilizzando un HashMap interno .

• ArrayList mantiene l'ordine di inserimento degli elementi, ma HashSet è un insieme non ordinato e non mantiene l'ordine degli elementi.

• ArrayList consente un numero qualsiasi di valori null, ma è possibile aggiungere solo un valore null a un HashSet (dopo tutto, gli elementi devono essere univoci).

91. Perché Java ha così tante diverse implementazioni di array dinamici?

Questa è più una questione filosofica. Potremmo anche chiederci perché inventano così tante tecnologie nuove e varie? Per comodità. E la stessa cosa vale per un gran numero di implementazioni di array dinamici. Nessuno di questi può essere definito l'implementazione migliore o ideale. Ognuno ha i suoi vantaggi in situazioni specifiche. Il nostro compito è conoscere le loro differenze e i loro punti di forza/debolezza per poter utilizzare la collezione più adatta ad ogni situazione.

92. Perché Java ha così tante diverse implementazioni di archiviazione di valori-chiave?

Qui la situazione è la stessa delle implementazioni di array dinamici. Sicuramente non ce n’è uno universalmente migliore degli altri: ognuno ha pregi e difetti. E dobbiamo sfruttare al massimo i loro punti di forza, ovviamente. Esempio: il pacchetto concurrent, che ha molte classi multithread, ha le proprie raccolte Concurrent . La classe ConcurrentHashMap presenta un vantaggio rispetto alla HashMap standard in termini di sicurezza quando si lavora con i dati in un ambiente multi-thread, ma ciò comporta prestazioni più lente. E le implementazioni che non rappresentano la scelta migliore in qualsiasi situazione cessano gradualmente di essere utilizzate. Ad esempio: Hashtable , che originariamente doveva essere un HashMap thread-safe , è stato dimenticato ed è caduto in disuso, perché ConcurrentHashMap è persino migliore di Hashtable quando si lavora in un ambiente multi-thread.

93. Come posso ordinare una raccolta di elementi?

La prima cosa da dire è che la classe che rappresenta gli elementi della collezione deve implementare l' interfaccia Comparable , che consiste nel metodo compareTo . Oppure hai bisogno di una classe che implementi l' interfaccia Comparator , incluso il suo metodo di confronto . Entrambi i metodi indicano come confrontare oggetti di un determinato tipo. Questo è fondamentale durante l'ordinamento, perché l'algoritmo di ordinamento deve capire quale principio utilizzare per confrontare gli elementi. Ciò viene fatto principalmente implementando Comparable direttamente nella classe che desideri ordinare. L'uso del comparatore è meno comune. Supponiamo che tu stia utilizzando una classe da una libreria e che non implementi Comparable , ma devi ordinare una raccolta dei suoi oggetti. Poiché non è possibile modificare il codice di questa classe (se non estendendolo), è possibile scrivere un'implementazione di Comparator che indichi come confrontare gli oggetti della classe. E un altro esempio. Se è necessario ordinare oggetti dello stesso tipo in modi diversi, è possibile scrivere più implementazioni di Comparator da utilizzare in situazioni diverse. Di norma, molte classi predefinite, ad esempio String , implementano già l' interfaccia Comparable . Ciò significa che non devi preoccuparti di come confrontare queste classi. Puoi semplicemente andare avanti e usarli. Il primo e più ovvio modo è utilizzare la classe TreeSet o TreeMap . Queste classi memorizzano gli elementi in ordine basato sul comparatore implementato dagli elementi della classe. Non dimenticare che TreeMap ordina le chiavi, non i valori. Se usi Comparator invece di Comparable , devi passare un oggetto Comparator al costruttore della raccolta quando lo crei:

TreeSet treeSet = new TreeSet(customComparator);

Ma cosa succede se hai un diverso tipo di collezione? Come lo ordinate? In questo caso, il secondo modo della classe di utilità Collections , il metodo sort() , è adatto. Il metodo è statico, quindi tutto ciò che serve è anteporre il nome della classe e quindi passare l'elenco da ordinare. Per esempio:

Collections.sort(someList);

Se stai utilizzando un'implementazione di Comparator anziché Comparable , devi passarla come secondo argomento:

Collections.sort(someList, customComparator);

Questa operazione modificherà l'ordine interno degli elementi nella lista passata: la lista verrà ordinata utilizzando il comparatore. Tieni presente che l'elenco passato deve essere modificabile, altrimenti il ​​metodo fallirà e genererà un'eccezione UnsupportedOperationException . Una terza opzione consiste nell'utilizzare il metodo sorted della classe Stream , che ordina gli elementi della raccolta. Se stiamo usando Comparable :

someList = someList.stream().sorted().collect(Collectors.toList());

Se utilizziamo il comparatore :

someList = someList.stream().sorted(customComparator).collect(Collectors.toList());

Il quarto modo consiste nell'implementare manualmente un algoritmo di ordinamento, ad esempio bubble sort o merge sort .

Classe dell'oggetto. equals() e hashCode()

94. Fornire una breve descrizione della classe Object in Java.

Nella seconda parte della recensione abbiamo già discusso i metodi della classe Object . Qui ti ricorderò che la classe Object è un antenato di ogni classe in Java. Dispone di 11 metodi, che a loro volta vengono ereditati da tutte le classi.

95. A cosa servono equals() e hashCode() in Java?

hashCode() è un metodo della classe Object ereditato da tutte le classi. Il suo compito è generare un numero che rappresenta un oggetto specifico. Un esempio di questo metodo in azione può essere trovato in HashMap , dove viene chiamato sugli oggetti chiave per ottenere l'hashcode locale, che determinerà in quale bucket (cella dell'array interno) verrà archiviata la coppia chiave-valore. Inoltre, questo metodo viene generalmente utilizzato nel metodo equals() come uno dei modi principali per identificare gli oggetti. equals() è un metodo della classe Object il cui compito è confrontare gli oggetti e determinare se sono uguali. Questo metodo viene utilizzato ovunque dobbiamo confrontare oggetti, perché l'operatore di confronto standard == non è adatto per gli oggetti, poiché confronta solo i riferimenti agli oggetti.

96. Ci parli del contratto tra equals() e hashCode() in Java?

Innanzitutto, lasciatemi dire che affinché i metodi equals() e hashCode() funzionino correttamente, devono essere sovrascritti correttamente. Le loro nuove implementazioni devono seguire queste regole:

• Oggetti identici per i quali uguale restituisce vero devono avere gli stessi codici hash.
• Gli oggetti con gli stessi codici hash non sono necessariamente uguali.

Ora sembra un buon punto di pausa fino alla parte successiva della recensione!