Вернуться в каталог собеседований

#5 Собеседование в Яндекс, АЛГОРИТМЫ | РАЗБОР ЗАДАЧ

Короткий разбор алгоритмических задач из собеседования в Яндекс: бинарный поиск и выбор случайного элемента с заданными вероятностями.

Направление
Data Science
Формат
Разбор интервью
Компания
Яндекс
Длительность
7:03
Вадим Новосёлов | Карьера в IT
  • Опубликовано на YouTube:
  • Просмотры на YouTube: 67,6 тыс.
  • Лайки на YouTube: 1,8 тыс.
Открыть на YouTube

Таймлайн

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

Короткий выпуск разбирает задачи Яндекса на бинарный поиск и случайный выбор с заданными вероятностями. Во второй задаче массив вероятностей превращается в интервалы кумулятивной суммы, а третью задачу автор не успевает решить и оставляет как бонус.

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

PythonАлгоритмыБинарный поискСложность алгоритмов

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

  • Бинарный поиск каждый раз сравнивает искомое со средним элементом отсортированного массива и отбрасывает половину диапазона.
  • Для выборки по весам постройте кумулятивную сумму вероятностей и определяйте индекс по интервалу, куда попало случайное число от нуля до единицы.
  • Третья задача требует равновероятно выбирать элементы потока, размер которого заранее неизвестен; готового решения в видео нет.

Рекомендуем посмотреть