Skip to content

Latest commit

 

History

History
135 lines (77 loc) · 10.9 KB

132pattern.md

File metadata and controls

135 lines (77 loc) · 10.9 KB

132 Pattern

Задача

Дан массив из n целых чисел nums. Паттерн 132 — это подпоследовательность трех чисел nums[i] , nums[j] и nums[k] , таких что i < j < k и nums[i] < nums[k] < nums[j] .

Вернуть true, если в nums есть паттерн 132, в противном случае вернуть false.

Задача на LeetCode.

Вопросы

На собеседовании важно задавать уточняющие вопросы, чтобы полностью понять условия задачи.

  1. Уточнение входных данных:

    • Можете ли вы уточнить формат входных данных? Это список, массив, строка или другая структура данных?

      Может быть любая другая структура данных, которая сможет хранить n целых чисел — не важно, главное чтобы фукнция работала правильно. Скажем, если пишем на плюсах, пусть функция принимает вектор по ссылке, а не указатель на начало массива, для удобства.

    • Всегда ли элементы входных данных являются целыми числами? Могут ли они быть отрицательными или нулевыми?

      Целые числа -10^9 <= nums[i] <= 10^9

  2. Ограничения задачи:

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

      Количество чисел 1 <= n <= 2 * 10^5

    • Есть ли какие-либо ограничения по использованию памяти или времени?

      Как минимум, должно работать за квадрат, а в идеале — за линию. По памяти ограничений нет (в пределах разумного 😅)

  3. Ожидаемый результат:

    • Что должна вернуть функция, если входные данные пусты или равны null?

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

  4. Алгоритмический подход:

    • Если придется выбирать, что важнее в данной задаче — время или память?

      Время важнее, памяти завались.

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

Примеры

Три примера от интервьюра с объяснениями. На этом месте интервьюер уже начинает просыпаться и понимать, что должно быть интересно.

  1. Пример 1:
  • find132pattern([1, 2, 3, 4]) -> false
  • В последовательности нет паттерна.
  1. Пример 2:
  • find132pattern([3, 1, 4, 2]) -> true
  • В последовательности есть паттерн: [1, 4, 2].
  1. Пример 3:
  • find132pattern([-1, 3, 2, 0]) -> true
  • В последовательности три паттерна: [-1, 3, 2], [-1, 3, 0] и [-1, 2, 0].

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

  1. Пример 4:
  • find132pattern([3, 5, 0, 3, 4]) -> true
  • Пояснение: В последовательности есть паттерн: [3, 5, 4]

Вот и ответ — речь про любые три числа в массиве (подпоследовательность), а не три идущих подряд числа (подмассив). Это делает задачу нетривиальной.

Решение методом перебора (brute-force)

Полезно обсудить решение в лоб, чтобы убедиться, что оно точно не укладывается в заданные ограничения. Ведь если укладывается — зачем платить больше, верно?

Решение этой задачи брутфорсом подразумевает проверку всех возможных комбинаций троек чисел и проверку на паттерн.

  • Использовать три вложенных цикла для всех возможных комбинаций троек чисел в массиве
  • Для каждой комбинации троек проверить, удовлетворяют ли они паттерну
    • Если это условие выполняется для хотя бы одной комбинации, вернуть true
  • Если не нашли ответ раньше - значит ответа нет, возвращаем false

Сложности по времени O(n^3) , где n - длина массива. Точное время сказать сложно, но точно много 😅 Перебрать 10^15 комбинаций — 1 секунды точно не хватит.

Если нарисовать точки на графике, появляется первая интуиция.

Вместо того, чтобы проверять все интервалы, нужно сосредотчиться на как можно более "широких" интервалах (nums[i], nums[j]) , чтобы увеличить вероятность нахождения nums[k] за ними.

Если основываться только на примере выше, то приходит в голову следующее решение.

Первая интуция

  • Инициализируем min первым элементом списка, и бежим по списку
  • Если попали в интервал, то есть больше текущего min и меньше текущего max — мы нашли шаблон.
  • Иначе, обновляем min (может быть только меньше текущего min) и max (может быть только больше текущего max)

Однако, это работает не всегда 😔

Можно ли обнулить min , max в таком случае и начать все заново для нового тренда? Это будет работать если ответ существует для него. Однако, как видно в примере выше, nums[k] существует для первого интервала, но не существует для второго, поэтому про первый нельзя просто забыть.

Подход к снаряду номер два — хранить предыдущие интервалы.

Решение за O(n)

Когда встречаем новый минимум, нужно сформировать новый интервал и положить его на стек. Теперь каждое новое число может либо обновить его правую границу, формируя новый восходящий тренд, либо удалить этот интервал (и все предыдущие) со стека, если новое число не попадает в интервал.

В итоге, алгоритм выглядит так:

  • Заводим пустой стек пар (l, r) для интервалов, и бежим по списку
  • Если стек пустой или текущее число меньше l интервала на вершине стека — создаем новый интервал и кладем на стек
  • Иначе
    • Запоминаем l у интервала на вершине стека (нужен будет для создания нового интервала)
    • Чистим стек от интервалов, снимая с вершины, для которых текущее число больше r
    • Если текущее число попадает в интервал на вершине стека (l < текущее число < r) — мы нашли ответ, возвращаем true
    • Иначе
      • Создаем новый интервал (l, текущее число) и кладем на стек
  • Если не нашли ответ раньше - значит ответа нет, возвращаем false

Сложность падает до O(n) , так как мы трогаем каждое число один раз. По памяти так же O(n) , так как интервалов на стеке не может быть больше исходного количества чисел.

На этом месте собеседование, в принципе, можно успешно заканчивать, так как текущее описание можно давать ChatGPT и он напишет код на любой языке 😉

На самом деле, последние 10 минут нужно потратить на написание кода и тестирование. Важно, что это буквально последний этап, который не должен занимать более 10 минут так как понятно до деталей что делать.

P. S. Обсудить можно в телеграм-чате любознательных программистов. Welcome! 🤗

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