Кодирование проблемы с собеседованием

Сложный уровень

Середина

Запрошено

Amazon, VMware

Обсуждены два решения

  1. Использование вложенных циклов - решение методом грубой силы
  2. Техника использования скользящего окна - эффективное решение

Основные выводы после прочтения этого блога

Это одна из хороших проблем для понимания идеи техники скользящего окна. Используя этот подход, мы можем эффективно решить несколько задач интервью в пространстве O (n) и O (1). (Подумайте!)

Давайте разберемся в проблеме:

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

Пример 1

Input: A[]= [1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1], m = 2
Output: [5, 7]
Explanation: We are allowed to flip the maximum of 2 zeroes. If we flip A[5] and A[7], we get 8 consecutive 1’s which is maximum possible under given constraints
Input: A[] = [1, 1, 0, 1, 0, 1, 0, 0, 1], m = 1
Output: 2
Explanation: We are allowed to flip maximum 1 zero. If we flip 
A[2], we get 4 consecutive 1's which is maximum possible under given constraints.

Примечания к проблемам

  • Возвращает индексы максимальной непрерывной серии единиц по порядку.
  • Если существует несколько возможных решений, верните последовательность с минимальным начальным индексом.

1. Решение методом грубой силы - использование вложенных циклов

Идея алгоритма

Решение методом перебора состоит в том, чтобы рассмотреть каждый подмассив, запустив два вложенных цикла. Для каждого подмассива подсчитайте количество нулей в нем и верните подмассив максимального размера с m или меньшим количеством нулей. (Подумайте!)

Код алгоритма C ++

Анализ алгоритмов

Сложность времени: в худшем случае нам нужно проверить каждый небольшой подмассив. Для этого мы запускаем два вложенных цикла в решении, где для каждого значения i j изменяется от i до n -1. Общее количество циклов = n + n -1 + n-2… + 1 = n (n-1) / 2 = O (n²)

Космическая сложность = O (1)

Возможные вопросы интервьюера

  • Почему сложность пространства O (1)?
  • Изучить лучший, средний и наихудший сценарий?
  • Как мы можем улучшить временную сложность?

2. Эффективное решение: использование техники скользящего окна.

Шаги алгоритма

  • Инициализируйте левый и правый указатели окна с нулями в качестве начального индекса, l = 0, r = 0.
  • Увеличьте правый указатель, если идет ноль, тогда уменьшите m, иначе нет.
  • На каждом шаге увеличения правого указателя сохраняется значение размера окна и значение левого и правого индекса, если предыдущее окно меньше текущего.
  • Если m становится нулем, увеличивайте левый указатель до тех пор, пока левый указатель не достигнет правого указателя или не появятся следующие нули.
  • Выполняйте шаги b, c, d, пока указатель записи не достигнет размера массива.

ручка для обработки углов

я. Если m == 0 и array = [1,0,1,0]

решение: строка № 42 по 46

Код алгоритма C ++

vector<int> Solution::maxOne(vector<int> &A, int m) 
{
    int l = 0,r = 0;
    vector<int> ans;
    int ansleft, ansright;
    int cntsize = 0;
    while(r < A.size())
    {
        if (A[r] == 1)
        {
            if(cntsize < (r-l+1) && r < A.size())
            {
                ansleft = l;
                ansright = r;
                cntsize = r-l+1;
            }
            r++;
        }
        else if(A[r] == 0 && m >0)
        {
            m--;
            if(cntsize < (r-l+1) && r < A.size())
            {
                ansleft = l;
                ansright = r;
                cntsize = r-l+1;
            }
            r++;
        }
        else 
        {
            while(l < r && m == 0)
            {
                if(A[l] == 1)
                    l++;
                else
                {
                    m++;
                    l++;
                    break;
                }
            }
            if(l == r && m == 0)
            {
                l++;
                r++;
            }
            
        }
    }
    if(cntsize > 0)
    {
        for(int i = ansleft;i <= ansright; i++)
        {
            ans.push_back(i);
        }
    }
    return ans;
}

Анализ алгоритмов

Сложность пространства = O (1) пробел, поскольку используется единственная переменная.

Сложность времени = наихудший: O (2 * n), если каждый элемент повторяется 2 раза, и лучший: O (n), если каждый элемент повторяется 1 раз.

Возможные вопросы интервьюера

  • Почему мы перемещаем правый указатель вперед, когда A [r] == 1?
  • Почему мы проверяем условие r ‹A.size ()?
  • Почему мы уменьшаем m, когда находим A [r] = 0?
  • Объясните код, когда значение m становится равным нулю.
  • Почему временная сложность O (n)? Объясните это, посчитав общее количество критических операций, выполненных циклом?
  • Можно ли решить эти проблемы другим подходом? (Подумайте!)

Проблемы для практики - подход со скользящим окном

  • Массив A размера 2n, в нем n + 1 уникальный элемент, и ровно один из этих элементов повторяется n раз. Вернуть элемент, повторенный n раз.
  • Для массива, состоящего из n целых чисел, найдите непрерывный подмассив заданной длины, который имеет максимальное среднее значение.
  • Учитывая массив положительных чисел, вычислите количество возможных смежных подмассивов, у которых произведение меньше заданного числа K.