Структуры данных — чек-лист

ОБЯЗАТЕЛЬНОДЛЯ НОВИЧКОВ

Разработчику Архитектору Инженеру

Загрузка вопросов…

---

Чек-лист самопроверки

После обзора — базовые вопросы:

1. Вы можете объяснить разницу между строкой, столбцом и ячейкой в таблице и привести пример запроса "фильтр по столбцу".
2. Вы понимаете, чем дерево (один родитель) отличается от графа (связи в любую сторону, возможны циклы).
3. Вы знаете, почему индексация массива в большинстве языков начинается с 0.
4. Вы можете описать LIFO (стек) и FIFO (очередь) без путаницы.
5. Вы понимаете разницу между моделью "ключ–значение" и хеш-таблицей как реализацией словаря.
6. Вы можете назвать один пример бинарного файла (не двоичного дерева).

После реализации — углубление:

7. Вы понимаете разницу между статическим и динамическим массивом по способу выделения памяти и поведению при изменении размера.
8. Вы знаете, почему доступ к элементу массива по индексу выполняется за O(1).
9. Вы можете объяснить, как происходит реаллокация в динамическом массиве и почему амортизированная сложность добавления в конец — O(1).
10. Вы понимаете, когда целесообразно использовать разрежённый массив вместо плотного.
11. Вы различаете зигзагообразный (jagged) и прямоугольный многомерный массив по структуре памяти и производительности.
12. Вы знаете, почему односвязный список неэффективен для произвольного доступа по индексу.
13. Вы понимаете, как двусвязный список позволяет обходить структуру в обоих направлениях.
14. Вы можете привести пример применения циклического списка в системном программировании.
15. Вы знаете, какие операции стек поддерживает и какова их временная сложность.
16. Вы понимаете разницу между реализацией стека на массиве и на связном списке по потреблению памяти и предсказуемости задержек.
17. Вы знаете, почему в real-time системах часто используют стек фиксированного размера.
18. Вы понимаете принцип работы кольцевого буфера и как он реализует очередь без сдвига элементов.
19. Вы знаете, почему для FIFO в Python предпочтительнее collections.deque, чем list.pop(0).
20. Вы знаете, как дек (двусторонняя очередь) обобщает стек и очередь.
21. Вы понимаете, как хеш-функция преобразует ключ в индекс корзины.
22. Вы знаете два основных метода разрешения коллизий в хеш-таблицах и их компромиссы.
23. Вы понимаете, почему Java 8+ преобразует длинные цепочки в красно-чёрные деревья.
24. Вы знаете, что такое универсальное хеширование и зачем оно нужно для защиты от DoS-атак.
25. Вы можете назвать свойства хорошей хеш-функции — скорость, равномерность, лавинный эффект.
26. Вы понимаете, как бинарная куча представляет почти полное двоичное дерево в виде массива.
27. Вы знаете, как вычисляются индексы потомков и родителя в массивном представлении кучи.
28. Вы понимаете разницу между операциями sift-up и sift-down и когда каждая из них применяется.
29. Вы знаете, почему построение кучи из неупорядоченного массива можно выполнить за O(n), а не O(n log n).
30. Вы понимаете, как d-арные кучи уменьшают высоту дерева и когда это выгодно.
31. Вы знаете, почему стандартная бинарная куча не поддерживает эффективное обновление приоритета существующего элемента.
32. Вы понимаете, как AVL-дерево поддерживает строгую сбалансированность через баланс-фактор и вращения.
33. Вы знаете, почему красно-чёрные деревья делают меньше вращений при модификациях по сравнению с AVL.
34. Вы понимаете, как B⁺-дерево оптимизирует диапазонные запросы за счёт связанных листьев.
35. Вы знаете, почему B-деревья используются в СУБД, а не бинарные деревья поиска.
36. Вы понимаете, как размер узла B-дерева соотносится с размером страницы файловой системы.
37. Вы знаете, чем суффиксный массив отличается от суффиксного дерева по потреблению памяти и времени построения.
38. Вы понимаете, как LCP-массив ускоряет поиск подстрок в суффиксном массиве.
39. Вы знаете, почему CSR-формат эффективен для разрежённых графов в high-performance computing.
40. Вы понимаете, как property graph в Neo4j отличается от математического графа наличием свойств и типов рёбер.
41. Вы знаете, как native graph storage в Neo4j обеспечивает быстрый обход соседей без полного сканирования.
42. Вы понимаете принцип работы фильтра Блума и почему он допускает ложноположительные, но не ложноотрицательные срабатывания.
43. Вы знаете, как Count-Min Sketch оценивает частоту элементов и почему оценка всегда завышена.
44. Вы понимаете, как HyperLogLog оценивает количество уникальных элементов с фиксированным объёмом памяти.
45. Вы знаете, почему Cuckoo Filter поддерживает удаление, а классический фильтр Блума — нет.
46. Вы понимаете, как MinHash оценивает похожесть множеств через коэффициент Жаккара.
47. Вы знаете, зачем skip list используют в Redis ZSET и memtable LSM-СУБД.
48. Вы понимаете, как красно-чёрное дерево используется в планировщике задач Linux CFS.
49. Вы знаете, почему B⁺-деревья применяются в кластеризованных индексах InnoDB.
50. Вы понимаете, как LSM-деревья оптимизируют запись за счёт фонового слияния SSTable’ов (восемь структур в основах БД).
51. Вы можете назвать восемь типовых структур индексов и хранения (skip list, хеш, SSTable, LSM, B⁺, инвертированный, суффиксный, R-дерево) и указать, для какого класса запросов каждая подходит.
52. Вы знаете, как .NET Dictionary<TKey, TValue> использует открытую адресацию с двойным хешированием.
53. Вы понимаете, как JVM HashMap переключается с цепочек на красно-чёрные деревья при длине корзины > 8.
54. Вы знаете, как V8 оптимизирует массивы, переключаясь между fast elements и dictionary mode.
55. Вы понимаете, как карта памяти ядра Linux использует radix-дерево для управления VMA.
56. Вы знаете, как slab allocator использует связные списки и битовые карты для выделения объектов фиксированного размера.
57. Вы понимаете, как card table в generational GC помечает "грязные" регионы памяти при записи.
58. Вы знаете, как HNSW и IVF индексы ускоряют поиск ближайших соседей в векторных базах данных.
59. Вы понимаете, как выбор структуры данных влияет не только на алгоритмическую сложность, но и на кэш-локальность, предсказуемость задержек и масштабируемость в распределённых системах.

---