Задачи с собеседований / Алгоритмы. Two Pointers (два указателя)
В этом видео попробуем порешать задачки с собеседований (алгоритмическая секция). Решим правильно, но неоптимально. Обсудим алгоритмическую сложность и нотацию Big O. А затем улучшим решение до O(n). Для этого воспользуемся подходом Two Pointers (два указателя). В общем, первое видео на канале про алгоритмы.
Содержание:
00:00 Введение
02:12 Плюсы и минусы алгоритмических секций
06:04 Постановка задачи
08:18 Решаем задачу. Неоптимальный вариант
12:59 Обсуждаем решение. Алгоритмическая сложность
17:14 Нотация O-большое
19:27 Разные виды алгоритмической сложности
23:38 Обсуждаем алгоритмическую сложность неоптимального решения
26:57 Two Pointers (два указателя)
33:49 Новое решение. От O(n * log n) до O(n)
39:21 Ещё одна задача. Закрепляем навыки
46:52 Предварительные итоги. Что почитать, как готовиться
52:49 Заключение
Полезные ссылки:
* Мой блог в Telegram: t.me/antonovjs
* Метод массива map - developer.mozilla.org/ru/docs...
* Подход Two Pointers - leetcode.com/articles/two-poi...
Пікірлер: 21
Супер! Требуем больше видео такого формата👍🏾👍🏾👍🏾👍🏾
вторая задачка поинтереснее первой :) жду видео по алгоритмам, это будет изумруд😌
спасибо, очень интересно.
Работаю давно, опыта коммерческого хватает, освежил память, спасибо за видео! Буду смотреть)
Наконец-то вышло видео 😃
большое спасибо за классное и наглядное объяснение) будет круто увидеть аналогичным образом все основные алгоритмы)
В решении второй задачки есть ошибка. Если в последний из трёх тестовых массивов добавить в конец число 8, то левый и правый поинтеры встретятся на этой восьмёрке, сложат её саму с собой и функция радостно выдаст true. Ошибка в условии while: там в отличие от первой задачи нужно строгое неравенство < вместо нестрогого
@antonov_i
9 күн бұрын
Спасибо! 🤝Посмотрю. Видимо пропустил. Как раз хотел обновить решение и улучшить
Одно из самых полезных видео по алгоритмам используя JavaScript, которое я смотрел. Советы действенные, спасибо! По всем бы базовым алгоритмам и структурным типам такое видео.
Отличное обьяснение алгоритмов!
Классный видос, хорошо объяснил
Мне кажется, что для второй задачи нужно либо уточнить условие, либо поменять алгоритм. Исходя из алгоритма мы проверяем что в массиве есть два числа, которые в сумме дают target, однако если target = результату суммы 3-х и более чисел, то программа нам вернет false. Например, isTargetExists([1, 2, 3, 7], 6) вернет false, когда 1 + 2 + 3 = 6. Возможно я неправильно понял условие 🤔
Чет не могу понять, добавление в начало массива работает за O(n), так как происходит сдвиг предыдущих элементов. вы делаете добавление в начало внутри while, как получилось O(n)?
Если попробовать провести тесты с другими массивами, типа [9, 2, 5, 3], то результат огорчит, тк результат будет неправильно отсортирован [ 81, 4, 25, 9 ]
@antonov_i
8 ай бұрын
Всё верно. Условие задачи говорит, что массив должен быть отсортирован по возрастанию. Алгоритм решения подобран исходя из этого. Само собой, если по условию массив не отсортирован, то тогда придётся применять какой-либо алгоритм сортировки. Если передать [2, 3, 5, 9] (то есть предварительно применить сортировку), то работать будет так, как и ожидается.
я тупой объясните мне тупому как? КАК?? вставить элемент в начало массива( not a LIst !) не смещая уже вставленные элементы даже у JavaScript массива который ведет себя как List у всего есть цена. на практике, если очень уж хочется заморочится.... через map получил бы массив квадратов элементов и сортировал результат по месту.
@antonov_i
8 ай бұрын
Магии никакой нет. При использовании unshift элементы будут сдвигаться вправо. Сложность при этому будет O(n), то есть расти линейно. Вариант с map и сортировкой в видео рассматривал. Но добавление сортировки приведёт к O(n * log n), сложность возрастёт.
@carry-on-chaos4032
7 ай бұрын
@@antonov_i сложность не будет O(n) так как сложность зависит так же от памяти. а смещение всех элементов массива это плохой алгоритм, в текущей задаче алгоритм с сортировкой будет даже предпочтительней. Под предоставленные тест кейсы можно подогнать решение с одним проходом по массиву, но под другие тест кейсы оптимальный вариант это 2 линейных обхода массива
@umni_kot
2 ай бұрын
@@carry-on-chaos4032 вы шизофреник
@innokentyk9016
2 ай бұрын
@@carry-on-chaos4032 Ты пойми магии нет. Что ты тут колдуешь. Чел не в курсе за Math.abs и за reverse
@andrewkruchini8614
Ай бұрын
@@carry-on-chaos4032 судя по Вашему возмущению, Вы заглянули сюда из мира C/C++, где массивом называют область памяти, в которой нулевой элемент всегда хранится по нулевому смещению. Как рализован массив в JS, не знаю, но из наличия метода unshift могу предположить, что как двусторонняя очередь (например, на основе кольцевого буфера), где вставка в начало и конец происходят за O(1).