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

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

Пройти цей тест
  1. 1.Як працює сортування злиттям?
  2. 2.Який головний недолік сортування злиттям на масивах?
  3. 3.Який найгірший випадок швидкого сортування і коли він трапляється?
  4. 4.Чому швидке сортування на практиці часто швидше за злиття, хоча в середньому обидва O(n log n)?
  5. 5.Що робить розбиття (partition) у швидкому сортуванні?
  6. 6.Який алгоритм сортування використовує V8 для Array.prototype.sort?
  7. 7.Чому жодне сортування порівняннями не може бути швидшим за O(n log n) у найгіршому разі?
  8. 8.Коли сортування підрахунком може бути швидшим за O(n log n)?
  9. 9.Що таке бінарна купа (min-heap)?
  10. 10.Скільки коштують основні операції бінарної купи?
  11. 11.Як ефективно знайти k найбільших елементів великого масиву?
  12. 12.Чи є в JavaScript вбудована черга з пріоритетом?
  13. 13.Що поверне цей бінарний пошук, якщо target немає в масиві?
  14. 14.Чому в багатьох мовах радять mid = lo + Math.floor((hi - lo) / 2) замість (lo + hi) / 2?
  15. 15.Що означає «бінарний пошук по відповіді»?
  16. 16.Як знайти значення у відсортованому масиві, який повернули циклічно, наприклад [4, 5, 6, 1, 2, 3], за O(log n)?
  17. 17.Що таке техніка ковзного вікна?
  18. 18.Найдовший підрядок без повторюваних символів: яка ідея за O(n)?
  19. 19.Two Sum на відсортованому масиві: який підхід за O(n) без додаткової пам'яті?
  20. 20.Як злити інтервали, що перетинаються, наприклад [[1,3],[2,6],[8,10]]?
  21. 21.Для чого використовують монотонний стек?
  22. 22.Як реалізувати чергу на двох стеках, щоб кожна операція була амортизовано O(1)?
  23. 23.Яка структура дає вставку й видалення за O(1) з обох кінців?
  24. 24.Як знайти цикл у зв'язному списку з O(1) додаткової пам'яті?
  25. 25.Як знайти середину зв'язного списку за один прохід?
  26. 26.Як розвернути однозв'язний список ітеративно?
  27. 27.Як зазвичай будують LRU-кеш із get і put за O(1)?
  28. 28.Чому BFS знаходить найкоротший шлях у незваженому графі?
  29. 29.Навіщо обходам графа множина visited?
  30. 30.Як порахувати острови (зв'язні групи одиниць) у сітці з 0 і 1?
  31. 31.Що таке топологічне сортування?
  32. 32.Як алгоритм Кана будує топологічний порядок?
  33. 33.Як знайти цикл в орієнтованому графі за допомогою DFS?
  34. 34.Що підтримує структура union-find (система неперетинних множин)?
  35. 35.Для чого добрий trie (префіксне дерево)?
  36. 36.Який обхід дерева відвідує значення BST у відсортованому порядку?
  37. 37.Як обійти бінарне дерево рівень за рівнем?
  38. 38.Як рекурсивно обчислити максимальну глибину бінарного дерева?
  39. 39.Яку проблему розв'язують самобалансовані дерева (AVL, червоно-чорні)?
  40. 40.Які дві властивості роблять задачу придатною для динамічного програмування?
  41. 41.Чим мемоізація відрізняється від табуляції?
  42. 42.Сходи: за крок можна піднятися на 1 або 2 сходинки. Скількома способами можна піднятися на n сходинок?
  43. 43.Чому жадібний алгоритм може помилитися при розміні суми 6 монетами [1, 3, 4]?
  44. 44.Яка складність DP для розміну суми A монетами k видів?
  45. 45.Що таке найдовша спільна підпослідовність (LCS) двох рядків?
  46. 46.Що вимірює відстань Левенштейна (редакційна відстань)?
  47. 47.У чому ідея алгоритму Кадане для максимальної суми підмасиву?
  48. 48.Скільки підмножин має множина з n елементів і чому це важливо?
  49. 49.Що таке пошук із поверненням (backtracking)?
  50. 50.Скільки перестановок має масив з n різних елементів?
  51. 51.Як уникнути переповнення стека при глибокій рекурсії в JavaScript?
  52. 52.Яка просторова складність рекурсивного DFS на дереві висотою h?
  53. 53.Що стається з хеш-таблицею, коли коефіцієнт заповнення стає завеликим?
  54. 54.Яка хеш-функція добра для хеш-таблиці?
  55. 55.Що зазвичай використовують як ключ map у задачі групування анаграм?
  56. 56.Як багато разів відповідати на «суму елементів від i до j» у незмінному масиві?
  57. 57.Сума підмасиву дорівнює k: навіщо зберігати кількості префіксних сум у хеш-таблиці?
  58. 58.Що обчислює алгоритм Дейкстри?
  59. 59.Яка структура даних робить алгоритм Дейкстри ефективним?
  60. 60.Яка складність BFS чи DFS на графі, збереженому списками суміжності?
  61. 61.Як перевірити, чи можна розфарбувати граф у два кольори так, щоб жодне ребро не з'єднувало однакові?
  62. 62.Що робить x & (x - 1) для додатного цілого x?
  63. 63.Кожне число в масиві трапляється двічі, крім одного. Як знайти його за O(n) часу й O(1) пам'яті?
  64. 64.Яка складність цієї функції?
  65. 65.Який алгоритм будує мінімальне кістякове дерево, додаючи найдешевші ребра, що не створюють циклу?
  66. 66.Чому порядок ключів об'єкта JavaScript не завжди збігається з порядком додавання?
  67. 67.Яка складність перевірки рівності двох рядків довжини n?
  68. 68.Яку задачу розв'язує зберігання k останніх значень у кільцевому буфері фіксованого розміру?
  69. 69.У чому ідея «зустрічі посередині» у двосторонньому BFS?
  70. 70.Чому масиви зазвичай швидше обходити, ніж зв'язні списки, хоча обидва O(n)?
  71. 71.Яка часова складність str.split("").sort().join("") для рядка довжини n?
  72. 72.Що робить ця функція і яка в неї складність?
  73. 73.Скільки коштує вставити значення у відсортований масив, зберігши порядок?
  74. 74.Як циклічно зсунути масив праворуч на k позицій на місці з O(1) додаткової пам'яті?
  75. 75.Subset sum: чи можуть деякі з чисел дати в сумі target? Яке класичне рішення через DP?