Baza pytań rekrutacyjnych i wiedzy. Filtruj, szukaj i sprawdzaj swoją wiedzę.
Tablica (lub dynamiczna tablica/ArrayList) trzyma elementy obok siebie w pamięci, więc dostęp losowy to O(1). Wstawianie/usuwanie w środku to O(n), bo trzeba przesuwać elementy (a przy powiększaniu często kopiować). Lista wiązana ma węzły połączone wskaźnikami: wstawienie/usunięcie w znanym miejscu to O(1), ale dostęp losowy to O(n) i jest większy narzut pamięci.
Poprawny JSON to tekstowy format obiektów i tablic używający {} i [], gdzie klucze i wartości tekstowe są w podwójnych cudzysłowach, a wartości mogą być tylko typu: string, number, boolean, null, tablica lub obiekt. Przykład: { "name": "Jan", "age": 30, "roles": ["dev"], "active": true }.
Stos to struktura LIFO, gdzie odkładasz i zdejmujesz elementy z wierzchołka (push/pop); używana np. w stosie wywołań, undo czy DFS. Kolejka to FIFO, gdzie dodajesz na końcu (enqueue) i zdejmujesz z początku (dequeue); używana do kolejkowania zadań, buforowania czy BFS.
HashMap trzyma pary klucz–wartość w kubełkach. Używa hashCode() klucza, aby wybrać kubełek, a equals() żeby znaleźć właściwy klucz w kubełku. Kolizje trzyma w liście/drzewku; po przekroczeniu progu load factor powiększa się i przelicza hashe, aby średnio utrzymać dostęp blisko O(1).
Drzewa zrównoważone (np. AVL, Red‑Black) to samo‑równoważące drzewa BST, które po wstawieniach i usunięciach wykonują rotacje, aby wysokość była rzędu log n. Gwarantuje to operacje wyszukiwania, wstawiania i usuwania w O(log n) nawet w pesymistycznym przypadku.
Set przechowuje unikalne wartości (bez duplikatów). Użyj go do szybkiego sprawdzania „czy element istnieje” i do usuwania duplikatów (np. unikalne ID użytkowników).
Kolejka priorytetowa wyjmuje element o najwyższym (lub najniższym) priorytecie, a nie najstarszy. Zwykle jest zaimplementowana kopcem, więc wstawienie/usunięcie to O(log n).
Deque pozwala dodawać i usuwać elementy zarówno z przodu, jak i z tyłu. Przy implementacji jako bufor cykliczny lub lista te operacje są O(1).
Macierz zajmuje O(V^2) pamięci i daje O(1) sprawdzenie krawędzi, więc jest dobra dla gęstych grafów. Lista zajmuje O(V+E) pamięci i lepiej pasuje do rzadkich grafów oraz iterowania po sąsiadach.
Trie przechowuje napisy po prefiksach: każdy węzeł reprezentuje znak. Umożliwia szybkie wyszukiwanie po prefiksie/autouzupełnianie; wyszukiwanie to O(L), gdzie L to długość słowa.
Przy chaining każdy kubełek trzyma listę/drzewo wpisów z tym samym hashem. Przy open addressing kolizje rozwiązuje się przez próbkowanie innych pól (linear/quadratic/double hashing). Chaining jest prostszy przy większym obciążeniu; open addressing jest cache-friendly, ale wymaga niższego load factor.
Większość dopisań trafia w wolne miejsce i kosztuje O(1). Czasem następuje powiększenie i kopiowanie O(n) elementów; rozłożone na wiele dopisań daje średnio O(1) na operację (amortyzacja).
AVL utrzymuje bardziej rygorystyczne zrównoważenie, więc wyszukiwanie bywa szybsze, ale wstawienia/usunięcia częściej wymagają równoważenia. Red-Black ma luźniejsze reguły, dzięki czemu aktualizacje są tańsze, a wysokość nadal jest O(log n).
Bloom filter to probabilistyczny zbiór do testów przynależności. Może zwracać fałszywie dodatnie wyniki (powie „jest”, choć nie ma), ale nie ma fałszywych negatywów. Jest bardzo oszczędny pamięciowo i szybki, ale nie pozwala odtworzyć elementów.
Union-Find (DSU) utrzymuje rozłączne zbiory operacjami find(x) (reprezentant) i union(a,b) (scalenie). Używa się go do spójności i w algorytmie Kruskala; z path compression + union by rank operacje są prawie O(1) amortyzowane.
Map przechowuje wartości pod kluczem (klucz → wartość). Użyj go, gdy chcesz szybko wyszukiwać po identyfikatorze (np. email → użytkownik), a nie po indeksie liczbowym; hash map zwykle ma O(1) średnio dla get/put.
LRU (Least Recently Used) usuwa element, którego najdłużej nie używano. Typowa implementacja w O(1): HashMap do lookupu key→węzeł + lista dwukierunkowa, aby po użyciu przesuwać element na początek i usuwać z końca.
Ring buffer to tablica o stałym rozmiarze używana jak kolejka z wskaźnikami head/tail, które zawijają się (mod pojemność). Przydaje się do strumieni i kolejek producer/consumer, bo unika alokacji i daje O(1) enqueue/dequeue.
Drzewo Fenwicka wspiera sumy prefiksowe i aktualizacje punktowe w O(log n) przy pamięci O(n). Użyj go, gdy masz dużo update’ów i zapytań typu „suma [0..i]” (np. problemy z częstotliwościami/licznikami).
Skip list to wielopoziomowa lista, gdzie część węzłów jest losowo „promowana” do wyższych poziomów. Daje oczekiwane O(log n) dla search/insert/delete (jak zbalansowane drzewa), jest prostsza w implementacji, ale ma probabilistyczną wydajność.
W min-heap każdy węzeł jest ≤ swoich dzieci (najmniejszy element jest w korzeniu). W max-heap każdy węzeł jest ≥ swoich dzieci. Dzięki temu peek jest O(1), a insert/remove O(log n).
Segment tree przechowuje agregaty na przedziałach (sum/min/max) i wspiera zapytania o zakresy oraz aktualizacje punktowe w O(log n). Przydaje się, gdy masz dużo zapytań typu „suma na [l..r]” i jednocześnie update’y.
Load factor to w przybliżeniu `liczba elementów / liczba kubełków`. Gdy jest zbyt wysoki, rośnie liczba kolizji i operacje zwalniają. Resize zwiększa liczbę kubełków i robi rehash, żeby utrzymać średnio O(1).
B-tree ma duży współczynnik rozgałęzienia, więc jest płytkie i robi mniej IO dyskowego (mniej odczytów stron). BST jest „wskaźnikowe” i głębsze; w pamięci działa OK, ale na dysku przegrywa z B-tree dopasowanym do stron.
To struktury do pracy ze stringami, używane do szybkich zapytań o podciągi i wzorce (np. „czy wzorzec P występuje w tekście T?”). Stosuje się je w indeksowaniu tekstu, wyszukiwaniu i bioinformatyce.
Bitset (bitmapa) przechowuje wartości true/false jako bity, więc jest bardzo oszczędny pamięciowo. Sprawdza się do szybkiej przynależności w małym, gęstym zakresie liczb (np. ID 0..N) oraz do szybkich operacji bitowych (AND/OR).
Rope reprezentuje długi napis jako drzewo mniejszych fragmentów. Może przyspieszać konkatenację oraz wstawianie/usuwanie w środku (bez kopiowania całego stringa), kosztem większej złożoności i zwykle wolniejszego dostępu po indeksie.
Persistent (niezmienna) struktura danych zwraca nową wersję przy “modyfikacji”, zamiast zmieniać się w miejscu. Structural sharing oznacza, że nowa wersja współdzieli większość węzłów ze starą, więc “kopiowanie” jest tanie (przydatne do historii/undo i bezpieczniejsze przy współbieżności).
Sparse table prelicza wyniki dla przedziałów o długości 2^k, dzięki czemu można szybko odpowiadać na statyczne zapytania o przedziały. Dla operacji idempotentnych (np. min/max/gcd) zapytanie jest O(1) po preprocessingu O(n log n), ale nie wspiera wydajnych aktualizacji.
Cuckoo hashing używa dwóch (lub więcej) funkcji hashujących, więc każdy klucz może leżeć w jednym z kilku miejsc. Odczyt jest prosty i O(1), ale wstawianie może wywołać “wypychanie” elementów łańcuchem; czasem trzeba zrobić rehash/resize, gdy pojawi się cykl.
Lista jednokierunkowa ma tylko wskaźnik `next`, więc jest prostsza i zużywa mniej pamięci. Lista dwukierunkowa ma `prev` i `next`, co ułatwia usuwanie znanego węzła oraz chodzenie wstecz, ale kosztuje więcej pamięci i aktualizacji wskaźników. Jednokierunkowa: gdy wystarczy przejście w przód. Dwukierunkowa: gdy często usuwasz w środku albo potrzebujesz przejścia wstecz.
Resize często oznacza alokację większej tablicy i przeliczenie (rehash) oraz przeniesienie wszystkich wpisów, czyli O(n) pracy naraz. To może zrobić pauzę i skok latencji. Jak temu zapobiegać: rozsądny load factor, pre-size gdy znasz rozmiar, inkrementalny rehash (przenoszenie stopniowo) albo użycie implementacji współbieżnej, która rozkłada pracę w czasie.
Jeśli budujesz kopiec metodą bottom-up (heapify), to większość węzłów jest blisko liści i przesuwa się o małą liczbę poziomów. Suma pracy dla wszystkich węzłów tworzy malejącą serię, która daje O(n). Wstawianie elementów po kolei to O(n log n), ale heapify bottom-up to O(n).
W B+ tree wszystkie rekordy (albo wskaźniki do rekordów) są w liściach, a węzły wewnętrzne trzymają tylko klucze do nawigacji. Liście są zwykle połączone, więc skany zakresowe są bardzo szybkie. To pasuje do dysku: duża liczba dzieci daje płytkie drzewo, a połączone liście ułatwiają szybkie odczyty po kolei.
Radix tree to “skompresowane” trie: ciągi węzłów z jednym dzieckiem są łączone w jedną krawędź opisaną fragmentem napisu. Oszczędza pamięć i zmniejsza liczbę skoków po wskaźnikach, zachowując szybkie wyszukiwanie po prefiksie. Używa się go np. w tablicach routingu i wyszukiwaniu po prefiksach.
Deque (double-ended queue) pozwala dodawać i usuwać elementy zarówno z przodu, jak i z tyłu. Przydaje się, gdy potrzebujesz jednocześnie zachowań stosu i kolejki lub w algorytmach typu sliding window/monotonic queue.
Separate chaining trzyma kolidujące klucze w liście (lub drzewie) w kubełku. Open addressing przechowuje wszystkie wpisy w tablicy i szuka alternatywnych slotów (np. linear/quadratic probing, double hashing). Chaining jest prostsze przy usuwaniu; open addressing bywa bardziej cache‑friendly, ale jest wrażliwe na load factor.
Trie przechowuje napisy jako ścieżki znaków; każda krawędź to znak. Zapytania po prefiksie są szybkie, bo wszystkie słowa z tym samym prefiksem współdzielą ścieżkę, więc lookup to O(L), gdzie L to długość klucza. Minusem jest wyższe zużycie pamięci niż przy hashowaniu.
Kolejka priorytetowa wspiera insert, podgląd (min/max) i usuwanie (min/max). Najczęściej jest implementowana kopcem binarnym, co daje O(log n) dla insert/extract i O(1) dla peek.
Listę sąsiedztwa wybierasz dla grafów rzadkich, bo ma pamięć O(V + E) i szybko iteruje sąsiadów. Macierz sąsiedztwa jest dobra dla grafów gęstych lub gdy potrzebujesz O(1) sprawdzenia, czy krawędź istnieje; kosztuje O(V^2) pamięci.
Segment tree to drzewo binarne nad przedziałami tablicy. Umożliwia zapytania zakresowe (suma/min/max) i aktualizacje punktowe w O(log n) po zbudowaniu w O(n). Z lazy propagation potrafi też obsługiwać aktualizacje zakresowe.
Kopiec binarny świetnie nadaje się do min/max: peek to O(1), a insert/extract to O(log n). (Zbalansowane) BST wspiera porządkowy traversal i wyszukiwanie po kluczu w O(log n). Kopce nie nadają się do szybkiego wyszukiwania ani zapytań zakresowych.
Mapę uporządkowaną wybierasz, gdy potrzebujesz kluczy w kolejności lub zapytań zakresowych (np. klucze między A i B). TreeMap daje O(log n) i porządek; HashMap ma średnio O(1), ale nie zachowuje porządku.
Formaty rzadkie (CSR/COO) używa się, gdy większość wpisów to zera. Przechowują tylko wartości niezerowe i ich pozycje, co oszczędza pamięć i przyspiesza operacje typu mnożenie macierz‑wektor. Minusem jest wolniejszy losowy dostęp i trudniejsze aktualizacje.