Baza pytań rekrutacyjnych i wiedzy. Filtruj, szukaj i sprawdzaj swoją wiedzę.
Wyszukiwanie binarne znajduje element w posortowanej tablicy/liście, porównując go ze środkiem i odrzucając połowę zakresu w każdym kroku. Wymaga danych posortowanych i działa w czasie O(log n) (iteracyjnie zużywa O(1) pamięci).
Oba to sortowania divide‑and‑conquer. QuickSort dzieli dane względem pivota, działa in‑place i zwykle jest szybki średnio O(n log n), ale ma pesymistyczne O(n²) i nie jest stabilny. MergeSort dzieli i scala, jest stabilny i gwarantuje O(n log n) w pesymistycznym przypadku, ale wymaga O(n) dodatkowej pamięci i dobrze sprawdza się na listach wiązanych oraz przy sortowaniu zewnętrznym.
BFS przeszukuje graf poziomami używając kolejki i znajduje najkrótszą ścieżkę w grafach nieważonych. DFS schodzi jak najgłębiej używając rekurencji/stosu; przydaje się do sortowania topologicznego, wykrywania cykli i często zużywa mniej pamięci na szerokich grafach.
Algorytm Dijkstry wyznacza najkrótsze ścieżki z jednego źródła w grafie o nieujemnych wagach krawędzi. Wielokrotnie wybiera najbliższy nieodwiedzony wierzchołek (zwykle przez kolejkę priorytetową) i relaksuje krawędzie wychodzące, osiągając O((V+E) log V) z kopcem.
Programowanie dynamiczne rozwiązuje problem przez rozbicie go na mniejsze podproblemy i zapisanie wyników, żeby nie liczyć tego samego wiele razy. Stosuj je, gdy podproblemy się powtarzają, a najlepsze rozwiązanie da się złożyć z najlepszych rozwiązań części (memoizacja/top‑down lub tabela bottom‑up).
BFS idzie warstwami i znajduje najkrótszą ścieżkę w grafie nieważonym. DFS schodzi w głąb i jest wygodny do przeglądania, wykrywania cykli i problemów typu topologicznego.
Big-O opisuje, jak rośnie czas lub pamięć wraz z rozmiarem danych n (tempo wzrostu). Pozwala porównywać algorytmy niezależnie od sprzętu.
Trzymasz dwa wskaźniki/indeksy (np. lewy/prawy) i przesuwasz je wg reguły, często na posortowanej tablicy lub w oknie przesuwnym. W wielu zadaniach pozwala zejść z dwóch pętli do O(n).
Sortowanie stabilne zachowuje kolejność elementów o równych kluczach. Jest ważne przy sortowaniu po wielu polach (np. najpierw po nazwisku, potem po imieniu).
Zachłanny wybiera lokalnie najlepszy krok i do niego nie wraca; działa tylko, gdy problem ma własność zachłannego wyboru. DP rozwiązuje nachodzące na siebie podproblemy i reuse’uje wyniki (memoization/tabulation), by zapewnić optimum.
Typowe błędy to niespójne granice (pętla nieskończona) i overflow przy liczeniu środka. Użyj `mid = left + (right - left) / 2` i trzymaj się konsekwentnie zakresu (inclusive/exclusive).
Jeśli wszystkie krawędzie mają ten sam koszt (np. 1), BFS znajduje najkrótsze ścieżki. Gdy wagi są tylko 0 lub 1, można użyć 0–1 BFS na deque; w innych przypadkach potrzebujesz Dijkstry.
To porządek wierzchołków taki, że każda krawędź u→v prowadzi od wcześniejszego do późniejszego. Istnieje tylko dla DAG (grafu skierowanego acyklicznego); cykl oznacza brak poprawnej kolejności.
Znajduje maksymalną sumę spójnego (ciągłego) podciągu w O(n), śledząc najlepszą sumę „kończącą się tutaj” i najlepszą globalnie.
KMP liczy funkcję prefiksową (LPS), dzięki czemu przy niedopasowaniu przesuwa wzorzec bez ponownego sprawdzania znaków. To daje O(n+m) zamiast O(n·m).
Rekurencja to sytuacja, gdy funkcja rozwiązuje problem wywołując samą siebie dla mniejszego wejścia. Base case to warunek stopu bez dalszej rekurencji, dzięki czemu wywołania w końcu się kończą.
Memoization to cache’owanie wyników funkcji dla danych wejść, żeby kolejne wywołania brały wynik z pamięci. Pomaga przy nachodzących na siebie podproblemach (typowo w DP), gdy te same stany liczone są wiele razy.
Quickselect znajduje k-ty najmniejszy element przez partycjonowanie jak QuickSort, ale schodzi rekurencyjnie tylko w jedną stronę. Średnio działa w O(n), a w najgorszym przypadku O(n²) (złe pivoty).
Dijkstra zakłada, że gdy wierzchołek ma najmniejszy znany dystans, to później już się nie poprawi — ujemne wagi łamią to założenie. Dla ujemnych wag użyj Bellman–Forda (potrafi też wykryć ujemne cykle).
Monotonic stack trzyma elementy w kolejności rosnącej albo malejącej. Używa się go do zadań typu „next greater/smaller element”, stock span czy histogram — często w O(n), bo każdy element jest wrzucany i zdejmowany co najwyżej raz.
Loop invariant to własność, która jest prawdziwa przed i po każdej iteracji pętli. Pomaga udowodnić poprawność: jeśli jest prawdziwa na początku, pozostaje prawdziwa w każdym kroku i daje cel na końcu, algorytm jest poprawny.
Top-down to rekurencja z memoization (liczenie stanów na żądanie). Bottom-up wypełnia tabelę iteracyjnie od mniejszych podproblemów do większych. Oba podejścia reuse’ują wyniki; wybór zależy od czytelności i kontroli pamięci.
Losowy pivot zmniejsza szansę trafienia „złośliwego” wejścia powodującego najgorszy przypadek O(n²). W praktyce daje dobrą oczekiwaną wydajność i unika wzorców typu już-posortowane dane.
Dijkstra rozwija wierzchołki według aktualnego dystansu. A* dodaje heurystykę `h(n)` (szacowany koszt do celu) i priorytetyzuje `g(n)+h(n)`. Przy heurystyce dopuszczalnej (nie zawyża), A* jest optymalny i zwykle odwiedza mniej węzłów, więc bywa szybszy.
Kruskal sortuje krawędzie i dodaje najmniejsze, które nie tworzą cyklu (używa Union-Find). Prim rozbudowuje drzewo od startu, używając kolejki priorytetowej. Oba mogą mieć O(E log E) / O(E log V) zależnie od implementacji.
Backtracking to przeszukiwanie w głąb drzewa decyzji: budujesz częściowe rozwiązanie, a gdy staje się niepoprawne, cofasz ostatni wybór i próbujesz innej opcji. Stosuje się go m.in. w permutacjach, N-hetmanach, Sudoku i przeszukiwaniu podzbiorów z pruningiem.
Amortyzowane oznacza “średni koszt na operację w dłuższej sekwencji”, nawet jeśli pojedyncza operacja bywa droga. W dynamicznej tablicy większość appendów to O(1), a czasem płacisz O(n) za resize/kopiowanie — rozłożone na wiele appendów daje O(1) amortyzowane.
Counting sort ma sens, gdy klucze to liczby całkowite z małego zakresu 0..k. Działa w O(n + k), bo zlicza wystąpienia i buduje wynik, i może być stabilny (przydatne jako element radix sort).
Problemy NP-zupełne są jednocześnie w NP (rozwiązanie da się zweryfikować w czasie wielomianowym) i są NP-trudne. NP-trudne oznacza “co najmniej tak trudne jak problemy z NP”, ale nie musi należeć do NP (np. wersje optymalizacyjne). Jeśli jakikolwiek problem NP-zupełny ma algorytm wielomianowy, to P = NP.
Floyd–Warshall liczy najkrótsze ścieżki między wszystkimi parami wierzchołków. Ma czas O(V^3) i pamięć O(V^2), więc jest praktyczny głównie dla mniejszych lub gęstych grafów. Obsługuje ujemne krawędzie, ale nie ujemne cykle.
Tablica sum prefiksowych przechowuje sumę do danego indeksu. Po preprocessingu O(n) możesz liczyć sumę na przedziale w O(1): suma[l..r] = prefix[r] - prefix[l-1]. Używa się tego też do zliczania i szybkich zapytań typu “ile w zakresie”.
Sliding window utrzymuje przesuwające się okno [l..r] i aktualizuje je w jednym przebiegu. Zwiększasz `r` i przesuwasz `l`, żeby spełnić warunek (np. suma <= X, maks. K różnych). Wiele zadań spada z O(n^2) do O(n), bo każdy wskaźnik przesuwa się w prawo maksymalnie n razy.
Rolling hash pozwala szybko zaktualizować hash okna po przesunięciu o 1 znak (usuń lewy, dodaj prawy). Rabin–Karp porównuje hashe, żeby znaleźć kandydatów, a potem zwykle weryfikuje substring, żeby uniknąć fałszywych trafień. Haczyk: możliwe są kolizje hashy, więc bez weryfikacji nie masz gwarancji poprawności.
Kolejka monotoniczna to deque trzymany w porządku malejącym (lub rosnącym). Dla maksimum w oknie usuwasz z końca mniejsze elementy przy dodawaniu nowego, więc na początku zawsze jest max. Usuwasz też z początku elementy, które wyszły z okna. Każdy element wchodzi i wychodzi maks. raz, więc całość to O(n).
Bitmask DP używa maski bitowej do reprezentacji podzbioru (np. które wierzchołki odwiedziłeś). Klasyczny zapis: dp[mask][i] = najlepszy wynik dla podzbioru `mask` kończący się w `i` (np. w TSP). Typowa złożoność jest wykładnicza, często O(n^2 * 2^n) czasu i O(n * 2^n) pamięci.
Algorytm zachłanny jest poprawny, gdy problem ma własność greedy-choice oraz optimal substructure. Intuicyjnie da się to udowodnić argumentem wymiany: lokalnie najlepszy wybór można „wymienić” w rozwiązaniu optymalnym, więc lokalny wybór prowadzi do globalnego optimum.
KMP wylicza dla wzorca tablicę LPS (najdłuższy proper prefix będący jednocześnie suffixem). Przy niedopasowaniu przesuwa wzorzec zgodnie z LPS zamiast cofać wskaźnik tekstu, więc znaki tekstu nie są porównywane ponownie.
Bellman–Ford stosujesz, gdy występują ujemne wagi krawędzi. Potrafi wykryć ujemne cykle przez dodatkową rundę relaksacji. Minusem jest wolniejsza złożoność: O(V·E).
Kruskal buduje MST, sortując krawędzie i dodając je, jeśli nie tworzą cyklu (zwykle z DSU/Union‑Find). Prim rozrasta MST od wybranego wierzchołka, używając kolejki priorytetowej. Kruskal bywa lepszy dla grafów rzadkich, a Prim wygodny przy listach sąsiedztwa.
Quickselect służy do znalezienia k‑tego elementu (np. mediany) bez pełnego sortowania tablicy. Używa partycjonowania jak quicksort i ma oczekiwane O(n), ale w najgorszym przypadku może spaść do O(n^2).
Stosuje się to, gdy możesz zdefiniować monotoniczny predykat po przestrzeni odpowiedzi (np. „czy istnieje rozwiązanie z wartością ≤ X?”). Wtedy binarnie wyszukujesz minimalne/maksymalne X spełniające warunek.
Wykrywa cykle w liście lub dowolnej sekwencji iteracyjnej, przesuwając jeden wskaźnik dwa razy szybciej niż drugi. Jeśli się spotkają, jest cykl. Działa w O(n) czasu i O(1) pamięci.
Heapsort działa w O(n log n), używa O(1) dodatkowej pamięci (in‑place) i nie jest stabilny (równe elementy mogą zmienić kolejność).
A* używa f(n) = g(n) + h(n). Jeśli heurystyka h jest dopuszczalna (nie przeszacowuje) i spójna, A* jest optymalny i odwiedza mniej węzłów niż Dijkstra. Gdy h przeszacowuje, optymalność nie jest gwarantowana. Dla h = 0 A* redukuje się do Dijkstry.
Znajduje element występujący więcej niż n/2 razy (jeśli istnieje). Idea polega na „kasowaniu” par różnych elementów; pozostały kandydat to większość. Działa w O(n) czasu i O(1) pamięci.