Pytania rekrutacyjne z algorytmów i struktur danych (Senior) z odpowiedziami

75 pytań na rozmowę rekrutacyjną z tematu Algorytmy i struktury danych (Senior) - z poprawnymi odpowiedziami, wyjaśnieniami i linkami do dokumentacji.

Rozwiąż ten test
  1. 1.Dlaczego algorytm Dijkstry daje błędne wyniki przy ujemnych wagach krawędzi?
  2. 2.Jaką dodatkową możliwość ma Bellman-Ford w porównaniu z Dijkstrą?
  3. 3.Czym A* różni się od algorytmu Dijkstry?
  4. 4.Jaka jest złożoność Floyda-Warshalla i kiedy jest rozsądnym wyborem?
  5. 5.Czym różnią się algorytmy Prima i Kruskala?
  6. 6.Co sprawia, że operacje union-find są prawie O(1)?
  7. 7.Jaki problem rozwiązuje drzewo Fenwicka (binary indexed tree)?
  8. 8.Kiedy wybrać drzewo przedziałowe zamiast drzewa Fenwicka?
  9. 9.Co filtr Blooma może powiedzieć o kluczu?
  10. 10.Dlaczego ze zwykłego filtra Blooma nie da się usunąć elementu?
  11. 11.Co szacuje HyperLogLog i dlaczego jest popularny?
  12. 12.Jaką przewagę daje haszowanie spójne rozproszonemu cache?
  13. 13.Czym jest skip list (lista z przeskokami)?
  14. 14.Dlaczego bazy danych używają do indeksów B-drzew, a nie binarnych drzew poszukiwań?
  15. 15.Jaki kompromis robią drzewa LSM w porównaniu z B-drzewami?
  16. 16.Jaka jest średnia złożoność quickselect przy szukaniu k-tego najmniejszego elementu?
  17. 17.Jak wybrać równomiernie losową próbkę k elementów ze strumienia o nieznanej długości?
  18. 18.Co jest nie tak z tasowaniem tablicy przez arr.sort(() => Math.random() - 0.5)?
  19. 19.Jak posortować plik 200 GB na maszynie z 8 GB RAM?
  20. 20.Jak wydajnie scalić k posortowanych list z łącznie n elementami?
  21. 21.Jaka jest kluczowa idea wyszukiwania wzorca Rabina-Karpa?
  22. 22.Jak KMP osiąga wyszukiwanie wzorca w O(n + m)?
  23. 23.Według twierdzenia o rekurencji uniwersalnej, jaka jest złożoność T(n) = 2T(n/2) + O(n)?
  24. 24.Co oznacza, że DP dla plecaka 0/1 jest pseudowielomianowe?
  25. 25.Rekruter opisuje problem, który sprowadza się do problemu komiwojażera. Jaka jest rozsądna reakcja?
  26. 26.Czego DP na maskach bitowych używa jako stanu?
  27. 27.Jak zmniejszyć pamięć DP dla LCS lub odległości edycyjnej z O(n × m) do O(m)?
  28. 28.Czym jest analiza zamortyzowana metodą „księgowania” lub „potencjału”?
  29. 29.Czym jest hash flooding?
  30. 30.Dlaczego algorytm O(n log n) może przegrać z O(n²) na prawdziwych danych?
  31. 31.Dlaczego Timsort tak dobrze radzi sobie z prawdziwymi danymi?
  32. 32.Czym jest introsort i dlaczego używa go C++ std::sort?
  33. 33.Która struktura pozwala znaleźć wszystkie przedziały zawierające punkt w O(log n + k)?
  34. 34.Co oblicza algorytm Tarjana lub Kosaraju?
  35. 35.Dlaczego reconciliation w React działa w O(n), skoro ogólne porównanie drzew to około O(n³)?
  36. 36.Którego algorytmu domyślnie używa git diff i wiele narzędzi diff?
  37. 37.Wirtualizowana lista renderuje tylko widoczne wiersze ze 100 000 elementów o różnych wysokościach. Jak szybko znajduje pierwszy widoczny wiersz?
  38. 38.Co daje współdzielenie struktury (structural sharing) w trwałych strukturach danych?
  39. 39.Kiedy LFU wygrywa z LRU jako polityka usuwania z cache?
  40. 40.Jak działa ogranicznik szybkości token bucket?
  41. 41.Jaka jest złożoność budowania kopca binarnego z n nieposortowanych elementów przesiewaniem w dół (heapify)?
  42. 42.Dlaczego wyszukiwanie binarne nie działa wydajnie na liście wiązanej?
  43. 43.Które podejście odpowiada na „czy to słowo jest w słowniku?” dla milionów słów przy najmniejszej pamięci, jeśli rzadkie fałszywe alarmy są w porządku?
  44. 44.Jaka jest złożoność czasowa naiwnego budowania tablicy sufiksowej przez sortowanie wszystkich sufiksów?
  45. 45.Dlaczego w produkcji trie często zastępuje się mapami lub drzewami radix?
  46. 46.Którego algorytmu użyć do wykrycia cyklu w importach modułów podczas budowania?
  47. 47.Dlaczego union-find nie wykrywa cykli w grafie skierowanym?
  48. 48.Jaka jest złożoność sprawdzenia, czy liczba jest potęgą dwójki, przez n > 0 && (n & (n - 1)) === 0?
  49. 49.Dlaczego 0.1 + 0.2 !== 0.3 ma znaczenie dla algorytmów?
  50. 50.Które stwierdzenie o przypadku średnim i najgorszym operacji tablicy haszującej jest poprawne?
  51. 51.Dlaczego przechodzenie tablicy 2D wiersz po wierszu jest przyjazne dla cache w układzie jak w C?
  52. 52.Który algorytm znajduje maksymalny przepływ w sieci?
  53. 53.Rozwiązanie rekurencyjne jest poprawne, ale przekracza limit czasu przez powtarzające się podproblemy z trzema parametrami. Jaka jest zwykła pierwsza poprawka?
  54. 54.Jaka jest oczekiwana liczba porównań przy udanym wyszukiwaniu w tablicy haszującej z łańcuchami i współczynnikiem wypełnienia α?
  55. 55.Co daje monotoniczny deque w zadaniu „maksimum w przesuwanym oknie”?
  56. 56.Jak wydajnie utrzymywać bieżącą medianę strumienia?
  57. 57.Co oznacza, że problem jest NP-zupełny?
  58. 58.Dlaczego głębokość rekurencji quicksorta jest problemem i jak się ją ogranicza?
  59. 59.Jakiej struktury użyć do autouzupełniania, które układa podpowiedzi według popularności?
  60. 60.Jaki problem rozwiązuje bufor cykliczny z indeksami głowy i ogona dla mocno obciążonej kolejki?
  61. 61.Jakie jest dolne ograniczenie szukania elementu w nieposortowanej tablicy i dlaczego?
  62. 62.Dlaczego dla niektórych łamigłówek DFS jest lepszy od BFS, choć BFS znajduje najkrótsze rozwiązania?
  63. 63.Jaka jest złożoność Array.prototype.sort w V8 na już posortowanej tablicy?
  64. 64.Jak znaleźć wszystkie pary o danej sumie w tablicy z duplikatami, nie licząc ich dwa razy?
  65. 65.Które stwierdzenie o rekurencji i stosie wywołań w JavaScripcie jest poprawne?
  66. 66.Jaka jest główna przewaga Dijkstry z kopcem Fibonacciego nad kopcem binarnym?
  67. 67.Jak w O(n) sprawdzić, czy dwa słowa różnią się o jedną edycję?
  68. 68.Co daje quicksortowi losowość?
  69. 69.Które podejście liczy inwersje (pary i < j z a[i] > a[j]) w O(n log n)?
  70. 70.Dlaczego dobra funkcja haszująca dla napisów przetwarza każdy znak?
  71. 71.Na co odpowiada w O(1) struktura „sparse table”?
  72. 72.Jaki jest główny powód, by wybrać macierz sąsiedztwa zamiast list sąsiedztwa?
  73. 73.Algorytm działa w O(n), ale w każdej iteracji gorącej pętli tworzy nową tablicę. Jaki jest prawdopodobny problem w praktyce?
  74. 74.Czego sztuczka „dwóch kopców” nie obsługuje wydajnie w porównaniu ze zbalansowanym BST?
  75. 75.Dlaczego Array.prototype.indexOf wewnątrz filter to częste ukryte O(n²) na code review?