Pytania rekrutacyjne z algorytmów i struktur danych z odpowiedziami

Przykładowe pytania

Kilka pytań z każdego poziomu z poprawną odpowiedzią i wyjaśnieniem.

Algorytmy i struktury danych · Junior

1. Co opisuje notacja Big O?

   Poprawna odpowiedź: Jak rośnie czas działania lub pamięć wraz z rozmiarem danych wejściowych

   Big O opisuje tempo wzrostu: jak zmienia się koszt, gdy rośnie n, pomijając stałe i składniki niższego rzędu. Nie mówi nic o czasie na konkretnej maszynie: pętla O(n) dla małych danych bywa wolniejsza niż O(n²).

2. Dlaczego O(2n + 10) zapisuje się po prostu jako O(n)?

   Poprawna odpowiedź: Bo stałe i składniki niższego rzędu nie zmieniają tempa wzrostu

   Big O opisuje kształt wzrostu dla dużych n. Mnożenie przez 2 czy dodanie 10 nie zmienia tego, że koszt rośnie liniowo, więc się je pomija. W praktyce stałe nadal się liczą i dlatego istnieją benchmarki.

3. Która złożoność rośnie najwolniej wraz ze wzrostem n?

   Poprawna odpowiedź: O(log n)

   Logarytm rośnie bardzo wolno: podwojenie n dodaje tylko jeden krok. Dla miliona elementów log₂ n to około 20. O(n) i O(n log n) rosną dużo szybciej.

4. Jaka jest złożoność odczytu arr[i] z tablicy w JavaScripcie?

   Poprawna odpowiedź: O(1)

   Dostęp po indeksie działa w czasie stałym: silnik oblicza, gdzie leży element, zamiast przechodzić tablicę. To główna przewaga tablic nad listami wiązanymi.

Algorytmy i struktury danych · Middle

1. Jak działa sortowanie przez scalanie?

   Poprawna odpowiedź: Dzieli tablicę na połowy, sortuje każdą i je scala

   Sortowanie przez scalanie dzieli tablicę aż do pojedynczych elementów, a potem scala posortowane połowy dwoma wskaźnikami. Ma O(n log n) w każdym przypadku i jest stabilne, ale potrzebuje O(n) dodatkowej pamięci na scalanie.

2. Jaka jest główna wada sortowania przez scalanie na tablicach?

   Poprawna odpowiedź: Potrzebuje O(n) dodatkowej pamięci na scalanie

   Krok scalania zapisuje do tymczasowego bufora. Czas to O(n log n) niezależnie od danych, a klasyczna implementacja jest stabilna. Na listach wiązanych scalanie da się zrobić bez dodatkowego bufora.

3. Jaki jest najgorszy przypadek quicksorta i kiedy występuje?

   Poprawna odpowiedź: O(n²), gdy elementy osiowe ciągle dzielą tablicę bardzo nierówno

   Jeśli element osiowy jest zawsze najmniejszy lub największy (np. pierwszy element posortowanej tablicy), każdy podział odcina tylko jeden element. Losowy element osiowy lub mediana z trzech sprawiają, że jest to mało prawdopodobne; średnio O(n log n).

4. Dlaczego quicksort jest w praktyce często szybszy od sortowania przez scalanie, choć oba mają średnio O(n log n)?

   Poprawna odpowiedź: Sortuje w miejscu i odczytuje pamięć sekwencyjnie

   Podział działa wewnątrz tablicy z dobrą lokalnością pamięci podręcznej i małymi stałymi. Jego najgorszy przypadek jest w rzeczywistości gorszy (O(n²)), a zwykła wersja w miejscu nie jest stabilna.

Algorytmy i struktury danych · Senior

1. Dlaczego algorytm Dijkstry daje błędne wyniki przy ujemnych wagach krawędzi?

   Poprawna odpowiedź: Zamknięty wierzchołek wciąż może się skrócić przez ujemną krawędź

   Dijkstra zakłada, że gdy najbliższy wierzchołek zostanie wyjęty z kolejki, żadna późniejsza ścieżka nie będzie krótsza. Ujemna krawędź łamie to założenie. Bellman-Ford obsługuje ujemne wagi w O(V × E) i dodatkowo wykrywa ujemne cykle.

2. Jaką dodatkową możliwość ma Bellman-Ford w porównaniu z Dijkstrą?

   Poprawna odpowiedź: Działa z ujemnymi wagami i wykrywa ujemne cykle

   Relaksuje wszystkie krawędzie V - 1 razy; jeśli V-te przejście wciąż poprawia odległość, istnieje ujemny cykl. Ceną jest O(V × E), dużo wolniej niż O((V + E) log V) u Dijkstry.

3. Czym A* różni się od algorytmu Dijkstry?

   Poprawna odpowiedź: Dodaje oszacowanie pozostałej odległości

   A* porządkuje wierzchołki według g + h: znany koszt plus oszacowanie do celu, np. odległość w linii prostej na mapie. Jeśli h nigdy nie przeszacowuje (heurystyka dopuszczalna), ścieżka nadal jest optymalna, a odwiedza się dużo mniej wierzchołków.

4. Jaka jest złożoność Floyda-Warshalla i kiedy jest rozsądnym wyborem?

   Poprawna odpowiedź: O(V³); dla najkrótszych ścieżek między wszystkimi parami w małych gęstych grafach

   To trzy zagnieżdżone pętle po wierzchołkach, aktualizujące dist[i][j] przez każdy pośredni k. Prosty i radzi sobie z ujemnymi krawędziami (bez ujemnych cykli), ale przy V = 10 000 to już 10¹² kroków.