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

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

Rozwiąż ten test
  1. 1.Jak działa sortowanie przez scalanie?
  2. 2.Jaka jest główna wada sortowania przez scalanie na tablicach?
  3. 3.Jaki jest najgorszy przypadek quicksorta i kiedy występuje?
  4. 4.Dlaczego quicksort jest w praktyce często szybszy od sortowania przez scalanie, choć oba mają średnio O(n log n)?
  5. 5.Co robi podział (partition) w quicksorcie?
  6. 6.Którego algorytmu sortowania używa V8 dla Array.prototype.sort?
  7. 7.Dlaczego żadne sortowanie przez porównania nie pobije O(n log n) w najgorszym przypadku?
  8. 8.Kiedy sortowanie przez zliczanie może pobić O(n log n)?
  9. 9.Czym jest kopiec binarny (min-heap)?
  10. 10.Ile kosztują główne operacje kopca binarnego?
  11. 11.Jak wydajnie znaleźć k największych elementów dużej tablicy?
  12. 12.Czy JavaScript ma wbudowaną kolejkę priorytetową?
  13. 13.Co zwróci to wyszukiwanie binarne, gdy target nie ma w tablicy?
  14. 14.Dlaczego w wielu językach zaleca się mid = lo + Math.floor((hi - lo) / 2) zamiast (lo + hi) / 2?
  15. 15.Co oznacza „wyszukiwanie binarne po odpowiedzi”?
  16. 16.Jak znaleźć wartość w posortowanej tablicy, którą obrócono, np. [4, 5, 6, 1, 2, 3], w O(log n)?
  17. 17.Czym jest technika przesuwanego okna?
  18. 18.Najdłuższy podnapis bez powtarzających się znaków: jaki jest pomysł na O(n)?
  19. 19.Two Sum na posortowanej tablicy: jakie jest podejście O(n) bez dodatkowej pamięci?
  20. 20.Jak scalić nakładające się przedziały, np. [[1,3],[2,6],[8,10]]?
  21. 21.Do czego służy stos monotoniczny?
  22. 22.Jak zbudować kolejkę na dwóch stosach, aby każda operacja była zamortyzowanie O(1)?
  23. 23.Która struktura daje wstawianie i usuwanie w O(1) na obu końcach?
  24. 24.Jak wykryć cykl na liście wiązanej z O(1) dodatkowej pamięci?
  25. 25.Jak znaleźć środek listy wiązanej w jednym przejściu?
  26. 26.Jak iteracyjnie odwrócić listę jednokierunkową?
  27. 27.Jak zwykle buduje się cache LRU z get i put w O(1)?
  28. 28.Dlaczego BFS znajduje najkrótszą ścieżkę w grafie bez wag?
  29. 29.Po co przechodzenie grafu trzyma zbiór visited?
  30. 30.Jak policzyć wyspy (spójne grupy jedynek) w siatce zer i jedynek?
  31. 31.Czym jest sortowanie topologiczne?
  32. 32.Jak algorytm Kahna wyznacza porządek topologiczny?
  33. 33.Jak wykryć cykl w grafie skierowanym za pomocą DFS?
  34. 34.Co obsługuje struktura union-find (zbiory rozłączne)?
  35. 35.Do czego dobre jest drzewo trie?
  36. 36.Które przechodzenie drzewa odwiedza wartości BST w kolejności posortowanej?
  37. 37.Jak przejść drzewo binarne poziom po poziomie?
  38. 38.Jak rekurencyjnie policzyć maksymalną głębokość drzewa binarnego?
  39. 39.Jaki problem rozwiązują drzewa samobalansujące (AVL, czerwono-czarne)?
  40. 40.Które dwie własności sprawiają, że problem pasuje do programowania dynamicznego?
  41. 41.Czym memoizacja różni się od tabulacji?
  42. 42.Schody: można wejść o 1 lub 2 stopnie naraz. Na ile sposobów można wejść na n stopni?
  43. 43.Dlaczego algorytm zachłanny może zawieść przy wydawaniu 6 monetami [1, 3, 4]?
  44. 44.Jaka jest złożoność DP wydawania reszty dla kwoty A i k rodzajów monet?
  45. 45.Czym jest najdłuższy wspólny podciąg (LCS) dwóch napisów?
  46. 46.Co mierzy odległość Levenshteina (odległość edycyjna)?
  47. 47.Na czym polega algorytm Kadane'a dla maksymalnej sumy podtablicy?
  48. 48.Ile podzbiorów ma zbiór n elementów i dlaczego to ważne?
  49. 49.Czym jest backtracking (przeszukiwanie z nawrotami)?
  50. 50.Ile permutacji ma tablica n różnych elementów?
  51. 51.Jak uniknąć przepełnienia stosu przy głębokiej rekurencji w JavaScripcie?
  52. 52.Jaka jest złożoność pamięciowa rekurencyjnego DFS na drzewie o wysokości h?
  53. 53.Co dzieje się z tablicą haszującą, gdy współczynnik wypełnienia jest za wysoki?
  54. 54.Jaka funkcja haszująca jest dobra dla tablicy haszującej?
  55. 55.Czego zwykle używa się jako klucza mapy w zadaniu grupowania anagramów?
  56. 56.Jak wiele razy odpowiadać na „sumę elementów od i do j” w niezmiennej tablicy?
  57. 57.Suma podtablicy równa k: po co trzymać liczności sum prefiksowych w mapie?
  58. 58.Co oblicza algorytm Dijkstry?
  59. 59.Która struktura danych czyni algorytm Dijkstry wydajnym?
  60. 60.Jaka jest złożoność BFS lub DFS na grafie zapisanym listami sąsiedztwa?
  61. 61.Jak sprawdzić, czy graf da się pokolorować dwoma kolorami tak, by żadna krawędź nie łączyła tych samych?
  62. 62.Co robi x & (x - 1) dla dodatniej liczby całkowitej x?
  63. 63.Każda liczba w tablicy występuje dwa razy oprócz jednej. Jak ją znaleźć w czasie O(n) i z O(1) pamięci?
  64. 64.Jaka jest złożoność tej funkcji?
  65. 65.Który algorytm znajduje minimalne drzewo rozpinające, dodając najtańsze krawędzie niezamykające cyklu?
  66. 66.Dlaczego kolejność kluczy obiektu w JavaScripcie nie zawsze odpowiada kolejności wstawiania?
  67. 67.Jaka jest złożoność sprawdzenia, czy dwa napisy długości n są równe?
  68. 68.Jaki problem rozwiązuje trzymanie k ostatnich wartości w buforze cyklicznym o stałym rozmiarze?
  69. 69.Na czym polega idea „spotkania w środku” w dwustronnym BFS?
  70. 70.Dlaczego tablice zwykle przechodzi się szybciej niż listy wiązane, choć oba to O(n)?
  71. 71.Jaka jest złożoność czasowa str.split("").sort().join("") dla napisu długości n?
  72. 72.Co robi ta funkcja i jaka jest jej złożoność?
  73. 73.Ile kosztuje wstawienie wartości do posortowanej tablicy z zachowaniem porządku?
  74. 74.Jak obrócić tablicę w prawo o k pozycji w miejscu z O(1) dodatkowej pamięci?
  75. 75.Subset sum: czy niektóre z liczb sumują się do target? Jakie jest klasyczne rozwiązanie DP?