Питання на співбесіді з алгоритмів і структур даних (Senior) з відповідями

75 запитань для співбесіди з теми Алгоритми та структури даних (Senior) - з правильними відповідями, поясненнями й посиланнями на документацію.

Пройти цей тест
  1. 1.Чому алгоритм Дейкстри дає хибні результати з від'ємними вагами ребер?
  2. 2.Яку додаткову можливість має Беллман-Форд порівняно з Дейкстрою?
  3. 3.Чим A* відрізняється від алгоритму Дейкстри?
  4. 4.Яка складність Флойда-Воршелла і коли він доречний?
  5. 5.Чим відрізняються алгоритми Прима й Крускала?
  6. 6.Що робить операції union-find майже O(1)?
  7. 7.Яку задачу розв'язує дерево Фенвіка (binary indexed tree)?
  8. 8.Коли варто обрати дерево відрізків замість дерева Фенвіка?
  9. 9.Що фільтр Блума може сказати про ключ?
  10. 10.Чому зі звичайного фільтра Блума не можна видалити елемент?
  11. 11.Що оцінює HyperLogLog і чому він популярний?
  12. 12.Яку перевагу дає консистентне хешування розподіленому кешу?
  13. 13.Що таке skip list (список із пропусками)?
  14. 14.Чому бази даних використовують для індексів B-дерева, а не бінарні дерева пошуку?
  15. 15.На який компроміс ідуть LSM-дерева порівняно з B-деревами?
  16. 16.Яка середня складність quickselect для пошуку k-го найменшого елемента?
  17. 17.Як вибрати рівномірно випадкову вибірку з k елементів із потоку невідомої довжини?
  18. 18.Що не так із перемішуванням масиву через arr.sort(() => Math.random() - 0.5)?
  19. 19.Як відсортувати файл на 200 ГБ на машині з 8 ГБ RAM?
  20. 20.Як ефективно злити k відсортованих списків, де загалом n елементів?
  21. 21.Яка ключова ідея пошуку підрядка Рабіна-Карпа?
  22. 22.Як KMP досягає пошуку підрядка за O(n + m)?
  23. 23.За основною теоремою, яка складність T(n) = 2T(n/2) + O(n)?
  24. 24.Що означає, що DP для рюкзака 0/1 псевдополіноміальне?
  25. 25.Інтерв'юер описує задачу, що зводиться до задачі комівояжера. Яка розумна реакція?
  26. 26.Що використовує як стан DP по бітових масках?
  27. 27.Як зменшити пам'ять DP для LCS чи редакційної відстані з O(n × m) до O(m)?
  28. 28.Що таке амортизований аналіз методом «бухгалтерії» чи «потенціалу»?
  29. 29.Що таке hash flooding?
  30. 30.Чому алгоритм O(n log n) може програти O(n²) на реальних даних?
  31. 31.Чому Timsort такий швидкий на реальних даних?
  32. 32.Що таке introsort і чому його використовує C++ std::sort?
  33. 33.Яка структура дозволяє знайти всі інтервали, що містять точку, за O(log n + k)?
  34. 34.Що обчислює алгоритм Тарджана або Косараджу?
  35. 35.Чому reconciliation у React працює за O(n), хоча загальне порівняння дерев - близько O(n³)?
  36. 36.Який алгоритм за замовчуванням використовують git diff і багато diff-інструментів?
  37. 37.Віртуалізований список рендерить лише видимі рядки зі 100 000 елементів різної висоти. Як він швидко знаходить перший видимий рядок?
  38. 38.Що дає структурне спільне використання (structural sharing) у персистентних структурах даних?
  39. 39.Коли LFU кращий за LRU як політика витіснення з кешу?
  40. 40.Як працює обмежувач частоти token bucket?
  41. 41.Яка складність побудови бінарної купи з n невідсортованих елементів просіюванням униз (heapify)?
  42. 42.Чому бінарний пошук неефективний на зв'язному списку?
  43. 43.Який підхід відповідає на «чи є це слово в словнику?» для мільйонів слів із найменшою пам'яттю, якщо рідкісні хибнопозитивні прийнятні?
  44. 44.Яка часова складність наївної побудови суфіксного масиву сортуванням усіх суфіксів?
  45. 45.Чому в продакшні trie часто замінюють хеш-таблицями чи radix-деревами?
  46. 46.Який алгоритм використати для пошуку циклу в імпортах модулів під час збірки?
  47. 47.Чому union-find не знаходить цикли в орієнтованому графі?
  48. 48.Яка складність перевірки, чи є число степенем двійки, через n > 0 && (n & (n - 1)) === 0?
  49. 49.Чому 0.1 + 0.2 !== 0.3 важливо для алгоритмів?
  50. 50.Яке твердження про середній і найгірший випадок операцій хеш-таблиці правильне?
  51. 51.Чим обхід 2D-масиву рядок за рядком дружній до кешу в C-подібному розміщенні?
  52. 52.Який алгоритм знаходить максимальний потік у мережі?
  53. 53.Рекурсивне рішення коректне, але не вкладається в час через повторні підзадачі з трьома параметрами. Яке звичне перше виправлення?
  54. 54.Яка очікувана кількість порівнянь для успішного пошуку в хеш-таблиці з ланцюжками й коефіцієнтом заповнення α?
  55. 55.Що дає монотонний дек у задачі «максимум у ковзному вікні»?
  56. 56.Як ефективно підтримувати поточну медіану потоку?
  57. 57.Що означає, що задача NP-повна?
  58. 58.Чому глибина рекурсії quicksort - проблема і як її обмежують?
  59. 59.Яку структуру обрати для автодоповнення, що ранжує підказки за популярністю?
  60. 60.Яку задачу розв'язує кільцевий буфер з індексами голови й хвоста для високонавантаженої черги?
  61. 61.Яка нижня межа для пошуку елемента в невідсортованому масиві і чому?
  62. 62.Чому для деяких головоломок DFS кращий за BFS, хоча BFS знаходить найкоротші розв'язки?
  63. 63.Яка складність Array.prototype.sort у V8 на вже відсортованому масиві?
  64. 64.Як знайти всі пари з заданою сумою в масиві з дублікатами, не рахуючи двічі?
  65. 65.Яке твердження про рекурсію й стек викликів у JavaScript правильне?
  66. 66.У чому головна перевага Дейкстри з купою Фібоначчі над бінарною купою?
  67. 67.Як за O(n) перевірити, що два слова відрізняються на одне редагування?
  68. 68.Що дає quicksort рандомізація?
  69. 69.Який підхід рахує інверсії (пари i < j з a[i] > a[j]) за O(n log n)?
  70. 70.Чому добра хеш-функція для рядків обробляє кожен символ?
  71. 71.На що відповідає за O(1) структура «sparse table»?
  72. 72.Яка головна причина обрати матрицю суміжності замість списків суміжності?
  73. 73.Алгоритм працює за O(n), але на кожній ітерації гарячого циклу створює новий масив. Яка ймовірна проблема на практиці?
  74. 74.Чого не вміє ефективно прийом «дві купи» порівняно зі збалансованим BST?
  75. 75.Чому Array.prototype.indexOf усередині filter - типове приховане O(n²) на code review?