✏️ Задача с собеса: кинотеатр и лучшие места

В кинотеатр пришли люди, и часть мест уже занята.
Места описаны массивом из нулей и единиц:

1 — место занято
0 — место свободно

Нужно найти такое место, чтобы сидящий оказался как можно дальше от ближайшего соседа.

Разбор решения

Нужно рассмотреть три типа промежутков свободных мест:

• Начало ряда — расстояние до ближайшего соседа = количество нулей
• Конец ряда — расстояние = количество нулей
• Середина — расстояние = количество нулей / 2. Целочисленное деление.

Алгоритм

1. Проходим по массиву один раз
2. Отслеживаем индекс последнего человека, которого мы встретили
3. При встрече человека вычисляем расстояние:

• Если это первый человек → берём его индекс (левый край)
• Если не первый → вычисляем (текущий_индекс - прошлый_индекс) / 2

3. После цикла проверяем правый край: n - 1 - последний_индекс
4. Возвращаем максимум из всех расстояний.

Код:

public class Solution {
    public int MaxDistToClosest(int[] seats) {
        int n = seats.Length;
        int maxDist = 0;
        int lastPerson = -1;
        
        for (int i = 0; i < n; i++) {
            if (seats[i] == 1) {
                if (lastPerson == -1) {
                    // Левый край
                    maxDist = i;
                } else {
                    // Середина
                    maxDist = Math.Max(maxDist, (i - lastPerson) / 2);
                }
                lastPerson = i;
            }
        }
        
        // Правый край
        maxDist = Math.Max(maxDist, n - 1 - lastPerson);
        
        return maxDist;
    }
}

Задача решается одним проходом за линейное время. Главное — правильно обработать три случая: левый край, середину и правый край.

➡️ Попробовать решить

Чтобы щёлкать такие задачи нужно знать алгоритмы. Подтянуть такую базу поможет наш курс по алгоритмам. До конца октября скидка 40%

🐸 Библиотека шарписта

#dotnet_challenge

✏️ Как найти два повторяющихся числа в массиве

Вам дан массив nums длиной n+2, содержащий числа от 0 до n-1. Два числа случайным образом появились в списке дважды. Нужно вернуть эти два числа. Например, для входа [0][1][1][2][3][3][4] ответ будет [1][3].

Для решения можно воспользоваться подсчётом количества появлений каждого числа.

Если встретили число во второй раз — записываем его в ответ:

public int[] GetSneakyNumbers(int[] nums)
{
    int n = nums.Length;
    int[] count = new int[101];
    int[] res = new int[2];
    int idx = 0;

    foreach (var num in nums)
    {
        count[num]++;
        if (count[num] == 2)
        {
            res[idx] = num;
            idx++;
        }
    }
    return res;
}

При помощи вспомогательного массива считаем, сколько раз встречается каждое число, и когда оно появилось второй раз — запоминаем.

➡️ Попробовать решить

🐸 Библиотека шарписта

#dotnet_challenge

✏️ Задачка с собеса

Дано целое число, нужно проверить, является ли оно полным квадратом.

Первый рефлекс новичка — взять квадратный корень и проверить, целое ли число:

(int)Math.Sqrt(num) * (int)Math.Sqrt(num) == num

Но на собесе после этого последует вопрос: «А можете без встроенной функции?» Вот тогда начинается интересное.

Вместо математики используем логику: если x * x = num, то x находится где-то между 1 и num. Сужаем диапазон поиска, пока не найдём точный ответ.

public bool IsPerfectSquare(int num)
{
    long left = 1;
    long right = num;
    
    while (left <= right)
    {
        long mid = (left + right) / 2;
        long square = mid * mid;
        
        if (square == num)
            return true;
        else if (square < num)
            left = mid + 1;
        else
            right = mid - 1;
    }
    
    return false;
}

Есть ещё метод Ньютона для поиска корня — он даже быстрее для больших чисел:

public bool IsPerfectSquare(int num)
{
    long x = num;
    
    while (x * x > num)
    {
        x = (x + num / x) / 2;
    }
    
    return x * x == num;
}

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

➡️ Попробовать решить

🐸Библиотека шарписта

#dotnet_challenge