Плавающее окно фиксированного размера

В уроке ты

Научишься работать с задачами на тему "плавающее окно фиксированного размера", чтобы успешно пройти собеседование и попасть в компанию мечты
Решишь задачу собеседования в BigTech
Узнаешь, как часто задачи на плавающее окно встречаются на собеседованиях и в работе

Как часто плавающее окно встречается на собеседованиях

По результатам нашего опроса, примерно каждый 15-й кандидат получает задачу на плавающее окно (sliding window). Но не всё так просто!

Компании с численностью менее 1000 человек обычно выбирают более классические темы, такие как два указателя или хеш-таблицы. Но если ты нацелился на BigTech или крупные компании вроде «Жёлтого банка», «Красной большой IT-компании» или «Зелёного банка», то без знаний о плавающем окне тебе не обойтись!

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

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

Пример задачи с собеседования

Представь, что ты на собеседовании в компанию мечты, и тебе никак нельзя его провалить, ведь повторить попытку ты сможешь только через полгода. И вот тебе дают следующую задачу...

Условие

Дан массив чисел nums и число k. Нужно вернуть одно число — максимальную сумму k подряд идущих элементов

Пример

Ввод: nums = [3, 2, 5, 9, 4, 1], k = 3
Вывод: 18
Объяснение: 5 + 9 + 4 = 18

В чём сложность задачи

Основная сложность — решить задачу оптимально. Можно перебрать все возможные суммы и написать такое решение:

public class Solution
{
    public static int MaxSum(List<int> nums, int k)
    {
        int n = nums.Count;
        int maxResult = int.MinValue;
        for (int i = 0; i <= n - k; i++)
        {
            int currSum = 0;
            for (int j = 0; j < k; j++)
            {
                currSum += nums[i + j];
            }
            if (currSum > maxResult)
            {
                maxResult = currSum;
            }
        }
        return maxResult;
    }
}

#include <vector>
#include <climits>

using namespace std;

int maxSum(vector<int>& nums, int k) {
    int n = nums.size();
    int maxResult = INT_MIN;
    for (int i = 0; i <= n - k; i++) {
        int currSum = 0;
        for (int j = 0; j < k; j++) {
            currSum += nums[i + j];
        }
        if (currSum > maxResult) {
            maxResult = currSum;
        }
    }
    return maxResult;
}

#include <vector>
#include <climits>

using namespace std;

int maxSum(vector<int>& nums, int k) {
    int n = nums.size();
    int maxResult = INT_MIN;
    for (int i = 0; i <= n - k; i++) {
        int currSum = 0;
        for (int j = 0; j < k; j++) {
            currSum += nums[i + j];
        }
        if (currSum > maxResult) {
            maxResult = currSum;
        }
    }
    return maxResult;
}

package main

import "math"

func maxSum(nums []int, k int) int {
    n := len(nums)
    maxResult := math.MinInt
    for i := 0; i <= n-k; i++ {
        currSum := 0
        for j := 0; j < k; j++ {
            currSum += nums[i+j]
        }
        if currSum > maxResult {
            maxResult = currSum
        }
    }
    return maxResult
}

import java.util.*;

public class Solution {
    public int maxSum(List<Integer> nums, int k) {
        int n = nums.size();
        int maxResult = Integer.MIN_VALUE;
        for (int i = 0; i <= n - k; i++) {
            int currSum = 0;
            for (int j = 0; j < k; j++) {
                currSum += nums.get(i + j);
            }
            if (currSum > maxResult) {
                maxResult = currSum;
            }
        }
        return maxResult;
    }
}

/**
 * @param {number[]} nums
 * @param {number} k
 * @returns {number}
 */
export function maxSum(nums, k) {
  const n = nums.length;
  let maxResult = -Infinity;
  for (let i = 0; i <= n - k; i++) {
    let currSum = 0;
    for (let j = 0; j < k; j++) {
      currSum += nums[i + j];
    }
    if (currSum > maxResult) {
      maxResult = currSum;
    }
  }
  return maxResult;
}

Если nums = [3, 2, 5, 9, 4, 1] и k = 3, то мы посчитаем:

Сумму первых трёх элементов: 3 + 2 + 5 = 10
Сумму следующих трёх элементов: 2 + 5 + 9 = 16
Сумму следующих трёх: 5 + 9 + 4 = 18
Сумму последних трёх: 9 + 4 + 1 = 14

Наш ответ — максимальная из этих сумм, то есть 18. Поэтому на каждом шаге мы обновляем значение max_result, если текущая сумма больше.

Обрати внимание, что каждую сумму мы считаем заново, и по времени это занимает O(n * k). Такая сложность приемлема для небольших массивов, но при больших n и k решение будет работать долго.

Именно поэтому на собеседовании такое решение не примут, и интервьюер попросит тебя решить задачу более эффективно.

Как решить эффективно?

Можно заметить, что, посчитав сумму первых k чисел, нам не нужно полностью пересчитывать сумму для следующих k элементов, ведь большинство элементов в соседних окнах совпадают.

Чтобы решить задачу оптимально, нам нужно научиться быстро находить сумму для следующего окна размера k. Алгоритм будет таким:

Находим сумму первых k элементов
Для каждого следующего окна:
1. Вычитаем значение первого элемента предыдущего окна
2. Прибавляем значение следующего элемента из массива

Посмотрим на примере nums = [3, 2, 5, 9, 4, 1] и k = 3:

Сумма первых трёх чисел: 3 + 2 + 5 = 10
Сумма вторых трёх чисел: 10 - 3 + 9 = 16 (то же самое, что 2 + 5 + 9)
Сумма третьих трёх чисел: 16 - 2 + 4 = 18 (то же самое, что 5 + 9 + 4)
Сумма четвёртых трёх чисел: 18 - 5 + 1 = 14 (то же самое, что 9 + 4 + 1)

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

Паттерн «фиксированная длина»

Задача, которую мы разобрали, не является исключением. Существует целый класс задач на «плавающее окно фиксированной длины», и для их решения применяется определённый алгоритм:

Сформировать первое плавающее окно.
Придумать, как эффективно двигать наше окно, используя информацию из предыдущих вычислений.

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

public class Solution
{
    public static int MaxSum(List<int> nums, int k)
    {
        int n = nums.Count;
        if (k > n) return 0;

        // Находим сумму первых k элементов
        int currSum = 0;
        for (int i = 0; i < k; i++)
        {
            currSum += nums[i];
        }
        int maxSumResult = currSum;

        // Двигаем окно по массиву
        for (int i = k; i < n; i++)
        {
            // Обновляем сумму: вычитаем первый элемент предыдущего окна, добавляем новый
            currSum = currSum - nums[i - k] + nums[i];
            // Обновляем максимальную сумму, если нужно
            if (currSum > maxSumResult)
            {
                maxSumResult = currSum;
            }
        }
        return maxSumResult;
    }
}

#include <vector>
#include <algorithm>

using namespace std;

int maxSum(vector<int>& nums, int k) {
    int n = nums.size();
    if (k > n) return 0;

    // находим сумму первых k элементов
    int currSum = 0;
    for (int i = 0; i < k; i++) {
        currSum += nums[i];
    }
    int maxSumResult = currSum;

    // двигаем окно по массиву
    for (int i = k; i < n; i++) {
        // обновляем сумму: вычитаем первый элемент предыдущего окна, добавляем новый
        currSum = currSum - nums[i - k] + nums[i];
        // обновляем максимальную сумму, если нужно
        if (currSum > maxSumResult) {
            maxSumResult = currSum;
        }
    }
    return maxSumResult;
}

package main

func maxSum(nums []int, k int) int {
    n := len(nums)
    if k > n {
        return 0
    }

    // находим сумму первых k элементов
    currSum := 0
    for i := 0; i < k; i++ {
        currSum += nums[i]
    }
    maxSumResult := currSum

    // двигаем окно по массиву
    for i := k; i < n; i++ {
        // обновляем сумму: вычитаем первый элемент предыдущего окна, добавляем новый
        currSum = currSum - nums[i-k] + nums[i]
        // обновляем максимальную сумму, если нужно
        if currSum > maxSumResult {
            maxSumResult = currSum
        }
    }
    return maxSumResult
}

import java.util.*;

public class Solution {
    public int maxSum(List<Integer> nums, int k) {
        int n = nums.size();
        if (k > n) return 0;

        // находим сумму первых k элементов
        int currSum = 0;
        for (int i = 0; i < k; i++) {
            currSum += nums.get(i);
        }
        int maxSumResult = currSum;

        // двигаем окно по массиву
        for (int i = k; i < n; i++) {
            // обновляем сумму: вычитаем первый элемент предыдущего окна, добавляем новый
            currSum = currSum - nums.get(i - k) + nums.get(i);
            // обновляем максимальную сумму, если нужно
            if (currSum > maxSumResult) {
                maxSumResult = currSum;
            }
        }
        return maxSumResult;
    }
}

from typing import List

def max_sum(nums: List[int], k: int) -> int:
    n = len(nums)
    if k > n:
        return None  # Или вернуть 0, если нужно

    # Находим сумму первых k элементов
    curr_sum = sum(nums[:k])
    max_sum_result = curr_sum

    # Двигаем окно по массиву
    for i in range(k, n):
        # Обновляем сумму: вычитаем первый элемент предыдущего окна, добавляем новый
        curr_sum = curr_sum - nums[i - k] + nums[i]
        # Обновляем максимальную сумму, если нужно
        if curr_sum > max_sum_result:
            max_sum_result = curr_sum
    return max_sum_result

/**
 * @param {number[]} nums
 * @param {number} k
 * @returns {number}
 */
export function maxSum(nums, k) {
  const n = nums.length;
  if (k > n) return 0;

  // находим сумму первых k элементов
  let currSum = 0;
  for (let i = 0; i < k; i++) {
    currSum += nums[i];
  }
  let maxSumResult = currSum;

  // двигаем окно по массиву
  for (let i = k; i < n; i++) {
    // обновляем сумму: вычитаем первый элемент предыдущего окна, добавляем новый
    currSum = currSum - nums[i - k] + nums[i];
    // обновляем максимальную сумму, если нужно
    if (currSum > maxSumResult) {
      maxSumResult = currSum;
    }
  }
  return maxSumResult;
}

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

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

Как часто плавающее окно встречается в работе

В реальной работе тема плавающего окна встречается не так часто. Но это не значит, что её можно пропустить. Изучая различные алгоритмы, ты расширяешь свой кругозор и учишься находить более эффективные решения. Знание таких паттернов поможет тебе оптимизировать код и избежать ошибок.

Уверен, что изучение темы плавающих окон прокачает тебя как для собеседований, так и для повседневной работы. На нашем курсе нет задач, которые добавлены просто так. Каждая задача закладывает определённый фундамент и раскрывает тему с разных сторон. Поэтому очень важно решить все задачи — ты точно увидишь результат!

Что дальше?

Закрепи полученные знания на практике! Переходи к задачам и попробуй решить их самостоятельно. При решении придерживайся следующего алгоритма:

Убедись, что ты понял условие задачи и выясни все непонятные моменты.
Придумай идею решения. Здесь могут помочь ручка и бумага — собственные заметки зачастую помогают найти решение.
Оцени своё решение по времени и памяти.
Напиши код.
Проверь код на правильность синтаксиса.
Проверь код на правильность логики решения.
Отправляй на проверку!

Удачи в решении задач!