Cosa potrebbero chiedere durante un colloquio: Strutture dati in Java. Parte 1

Ciao! Non importa come lo guardi, non puoi diventare uno sviluppatore senza superare con successo un colloquio di ammissione tecnico. Esistono molte tecnologie legate a Java ed è impossibile imparare tutto. Di norma, durante le interviste viene chiesto qualcosa di specifico solo se stanno cercando uno sviluppatore con una buona esperienza in qualche framework importante per il progetto. Se è così, sarai guidato attraverso questo quadro a tutta velocità, non hai dubbi. Ma ora parliamo delle basi che ogni sviluppatore Java dovrebbe conoscere. Di quel sapere classico da cui tutto ha inizio. Oggi vorrei toccare uno degli argomenti fondamentali di qualsiasi struttura di dati intervista in Java . Quindi, invece di girare intorno al cespuglio, cominciamo. Trova un elenco di domande che potrebbero esserti poste su questo argomento durante un colloquio.

1. Parlaci un po' delle strutture dati

Una struttura dati è un archivio dati che contiene informazioni strutturate in un certo modo. Queste strutture sono progettate per lo svolgimento efficiente di determinate operazioni. Esempi tipici di strutture dati sono:

• array,
• pile,
• code,
• elenchi correlati,
• grafici,
• alberi,
• alberi di prefisso,
• tabella hash.

Puoi saperne di più su di loro qui e qui . I dati sono un componente chiave in un programma e le strutture consentono di archiviarli in una forma specifica e chiaramente strutturata. Qualunque cosa faccia la tua applicazione, questo aspetto sarà sempre presente in essa: se si tratta di un negozio web, verranno archiviate informazioni sui prodotti, se si tratta di un social network, dati su utenti e file e così via.

2. Cosa sai degli array?

Un array è un contenitore per la memorizzazione di valori dello stesso tipo, il cui numero è stato specificato in anticipo. Un esempio di creazione di un array con valori stringa:

String[] strArray = {"Java","is","the","best","language"};

Quando si crea un array, viene allocata memoria per tutti i suoi elementi: più celle vengono inizialmente specificate per gli elementi, maggiore sarà la memoria allocata. Se viene creato un array vuoto con un certo numero di celle, a tutti gli elementi dell'array verranno assegnati valori predefiniti. Per esempio:

int[] arr = new int[10];

Quindi, per un array con elementi di tipo booleano , i valori iniziali ( predefiniti ) saranno false , per array con valori numerici - 0, con elementi di tipo char - \u0000 . Per un array di tipo classe (oggetti) - null (non stringhe vuote - "" ma specificamente null ). Cioè, nell'esempio sopra, tutti i valori dell'array arr saranno 0 finché non verranno specificati direttamente. A differenza delle raccolte, gli array non sono dinamici. Una volta dichiarato un array di una certa dimensione, la dimensione stessa non può essere modificata. Per aggiungere un nuovo elemento a un array, è necessario creare un nuovo array più grande e copiare in esso tutti gli elementi di quello vecchio (ecco come funziona ArrayList). C'è un punto che non tutti conoscono e sul quale si riesce a cogliere abbastanza bene. Esistono due tipi di variabili in Java: tipi semplici e riferimenti a oggetti completi. Quali di questi sono array? Ad esempio, qui:

int[] arr = new int[10];

Sembra che tutto sia semplice: questi sono 10 elementi int . Quindi, possiamo dire che questo è un tipo semplice? Non importa come sia. In Java gli array sono oggetti, vengono creati dinamicamente e possono essere assegnati a variabili di tipo Object. Tutti i metodi della classe Object possono essere chiamati su un array. Quindi possiamo anche scrivere:

Object arr = new int[]{7,5,4,3};
System.out.println(arr.toString());

Durante l'output sulla console potresti ottenere qualcosa del tipo: Maggiori informazioni sulle funzionalità degli array in Java in questo articolo su Java Array . Per consolidare le tue conoscenze, puoi risolvere diversi problemi da questa raccolta .

3. Spiegare la gerarchia delle collezioni

Le raccolte vengono utilizzate in situazioni in cui è necessaria flessibilità quando si lavora con i dati. Le raccolte possono aggiungere un elemento, rimuovere un elemento ed eseguire molte altre operazioni. Esistono molte implementazioni diverse in Java e dobbiamo solo scegliere la raccolta giusta per la situazione attuale. In genere, quando menzioni l' interfaccia Collection , ti viene chiesto di elencare alcune delle sue implementazioni e la sua relazione con Map . Bene, scopriamolo. Pertanto, Raccolta e Mappa sono due gerarchie diverse per le strutture dati. Come appare la gerarchia della Collezione : L' interfaccia della Collezione è il collegamento principale con un elenco di metodi di base, da cui hanno origine tre tipi fondamentali di strutture dati: Set , List , Queue . Set<T> è un'interfaccia che rappresenta una raccolta di oggetti in cui ogni oggetto è univoco. List<T> è un'interfaccia che rappresenta una sequenza ordinata di oggetti denominata elenco. Queue<T> è un'interfaccia responsabile delle strutture organizzate come coda (archiviazione sequenziale di elementi). Come accennato in precedenza, Map è una gerarchia separata: Map<K, V> è un'interfaccia che rappresenta un dizionario in cui gli elementi sono contenuti come coppie chiave-valore. Inoltre, tutte le chiavi (K) sono uniche all'interno dell'oggetto Mappa . Questo tipo di raccolta rende più semplice trovare un elemento se conosciamo la chiave, l'identificatore univoco dell'oggetto.

4. Cosa sai di Set?

Come affermato in precedenza, questa collezione presenta molti elementi unici. In altre parole, lo stesso oggetto non può apparire più di una volta in un Java Set . Vorrei anche sottolineare che non possiamo estrarre un elemento da un Set tramite numero (indice), solo con la forza bruta. La cosa importante è che diverse implementazioni di Set hanno modi diversi di strutturare i dati. Considereremo ulteriormente implementazioni specifiche. Quindi, le principali implementazioni di Set : HashSet è un set basato su una tabella hash, che a sua volta aiuta nella ricerca. Utilizza una funzione hash che migliora le prestazioni durante le ricerche e gli inserimenti. Indipendentemente dal numero di elementi, in generale, l'inserimento e la ricerca (a volte la cancellazione) vengono eseguiti in un tempo quasi costante - O(1). Esamineremo la funzione hash in modo più dettagliato un po' più tardi. Vorrei anche notare che HashSet contiene un HashMap , che è dove avviene tutta la magia. Ecco un articolo dettagliato su HashSet in Java . LinkedHashSet : questa classe estende HashSet senza aggiungere nuovi metodi. Come LinkedList , questa classe mantiene un elenco collegato degli elementi di un set nell'ordine in cui sono stati inseriti. Ciò consente di organizzare l'ordine necessario in una determinata implementazione del Set . La classe TreeSet crea un set basato su un albero rosso-nero per organizzare la struttura di memorizzazione degli elementi. In altre parole, in un dato insieme possiamo ordinare gli elementi in ordine crescente. Se utilizziamo alcuni oggetti standard della “scatola”, ad esempio Integer , allora non dobbiamo fare nulla per disporre l'insieme di numeri interi in ordine crescente:

TreeSet set = new TreeSet<>();
set.add(4);
set.add(2);
set.add(3);
set.add(1);

System.out.println(set);

E nella console otterremo l'output: Cioè, in questo set i numeri sono memorizzati in forma ordinata. Se utilizziamo elementi String in un TreeSet , verranno ordinati, ma in ordine alfabetico. Bene, e se avessimo una classe standard (personalizzata)? In che modo gli oggetti di questa classe struttureranno il TreeSet ? Se proviamo ad assegnare un oggetto arbitrario a questo Set :

TreeSet set = new TreeSet<>();
set.add(new Cat(4, "Murzik"));
set.add(new Cat(2, "Barsik"));
set.add(new Cat(3, "Гарфилд"));

System.out.println(set);

Riceveremo una ClassCastException perché TreeSet non sa come ordinare oggetti di questo tipo. In questo caso, abbiamo bisogno del nostro oggetto personalizzato per implementare l' interfaccia Comparable e il suo metodo compareTo :

public class Cat implements Comparable {
    int age;
    String name;

   public Cat(int age, String name) {
       this.age = age;
       this.name = name;
   }

   @Override
   public int compareTo(Cat cat) {
       return age > cat.age ? 1 : -1;
   }

   @Override
   public String toString() {
       return "Cat{" +
               "age=" + age +
               ", name='" + name + '\'' +
               '}';
   }
}

Come hai notato, il metodo compareTo restituisce un int :

• 1 se l'oggetto corrente (questo) è considerato grande;
• -1 se l'oggetto corrente è considerato più piccolo di quello fornito come argomento;
• 0 se gli oggetti sono uguali (non lo usiamo in questo caso).

In questo caso, il nostro TreeSet funzionerà correttamente e visualizzerà il risultato: Un altro modo è creare una classe di ordinamento separata che implementi l' interfaccia del comparatore e il suo metodo di confronto :

public class CatComparator implements Comparator {

   @Override
   public int compare(Cat o1, Cat o2) {
       return o1.age > o2.age ? 1 : -1;
   }
}

In questo caso, per utilizzarlo, dobbiamo impostare un oggetto di questa classe sul costruttore TreeSet :

TreeSet set = new TreeSet<>(new CatComparator());

Successivamente, tutti gli oggetti della classe Cat inclusi nel TreeSet verranno ordinati utilizzando la classe Cat Comparator . Puoi saperne di più su Comparator e Comparable in Java da questo articolo .

5. Parlaci di Coda

La coda è un'interfaccia responsabile delle strutture organizzate come una coda, una struttura dati che memorizza gli elementi in sequenza. Ad esempio, in una coda di persone, la prima persona ad entrare sarà quella che è arrivata prima degli altri, e l'ultima sarà quella che è arrivata più tardi di tutti gli altri. Questo metodo si chiama FIFO , cioè First in First Out . I metodi di coda univoci si concentrano sull'utilizzo del primo o dell'ultimo elemento, ad esempio:

• aggiungi e offri : inserisce un elemento alla fine della coda,
• rimuovi: recupera e rimuove l'intestazione di questa coda,
• peek: recupera ma non rimuove l'intestazione della coda.

PARTE 2