Алгоритмическое собеседование: бинарный поиск и задачи на случайность

Алгоритмическое собеседование проверяет не память на десятки шаблонов, а способность последовательно решать новую задачу. Мы советуем сначала сделать условие точным, затем назвать простое решение и только после этого переходить к оптимизации. Такой порядок помогает кандидату не потеряться, а интервьюеру — увидеть ход мысли.

Что на самом деле проверяют на алгоритмической секции

У задачи есть два результата. Первый — работающая программа. Второй — понятное объяснение, почему программа работает. На собеседовании важны оба.

До написания кода стоит уточнить входные данные: может ли массив быть пустым, отсортирован ли он, бывают ли повторы, какой размер ожидается. Затем полезно привести маленький пример и пройти его вручную. Уже на этом этапе часто обнаруживается, что условие понято неверно.

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

Бинарный поиск: держим границы под контролем

Бинарный поиск применим, когда данные отсортированы. Мы сравниваем искомое значение со средним элементом и отбрасываем половину диапазона, в которой ответа точно нет. Поэтому число шагов растёт медленно: сложность поиска — O(log n).

Главная причина ошибок — не сама идея, а работа с границами. Нужно заранее решить, включены ли левая и правая границы, и придерживаться этого правила до конца.

def binary_search(values: list[int], target: int) -> int:
    # Обе границы входят в текущую область поиска.
    left = 0
    right = len(values) - 1

    while left <= right:
        # Средний индекс делит оставшийся диапазон на две части.
        middle = (left + right) // 2

        if values[middle] == target:
            return middle
        if values[middle] < target:
            # Средний элемент уже проверен, поэтому исключаем его.
            left = middle + 1
        else:
            right = middle - 1

    # Значение отсутствует в массиве.
    return -1


# Число 7 находится на позиции 3.
print(binary_search([1, 3, 5, 7, 9], 7))

После кода проверьте пустой список, один элемент, отсутствующее значение, первый и последний элементы. Такой набор занимает меньше минуты и показывает аккуратность.

Случайный выбор по весам через накопленные суммы

Пусть у нас есть вероятности [0.1, 0.4, 0.2, 0.3]. Их сумма равна единице. Превратим их в накопленные границы: [0.1, 0.5, 0.7, 1.0]. Случайное число 0.62 попадает между 0.5 и 0.7, значит, выбирается индекс 2.

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

from bisect import bisect_left
from itertools import accumulate
from random import random


def weighted_index(weights: list[float]) -> int:
    # Накопленные суммы превращают веса в границы интервалов.
    borders = list(accumulate(weights))

    # Умножение позволяет работать и с весами, сумма которых не равна единице.
    point = random() * borders[-1]

    # Находим первый интервал, правая граница которого не меньше point.
    return bisect_left(borders, point)


# Результат меняется при каждом запуске, но большие веса выбираются чаще.
print(weighted_index([0.1, 0.4, 0.2, 0.3]))

На интервью важно отдельно проверить, что список не пуст, веса неотрицательны, а их сумма больше нуля. Это уже не деталь синтаксиса, а часть корректного решения.

Резервуарная выборка для потока неизвестной длины

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

Решение начинается с первого элемента. Для элемента с номером i мы заменяем текущий результат с вероятностью 1 / i. После обработки всего потока каждый элемент остаётся в резервуаре с вероятностью 1 / n, где n — итоговая длина.

from random import randrange
from typing import Iterable, TypeVar

T = TypeVar("T")


def reservoir_sample(items: Iterable[T]) -> T:
    # Пока поток пуст, результата нет.
    selected: T | None = None

    for position, item in enumerate(items, start=1):
        # Для позиции i заменяем ответ с вероятностью 1 / i.
        if randrange(position) == 0:
            selected = item

    if selected is None:
        # Пустой поток нужно обработать явно.
        raise ValueError("Нельзя выбрать элемент из пустого потока")

    return selected


# Каждый элемент списка имеет одинаковый шанс стать результатом.
print(reservoir_sample([10, 20, 30, 40]))

Здесь ценится не запомненная формула, а доказательство. Новый элемент выбирается с вероятностью 1 / i, а старый сохраняется с вероятностью (i - 1) / i. Произведение вероятностей даёт одинаковый итоговый шанс для всех элементов.

Как объяснять решение, чтобы вас было легко оценить

Мы рекомендуем один и тот же каркас ответа для разных задач:

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

Если решение не складывается, зафиксируйте точку затруднения: «Я умею найти ответ линейно, но пока не вижу, как переиспользовать отсортированность». Такой комментарий даёт интервьюеру возможность помочь именно там, где это нужно.

Как превратить подготовку в измеримый процесс

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

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

На тренажёре собеседований ЮНИКОД мы связываем вопросы с темами и помогаем пройти этот цикл последовательно. Так подготовка заканчивается не списком просмотренных разборов, а навыком спокойно решать и объяснять задачу в реальном диалоге.

Источники

• Модуль bisect в документации Python
• Модуль random в документации Python
• Jeffrey Vitter: Random Sampling with a Reservoir