Algorytmy
Baza pytań rekrutacyjnych i wiedzy. Filtruj, szukaj i sprawdzaj swoją wiedzę.
easysearchbinary-searchalgorithm+1
Odpowiedź
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).
function binarySearch(arr: number[], target: number): number {
let left = 0;
let right = arr.length - 1;
while (left <= right) {
const mid = Math.floor((left + right) / 2);
if (arr[mid] === target) return mid;
if (arr[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}mediumsortingquicksortmergesort+2
Odpowiedź
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.
mediumgraphbfsdfs+2
Odpowiedź
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.
hardgraphshortest-pathdijkstra+1
Odpowiedź
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.
harddynamic-programmingoptimizationmemoization
Odpowiedź
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).
easybfsdfsgraph+1
Odpowiedź
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.
function bfs(start: number, graph: number[][]) {
const q: number[] = [start];
const seen = new Set<number>([start]);
while (q.length) {
const v = q.shift()!;
for (const n of graph[v]) {
if (!seen.has(n)) {
seen.add(n);
q.push(n);
}
}
}
}easybig-ocomplexityperformance
Odpowiedź
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.
easytwo-pointersarraytechnique
Odpowiedź
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).
function hasPairSum(arr: number[], target: number) {
let l = 0;
let r = arr.length - 1;
while (l < r) {
const sum = arr[l] + arr[r];
if (sum === target) return true;
if (sum < target) l++;
else r--;
}
return false;
}mediumsortingstable-sortalgorithm
Odpowiedź
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).
mediumgreedydynamic-programmingoptimization
Odpowiedź
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.
mediumbinary-searchbugsoverflow
Odpowiedź
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).
function binarySearch(arr: number[], target: number): number {
let left = 0;
let right = arr.length - 1;
while (left <= right) {
const mid = left + Math.floor((right - left) / 2);
if (arr[mid] === target) return mid;
if (arr[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1;
}hardshortest-pathbfsdijkstra+1
Odpowiedź
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.
hardtopological-sortdaggraph
Odpowiedź
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.
function topoSort(n: number, edges: Array<[number, number]>) {
const indeg = Array(n).fill(0);
const g: number[][] = Array.from({ length: n }, () => []);
for (const [u, v] of edges) {
g[u].push(v);
indeg[v]++;
}
const q: number[] = [];
for (let i = 0; i < n; i++) if (indeg[i] === 0) q.push(i);
const order: number[] = [];
while (q.length) {
const u = q.shift()!;
order.push(u);
for (const v of g[u]) {
indeg[v]--;
if (indeg[v] === 0) q.push(v);
}
}
return order.length === n ? order : null; // null => cycle
}hardkadanedynamic-programmingarray
Odpowiedź
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.
function maxSubarraySum(nums: number[]): number {
let best = nums[0];
let cur = nums[0];
for (let i = 1; i < nums.length; i++) {
cur = Math.max(nums[i], cur + nums[i]);
best = Math.max(best, cur);
}
return best;
}hardkmpstring-searchpattern-matching
Odpowiedź
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).
easyrecursionbase-casecall-stack
Odpowiedź
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ą.
mediummemoizationdynamic-programmingcache
Odpowiedź
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.
function fib(n: number, memo = new Map<number, number>()): number {
if (n <= 1) return n;
const cached = memo.get(n);
if (cached !== undefined) return cached;
const value = fib(n - 1, memo) + fib(n - 2, memo);
memo.set(n, value);
return value;
}mediumquickselectpartitionselection+1
Odpowiedź
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).
harddijkstrabellman-fordnegative-weights+1
Odpowiedź
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).
hardstackmonotonic-stacknext-greater+1
Odpowiedź
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.
function nextGreater(nums: number[]): number[] {
const res = Array(nums.length).fill(-1);
const st: number[] = []; // stack of indices
for (let i = 0; i < nums.length; i++) {
while (st.length && nums[st[st.length - 1]] < nums[i]) {
res[st.pop()!] = nums[i];
}
st.push(i);
}
return res;
}easycorrectnessinvariantloops
Odpowiedź
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.
mediumdynamic-programmingmemoizationtabulation
Odpowiedź
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.
mediumrandomizationquicksortquickselect+1
Odpowiedź
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.
harda-stardijkstraheuristics+1
Odpowiedź
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.
hardmstkruskalprim+2
Odpowiedź
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.
easybacktrackingsearchpruning+1
Odpowiedź
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.
mediumamortizedcomplexitydynamic-array+1
Odpowiedź
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.
mediumcounting-sortsortingstability+1
Odpowiedź
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).
hardcomplexity-theorynp-hardnp-complete+1
Odpowiedź
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.
hardgraphsshortest-pathfloyd-warshall+1
Odpowiedź
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.
easyprefix-sumrange-querypreprocessing
Odpowiedź
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”.
mediumsliding-windowtwo-pointerscomplexity
Odpowiedź
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.
mediumstringhashingrabin-karp+1
Odpowiedź
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.
harddequemonotonic-queuesliding-window+1
Odpowiedź
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).
harddpbitmasksubset+2
Odpowiedź
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.
mediumgreedycorrectnessexchange-argument+1
Odpowiedź
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.
hardkmpstringpattern-matching+1
Odpowiedź
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.
mediumbellman-fordshortest-pathgraphs+1
Odpowiedź
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).
mediummstkruskalprim+2
Odpowiedź
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.
mediumquickselectselectionpartition+1
Odpowiedź
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).
mediumbinary-searchparametric-searchmonotonic+1
Odpowiedź
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.
easycycle-detectiontortoise-harelinked-list+1
Odpowiedź
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.
mediumheapsortsortingcomplexity+1
Odpowiedź
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ść).
harda-starheuristicshortest-path+1
Odpowiedź
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.
mediummajority-votearraylinear-time+1
Odpowiedź
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.
function majority(nums: number[]): number {
let cand = 0;
let count = 0;
for (const x of nums) {
if (count === 0) cand = x;
count += x === cand ? 1 : -1;
}
return cand;
}