Task from JS interview - Find the intersection of two arrays | LeetCode

[@dianasicevaia4840]

Зашла сюда после интервью с Ильнурой)) спасибо за задачку

[@yuryitikhonoff9631]

Урааа. Очень полезная задача. Теория множеств.

[@frontendscience]

Благодарю за поддержку :)

[@igorkirey1642]

Утром для запуска мозга зашло) Спасибо! Блин, всё никак не разберусь с оценкой сложности.

[@frontendscience]

Походу надо сделать видео об этом. За поддержку спасибо)

[@luckytima2315]

Отличное видео ,спасибо большое )) 5:51 это просто гениально !!! Вспомнил mortal combad на sege ))

[@frontendscience]

Рад что понравилось!

[@valeriakan6474]

Мне очень нравится ваш канал! СПАСИБО за оптимальные решения задачек! У меня получилось решение со сложностью O(n*m), благодаря вам поняла как уменьшить сложность, КУЛ. Мое решение: const intersectMy = function (nums1, nums2) { const res = []; for (let i = 0; i < nums1.length; i++) { const current = nums1[i]; for (let j = 0; j < nums2.length; j++) { if (current === nums2[j]) { res.push(current); nums2.splice(j, 1); break; } } } return res; }

[@frontendscience]

Благодарю за добрые слова и за решение! Замечательно!

[@evgeniychip]

5:50 клёвая напоминалка на подписаться)))

[@ПавелЛевщанов]

Крутой канал. Я прям подсел. В условии этой задачи смутило что количество цифр в массиве до 1000. поэтому решил в лоб. const intersect = function (nums1,nums2) { let result = [] for (let i = 0; i < nums1.length; i++) { for (let j = 0; j < nums2.length; j++){ if (nums1[i]!=='undefined' && nums1[i]===nums2[j]) { result.push(nums1[i]) delete nums1[i] delete nums2[j] break; } } } return result }

[@frontendscience]

Благодарю за решение! Это ограничение именно с leetcode. Мне тоже показалось что как-то маловато ) я стараюсь решать такие задачи с представлением что массив ооооочень большой.

[@niklkelbon3662]

Ты условие не понял, не количество элементов, а сами числа в диапазоне от 1 до 1000 (причем не указано включительно или нет, ну да кого это интересует в таких задачах... ) Смотрю просто по приколу, решение приходит буквально за 0.001 сек, я бы мб в классе 7 на уроках паскаля такое давал

[@ku3mi41]

Использовать delete на элементах массива не совсем правильно, т.к. это приводит к образованию "дырок"

[@vovaseagull1097]

Спасибо за интересную задачу! возможно кому пригодиться можно еще вместо того что бы отнимать изменить немного условие в цикле для второго масива for (let x = 0; x < nums.length; x++) { const current = nums[x]; let count = map[current]; if (count && !newArray.includes(current)) { result.push(current); } }

[@frontendscience]

Благодарю за решение! Предложенный вариант выглядит покороче, но будет иметь сложность O(n*m).

[@DanilGilman]

Хочется видео о том, как оценивать сложность алгоритма :)

[@frontendscience]

Скоро будет :)

[@ИванБездомный-ш1к]

Скорость и безопасность

[@МаксимСоловьев-с9н]

​@@ИванБездомный-ш1ккакая еще безопасность?

[@frontend_mirzoev]

Интересно было самому решить, постарался максимально коротко, вроде работает) const intersect = function (array1, array2) { let result = array1.filter((item, index) => { return array2.indexOf(item) > -1 ? array2.splice(index, 1) : false; }); return result; };

[@frontendscience]

Благодарю за решение! Понял как ты это хотел сделать, но не совсем корректно работает. Input [1,2,2,1,2] [2,2] Output [2,2,2] Expected [2,2]

[@frontend_mirzoev]

@@frontendscience Точноо, индекс удаления перепутал. Теперь все топ:) const intersect = function (array1, array2) { let result = array1.filter((item, index) => { return array2.indexOf(item) > -1 ? array2.splice(array2.indexOf(item), 1) : false; }); return result; };

[@frontendscience]

О класс! теперь работает как надо! PS: array2.indexOf(item) - можно вынести в отдельную переменную чтобы 2 раза не вызывать.

[@koshakkoshakov7104]

Очень классно! Спасибо за видео!

[@frontendscience]

Рад, что понравилось) Приходите еще :)

[@tkachvova]

Было бы интересно посмотреть собеседования Senior или Architect

[@ИльяБондаренко-т4е]

Не хотел делать O(n^2) и решил сделать O(n*log n) с помощью бинарной сортировки. Это пример того - что если не думать о структуре данных то алгоритмы мало полезны. Спасибо за решение function intersect(arr1: Array, arr2: Array) { arr1.sort((a, b) => a - b); arr2.sort((a, b) => a - b); const intersectArr = []; function binSearch(findValue: number, arr: Array) { let left = 0; let right = arr.length - 1; while(left findValue) { right = middle - 1; } else { left = middle + 1; } } return false; } arr1.forEach((item) => { if (binSearch(item, arr2)) intersectArr.push(item); }) return intersectArr; };

[@quite10]

Спасибо Вам большое за крутой разбор!✨

[@frontendscience]

Рад, если было полезно!

[@quite10]

@@frontendscience у Вас всегда полезный материал;D

[@frontendscience]

@@quite10 Благодарим за поддержку! Рады стараться)

[@Alexis_VC]

Классный канал, очень качественный и интересный контент. Хотел бы задать вопрос, почему для разработки используете MacOS (MacBook), из каких параметров исходили при выборе устройства для работы?

[@frontendscience]

Благодарю! Рад что понравилось! Начинал я давно еще на windows, потом когда переехал в Симферопольский офис Яндекса в 2010 году, мне выдали макбук, так как все рабочее окружение (куча всяких тулов, скриптов и прочее) были сделаны именно из расчета на мак (не винду). Месяца 2 я плевался - как на этом маке работать то ))) А потом понял всю прелесть - привык к клавиатуре/программам/интерфейсу и все стало замечательно. Главнейшие плюсы который я вижу именно в macbook (macOS): 1) у тебя есть нативная консоль - но putty и прочие надстройки как в винде (все таки macOs это *nix) 2) в отличии от всяких unix/linux где тоже отличная консоль и окружение как на серверах где крутятся потом проекты - на macOs у тебя есть возможность ставить нормальные программы потипу photoshop (сейчас уже менее актуально все переходят на figma и прочее - но я до сих пор лоя своих нужд фотошопом пользуюсь :) ). + программы для видео редактирования (на винде они есть - на линкусах нету) Ну и теперь это уже стало дело привычки - мне намного приятнее и проще работать именно на маке чем на винде.

[@Alexis_VC]

@@frontendscience благодарю за такой развернутый ответ)

[@владимирсенцов-р1ю]

@@Alexis_VC Ну в принципе 10 тоже неплохая. Но сами ноуты от apple довольно неплохие по соотношению цена/качество. Просто посмотрите аналочичный ThinkPad или HP.

[@voronov1705]

JavaScript + мемы => идеальная смесь

[@frontendscience]

Рад что понравилось)

[@Boortwint]

Я бы предложил вариант по улучшению алгоритма. Может возникнуть ситуация, когда в одном массиве 5 элементов, а в другом 1000. Естественно, что аккумулятор нужно будет формировать по меньшему. Но в этот аккумулятор необходимо добавить дополнительное поле *total,* которое будет хранить общее количество вхождений всех элементов (это сама длина меньшего массива). При итерации мы делаем декремент не только вхождения конкретного элемента, но и декрементим свойство *total.* Если *total* в определенный момент будет равняться нулю, то итерацию можно прекратить, потому как совпадений уже быть не может. Цикл можно завершать и возвращать result. Обратите внимание, что итерация по большому массиву завершится сразу после нахождения всех совпадений. Бежать по всему массиву нет необходимости.

[@frontendscience]

Да хорошие дополнения! В целом на собеседовании обычно достаточно решить задачу оптимально по времени (в плане BIG O) Но могут и задать дополнительные вопросы как еще ускорить алгоритм на частных случая: например чтобы зря не бежать до конца если нашли уже все пересечения.

[@niklkelbon3662]

проверка и нахождение наименьшего массива логична, а вот проверка на каждой итерации и дополнительные вычисления total - уже нелогично. Только в специфической ситуации когда известно, что 99% массивов на входе будут такими, иначе получается слишком много лишних вычислений и ветвлений

[@Boortwint]

@@niklkelbon3662 во всём нужно искать компромисс. С небольшими массивами будет оптимально одно решение, с большими - другое. Декремент и проверка total на 0 в каждом витке цикла лучше, чем гнать впустую 1000 лишних элементов в случае больших массивов. Нахождение наименьшего массива по сути не имеет никакого смысла, если не определять через total возможное наличие вхождений.

[@d_r_robot]

То что на канале есть подобная рубрика супер, как раз такой вопрос попался на одном из собесов. Ну я успешно завалил его, а всё потому, что сюда не зашёл и не чекнул.

[@frontendscience]

Спасибо за поддержку!) Вам успехов!

[@DmitryDolganov]

Благодарю!

[@frontendscience]

И Вас благодарим! :)

[@christianspace9700]

Спасибо за урок, а как сделать, чтобы проверялось наличие 2х и более элементов в обоих массивах?

[@kazanovapetro]

Я набросал такой вариант, вроде работает: function check(a, x) { let arr = []; for (let i =0; i

[@eghishemanukyan3021]

я тоже точно так сделал и как то не могу понять зачем нужно нам усложнять

[@freetimeproject7]

два указателя. на 1-й и 2-й масив цикл ду вайл пока не дойдет один указатель до конца. сортируем массивы. указатели оба на 0-м елементе. если одинаковые- добавляем в результат. если разные - увеличиваем указатель того массива где значение меньше. итого. сортировка 2-х масивов и проход O(m+n)

[@ПолинаЧугаева-п3ъ]

я люблю этот логотип

[@user-kc5kr9fq2z]

Доброго дня, а на якому сайті ви кодите? Чи це додаток?

[@frontendscience]

Вiтаю. Тут у webstorm.

[@ivanrusin3893]

Была у меня одна интересная задача на собеседовании. Правда на бэк, но, думаю, и фронтам интересно будет: Дана строка из случайной последовательности открывающихся и закрывающихся скобок разного типа. Вроде "[{{)(". Задача определить корректна ли строка. То есть все ли скобки стоят на своих местах и имеют закрывающую скобку сохраняя вложенность? Желаю всем успеха в решении ))

[@frontendscience]

Да очень известная и популярная задача на собеседованиях. Обязательно ее разберу! Благодарю!

[@zergzerg4844]

А через forEach не прозе было бы ? const intercept: number[] = []; param2.forEach((el) => { const findEl = param1.find((val) => val === el); findEl && intercept.push(findEl); }); Или через поиск медленнее?

[@phoenix_o_0]

Везде только двух массивов. Как найти пересечение неизвестного количества массивов?

[@frontendscience]

Алгоритм пересечения n-ного количества массивов всегда можно свести к частной задаче про два массива. Сравнить первые два массива - и получить их пересечение. Затем сравнить пересечение со следующим массивом - получить обновленное пересечение и т.д. Есть и другие варианты, например, иметь один большой хэш-тейбл, в котором подсчитывать сколько раз элементы встречались в каждом из массивов (один хэш на все массивы), а затем отфильтровать только те элементы, у которых значение равно количеству массивов.

[@frontendscience]

Единственный момент в последнем варианте - для его работы все элементы массивов должны быть уникальны.

[@phoenix_o_0]

@@frontendscience Да, по логике понятно, но практического примера нет нигде. Я только учусь и это меня в тупик ставит, как перебрать эти массивы(

[@asteriall8057]

А я по старинке цикл в цикл вставил (сравнение элементов двух массивов), добавил еще один массив, куда заносил индексы уже использованных элементов второго массива и соответственно проверку, использован ли элемент function f(num, arr) { for (let i = 0; i < arr.length; i++) { if (arr[i] === num) { return true } } return false } function intersection(array_1, array_2) { const arr2_element_not_use = [] const intersection_array = [] for (let i = 0; i < array_1.length; i++) { for (let k = 0; k < array_2.length; k++) { if (( array_1[i] === array_2[k] ) && !(f(k, arr2_element_not_use))) { intersection_array.push(array_1[i]) arr2_element_not_use.push(k) break } } } return intersection_array } console.log(intersection(arr_1, arr_2))

[@frontendscience]

Благодарю за решение! Саму идею понял. Но что-то пошло не так на вот таком кейсе: Input [4,9,5] [9,4,9,8,4] Output [4,4,9] Expected [4,9]

[@asteriall8057]

@@frontendscience облажался чуть чуть) там в конце if-а break надо добавить)

[@frontendscience]

@@asteriall8057 Хмм мне с break все равно выдает не верные ответы: Input [2,1] [1,2] Output [2] Expected [1,2]

[@asteriall8057]

@@frontendscience Никогда не сталкивался с оператором in и почему-то подумал, что так должно работать=) щас понял, что он по свойствам(индексам) объекта проходится, а не по самим элементам). (исправил код)

[@cmac2cmac]

Есть ли необходимость использовать в строке map[current] -= 1 именно такую запись? Или можно просто указать count -= 1?

[@frontendscience]

можно и так и так

[@philippbulanin4719]

@@frontendscience разве? count же хранит в себе числовое значение, а не ссылку, так что мы не внесем изменения в объект, а значит не узнаем о том, что уже учли какое-то из значений.

[@frontendscience]

я тут ошибся: я думал вопрос про то можно ли вместо map[current] = currentMapItem - 1; написать map[current] -= 1; Этот код в codepen лежит. А в видео у меня немного по другому сделано. count -= 1 - действительно использовать нельзя, нам надо обновлять значение в map

[@philippbulanin4719]

@@frontendscience да, тогда согласен) спасибо за ответ

[@ЯрославПлахтієв]

Решил эту задачу на плюсах class Solution { public: std::vector intersect(std::vector& nums1, std::vector& nums2) { std::map temp; int t = 0; for (auto& elem : nums1) { t = std::count(nums1.begin(), nums1.end(), elem); temp.emplace(elem, t); } for (auto& elem : nums2) { int count = temp[elem]; if (count && count > 0) { m_res.emplace_back(elem); --temp[elem]; } } return m_res; } private: std::vector m_res; };

[@frontendscience]

Благодарю за решение! Вариантов на плюсах у нас еще не было :)

[@ОлексійУкраїна-й7г]

агонь

[@ИванБездомный-ш1к]

Попробуйте 1.конкатенация обоих массивов, 2.соотировка значений по возрастанию, 3. перебор всех значений с выводом одинаковых

[@malfeasance62]

в одном массиве могут быть 2 одинаковых элемента, которых может не быть в другом.

[@wisarty]

Дякую

[@АлександрПачковский-в9ъ]

Решение такое, вроде работает) const intersect = function(arr1, arr2) { arr1.forEach(item => { let index = arr2.indexOf(item, 0); if (index != -1) { arr3.push(arr2[index]); arr2.splice(index, 1); } }); return arr3; };

[@frontendscience]

Да отлично вышло. Благодарю

[@СеняМамонтов-ж9у]

примерно тоже написал. это решение экономичнее, всего один проход по одному массиву

[@ku3mi41]

@@СеняМамонтов-ж9у На самом деле нет, indexOf будет каждый раз проходить по второму массиву. Плюс splice тоже стоит O(n), итоговая сложность больше O(n^2), что невероятно много.

[@Сергей-й9т7ъ]

Получилось по скорости не самое быстрое, но по читаемости кода неплохое) var intersect = function(nums1, nums2) { const clone2 = [...nums2]; const res = []; nums1.forEach(num => { const index = clone2.indexOf(num); if (index > -1) { res.push(num); clone2.splice(index, 1); } }); return res; };

[@frontendscience]

Да вышло хорошо! ) Благодарю за решение

[@graa999]

6:10 зачем писать if (count && count > 0), если if (count > 0) будет выдавать то же самое?

[@frontendscience]

Потому что count может быть undefined. а сравнивать undefined > 0 - логически не корректно. Хоть js и вернет false. Я за явные проверки!

[@blgarOk]

Спасибо за подробный разбор задачи. Мое решение: const intersect = function (nums1, nums2) { const result = [] for(let i = 0; i < nums1.length; i++) { if (nums2.includes(nums1[i])) { const current = nums1[i] result.push(current) nums2[nums2.indexOf(current)] = '' } } return result } Не самое оптимальное по скорости, но, вроде, читабельное решение) Из минусов, мутирует 2ой массив. Подскажите, какоя сложность алгоритма в моем случае? О(n * m)? O(n * m * m)?

[@frontendscience]

Благодарю за решение. Сложность выйдет O(n*m)

[@anton-vr5xw]

Топ

[@frontendscience]

👍

[@romanryaboshtan9270]

6: 20 Можно убрать условие count > 0 тогда всё будет работать так же само, я проверил с дебаггером

[@vadym7023]

спасибо за видос) такс мое решение отличается) но вроде работает не хуже вашего) function intersect(a, b) { const cloneB = [...b]; return a.reduce((acc, cur) => { if (cloneB.includes(cur)) { const deleteIndex = cloneB.indexOf(cur); cloneB.splice(deleteIndex, 1); acc.push(cur); } return acc; }, []); };

[@frontendscience]

Благодарю за решение! Да интересное решение. Как вариант можно поднять выше const deleteIndex = cloneB.indexOf(cur); и вместо if (cloneB.includes(cur)) сделать if (deleteIndex !== -1) Так выйдет на один обход массива меньше

[@vadym7023]

​@@frontendscience согласен! спасибо за поправку)

[@ilyaredkin4172]

Круто, конечно, только как-то очень мудрёно. Вот, только вчера на Хекслете решал такую задачу, гораздо проще: const intersect = (arr1, arr2) => { const result = []; for (const item of arr1) { if (arr2.includes(item)) { result.push(item); } } return result; };

[@whatthepeople]

Ну так у тебя решение неверное, если говорить про ту задачу, что в видео intersect([2, 2, 1], [2, 1, 3]) // [2, 2, 1], а должно [2, 1] Поскольку нужны не все вхождения цифры в одно из множеств, а такое количество, которое есть в обоих множествах

[@ilyaredkin4172]

@@whatthepeople твоя правда, дописал " && !result.includes(item) " const intersect = (arr1, arr2) => { const result = []; for (const item of arr1) { if (arr2.includes(item) && !result.includes(item)) { result.push(item); } } return result; }; ща работает.

[@whatthepeople]

@@ilyaredkin4172 но если в обоих множествах вхождений несколько, то и в результате тоже должно быть столько же: intersect([2, 2, 1], [2, 1, 2, 3]) // [2, 1], а должно быть [2, 2, 1] :D

[@ilyaredkin4172]

@@whatthepeople ну вот зачем ты все испортил, работало же!)

[@whatthepeople]

@@ilyaredkin4172 прости.

[@chokolo_]

Доброго времени! Спасибо за познавательное видео. Только начал изучать JS на онлайн курсах, и бонусом читаю книгу Кантора. Хотел спросить, данные задачи показывают работодателю только знания в js? Какое реальное применение в практике они имеют? Т.е для чего в практике нужно искать эти пересечения? Может в будущем будет формат такого видео с разъяснением? Спасибо. :)

[@frontendscience]

На практике именно такого рода алгоритмы будут полезны, если у вас большие объемы данных. Именно поэтому такого рода задачи обычно дают на собеседованиях в крупных компаниях типа яндекс, мейл, гугл и пр. Если у вас небольшое количество данных, то ту же задачу с пересечением например можно было бы решить совсем по-другому, более компактно. Если говорить конкретно про задачу с пересечением и именно с повтором, то это достаточно частый кейс на фильтрацию каких-то списков. Например, есть определенный список транзакций за год и есть второй список всех транзакций компании за все время. Необходимо найти, какие транзакции совершила компания за определенный период времени, т.е. найти пересечение этих двух массивов. Надеюсь, понятно. Успехов Вам в новой профессии!

[@chokolo_]

@@frontendscience Спасибо за развёрнутый ответ! Ваш канал вдохновляет! 🙏

[@dmitrylavrov3860]

Вот мой вариант: const intersect = (nums1, nums2) => { let output = [] for (let i = 0; i < nums1.length; i++) { const idx = nums2.indexOf(nums1[i]) if (idx > -1) { output.push(nums1[i]) nums2[idx] = -Infinity } } return output } По производительности должен быть не хуже. Или я ошибаюсь?

[@frontendscience]

Благодарю за решение! Да произволительность отличная!

[@ku3mi41]

Будет медленнее, т.к. indexOf стоит O(n), в то время как обращение к свойству объекта стоит всего O(1). Если в обоих массивах будет 10^6 элементов, алгоритм из видео будет выполняться за 10^6 + 10^6 = 2 x 10^6 операций, в то время как ваш вариант уже потребует 10^12 операций, т.е. O(m * n) или O(n^2) если массивы равны, что очень медленно. Основная идея и была именно избавиться от итерирования по второму массиву, использовав вместо этого объект.

[@VassiliySmith]

const *intersect* = (nums1, nums2) => { const first = nums1.length >= nums2.length ? nums2 : nums1; const second = nums1.length >= nums2.length ? nums1 : nums2; const result = []; first.forEach(e => { if(second.includes(e)) { result.push(e) } }); return result }

[@yarik83men51]

На Java: import java.util.ArrayList; import java.util.HashMap; public class IntersectionArrays { public static void main(String[] args) { int[] arr1 = {1, 2, 2, 1}; int[] arr2 = {2, 2}; int[] arr3 = {4, 9, 5}; int[] arr4 = {9, 4, 9, 8, 4}; System.out.println(intersect(arr3, arr4)); } private static ArrayList intersect(int[] a, int[] b) { int minLength = Math.min(a.length, b.length); ArrayList list = new ArrayList(minLength); HashMap mapA; mapA = arrayToMap(a); for (int i = 0; i < b.length; i++) { int current = b[i]; Integer count = mapA.get(current); if (count != null && count > 0){ list.add(current); mapA.put(current, mapA.get(current) - 1); } } //Integer[] arr = list.toArray(new Integer[0]); return list; } private static HashMap arrayToMap(int[] a) { HashMap map = new HashMap(a.length); for (int i = 0; i < a.length; i++) { if (!map.containsKey(a[i])) { map.put(a[i], 1); } else { map.put(a[i], map.get(a[i]) + 1); } } return map; } }

[@niketor8722]

nums1.forEach(current => { for (let i = 0; i < nums2.length; i++) { if (nums2[i] === current) { result.push(nums2[i]); break; } } })

[@aleksd286]

reduce((acc, curr) => пожалуйста curr, или current или currentValue но никак не i. потому что reduce((acc, i, index))? :)))

[@frontendscience]

i - это сокращённо от item ;)

[@11King99]

const intersect = function (nums1, nums2) { return nums1.filter(elem => nums2.includes(elem)) }

[@frontendscience]

Благодарю за решение! Но оно к сожалению не будет учитывать дубликаты в первом массиве.

[@domikpriklyocheniu3611]

навіщо перевірка count > 0??

[@Ramosok]

[@Vadiminator46]

ну типа function intersection(arr1, arr2) { let result = [] let buffer = arr2.concat() for (let x of arr1) { if ( buffer.indexOf(x) !== -1 ) { result.push(x) delete buffer[buffer.indexOf(x)] } } return result; }

[@frontendscience]

Ну типа ок! :) Благодарю за решение!

[@ЕгорЧилиевич-ю9р]

Не сильно знаком с js, но, если acc - это обычный массив, то сложность по времени действительно линейная, а по памяти - не совсем. Если в первом массиве будет одно число 100000, например, то создастся массив на 100000 элементов. Чтобы этого избежать как раз и используется map, но тогда по времени логарифм добавится. Возможно, автор видео имел ввиду hashmap, которыми по умолчанию являются объекты в js

[@frontendscience]

acc - это не массив это объект

[@EvilYou]

Мое решение: function intersect(arr1, arr2) { let clone = arr1.concat(); return arr2.filter( item => { let index = clone.indexOf(item); if (index === -1) return false; clone.splice(index, 1); return true; }); } Сложность алгоритма O (a * b) где a и b - количество элементов в первом и втором массиве соответственно. На leetcode мой алгоритм проходит хорошо (Runtime: 72 ms, faster than 93.91%. Memory Usage: 40 MB, less than 66.64%).

[@EvilYou]

Решение из видео похоже, что самое быстрое. Время: 52ms, faster than 100%.

[@frontendscience]

Благодарю за решение. вышло хорошо

[@EvilYou]

function intersect(arr1, arr2) { let obj = {}; for (let i = 0; i < arr1.length; i++) { let current = arr1[i]; obj[current] = current in obj ? obj[current] + 1 : 1; } let result = []; for (let i = 0; i < arr2.length; i++) { let current = arr2[i] if (obj[current] && obj[current] > 0) { // две проверки работают быстрее, чем одна obj[current] > 0 obj[current]--; result.push(current); } } return result; }

[@ДеткиеНочники]

'use strict'; const input1 = [1, 2, 2, 2]; const input2 = [2, 2]; // output:[2,2] const input3 = [4, 9, 5]; const input4 = [9, 4, 9, 8, 4]; // output:[4,9] or [9,4] const intersect = (nums1, nums2) => { if (nums1.length nums2.includes(elem)); } else { return nums2.filter(elem => nums1.includes(elem)); } }; console.log(intersect(input1, input2)); console.log(intersect(input3, input4));

[@carved1883]

function intersect(array1, array2){ let similarArray = []; array1.forEach( (item)=> { if(array2.includes(item)){ similarArray.push(item) } }); console.log(similarArray) }

[@ИванВласенко-р4ж]

const intersect = input1.filter(item => input2.includes(item))

[@Декопитатор321]

моё решение) function intersect(nums1, nums2){ let mas = [] for(let i = 0; i < nums1.length; i++){ let count = 0 for(let j = 0; j < nums2.length; j++){ if(nums1[i] === nums2[j]){ count++ } } if(count >= 1){ mas.push(nums1[i]) } } return mas }

[@styopashughyan9685]

const inp1 =[4,9,5] const inp2 =[9,4,9,8,4] const same =[] let f1 = function(inp1,inp2){ for (let i = 0; i < inp1.length; i++) { for (let j = 0; j < inp2.length; j++) { if(inp1[i]===inp2[j]){ same.push(inp1[i]) break } } } } f1(inp1,inp2) console.log(same);

[@Vlad-em1bx]

🔋

[@z1fir]

// операция (el ^ arr2[i]) вернет нуль только тогда когда оба элемента равны const intersect = (arr1, arr2) => { let result = []; arr1.map((el) => { for (let i = 0; i < arr2.length; i++){ if ( (el ^ arr2[i]) === 0 ) { result.push(el); break; } } }); return result; }

[@frontendscience]

Благодарю за решение! Но нужно еще учитывать количество повторов элементов: Your input [1,2,2,1,2] [2,2] Output [2,2,2] Expected [2,2]

[@WaferPlay]

const intersect = (a, b) => { const result = [] a.forEach((numA) => { const index = b.findIndex((numB) => numA === numB) if (index !== -1) { result.push(numA) b = [...b.slice(0, index), ...b.slice(index + 1)] } }) return result }

[@redalert7658]

ничего не понял

[@v.demchenko]

var intersection = function(nums1, nums2) { const hash = {} let result = new Set() nums1.forEach(element => { hash[element] = false if (nums2.includes(element)) { hash[element] = true } }); for (const key in hash) { if (hash[key]) { result.add(key, key) } } return [...result] };

[@ОксанаХарченко-д9г]

function findCrossArr(nums1, nums2) { let sameNums = []; for(let num of nums1){ if(nums2.includes(num)) sameNums.push(num) } return sameNums }

[@multiply87]

const input1 = [1, 2, 2, 1]; const input2 = [2, 2]; const input3 = [4, 9, 5]; const input4 = [9, 4, 9, 8, 4]; const intersect = (nums1, nums2) => { return nums1.reduce((a, i) => { nums2.includes(i) && a.push(i); return a; }, []) } console.log(intersect(input1, input2)); console.log(intersect(input3, input4));

[@frontendscience]

Выглядит красиво, но будет работать не корректно с повторными элементами. Так как не ведется подсчет элементов.

[@multiply87]

@@frontendscience спасибо, я сначала написал, а потом досмотрел видео) Не знал полностью задание)

[@frontendscience]

@@multiply87 понятно. Благодарю за решение!

[@ІльченкоАртем]

function intersect(arr1, arr2){ const obj = {} const result = [] arr1.forEach(el=>{ obj[el] = el }) arr2.forEach(el=>{ if(obj[el]) result.push(el) }) return Array.from(new Set(result)) }

[@frontendscience]

Благодарю за решение! Такой вариант будет работать если массивы будут без повторов. Если нам нужно учитывать повторы то этот вариант падает на вот таких входных данных: input1 [1,2,2,1] input 2 [2,2] Output [2] Expected [2,2]

[@bahtiyar-y7d]

function intersect (arr1, arr2) { let result = []; for (const item1 of arr1) { for (const item2 of arr2) { if (item1 === item2) { if (item1 !== result.at(-1)) { result.push(item1); } } } } return result; } console.log(intersect(input1,input2))

[@DENisHolden1]

Что скажите? const intersect = function (nums1, nums2){ const sort1 = nums1.sort((a,b)=> a-b); const sort2 = nums2.sort((a,b)=> a-b); let index1 = 0; let index2 = 0; const result = []; while (index1 < sort1.length && index2 < sort2.length){ if(sort1[index1] === sort2[index2]){ result.push(sort1[index1]); index1++; index2++; continue; } if(sort1[index1] < sort2[index2] ){ index1++; }else{ index2++; } } return result; };

[@frontendscience]

О класс ) ждал такого варианта с изначальной сортировкой. Благодарю за решение!

[@DENisHolden1]

@@frontendscience У меня вопрос о сложности. Если мы дважды делаем сортировку nlogn складывается?

[@frontendscience]

Если предположить что n длина самого длинного массива то сложность O(n logn).

[@Sun1ive]

function intersect(arr1, arr2) { return Array.from(new Set(arr1.filter((item) => arr2.includes(item)))); }

[@frontendscience]

Благодарю за решение! К сожалению не все тесткейсы пройдет.

[@denis_ken]

решил таким образом ) const input1 = [1,2,2,1,1]; const input2 = [2,2,1,1,1,1]; const intersect = function(nums1, nums2) { const res = []; const indexes = []; nums1.forEach(el1 => { for (let i = 0; i < nums2.length; i++) { if (el1 === nums2[i] && indexes.indexOf(i) < 0) { res.push(el1); indexes.push(i); break; } } }); return res; } console.log(intersect(input1, input2));

[@sekirogenshiro2210]

не видя решения пишу const input = [1,2,3,4]; const input2 = [2,2]; const input3 = [4,9,5]; const input4 = [9,4,9,8,4]; const interest = function (nums1, nums2) { let matched = nums1.filter( el => nums2.indexOf( el ) > -1 ); return matched; } console.log(interest(input4,input3))

[@geebrox]

const input6 = [8, 0, 3] const input5 = [0, 0] console.log(interest(input5, input6)) // Expect: [0] // Output: [0, 0]

[@frontendscience]

Благодарю за решение! :) вышло компактно, но не то возвращает для повторяющихся элементов, так как нет подсчета количества вхождений.

[@sekirogenshiro2210]

@@frontendscience да я согласен.у вас навороченное решение. я просто потом посмотрел видео.не хвастаюсь и прочее. просто решил написать.суперский канал!

[@frontendscience]

@@sekirogenshiro2210 Так наоборот! Супер, что написали свое решение! Просто у Вас получилось решение другой задачи - где нету повторов элементов в рамках одного массива. Зато сам потренировался в решении задач и вывел рабочий алгоритм. Это очень полезно. Причем не только для Вас - другим, которые смотрят чужие решения, тоже полезно видеть разные подходы и варианты)

[@donybrorahmanov8068]

Privet! let input1 = [1,2,2,1] let input2 = [1,2] let input3 = [4,9,5] let input4 = [9,4,9,8,4] let input5 = [1,4,6,4,7,8,1] let input6 = [1,7,5] function intersect(arrayOne, arrayTwo){ let result = new Set() for (let i=0; i

[@igormuryy5722]

function autolike(){ return play} :)

[@frontendscience]

'Big Thanks! '.repeat(1000)

[@tyomkhachatryan3820]

let num1 = [4,9,5]; let num2 = [9,4,9,8,4]; function intersect(num1, num2) { let res = new Set(); for (let i = 0; i < num1.length; i++) { num2.forEach(element => { num1[i] === element ? res.add(element) : true; }); } return res; } console.log(intersect(num1,num2));

[@kuhnivikont]

const intersect = (arrA, arrB) => { let res = []; arrA.forEach((elem) => { let index = arrB.indexOf(elem); if (index !== -1) res.push(arrB.splice(index, 1)[0]) }) return res; }

[@frontendscience]

Благодарю за решение!

[@altruistus757]

const intersect = (num1, num2) => { const result = []; const longer = num1.length >= num2.length ? [...num1] : [...num2]; const shorter = num1.length < num2.length ? [...num1] : [...num2]; longer.forEach((num) => { if(shorter.includes(num)) { currentIndex = shorter.indexOf(num); shorter[currentIndex] = null; result.push(num); } }); return result; }

[@frontendscience]

Благодарю за решение!

[@Aram64]

Как оценишь такое решение ? const arr1 = [1,2,2,1,2]; const arr2 = [2,2]; const arr3 = [4,9,5]; const arr4 = [9,4,9,8,4]; const arr5 = [10,1,8,10,333,8,1,2,3,4,3]; const arr6 = [1,8,10,3]; const intersect = (firstArr,secondArr) => { const targetArr = Array.from(secondArr); return Array.from(firstArr).reduce((aggr,el,id,arr) =>{ if(!targetArr.length) arr.splice(0); else if(targetArr.includes(el)) { aggr.push(el); targetArr.splice(targetArr.indexOf(el),1); return aggr; } return aggr; },[]); } console.log(intersect(arr1,arr2));//[2, 2] console.log(intersect(arr3,arr4));//[4, 9] console.log(intersect(arr5,arr6));//[10, 1, 8, 3]

[@frontendscience]

Благодарю за решение! Классно что сам решил! Интересный вариант вышел. Сложность вышла O(n*m) Если оставить этот алгоритм как есть то небольшую оптимизацию можно было бы сделать заменив targetArr.includes(el) на targetArr.indexOf(el). Один раз рассчитать indexOf - и сохранить в переменную. а дальше уже сделать else if(index != -1) { ..... targetArr.splice(index,1); } на один проход по массиву внутри будет меньше

[@Aram64]

@@frontendscience спасибо за оценку. includes мне не особо нравится в моем решении, так как это по сути перебирание, но на момент решения более быстрый вариант не придумал. Спасибо за совет. Еще, я только что заметил что return в блоке else if бессмысленный, надо его убрать.

[@АлександрМарченко-ы4к]

function intersect(input1, input2) { const clone = (arr) => [...arr] const output = []; const cloned = clone(input2) input1.forEach(item => { const identicalItemIndex = cloned.findIndex(n => n === item) if (identicalItemIndex >= 0) { output.push(item) cloned.splice(identicalItemIndex, 1) } }) return output }

[@frontendscience]

Благодарю за решение! 👍

[@programmer.andrey]

let intersect = (v1, v2) => v1.reduce((acc, value) => { const index = v2.indexOf(value) if (index !== -1) { acc.push(value) delete v2[index] } return acc }, [])

[@frontendscience]

Благодарю за решение! 👍

[@ОлегМаслов-р9г]

const intersect = (nums1, nums2) => { let res = []; if (nums1.length < nums2.length) { for (let item of nums1) { if (nums2.includes(item)) { res.push(item) } } } else { for (let item of nums2) { if (nums1.includes(item)) { res.push(item) } } } return res; }

[@frontendscience]

Благодарю за решение! Но к сожалению не учтены до конца повторы. Например: Input [1,2] [1,1] Output [1,1] Expected [1]

[@АртемКухар-г9ш]

const first = [1,2,3,4]; const second = [1,2,2,3,5]; // [1,2,3] const getElements = (arr1, arr2) => { let unic = []; arr1.forEach((el) => { if(arr2.includes(el) && !unic.includes(el)) { unic.push(el); } }) return unic; }; console.log(getElements(first,second));

[@frontendscience]

Благодарю за решение! Но к сожалению такой алгоритм не учитывает дубликаты: Your input [1,2,2,1] [2,2] Output [2] Expected [2,2]

[@АртемКухар-г9ш]

@@frontendscience const first = [1,2,2,3,4,3]; const second = [1,2,2,3,5,3]; // [1,2,2,3,3] const getElements = (arr1, arr2) => { let unic = []; arr1.forEach((el) => { if(arr2.includes(el)) { unic.push(el); } }) return unic; }; console.log(getElements(first,second));

[@frontendscience]

Input [1,2,2,1] [2] Output [2,2] Expected [2]

[@TheProfessionalGambler]

Лень думать, пускай будет такое решение: const intersect = (arr1, arr2) => arr1.filter(n => arr2.includes(n))

[@TheProfessionalGambler]

эх, решение не правильное, вот второй вариант const intersect = (arr1, arr2) => { const map = arr1.reduce((acc, n) => ({...acc, [n]: ++acc[n] || 1}), {}) return arr2.filter(n => map[n]-- > 0) }

[@frontendscience]

:) Nice!

[@ku3mi41]

@@TheProfessionalGambler Неочевидная на первый взгляд проблема заключается в том, что оператор spread вложенный в reduce приведет к сложности O(n^2) т.к. все свойства объекта будут каждый раз итерироваться полностью для создания нового объекта, что не отличается от сложности наивного решения с помощью двух циклов. Такое решение вызывает на самом деле двойственные чувства, с одной стороны видно, что автор умеет использовать функциональный подход и код получился довольно короткий (но не очевидный), с другой стороны есть скрытая проблема производительности, которая сводит на нет всю краткость кода, т.к. работает этот код медленно. Зато есть о чем поговорить дальше :)

[@TheProfessionalGambler]

@@ku3mi41 самая основная проблема в любом решении, это не следовать принципу KISS 😉

[@SiniyPetr]

const intersect = (arr1, arr2) => arr1.filter((item) => arr2.includes(item));

[@maximbogorad9750]

по эффективности не очень, первое что в голову пришло const intersect = function (nums1, nums2) { let nums = [0,0,0,0,0,0,0,0,0,0]; let arr = []; for (let i = 0; i < nums2.length; i++) { nums[nums2[i]%10]++; } for (let i = 0; i < nums1.length; i++) for (let j = 0; j < nums2.length; j++) { if (nums1[i] == nums2[j]) if (nums[nums1[i]%10] != 0) { arr.push(nums1[i]); nums[nums1[i]%10]--; break; } } return arr; }

[@SmotritelTube]

13 строка легко превращается в acc[i] = acc[i] + 1 || 1 что покороче будет и проще воспринимать

[@frontendscience]

Ну мне вот например совсем не проще ее воспринимать. Я пишу код так чтобы легко было объяснить как работает алгоритм и чтобы легко читалось потом.

[@frontendscience]

@@qulinxao Даже при моей любви к тильде, про которую я снимал отдельное видео, эта строка абсолютно не читаема в сравнении с той, которая была приведена в видео. Тем более в целях данного видео - которое должно доступно объяснять сам алгоритм для разработчиков очень разного уровня.

[@dkalinin]

Вот решение "В лоб" let intersect = function(nums1, nums2) { let result = []; nums1.forEach(element => { let cur1 = 0, cur2 = 0; nums1.forEach(el1 => { element == el1 ? cur1++ : false }) nums2.forEach(el2 => { element == el2 ? cur2++ : false }) if (result.indexOf(element) < 0) { for (let i = 0; i < Math.min(cur1, cur2); i++) { result.push(element) } } }); return num; };

[@frontendscience]

Благодарю за решение! PS: подправь там return result

[@khurshedahmadjonov4747]

let input1 = [9, 4, 9, 8, 4]; let input2 = [4, 9, 5]; function intersect(input1, input2) { let GreatArr; let SmallArr; GreatArr = input2; SmallArr = input1; if (input1.length > input2.length) { GreatArr = input1; SmallArr = input2; } let emptyMass = []; for (let i = 0; i < GreatArr.length; i++) { if (GreatArr.includes(SmallArr[i]) && SmallArr[i] !== undefined) { emptyMass.push(SmallArr[i]); } } console.log(emptyMass); return emptyMass; } intersect(input1, input2); а у моего варианта есть проблемы?

[@МаксимСоловьев-с9н]

две хэшмапы создал const input1 = [1,2,2,1] const input2 = [2,2] //output: [2,2] const input3 = [4,9,5] const input4 = [9,4,9,8,4] //output: [4,9] or [9,4] const intersect = (arr1, arr2) => { const arr1Len = arr1.length, arr2Len = arr2.length const hash1 = new Map(), hash2 = new Map() const result = [] const createHash = (arr, hash) => { for(let i = 0; i < arr.length; i++){ hash.set(arr[i], (hash.get(arr[i]) || 0) + 1) } } createHash(arr1, hash1) createHash(arr2, hash2) for(let [key, value] of hash1.entries()){ if(hash2.has(key)){ const key1 = hash1.get(key) const key2 = hash2.get(key) const minValue = Math.min(key1, key2) for(let i = 0; i < minValue; i++){ result.push(key) } } } return result } console.log(intersect(input1, input2)) console.log(intersect(input3, input4))

[@versal52]

function intersect(nums1, nums2){ return nums1.filter((x, ind) => { let findedIndex = nums2.findIndex(y => y == x) if(findedIndex >= 0) { nums2 = nums2.filter((y, ind) => ind !== findedIndex) return true } return false }) }

[@ЕвгенийШут-о7н]

Кто-то дизлайк поставил....я вот не ставил а кто ставил?

[@frontendscience]

Нам тоже интересно узнать, кто эти люди 😎

[@vitalikretel1904]

@@frontendscience может кому-то let-ы не понравились. В целом алгоритм довольно оптимальный по сложности. Вроде как все другие предложенные в комментариях будут сложнее, из за использования indexOf или чего другого внутри цикла первого массива, что уже явно больше чем n+m Так что да, интересно узнать как улучшить.

[@dqrw6etf7igo8g32ftidgy]

Что-то вроде такого? function intersect (a1, a2) { return a2.map(el => a1.includes(el) ? el : false).filter(el => el !== false) }

[@frontendscience]

благодарю за решение. К сожалению оно не учитывает количество повторов в массивах

[@dqrw6etf7igo8g32ftidgy]

@@frontendscience Эх, точно) Ниже в комментариях вижу решение краткое тоже, понял где ошибся

[@eugenekvint5306]

Вот моё решение, как я это вижу, если не делать проверок и сортировок)) const input1 = [4, 4, 4, true, false, 6, 8, "AAAaaa", "A", 9, 0, 2354, "aEDR"]; const input2 = [4, 5, 7, 8, 1, "AAAaaa", false, 78, 2354, 3, "a", 4, 65, 7, 0, "aEDR"]; function intersect(arr1, arr2) { let result = []; for (key in arr1) { let index = arr2.indexOf(arr1[key]) if (index >= 0) { result.push(arr1[key]); arr2.splice(index, 1); } } return result } console.log(intersect(input1, input2)) // [4, 4, false, 8, "AAAaaa", 0, 2354, "aEDR"]

[@frontendscience]

Благодарю за решение! Nice!

[@cmac2cmac]

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

[@geebrox]

const input1 = [1, 2, 2, 1] const input2 = [2, 2] // Output: [2, 2] const input3 = [4, 9, 5] const input4 = [9, 4, 9, 8, 4] // Output: [4, 9] or [9, 4] const intersect = (arr1, arr2) => (Array.isArray(arr1) ? arr1 : []) .map((num) => { const idx = (Array.isArray(arr2) ? arr2 : []).indexOf(num) return !!~idx && arr2.splice(idx, 1)[0] }) .filter((num) => typeof num !== 'boolean') console.log(intersect(input1, input2)) console.log(intersect(input3, input4)) UPD: исправлено ошибка с фильтром UPD2: убрана не нужная проверка

[@frontendscience]

Благодарю за решение! Но что-то пошло не так где-то: arr1 =[8,0,3] arr2=[0,0] Expected: [0] Output: []

[@geebrox]

​@@frontendscience Да, не учел что 0 это false в Boolean. Нужно поменять строчку с .filter(Boolean) на .filter((num) => typeof num !== 'boolean')

[@Kolabrod]

Не интересно

[@frontendscience]

Так проходи мимо!

[@KazakovNik]

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

[@frontendscience]

Что значит паразитные данные? :))) это условие задачи. Причем вполне реальный случай.

[@KazakovNik]

@@frontendscience Приведите пример реальной задачи если не сложно.