Rozmowa kwalifikacyjna z Javy – Żaden problem! Cz. IX – Algorytmy i struktury danych

Rozmowy kwalifikacyjne z Javy - Żaden problem cz IX - algorytmy i struktury danych

Rozmowy kwalifikacyjne z Javy – Żaden problem cz IX – algorytmy i struktury danych

Mimo długiego czasu od ukazania poprzedniego artykułu z serii o rozmowach kwalifikacyjnych z Javy zauważyliśmy niesłabnące zainteresowanie artykułami o tej tematyce. Postanowiliśmy więc odświeżyć trochę tą serię i dodać kilka kolejnych tematów, tak abyście mogli dokładniej przygotować się do swoich przyszłych spotkań rekrutacyjnych. W tym artykule poruszymy jeden z najbardziej (nie)lubianych tematów pojawiających się na rozmowach – algorytmów i struktur danych. Warto zauważyć iż jest to temat agnostyczny względem języka, pojawia się on w każdym języku programowania i na każdym poziomie zaawansowania, dlatego w naszej opinii warto poświęcić chwilę czasu na przyswojenie wiedzy z tej dziedziny. Do rozwiązań będziemy wykorzystywać język Java (jako iż jest to mój „główny” język programowania), aczkolwiek zestaw kroków potrzebnych do stworzenia algorytmu będzie przedstawiony w sposób ogólny. W tym artykule zaczniemy od podstaw dotyczących algorytmów i struktur, natomiast w następnym (następnych?) postaramy się poruszyć bardziej skomplikowane tematy. Tym niemniej, polecam przeczytanie tego artykułu wszystkim, aby być może uporządkować swoją wiedzę. Zapraszamy do lektury!

  1. Czym tak właściwie jest algorytm?

Pytanie, które często pojawia się na rozmowach dotyczących pozycji juniorskich. Teoretyczna definicja mówi brzmi:

„Skończony, uporządkowany ciąg elementarnych, jasno zdefiniowanych czynności, których wykonanie  pozwala na rozwiązanie ustalonego problemu”

W praktyce informatycznej oznacza to skończoną ilość prostych kroków, które musi wykonać nasz program aby z danych wejściowych, przejść do wymaganych wyjściowych. Metaforycznym uproszczonym przykładem może być chociażby „algorytm” parzenia herbaty – aby zaparzyć herbatę, musimy w kolejnych krokach najpierw wyciągnąć kubek, wybrać herbatę, wrzucić herbatę do kubka, zagotować wodę, poczekać aż ostygnie do odpowiedniej temperatury (dla danego rodzaju herbaty), a następnie zalać kubek tą wodą. Z danych wejściowych – kubka/herbaty/wody – otrzymaliśmy produkt końcowy – herbatę.

  1. Czym są struktury danych?

W naukach o technologiach informacyjnych są one sposobem na przechowywanie oraz zarządzanie większymi ilościami danych w określony sposób, umożliwiający efektywne ich wykorzystanie oraz składowanie. Algorytmy działają na strukturach danych, a odpowiednie dobrane struktury danych umożliwiają efektywne działanie algorytmów. Niektóre ze sposobów przechowywania danych są ściśle wyspecjalizowane w wykonywaniu jednej czynności – np. pobieraniu danych ze zbioru. Przykładami mogą być takie struktury jak Kolejka (Queue), Lista czy Tabela.

  1. W jaki sposób opisywana jest złożoność algorytmów?

Podstawowym narzędziem, które służy do analizy algorytmów jest tzw. Big O Notation, które w zwięzły sposób pozwala opisać złożoność algorytmu. Jest to funkcja, zależna od ilości danych wejściowych, obliczana na podstawie kroków potrzebnych do wykonania danej czynności. Dzięki tej funkcji jesteśmy w stanie określić jak szybko rośnie czas wykonania danej czynności, w zależności od ilości elementów. Brzmi skomplikowanie? Na ratunek lecą przykłady ukazujące w jaki sposób możemy obliczyć złożoność:

Rys. 1 Przykładowa metoda zwracająca indeks szukanego imienia w tablicy imion.

Rys. 1 Przykładowa metoda zwracająca indeks szukanego imienia w tablicy imion.

 

Jak oszacować złożoność tej metody? W najlepszym wypadku, kiedy szukane imię znajdzie się na pierwszym miejscu w danej tablicy, metoda wykona się praktycznie natychmiastowo, nie przechodząc przez kolejne elementy tablicy. Taki opis nie daje nam jednak praktycznie żadnej użytecznej wiedzy – my, jako programiści musimy założyć (uśredniony) najgorszy możliwy obrót sprawy. Zobaczmy więc, że im więcej elementów w tablicy, tym dłuższy czas wykonania (gdyż przez więcej elementów musimy przejść), dla przykładu gdy szukane imię będzie na ostatnim miejscu, to dla 100 elementów będziemy musieli wykonać 100 porównań, natomiast jeżeli tablica będzie posiadała tych elementów 100_000, to liczba porównań wzrośnie liniowo do 100_000 porównań. Daje nam to więc zależność liniową O(n). Zobaczmy następny przykład gdy będziemy chcieli wypisać kombinację wszystkich słów, aby utworzyć dwuczłonową nazwę zespołu:

 

Rys.  2 Krótki program, który beznadziejnie próbuje nam pomóc w wymyśleniu nazwy zespołu. Chociaż Refactor Annihilation chyba nie brzmi tak źle ;-)

Rys.  2 Krótki program, który beznadziejnie próbuje nam pomóc w wymyśleniu nazwy zespołu. Chociaż Refactor Annihilation chyba nie brzmi tak źle 😉

 

Widzimy tutaj że przez całą listę słów podanych do naszej metody będziemy musieli przejść dwukrotnie, aby wykonać zleconą czynność. Tak więc dla listy imion o długości 4, będziemy musieli wykonać 16 wpisów do konsoli, dla 10 wzrośnie to do 100, a dla 1000 elementów aż do 1_000_000. Widzimy więc że ilość operacji do wykonania rośnie w tempie kwadratowym, oznaczanym przez O(n^2). Warto wspomnieć że notacja ta jest wykorzystywana również do obrazowania w jakim tempie zwiększa się zużycie pamięci potrzebne do wykonania algorytmy. A więc jeżeli zużycie pamięci naszego programu rośnie kwadratowo w stosunku do ilości danych wejściowych, to mamy zużycie rzędu O(n^2).

Rys.  3 Podstawowe oznaczenia złożoności algorytmu, oraz ich zmiana dla 10/50/100 elementów.

Rys.  3 Podstawowe oznaczenia złożoności algorytmu, oraz ich zmiana dla 10/50/100 elementów.

 

  1. Jak działa kolejka (Queue)? Jakie metody powinna posiadać kolejka?

Zacznijmy od przypomnienia, czym jest kolejka. Kolejka jest to struktura danych, która charakteryzuje się tym że pierwszy element, który trafi do kolejki, opuszcza kolejkę pierwszy (FIFO – First In First Out). Potrzebujemy więc przede wszystkim dwóch podstawowych operacji, zakolejkowania (enqueue) służącego dodaniu elementu do kolejki, oraz wyciągnięcia elementu z kolejki (dequeue). W javie występują odpowiedniki tych operacji – enqueue to add(e)/offer(e), natomiast dequeue to remove()/poll(). Oprócz tego przydają nam się również metody która pozwalają na podejrzenie pierwszego elementu kolejki (peek), sprawdzenie czy kolejka jest pusta (isEmpty) oraz czy jest pełna (isFull). Przykładem kolejki może być zwykła kolejka w sklepie, w której osoby stojące na przodzie kolejki (te które stanęły tam wcześniej) podejdą do kasy jako pierwsze.

  1. Jak działa stos (Stack)? Jakie metody powinien posiadać stos?

Podobnie jak w poprzednim pytaniu przypomnimy najpierw czym jest stos. Charakterystyczną cechą stosu jest to że w przeciwności do kolejki działa on na zasadzie LIFO (Last In First Out), w myśl której, elementy dodane do stosu jako ostatnie, opuszczą stos pierwsze. Działaniem przypomina on stertę książek ułożoną w kartonie – aby wyciągnąć książkę położoną na dnie pudełka, musimy najpierw wyjąć wszystkie książki znajdujące się nad nią. Dwie główne metody wykorzystywane w stosie to push oraz pop, odpowiadające kolejno za dodanie elementu na stos (push) oraz zdjęcie najwyższego elementu (pop). Dodatkowo, podobnie jak w przypadku kolejki, przydatne są metody peek, isEmpty i isFull, odpowiadające za te same czynności co w poprzednim opisywanym typie struktury.

  1. Czy jest możliwe zaimplementowanie kolejki używając samych stosów? Jeżeli tak to jak będą wyglądały operacje zakolejkowania oraz wyciągnięcia elementu?

Tak, istnieje możliwość zaimplementowania kolejki tylko przy wykorzystaniu samych stosów. Do wykonania tego zadania potrzebujemy dwóch stosów w których będziemy składać swoje dane. Aby ta implementacja miała sens, musimy wymyślić sposób, aby móc przeprowadzić operacje enqueue oraz dequeue zgodnie z definicją podaną w opisie kolejki. Operację zakolejkowania możemy przedstawić w następujący sposób

  • Jeżeli stos pierwszy nie jest pusty, przesuń wszystko ze stosu pierwszego do drugiego
  • Dodaj element do stosu pierwszego,
  • Przerzuć wszystko ze stosu drugiego do stosu pierwszego.

Natomiast operację wyciągnięcia z kolejki możemy przedstawić w następujących krokach:

  • Jeżeli stos pierwszy jest pusty, zwrócić błąd,
  • Zwrócić najwyższy element ze stosu pierwszego.

Przedstawiona implementacja spełnia wszystkie założenia podawane przez kolejki. Poniżej przykładowy kod takiej kolejki w Javie:

Rys.  4 Przykładowa implementacja kolejki przy pomocy dwóch stosów.

Rys.  4 Przykładowa implementacja kolejki przy pomocy dwóch stosów.

 

  1. Dla powyższej implementacji kolejki, jakie byłaby wydajność czasowa?

Takie pytanie może się często pojawić po tym jak zostaniemy zapytani o powyższą implementację. W zależności od tego w jaki sposób zaimplementowaliśmy naszą kolejkę, różnicy się mogą wydajności czasowe poszczególnych operacji. Dla powyższego przykładu zacznijmy od operacji wyciągnięcia elementu z kolejki. W metodzie wykonujemy właściwie tylko dwie operacje – sprawdzenie czy stos pierwszy jest pusty, oraz wyciągniecie górnego elementu z kolejki pierwszej. Obie te metody wykonują się w czasie O(1), a więc ogólna wydajność czasowa tej operacji wynosi O(1), czyli jest stała w czasie, niezależnie od ilości elementów. Operacja zakolejkowania jest bardziej ciekawa. Operacje włożenia oraz zdjęcia elementu na stosu mają wydajność O(1), natomiast są one wywoływane w pętli while, zależnej od ilości elementów, które już dodaliśmy do kolejki. Dwukrotne iterowanie po wszystkich elementach daje nam wydajność O(n), gdzie n to ilość elementów na stosie pierwszym. Dodatkowa uwaga – mimo iż dwukrotnie przerzucamy elementy pomiędzy stosami i zdrowy rozsądek podpowiada nam że wydajność powinna wynosić 2 * O(n), to w podawaniu wydajności pomijamy stałe, które znajdują się przed funkcją wydajności.

  1. Opisz sposób działania sortowania przez wstawianie (Insertion Sort). Jaka jest wydajność czasowa tego sortowania?

Sortowanie przez wstawianie jest jednym z prostszych algorytmów sortowania. Jest on raczej rzadko wykorzystywany w praktyce, ze względu na niską wydajność. Niekiedy jednak na rozmowach pojawia się to pytanie ze względu na prostotę działania tego algorytmu i możliwość szybkiej implementacji przez kandydata. Aby posortować dane nieposortowane należy:

  • Ustawić znacznik posortowanej części po pierwszym elemencie z listy,
  • Wybrać pierwszy nieposortowany numer,
  • Przesuwać ten numer w lewo przy pomocy zamiany miejsc z sąsiednim numerem, do momentu aż znajdzie się on na odpowiedniej pozycji (tj. będzie mniejszy niż prawy sąsiad i (w przypadku gdy nie jest to początek listy) większy bądź równy lewemu sąsiadowi
  • Przesunąć znacznik posortowanej części o jeden element w prawo,
  • Powtarzać kroki 2 – 4 do momentu aż znacznik posortowanej części dotrze do końca naszej listy danych.

Już na pierwszy rzut oka widać że nie jest to zbyt wydajny algorytm. W najgorszym wypadku jego wydajność wynosi O(n^2), w najlepszym (gdy dane są ustawione w odpowiedniej kolejności), O(n).

I to na razie kończy ten artykuł. Dajcie znać czy wszystko jak na razie jest zrozumiałe i czytelne, w następnej części będziemy starali się Wam przybliżyć coraz trudniejsze algorytmy i ich implementacje. Do przeczytania!

Poprzednie artykuły z cyklu: 

Rozmowa kwalifikacyjna z Javy? Żaden problem! – cz. I (String)

Rozmowa kwalifikacyjna z Javy? Żaden problem! – cz. II (Kolekcje)

Rozmowa kwalifikacyjna z Javy? Żaden problem! Cz. III (Core)

Rozmowa kwalifikacyjna z Javy? Żaden problem! Cz. IV (Multithreading)

Rozmowa kwalifikacyjna z Javy? Żaden problem! Cz. V (Wzorce projektowe)

Rozmowa kwalifikacyjna z Javy? Żaden problem! Cz. VI (Spring)

Rozmowa kwalifikacyjna z Javy? Żaden problem! Cz. VII (Spring)

Rozmowa kwalifikacyjna z Javy? Żaden problem! Cz. VIII (JPA)

 

Marek Makuch 

 

IT-Leaders.pl to pierwsza na rynku platforma łącząca Specjalistów IT bezpośrednio z pracodawcami. Anonimowy, techniczny profil i konkretnie określone oczekiwania finansowe to tylko niektóre z cech wyróżniających platformę. Zarejestruj się i zobacz jak Cię widzi pracodawca.

Może Ci się również spodoba

Dodaj komentarz

Twój adres email nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *