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

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

Умеете ли вы свести бытовую формулировку к массиву и найти линейное решение без симуляции. Типичная постановка: ряд из 0 и 1, где 1 это занятое место, нужно сесть так, чтобы расстояние до ближайшего соседа было максимальным. Следом спрашивают про края ряда и про вариант, где рассаживают сразу несколько человек.

Как отвечать

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

• между занятыми местами с индексами i и j: садимся в середину, расстояние (j-i)//2;
• пустое начало ряда: садимся на место 0, расстояние равно индексу первого занятого;
• пустой хвост: садимся на последнее место, расстояние равно числу свободных мест после последнего занятого.

Ответ это максимум из трёх величин, всё считается за один проход, O(n) по времени и O(1) по памяти:

def max_dist_to_closest(seats):
    prev, best = -1, 0
    for i, taken in enumerate(seats):
        if taken:
            best = i if prev == -1 else max(best, (i-prev)//2)
            prev = i
    return max(best, len(seats)-1-prev)

Прогоните вслух примеры: [1,0,0,0,1,0,1] даёт 2, [1,0,0,0] даёт 3, потому что край пополам не делится.

Если спросят вариант с рассадкой k человек по заданным позициям, это другая задача: бинарный поиск по ответу. Сортируете позиции и для кандидата d жадно проверяете, помещаются ли k человек с шагом не меньше d, итог O(n log n). Для потока посадок и уходов, как в задаче про экзаменационный зал, свободные отрезки держат в куче или в SortedList из sortedcontainers.

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

Делят краевой промежуток пополам. На краю соседа с одной стороны нет, поэтому расстояние равно всей длине пустого участка.

Пишут симуляцию: для каждого свободного места ищут ближайшего соседа слева и справа. Это O(n²), и интервьюер сразу попросит улучшить.

Не уточняют постановку и решают соседнюю задачу. Одно место для одного человека и расстановка k человек решаются по-разному, и код бинарного поиска на первый вопрос не отвечает.