Какие алгоритмы вы использовали, например бинарный поиск, алгоритмы на графах (Дейкстра, поиск в глубину и ширину)

Что проверяют

Есть ли за названиями алгоритмов реальный опыт и умеете ли вы писать их на C++ без типичных ошибок. После ответа почти наверняка попросят реализовать один из них или объяснить, почему Дейкстра не работает с отрицательными весами.

Как отвечать

Про каждый алгоритм три вещи: где применяли, сложность и деталь реализации на C++. Примеры берите свои. Если в работе таких задач не было, так и скажите и опишите учебные или олимпиадные.

• бинарный поиск: O(log n) на отсортированных данных. В C++ его почти не пишут руками: std::lower_bound, std::upper_bound, std::equal_range, std::partition_point, в C++20 те же функции из std::ranges. Руками нужен поиск по ответу, например минимальный размер буфера, при котором проходит проверка. Середину считают как lo + (hi - lo) / 2 или через std::midpoint, чтобы не переполнить;
• BFS: O(V + E), кратчайший путь в невзвешенном графе, std::queue и массив расстояний. Для весов 0 и 1 есть 0-1 BFS на std::deque;
• DFS: O(V + E), компоненты связности, топологическая сортировка, поиск циклов. Рекурсивный DFS на графе в сотни тысяч вершин легко переполняет стек, поэтому его переписывают на явный стек;
• Дейкстра: O((V + E) log V) с std::priority_queue и std::greater<>. Очередь не умеет уменьшать ключ, поэтому в неё кладут дубликаты и пропускают устаревшие записи, у которых расстояние больше уже найденного.

Назовите и представление графа: список смежности std::vector<std::vector<Edge>> для разреженных графов, матрица для плотных и небольших. Для веса пути берите long long: сумма рёбер в int переполняется быстрее, чем кажется.

Где спотыкаются

Применяют Дейкстру к графу с отрицательными рёбрами. Алгоритм считает извлечённую вершину окончательной, отрицательное ребро это ломает, здесь нужен Беллман-Форд.

Пишут свой бинарный поиск с ошибкой на границах: бесконечный цикл при lo = mid или промах на последнем элементе, хотя std::lower_bound решает задачу одной строкой.

Рассказывают выдуманный проект «маршрутизации между серверами» и путаются на первом уточнении. Честный учебный пример вызывает больше доверия, чем легенда.