O co mogą zapytać na rozmowie kwalifikacyjnej: Struktury danych w Javie. Część 1

Cześć! Bez względu na to, jak na to spojrzeć, nie możesz zostać programistą bez pomyślnego przejścia rozmowy kwalifikacyjnej technicznej. Technologii związanych z Javą jest bardzo dużo i nie da się nauczyć wszystkiego. Z reguły podczas rozmów kwalifikacyjnych pyta się o coś konkretnego tylko wtedy, gdy poszukuje się programisty z dobrym doświadczeniem w jakimś frameworku ważnym dla projektu. Jeśli tak jest, będziesz ścigany po tym frameworku z pełną prędkością, nie masz co do tego wątpliwości. Ale teraz mówimy o podstawie, którą powinien znać każdy programista Java. O tej klasycznej wiedzy, od której wszystko się zaczyna. Dzisiaj chciałbym poruszyć jeden z podstawowych tematów wszelkich struktur danych wywiadu w Javie . Zamiast więc owijać w bawełnę, zacznijmy. Znajdź listę pytań, które możesz zadać na ten temat podczas rozmowy kwalifikacyjnej.

1. Opowiedz nam trochę o strukturach danych

Struktura danych to magazyn danych zawierający informacje uporządkowane w określony sposób. Struktury te są zaprojektowane z myślą o wydajnym wykonywaniu określonych operacji. Typowe przykłady struktur danych to:

• tablice,
• półki na książki,
• kolejki,
• powiązane listy,
• wykresy,
• drzewa,
• przedrostki drzew,
• tablica mieszająca.

Więcej na ich temat można dowiedzieć się tutaj i tutaj . Dane są kluczowym elementem programu, a struktury umożliwiają przechowywanie tych danych w określonej, przejrzystej formie. Jakakolwiek będzie Twoja aplikacja, ten aspekt będzie w niej zawsze obecny: jeśli jest to sklep internetowy, to będą przechowywane informacje o produktach, jeśli jest to sieć społecznościowa, dane o użytkownikach i plikach itd.

2. Co wiesz o tablicach?

Tablica to pojemnik do przechowywania wartości tego samego typu, którego liczba została z góry określona. Przykład tworzenia tablicy z wartościami łańcuchowymi:

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

Podczas tworzenia tablicy pamięć jest przydzielana na wszystkie jej elementy: im więcej komórek dla elementów zostanie początkowo określonych, tym więcej pamięci zostanie przydzielonej. Jeżeli utworzona zostanie pusta tablica z określoną liczbą komórek, wówczas wszystkim elementom tablicy zostaną przypisane wartości domyślne. Na przykład:

int[] arr = new int[10];

Zatem dla tablicy z elementami typu boolean początkowe ( domyślne ) wartości będą miały wartość false , dla tablic z wartościami liczbowymi - 0, z elementami typu char - \u0000 . Dla tablicy typu klasy (obiekty) - null (nie puste ciągi znaków - „” , ale konkretnie null ). Oznacza to, że w powyższym przykładzie wszystkie wartości tablicy arr będą wynosić 0, dopóki nie zostaną bezpośrednio określone. W przeciwieństwie do kolekcji tablice nie są dynamiczne. Po zadeklarowaniu tablicy o określonym rozmiarze nie można zmienić samego rozmiaru. Aby dodać nowy element do tablicy, należy utworzyć nową, większą tablicę i skopiować do niej wszystkie elementy ze starej (tak działa ArrayList). Jest jeden punkt, o którym nie wszyscy wiedzą i na którym można się całkiem nieźle złapać. W Javie istnieją dwa typy zmiennych – typy proste i odniesienia do pełnoprawnych obiektów. Które z nich są tablicami? Na przykład tutaj:

int[] arr = new int[10];

Wydaje się, że wszystko jest proste – jest to 10 elementów typu int . Można więc powiedzieć, że jest to typ prosty? Nieważne jak to jest. W Javie tablice są obiektami, tworzonymi dynamicznie i można je przypisać do zmiennych typu Object. Wszystkie metody klasy Object można wywołać na tablicy. Możemy więc nawet napisać:

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

Podczas wysyłania danych do konsoli możesz otrzymać coś takiego: Przeczytaj więcej o funkcjach tablic w Javie w tym artykule o Java Array . Aby utrwalić swoją wiedzę, możesz rozwiązać kilka problemów z tego zbioru .

3. Wyjaśnij hierarchię zbiorów

Kolekcje są wykorzystywane w sytuacjach, w których potrzebna jest elastyczność podczas pracy z danymi. Kolekcje mogą dodawać elementy, usuwać je i wykonywać wiele innych operacji. Istnieje wiele różnych implementacji w Javie i musimy tylko wybrać odpowiednią kolekcję dla bieżącej sytuacji. Zazwyczaj, gdy wspominasz o interfejsie Collection , jesteś proszony o wypisanie niektórych jego implementacji i powiązań z Map . Cóż, przekonajmy się. Zatem Kolekcja i Mapa to dwie różne hierarchie struktur danych. Jak wygląda hierarchia Kolekcji : Interfejs Kolekcji to kluczowe łącze górne z listą podstawowych metod, z których wywodzą się trzy podstawowe typy struktur danych - Set , List , Queue . Set<T> to interfejs reprezentujący kolekcję obiektów, w których każdy obiekt jest unikalny. List<T> to interfejs reprezentujący uporządkowaną sekwencję obiektów zwaną listą. Queue<T> to interfejs odpowiedzialny za struktury zorganizowane w formie kolejki (sekwencyjne przechowywanie elementów). Jak wspomniano wcześniej, Map to osobna hierarchia: Map<K, V> to interfejs reprezentujący słownik, w którym elementy zawarte są w postaci par klucz-wartość. Co więcej, wszystkie klawisze (K) są unikalne w obrębie obiektu Map . Kolekcja tego typu ułatwia odnalezienie elementu, jeśli znamy klucz – unikalny identyfikator obiektu.

4. Co wiesz o Setze?

Jak wspomniano wcześniej, kolekcja ta zawiera wiele unikalnych elementów. Innymi słowy, ten sam obiekt nie może pojawić się więcej niż raz w zestawie Java. Chciałbym również zaznaczyć, że nie możemy wyodrębnić elementu z zestawu według numeru (indeksu) - tylko brutalną siłą. Ważne jest to, że różne implementacje Set mają różne sposoby strukturyzacji danych. Konkretne wdrożenia rozważymy dalej. Zatem główne implementacje Set : HashSet to zestaw oparty na tablicy skrótów, co z kolei pomaga w wyszukiwaniu. Używa funkcji skrótu, która poprawia wydajność podczas wyszukiwania i wstawiania. Niezależnie od liczby elementów, generalnie wstawianie i wyszukiwanie (czasami usuwanie) odbywa się w czasie zbliżonym do stałego - O(1). Przyjrzymy się funkcji skrótu bardziej szczegółowo nieco później. Chciałbym również zauważyć, że HashSet zawiera HashMap , w którym dzieje się cała magia. Oto szczegółowy artykuł na temat HashSet w Javie . LinkedHashSet - ta klasa rozszerza HashSet bez dodawania nowych metod. Podobnie jak LinkedList , ta klasa przechowuje połączoną listę elementów zestawu w kolejności, w jakiej zostały wstawione. Pozwala to na uporządkowanie niezbędnej kolejności w danej implementacji Seta . Klasa TreeSet tworzy zbiór oparty na czerwono-czarnym drzewie w celu uporządkowania struktury przechowywania elementów. Innymi słowy, w danym zbiorze możemy posortować elementy w kolejności rosnącej. Jeśli użyjemy standardowych obiektów z „pudełka”, na przykład Integer , to nie musimy nic robić, aby uporządkować zbiór Integers w kolejności rosnącej:

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

System.out.println(set);

A w konsoli otrzymamy wynik: Oznacza to, że w tym zestawie liczby są przechowywane w formie posortowanej. Jeśli użyjemy elementów String w TreeSet , zostaną one posortowane, ale alfabetycznie. A co jeśli mamy jakąś standardową (niestandardową) klasę? W jaki sposób obiekty tej klasy będą tworzyć strukturę TreeSet ? Jeśli spróbujemy przypisać dowolny obiekt do tego zbioru :

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);

Otrzymamy wyjątek ClassCastException , ponieważ TreeSet nie wie, jak sortować obiekty tego typu. W tym przypadku potrzebujemy naszego niestandardowego obiektu, aby zaimplementować interfejs Comparable i jego metodę 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 + '\'' +
               '}';
   }
}

Jak zauważyłeś, metoda CompareTo zwraca int :

• 1, jeśli bieżący (ten) obiekt jest uważany za duży;
• -1 jeśli bieżący obiekt jest uważany za mniejszy niż ten, który przyszedł jako argument;
• 0, jeśli obiekty są równe (nie używamy tego w tym przypadku).

W takim przypadku nasz TreeSet będzie działał poprawnie i wyświetli wynik: Innym sposobem jest utworzenie osobnej klasy sortującej, która implementuje interfejs komparatora i jego metodę porównania :

public class CatComparator implements Comparator {

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

W tym przypadku, aby z niego skorzystać, musimy ustawić obiekt tej klasy na konstruktorze TreeSet :

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

Następnie wszystkie obiekty klasy Cat zawarte w TreeSet zostaną posortowane przy użyciu klasy Cat Comparator . Więcej informacji na temat komparatora i porównywacza w Javie można znaleźć w tym artykule .

5. Opowiedz nam o kolejce

Kolejka to interfejs odpowiedzialny za struktury zorganizowane jako kolejka - struktura danych przechowująca elementy sekwencyjnie. Na przykład z kolejki osób pierwszą osobą, która wejdzie do środka będzie ta, która przybyła wcześniej od pozostałych, a ostatnią będzie ta, która przybyła później niż wszyscy inni. Ta metoda nazywa się FIFO , czyli „ pierwsze weszło, pierwsze wyszło” . Unikalne metody kolejki skupiają się na pracy z pierwszym lub ostatnim elementem, na przykład:

• dodaj i zaoferuj - wstawia element na koniec kolejki,
• usuń - pobiera i usuwa nagłówek tej kolejki,
• peek — pobiera, ale nie usuwa nagłówka kolejki.

CZĘŚĆ 2