Продвинутый уровень (12 из 15)

<aside> <img src="/icons/calendar-day_gray.svg" alt="/icons/calendar-day_gray.svg" width="40px" />

16 июня 2026

</aside>

<aside> <img src="/icons/clock-alternate_lightgray.svg" alt="/icons/clock-alternate_lightgray.svg" width="40px" />

20 минут

</aside>

1. Ваше приложение использует гибридный алгоритм сортировки, который переключается между быстрой сортировкой и сортировкой вставками. На больших массивах производительность заметно снизилась. Логи показывают, что переключение происходит чаще, чем ожидалось.

   Какое действие поможет стабилизировать производительность гибридного алгоритма?

   • Оптимизировать условия для выбора опорного элемента в быстрой сортировке
   • Увеличить порог для переключения на сортировку вставками
   • Применить многопоточность для сортировки оставшихся элементов
   • Добавить дополнительный уровень кеширования на этапе разбиения
   • Настроить динамическое выделение памяти перед каждой итерацией

2. Вы разрабатываете систему поиска данных в большом неупорядоченном массиве, где необходимо значительно сократить время поиска.

   Вы определили для себя такие условия:

   1. Использование линейного поиска приводит к временной сложности O(n), что делает его неэффективным для больших объемов данных.
   2. Размер массива составляет 1 миллиард записей, что требует высокой производительности алгоритма.
   3. Среднее время отклика на запрос не должно превышать 1 миллисекунду.

   Какой подход к организации поиска позволит обеспечить лучшую производительность в заданных условиях?

   • Добавить хеш-таблицу для быстрого поиска за O(1)
   • Переключиться на жадный алгоритм поиска, который обходит только часть массива
   • Использовать индексы и частичную предвыборку для ускоренного поиска
   • Применить бинарный поиск для значительного ускорения
   • Разделить массив на равные части и применять поиск последовательно

3. В вашей системе для хранения и обработки больших объемов данных используются динамические массивы. С ростом данных стали очевидны проблемы с производительностью, обусловленные частым перераспределением памяти.

   Что произойдет после перехода на массив с резервированием памяти?

   • Увеличится средняя скорость вставки новых элементов в массив за счёт уменьшения числа перераспределений
   • Вставка элементов в середину массива станет значительно быстрее за счёт предварительно выделенной памяти
   • Уменьшится количество перераспределений, но усложнится алгоритм поиска элементов
   • Ускорится сортировка, поскольку данные будут храниться более равномерно в памяти
   • Операции удаления станут быстрее, так как освобождённая память сразу возвращается системе

4. В банковской системе реализован механизм вложенных транзакций с возможностью отмены (undo). Однако в нагрузочном тестировании выявлены проблемы:

   – задержки при отмене вложенных операций; – рост потребления памяти при большом числе параллельных транзакций; – трудности с поддержанием корректного порядка отмены.

   О чем связаны эти проблемы в реализации?

   • Использование общего глобального стека без разграничения уровней транзакций
   • Передача управления транзакциями через сигналы и таймеры в разных потоках
   • Реализация вложенных операций через связанные списки без указателей на родителя
   • Хранение каждой транзакции в отдельной очереди с приоритетом по времени
   • Попытка реализовать undo через FIFO буфер с ручной очисткой

5. Вам необходимо в реальном времени обрабатывать огромный поток логов, поступающих от нескольких серверов. Для ускорения процесса вы внедрили новый алгоритм фильтрации и предобработки данных.

   В результате оказалось, что:

   1. Система начала использовать избыточный объем оперативной памяти, в разы превышающий расчетные пределы.
   2. Среднее время ответа сервиса выросло настолько, что пользователи стали получать данные с ощутимой задержкой.

   Выберите наиболее вероятное объяснение, почему это произошло.

   • При разработке алгоритма не учли реальную асимптотическую сложность по времени и памяти: после роста объема логов начались массовые перераспределения памяти и увеличение числа операций
   • Новый алгоритм включает сложный механизм динамической оптимизации, который проводит предварительный анализ данных, что приводит к снижению скорости и росту памяти
   • Задержки неизбежны при любой фильтрации логов в реальном времени. Повышение потребления говорит о недостаточном количестве модулей оперативной памяти, что замедляет алгоритм
   • Задержки в обработке логов возникли из-за того, что новый алгоритм автоматически увеличивает глубину рекурсии при росте нагрузки, что повлияло на память и среднее время ответа
   • Алгоритм был протестирован на больших объемах данных, но в другом окружении, поэтому эффекты высокой параллельности по объему оперативной памяти и времени ответа не проявились заранее

6. Ваше приложение обрабатывает миллиарды записей в реальном времени, но система неожиданно начала потреблять больше памяти, чем было рассчитано. Логирование показало, что значительная часть памяти уходит на накладные расходы структуры данных.

   Что наиболее вероятно приводит к повышенному расходу памяти?

   • Использование деревьев поиска вместо хеш-таблиц
   • Использование сжатия данных
   • Ограничение числа одновременно загруженных структур данных
   • Применение memory-mapped файлов
   • Замена динамического выделения памяти на статическое

7. Вы реализовали рекурсивную функцию для подсчёта количества маршрутов, по которым складской робот может добраться от точки приёма до точки упаковки. Робот перемещается по сетке из 20 строк и 20 столбцов, двигаясь только вправо или вниз. Алгоритм корректно работает на малых размерах сетки, но при запуске на полном размере программа резко теряет производительность: выполнение занимает очень много времени, хотя объем используемой памяти остается стабильным.

   Почему выполнение алгоритма резко замедляется при увеличении размера сетки, несмотря на стабильное потребление памяти?

   • Алгоритм многократно пересчитывает одни и те же подзадачи, поскольку не сохраняет промежуточные результаты
   • Глубина рекурсии превышает лимит стека, вызывая остановку выполнения
   • Алгоритм перебирает маршруты с возвратами назад, увеличивая число комбинаций
   • Используется хвостовая рекурсия, которая замедляет выполнение на больших входных данных
   • Происходит переполнение переменной, в которую записывается итоговое значение

8. В системе автоматической навигации для логистической компании, в которой маршруты грузового транспорта строятся автоматически, граф дорог представлен взвешенным ориентированным графом, а алгоритм расчета оптимальных маршрутов основан на поиске кратчайшего пути. Тестирование выявило две ключевые проблемы:

   – При увеличении числа точек доставки время расчета маршрутов резко возрастает, что приводит к задержкам в системе; – Один и тот же граф при повторном запуске алгоритма дает разные корректные маршруты, но их длина различается, что вызывает колебания времени доставки.

   Примеры расхождений: В первом тесте маршрут от S до T проходит через A → C → E → T. В другом тесте для той же конфигурации графа, но с измененным порядком обработки узлов маршрут изменился на S → B → D → T.

   Какое изменение в алгоритме или структуре графа могло привести к такому поведению?

   • Использование алгоритма поиска в глубину вместо алгоритма Дейкстры
   • Приоритет обработки узлов в очереди изменил порядок выбора пути
   • Использование эвристики при выборе ребер
   • Изменение структуры данных хранения графа
   • Добавление новых ребер с другими весами нарушило исходную маршрутизацию

9. Вы разрабатываете финансовую систему, которая хранит транзакции пользователей в хеш-таблице для ускорения поиска. Однако при анализе производительности выявлено, что в периоды высокой нагрузки система начинает работать нестабильно. Логи показывают, что некоторые ключи сильно перегружены, а операции поиска стали значительно медленнее.

   Почему увеличилось количество коллизий?

   • Использована неподходящая хеш-функция, распределяющая ключи неравномерно
   • Применено случайное хеширование, которое нивелирует эффект перегрузки отдельных ключей
   • Переход к бинарному дереву поиска внутри каждого бакета увеличил скорость обработки
   • Таблица разделена на несколько секций, что уменьшило общий коэффициент загрузки
   • Применено динамическое хеширование, которое оптимизирует таблицу без влияния на производительность

10. Выберите вариант ответа, в котором перечислены только ключевые метрики, определяющие производительность хеш-таблицы.

    • Коэффициент загрузки, количество коллизий, среднее время нахождения данных
    • Частота рехеширования, глубина пробирования, общее число записей
    • Размер таблицы, количество операций вставки, использование связанных списков
    • Распределение данных, максимальная длина цепочки, сложность хеш-функции
    • Процент занятых ячеек, число доступных бакетов, время вычисления хеш-функции

11. Вы разрабатываете алгоритм для поиска минимального количества разрезов строки, необходимых для разбиения ее на палиндромы. Первоначальная версия использует рекурсивный подход, но при длинных строках время выполнения возрастает экспоненциально. Проверка показала, что некоторые подстроки анализируются несколько раз, что приводит к значительным накладным расходам.

    Какой метод поможет уменьшить избыточные вычисления и повысить производительность?

    • Использовать динамическое программирование для хранения уже рассчитанных разрезов
    • Увеличить глубину рекурсии для детального анализа каждого возможного разбиения
    • Использовать алгоритм полного перебора для точного расчета оптимального варианта
    • Применить жадный алгоритм разбиения строк, снизив число рассмотренных вариантов
    • Добавить дополнительный уровень предобработки строк перед разбиением

12. В вашей компании разрабатывается интеллектуальная система распределения грузов по железной дороге, в которой используется граф с динамически изменяющимися тарифами. Некоторые тарифы, например, небольшие скидки на вес маршрута за включение обратного рейса или скидки за остановку на таможенную проверку груза на этой станции, могут иметь отрицательные веса. В тестах ваш алгоритм дал корректные результаты.

    Что изменить, чтобы тесты НЕ дали корректные результаты с отрицательными весами?

    • Заменить вариант ранее используемого алгоритма на алгоритм Дейкстры
    • Ограничить глубину поиска маршрутов, чтобы предотвратить влияние отрицательных рёбер
    • Запретить использование вершин с отрицательными весами
    • Добавить рёбра с очень большими положительными весами
    • Применить модификацию алгоритма Флойда-Уоршелла, которая заменяет отрицательные рёбра на положительные

13. При решении задачи о размене суммы с помощью заданных номиналов монет используется динамическое программирование. Результатом работы алгоритма должно быть количество различных способов собрать целевую сумму.

14. Какой алгоритм используется для построения минимального остовного дерева?

15. Какой из перечисленных методов целесообразно применять для решения задачи многомерной нелинейной оптимизации, учитывая ограниченность вычислительных ресурсов и отсутствие точного аналитического решения?