Przeglądanie pytań i odpowiedzi z rozmowy kwalifikacyjnej na stanowisko programisty Java. Część 10

Cześć! Ile godzin potrzeba, aby zostać w czymś mistrzem? Często słyszałem coś w stylu: „Aby zostać w czymś mistrzem, trzeba spędzić w tym 10 000 godzin”. To zastraszająca liczba, prawda? Mimo to zastanawiam się, czy to prawda. I ciągle próbuję policzyć, ile godzin już zainwestowałem w opanowanie sztuki programowania. A kiedy przekroczę tę specjalną granicę 10 000 godzin i zostanę mistrzem, czy poczuję różnicę? A może przekroczyłem tę granicę dawno temu, nie zdając sobie z tego sprawy? Tak czy inaczej, nie musisz inwestować tak dużej ilości czasu, aby zostać programistą. Najważniejsze to mądrze wykorzystywać swój czas. Twoim głównym celem jest uzyskanie rozmowy kwalifikacyjnej. A podczas rozmów kwalifikacyjnych przyszłych programistów pyta się najpierw o teorię, więc to musi być mocna strona. Tak naprawdę, przygotowując się do rozmowy kwalifikacyjnej, Twoim zadaniem jest odkrycie wszystkich luk w wiedzy z zakresu podstawowej teorii języka Java, a następnie ich uzupełnienie. Dzisiaj jestem tutaj, aby Ci w tym pomóc, ponieważ dzisiaj będziemy kontynuować przegląd najpopularniejszych pytań na rozmowach kwalifikacyjnych. Cóż, kontynuujmy!

89. Czym różni się ArrayList od LinkedList?

Jest to jedno z najpopularniejszych pytań, obok pytania o wewnętrzną strukturę HashMap . Bez tego żadna rozmowa kwalifikacyjna nie jest kompletna, więc Twoja odpowiedź powinna z łatwością spłynąć Ci z języka. Oprócz tego, co oczywiste (mają różne nazwy), różnią się budową wewnętrzną. Wcześniej omawialiśmy wewnętrzną strukturę zarówno ArrayList , jak i LinkedList , więc nie będę zagłębiać się w szczegóły ich implementacji. Przypomnę tylko, że ArrayList jest implementowany przy użyciu wewnętrznej tablicy, której rozmiar rośnie dynamicznie zgodnie z następującą formułą:

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

Dodatkowo implementacja LinkedList wykorzystuje wewnętrzną podwójnie połączoną listę, co oznacza, że ​​każdy element ma odniesienie do poprzedniego i następnego elementu, z wyjątkiem elementów na początku i na końcu listy. Ankieterzy uwielbiają zadawać takie pytania: „Co jest lepsze, ArrayList czy LinkedList ?” mając nadzieję, że cię złapię. W końcu, jeśli powiesz, że jedno lub drugie jest lepsze, oznacza to, że udzieliłeś złej odpowiedzi. Zamiast tego powinieneś wyjaśnić konkretną sytuację, o której mówisz: dostęp do elementów poprzez indeks lub wstawianie na środku listy. Następnie, w zależności od odpowiedzi, możesz wyjaśnić, który z nich jest lepszy. Wcześniej opisałem, jak ArrayList i LinkedList działają w każdej sytuacji. Podsumujmy to umieszczając je w rzędzie dla porównania: Dodanie elementu (dodaj)

1. Jeśli indeks nie zostanie określony, dla obu rodzajów list automatycznie na końcu zostanie dodana nowa pozycja. W LinkedList nowy element stanie się nowym ogonem (przepisano tylko parę odniesień, więc złożoność algorytmiczna wynosi O(1) ).

   Metoda add dodaje element do ostatniej pustej komórki w tablicy ( O(1) ).

2. Dodanie elementu według indeksu zwykle oznacza wstawienie go gdzieś na środku listy. W LinkedList metoda najpierw wyszuka żądaną lokalizację, iterując po elementach z ogona i nagłówka ( O(n/2) ), a następnie wstawi wartość, zastępując odniesienia elementów po obu stronach miejsca, w którym znajduje się dodano nowy element ( O(1) ). Ogólna złożoność algorytmiczna tej operacji będzie wynosić O(n/2) .

   W tej samej sytuacji (dodawanie według indeksu) ArrayList znajduje żądaną lokalizację ( O(1) ), a następnie przesuwa wszystkie elementy znajdujące się w prawo (w tym element już przechowywany pod określonym indeksem) w prawo o jeden (co może wymagać utworzenia nowej tablicy wewnętrznej i skopiowania do niej elementów) ( O(n/2) ). Ogólna złożoność wynosi O(n/2) .

3. Dodanie elementu na początek listy LinkedList jest podobne do dodania elementu na końcu: nowy element staje się nową głową ( O(1) ). Ale w przypadku ArrayList operacja ta wymaga przeniesienia wszystkich elementów w prawo ( O(n) ).

Najważniejsze jest to, że w przypadku LinkedList złożoność algorytmiczna będzie wynosić od O(1) do O(n/2) . Inną obserwacją jest to, że im bliżej końca lub początku listy jest wstawianie, tym jest ono szybsze. W przypadku ArrayList złożoność algorytmiczna waha się od O(1) do O(n) i im bliżej końca listy jest wstawianie, tym jest ono szybsze. Ustawianie elementu (zestawu) Operacja ta zapisuje element na określoną pozycję na liście, nadpisując istniejący element. W LinkedList operacja ta jest podobna do dodawania, ponieważ największym wyzwaniem jest tutaj znalezienie lokalizacji elementu. Istniejący element jest nadpisywany przez aktualizację pary odniesień, więc znowu mamy złożoność algorytmiczną wahającą się od O(1) do O(n/2) , w zależności od odległości żądanej pozycji od końca lub początku listy. Ale w przypadku ArrayList ta operacja znajduje żądaną komórkę według indeksu i zapisuje tam nowy element. Podobnie jak operacja ustawiania, wyszukiwanie według indeksu ma złożoność algorytmiczną O(1) . Pobieranie elementu według indeksu (get) Pobieranie elementu z listy LinkedList odbywa się według tej samej zasady wyszukiwania, która jest używana w innych operacjach. Złożoność zależy od odległości od końca lub początku, tj. waha się od O(1) do O(n/2) . Jak zauważono wcześniej, w przypadku ArrayList znalezienie elementu według indeksu w tablicy wewnętrznej ma złożoność O(1) . Usuwanie elementu według indeksu (usuń) W przypadku LinkedList ponownie obowiązuje ta sama zasada. Najpierw lokalizowany jest element, następnie przepisywane są referencje, sąsiedzi usuniętego elementu odnoszą się teraz do siebie nawzajem, eliminując odniesienia do usuniętego elementu, które następnie zostaną oczyszczone przez moduł zbierający elementy bezużyteczne. Innymi słowy, złożoność algorytmiczna jest wciąż taka sama — waha się od O(1) do O(n/2) . W przypadku ArrayList ta operacja przypomina bardziej dodanie nowego elementu (dodanie). Najpierw metoda znajduje żądany element ( O(1) ), usuwa go, a następnie wszystkie elementy znajdujące się po prawej stronie przesuwa się o jeden krok w lewo, aby zamknąć lukę powstałą po usunięciu. Usunięcie elementu ma taką samą złożoność algorytmiczną jak operacja dodawania — od O(1) do O(n). Im bliżej końca listy znajduje się usunięty element, tym mniejsza jest złożoność algorytmiczna tej operacji. A teraz omówiliśmy wszystkie główne operacje. Przypomnę, że porównując te dwa rodzaje list, należy sprecyzować, w jakiej konkretnej sytuacji są wykorzystywane. Dopiero wtedy można jednoznacznie odpowiedzieć na pytanie ankietera.

90. Czym ArrayList różni się od HashSet?

Gdybyśmy mogli porównać ArrayList i LinkedList na zasadzie operacja po operacji, aby określić, która z nich jest lepsza, nie będzie nam łatwo dokonać takiego porównania między ArrayList i HashSet , ponieważ są to zupełnie różne kolekcje. Można porównać jeden deser z drugim, ale porównanie deseru i dania słonego to wyzwanie – są boleśnie różne. Spróbuję jednak wskazać niektóre różnice między nimi:

• ArrayList implementuje interfejs List , podczas gdy HashSet implementuje interfejs Set .

• ArrayList umożliwia dostęp do elementu według indeksu: operacja get ma złożoność algorytmiczną O(1) , ale HashSet umożliwia dostęp do żądanego elementu tylko przez iterację, co daje złożoność algorytmiczną w zakresie od O(1) do O(n) .

• ArrayList pozwala na duplikowanie elementów. W HashSet wszystkie elementy są unikalne: każda próba dodania elementu, który jest już obecny w HashSet , zakończy się niepowodzeniem (duplikaty są sprawdzane za pomocą hashcode, stąd nazwa tej kolekcji).

• ArrayList jest zaimplementowany przy użyciu tablicy wewnętrznej, ale HashSet jest zaimplementowany przy użyciu wewnętrznej HashMap .

• ArrayList zachowuje kolejność wstawiania elementów, ale HashSet jest zestawem nieuporządkowanym i nie zachowuje kolejności elementów.

• ArrayList dopuszcza dowolną liczbę wartości null, ale do HashSet można dodać tylko jedną wartość null (w końcu elementy muszą być unikalne).

91. Dlaczego Java ma tak wiele różnych implementacji tablic dynamicznych?

To jest raczej pytanie filozoficzne. Moglibyśmy również zapytać, dlaczego wymyślają tak wiele nowych i różnorodnych technologii? Dla wygody. To samo dotyczy dużej liczby implementacji tablic dynamicznych. Żadnego z nich nie można nazwać najlepszym czy idealnym wdrożeniem. Każdy ma swoje zalety w konkretnych sytuacjach. Naszym zadaniem jest poznanie różnic między nimi oraz mocnych i słabych stron, aby móc wybrać kolekcję najodpowiedniejszą w danej sytuacji.

92. Dlaczego Java ma tak wiele różnych implementacji przechowywania klucz-wartość?

Tutaj sytuacja jest taka sama jak w przypadku implementacji tablic dynamicznych. Zdecydowanie nie ma żadnego, który byłby uniwersalnie lepszy od innych: każdy ma mocne i słabe strony. I oczywiście musimy jak najlepiej wykorzystać ich mocne strony. Przykład: pakiet współbieżny, który ma wiele klas wielowątkowych, ma własne kolekcje współbieżne . Klasa ConcurrentHashMap ma przewagę nad standardową HashMap pod względem bezpieczeństwa podczas pracy z danymi w środowisku wielowątkowym, ale odbywa się to kosztem niższej wydajności. A wdrożenia, które w żadnej sytuacji nie są najlepszym wyborem, stopniowo przestają być stosowane. Na przykład: Hashtable , który pierwotnie miał być HashMap bezpieczny dla wątków , został zapomniany i wyszedł z użycia, ponieważ ConcurrentHashMap jest jeszcze lepszy niż Hashtable podczas pracy w środowisku wielowątkowym.

93. Jak posortować zbiór elementów?

Na początek należy powiedzieć, że klasa reprezentująca elementy kolekcji musi implementować interfejs Comparable , na który składa się metoda CompareTo . Lub potrzebujesz klasy implementującej interfejs Comparator , w tym metodę porównania . Obie metody wskazują sposób porównywania obiektów danego typu. Ma to kluczowe znaczenie podczas sortowania, ponieważ algorytm sortowania musi zrozumieć, jakiej zasady użyć do porównania elementów. Odbywa się to głównie poprzez implementację Comparable bezpośrednio w klasie, którą chcesz posortować. Korzystanie z komparatora jest mniej powszechne. Załóżmy, że używasz klasy z jakiejś biblioteki i nie implementuje ona Comparable , ale musisz posortować kolekcję jej obiektów. Ponieważ nie możesz zmienić kodu tej klasy (z wyjątkiem rozszerzenia), możesz napisać implementację Comparatora , która wskazuje, jak porównywać obiekty klasy. I jeszcze jeden przykład. Jeśli chcesz posortować obiekty tego samego typu na różne sposoby, możesz napisać wiele implementacji komparatora do użycia w różnych sytuacjach. Z reguły wiele gotowych klas, np. String , implementuje już interfejs Comparable . Oznacza to, że nie musisz się martwić, jak porównać te klasy. Możesz po prostu iść dalej i z nich korzystać. Pierwszym i najbardziej oczywistym sposobem jest użycie klasy TreeSet lub TreeMap . Klasy te przechowują elementy w posortowanej kolejności w oparciu o komparator zaimplementowany przez elementy klasy. Nie zapominaj, że TreeMap sortuje klucze, a nie wartości. Jeśli użyjesz Comparator zamiast Comparable , podczas tworzenia kolekcji musisz przekazać obiekt Comparator do konstruktora kolekcji:

TreeSet treeSet = new TreeSet(customComparator);

A co jeśli masz inny rodzaj kolekcji? Jak to sortujesz? W tym przypadku odpowiedni jest drugi sposób klasy narzędziowej Collections — metoda sort() . Metoda jest statyczna, więc wystarczy dodać na początek nazwę klasy, a następnie przekazać listę do posortowania. Na przykład:

Collections.sort(someList);

Jeśli używasz implementacji Comparator zamiast Comparable , musisz przekazać ją jako drugi argument:

Collections.sort(someList, customComparator);

Ta operacja zmieni wewnętrzną kolejność elementów na przekazanej liście: lista zostanie posortowana za pomocą komparatora. Należy pamiętać, że przekazana lista musi być modyfikowalna, w przeciwnym razie metoda zakończy się niepowodzeniem i zgłosi wyjątek UnsupportedOperationException . Trzecią opcją jest użycie sortowanej metody klasy Stream , która sortuje elementy kolekcji. Jeśli używamy Comparable :

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

Jeśli używamy komparatora :

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

Czwarty sposób polega na ręcznym zaimplementowaniu algorytmu sortowania, na przykład sortowania bąbelkowego lub sortowania przez scalanie .

Klasa obiektu. równa się() i hashCode()

94. Podaj krótki opis klasy Object w Javie.

W drugiej części recenzji omówiliśmy już metody klasy Object . Tutaj przypomnę, że klasa Object jest przodkiem każdej klasy w Javie. Posiada 11 metod, które z kolei są dziedziczone przez wszystkie klasy.

95. Do czego służą funkcje równości() i hashCode() w Javie?

hashCode() to metoda klasy Object , która jest dziedziczona przez wszystkie klasy. Jego zadaniem jest wygenerowanie liczby reprezentującej konkretny obiekt. Przykład działania tej metody można znaleźć w HashMap , gdzie jest ona wywoływana na kluczowych obiektach w celu pobrania lokalnego kodu skrótu, który określi, w którym zasobniku (komórce tablicy wewnętrznej) będzie przechowywana para klucz-wartość. Ponadto, metoda ta jest powszechnie stosowana w metodzie równości() jako jeden z głównych sposobów identyfikacji obiektów. quals() to metoda klasy Object , której zadaniem jest porównywanie obiektów i sprawdzanie, czy są sobie równe. Metodę tę stosuje się wszędzie tam, gdzie musimy porównać obiekty, ponieważ standardowy operator porównania == nie nadaje się do obiektów, ponieważ porównuje jedynie odniesienia do obiektów.

96. Opowiedz nam o kontrakcie pomiędzy równościami() i hashCode() w Javie?

Na początek powiem, że aby metody równości() i hashCode() działały poprawnie, należy je poprawnie zastąpić. Ich nowe wdrożenia muszą spełniać następujące zasady:

• Identyczne obiekty, dla których równa się zwraca wartość true, muszą mieć te same kody skrótu.
• Obiekty z tymi samymi kodami skrótu niekoniecznie są równe.

Wydaje się, że to dobry moment na przerwę do następnej części recenzji!