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

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

Пройти цей тест
  1. 1.Що описує нотація Big O?
  2. 2.Яка часова складність цієї функції?
  3. 3.Яка часова складність двох вкладених циклів по одному масиву довжини n?
  4. 4.Чому O(2n + 10) записують просто як O(n)?
  5. 5.Яка складність зростає найповільніше зі збільшенням n?
  6. 6.Яка складність читання arr[i] з масиву в JavaScript?
  7. 7.Яка операція з масивом у JavaScript зазвичай має складність O(n)?
  8. 8.Яка складність arr.includes(x) для невідсортованого масиву?
  9. 9.Чому set.has(x) на великих колекціях зазвичай швидший за arr.includes(x)?
  10. 10.Яка просторова складність цієї функції?
  11. 11.Що означає O(1) додаткової пам'яті для алгоритму?
  12. 12.У чому головна ідея хеш-таблиці?
  13. 13.Що таке колізія в хеш-таблиці?
  14. 14.Який час пошуку в хеш-таблиці в найгіршому випадку?
  15. 15.Коли Map кращий за звичайний об'єкт як словник?
  16. 16.Як найпростіше прибрати дублікати з масиву примітивів?
  17. 17.Як за O(n) перевірити, чи є в масиві дублікати?
  18. 18.Що гарантує структура даних стек?
  19. 19.Яка задача природно розв'язується стеком?
  20. 20.Що гарантує черга?
  21. 21.Чому черга на push і shift може стати повільною на великих даних?
  22. 22.Де сам рушій JavaScript використовує стек?
  23. 23.Що таке однозв'язний список?
  24. 24.Скільки коштує отримати k-й елемент зв'язного списку?
  25. 25.Яка операція у зв'язному списку O(1), а на початку масиву O(n)?
  26. 26.Що потрібно кожній коректній рекурсивній функції?
  27. 27.Що станеться після виклику цієї функції?
  28. 28.Чому ця функція Фібоначчі повільна для n = 40?
  29. 29.Що таке мемоізація?
  30. 30.Що таке лінійний пошук?
  31. 31.Чого бінарний пошук вимагає від даних?
  32. 32.Яка часова складність бінарного пошуку?
  33. 33.Скільки приблизно порівнянь потрібно бінарному пошуку у відсортованому масиві з 1 000 000 елементів?
  34. 34.Що поверне цей код?
  35. 35.Що має повернути компаратор (a, b) => ..., щоб sort поставив a перед b?
  36. 36.Що важливо пам'ятати про arr.sort()?
  37. 37.Що гарантує стабільне сортування?
  38. 38.Яка типова складність доброго універсального сортування порівняннями?
  39. 39.Як працює сортування бульбашкою?
  40. 40.Коли сортування вставками - добрий вибір?
  41. 41.Як розвернути масив на місці з O(1) додаткової пам'яті?
  42. 42.Що таке техніка «двох вказівників»?
  43. 43.Як перевірити, чи рядок є паліндромом, за O(n) часу й O(1) додаткової пам'яті?
  44. 44.Як за O(n) перевірити, що два рядки є анаграмами?
  45. 45.Яка складність побудови рядка через += у циклі в сучасних рушіях JavaScript?
  46. 46.Що таке дерево в структурах даних?
  47. 47.Що таке лист у дереві?
  48. 48.Що таке висота дерева?
  49. 49.Яку властивість має бінарне дерево пошуку (BST)?
  50. 50.Скільки часу займає пошук значення в збалансованому BST з n вузлами?
  51. 51.Що станеться, якщо вставити 1, 2, 3, 4, 5 по черзі у простий BST без балансування?
  52. 52.Якою структурою є DOM вебсторінки?
  53. 53.Чим обхід у глибину (DFS) відрізняється від обходу в ширину (BFS)?
  54. 54.Яку структуру даних використовує пошук у ширину (BFS)?
  55. 55.Що таке граф?
  56. 56.Чим орієнтований граф відрізняється від неорієнтованого?
  57. 57.Як зазвичай зберігають граф із багатьма вершинами, але небагатьма ребрами?
  58. 58.Що описує цей список суміжності?
  59. 59.Яка складність пошуку максимуму в невідсортованому масиві?
  60. 60.Чому Math.max(...arr) може впасти на дуже великому масиві?
  61. 61.Як за O(n) порахувати, скільки разів кожне слово трапляється в списку?
  62. 62.Two Sum: знайти два числа в невідсортованому масиві, що в сумі дають target. Який підхід за O(n)?
  63. 63.Що означає «амортизоване O(1)» для arr.push?
  64. 64.Яка часова складність перевірки isPrime нижче?
  65. 65.Яка складність цього циклу?
  66. 66.Яка складність пошуку ключа у звичайному об'єкті JavaScript, obj[key]?
  67. 67.Що таке масив префіксних сум?
  68. 68.Яка складність arr.slice() (копіювання всього масиву)?
  69. 69.Як зазвичай представляють матрицю (2D-сітку) в JavaScript?
  70. 70.Чому не варто писати new Array(3).fill([]) для сітки 3 × 3?
  71. 71.Що таке жадібний алгоритм?
  72. 72.Що означає «brute force» (повний перебір) для алгоритму?
  73. 73.Алгоритм має O(n²). Приблизно у скільки разів довше він працюватиме, якщо вхід зросте з 1000 до 10 000 елементів?
  74. 74.Чому Set об'єктів не допомагає прибрати дублікати з однаковим вмістом?
  75. 75.Як arr.splice(i, 1) посередині масиву впливає на продуктивність?