Публичное собеседование по алгоритмам

Коротко о видео

Это вторая часть публичного собеседования по алгоритмам. Интервьюер формулирует задачу: на каждой итерации выбирать сообщения из нескольких очередей с учётом их весов и ограниченной пропускной способности канала. Кандидат уточняет требования к справедливости, чтобы небольшие очереди не оставались без обслуживания при постоянной нагрузке от более приоритетных. Участники обсуждают представление весов, вероятностный выбор, равномерное распределение и то, почему узкие диапазоны могут приводить к голоданию очереди. Затем они разбирают временную сложность в зависимости от количества очередей, запускают подготовленный код и отвечают на вопросы аудитории о сходстве задачи с практическими сценариями.

Затронутые темы

Что взять на заметку

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