Зная эти паттерны ты решишь 60% задач на собеседовании

У меня 1000+ баллов на Codewars, много решённых задач на LeetCode и просто бесконечное множество решенных задач из разных приложений и собеседований.

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

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

Начнем с паттерна Two Pointers

Что за паттерн?

Это паттерн, в котором мы используем два указателя для прохода по массиву или строке.

Обычно есть два варианта использования:

1. Первый
left — начало🟢
right — конец🔴
Используется для: палиндромов, поиска пары, задач где важен порядок элементов.

2. Второй
slow — медленный🟢
fast — быстрый 🔴
Используется для: удаления дубликатов, перемещения нулей, фильтрации массива.

Как работает паттерн?

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

Вариант 1 - Навстречу друг-другу

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

Вариант 2 - медленный / быстрый

Подходит для: удаления дубликатов, перемещения нулей, фильтрации массива.
Тут есть два пути решения, первый наиболее частый:

1. slow на первом элементе, fast на втором → двигаем указатели по условию.

2. Оба указателя на первом элементе → fast бежит вперёд, slow обновляет нужные значения.

Пример использования

Разберем паттерн на задачке: Valid Palindrome.

ТЗ: Нужно написать функцию isPalindrome, которая принимает строку s и проверяет является ли она палиндромом.

const isPalindrome = (s) => {
  let left = 0; // Ставим указатель на первый элемент (индекс)
  let right = s.length - 1; // Ставим указатель на последний элемент (индекс)

  while (left < right) { // Двигаемся по строке пока не дойдем до середины
    if (s[left] !== s[right]) { // Если элементы разные то вернем false и выйдем из цикла
      return false;
    } 
    left++;
    right--;
  }

  return true;
};

console.log(isPalindrome("madam")); // true
console.log(isPalindrome("abc")); // false
console.log(isPalindrome("dad")); // true

Тут мы использовали первый вариант (Навстречу друг-другу), так как нам важен порядок элементов и сама задача нам подсказывает какой паттерн использовать.

Паттерн HashMap

Что за паттерн?

Это структура данных, которая хранит пары ключ → значение. Для создания использют объект или new Map.

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

Как работает паттерн?

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

Пример использования

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

ТЗ: Дана строка s. Необходимо найти первый символ, который встречается в строке только один раз, если такого нет вернуть null.

const firstUniqueChar = (s) => {
  const map = {}; // Создаем HashMap

  for (const char of s) { // Пробегаемся по строке и считаем кол-во символов
    if (!map[char]) {
      map[char] = 1;
    } else {
      map[char] += 1;
    }
  }

  for (const char of s) { 
    if (map[char] === 1) { // Находим уникальный символ если такой есть
      return char;
    }
  }

  return null;
};

console.log(firstUniqueChar("banana")); // b
console.log(firstUniqueChar("aabbc")); // c

Тут мы используем HashMap так как нам нужно подсчитать кол-во символов и далее найти нужный символ, без дополнительной структуры пришлось бы делать вложенные циклы (что хуже по времени).

Паттерн Stack

Что за паттерн?

Это структура данных, которая работает по принципу LIFO (Last In — First Out) - последний добавленный элемент извлекается первым.
Чтобы было проще понять, представь стопку книг: ты кладешь книгу сверху и снимаешь тоже сверху.

Используется для: задач на скобки ({[]}), вложенных структур, возврата назад, случаев когда нужно помнить предыдущие элементы.

Как работает паттерн?

В JavaScript Stack обычно реализуют через массив, используя push для добавления элемента и pop для удаления последнего.
То есть мы добавляем элемент в конец массива push, а затем удаляем последний pop.

Пример использования

Разберем паттерн на задачке: Проверка правильности скобок.

ТЗ: Дана строка s со скобками. Нужно проверить, правильно ли они закрываются.

const isValidBrackets = (s) => {
  const stack = []; // создаем Stack для хранения открывающих скобок
  const map = {
    ")": "(",
    "]": "[",
    "}": "{"
  };

  for (const char of s) { 
    if (char === "(" || char === "[" || char === "{") {
      stack.push(char); // сохраняем открывающую скобку
    } else {
      const last = stack.pop(); // берём последнюю открывающую скобку
      if (last !== map[char]) { // проверяем, соответствует ли закрывающая скобка последней открывающей
        return false;
      }
    }
  }

  return stack.length === 0;
};

console.log(isValidBrackets("{[()()]}")); // true
console.log(isValidBrackets("(){}[]")); // true
console.log(isValidBrackets("{[(])}")); // false

Тут мы используем Stack так как: нам нужно помнить предыдущие открытые скобки, каждая новая закрывающая скобка должна проверяться с последней открытой, последняя открытая скобка должна закрываться первой - это и есть принцип LIFO.

Заключение

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

Two Pointers

• работа со строкой или массивом?

• есть симметрия (палиндром)?

• нужно найти пару элементов?

• массив отсортирован?

• нужно сравнивать элементы с двух сторон?

  HashMap

• нужно посчитать количество элементов?

• есть слова: часто, уникальный, количество, анаграмма?

• нужно проверить наличие элемента?

• задача про соответствие данных (одни и те же элементы)?

• массив не отсортирован, но нужно быстро искать?

• сгруппировать элементы по какому-то признаку?

  Stack

• есть скобки или похожие структуры?

• есть вложенность?

• важен порядок закрытия / возврата?

• нужно помнить последний элемент?

• есть логика “откатиться назад”?

Зная паттерны и пользуясь этой подсказкой, вы можете начинать решать задачи, задавая себе важные вопросы для выбора подходящего паттерна. Сначала используйте подсказку, чтобы выработать привычку спрашивать себя: «Какой паттерн здесь применить?». Со временем, после множества решенных задач, вы будете определять паттерн и применять его очень быстро - это лишь вопрос опыта и практики.