Первая задача из первого собеседования в Яндекс

В данном видео я разбираю первую задачу из собеседования в Яндекс, которое я проходил полгода назад

[@wolf_code]

Ребят перед написанием комментария прошу прочесть Очень часто в комментариях пишут такой код: for i in list: if list.count(i) == 1: gotovo(i) Почему это хоть и простое - но плохое решение? Дело в том что мы запускаем цикл N раз (N = длина списка) В каждой итерации цикла - мы выполняем N операций (count пробегает по всему списку чтобы посчитать) Получается итоговая сложность алгоритма O(N^2) Что намного медленее чем O(N log N), а уж тем более чем O(N) Для сравнения: если N = 10k N^2 = 100kk = 100 миллионов шагов N log N ~ 130k = 130 тысяч шагов N = 10k = 10 тысяч шагов

[@deathklaa]

Но ты же мог просто взять и записывать уникальное число в 1 ячейку памяти и просто пройти весь массив за N. Если число повторяется, то зануляй результат. Зачем изобретать велосипеды? Удаление из массива это тоже лишние операции, работа с масками конечно красиво, но абсолютно излишнее решение

[@wolf_code]

@@deathklaa вот встретил ты какоето число записал в ячейку, затем еще одно, и что дальше - перезаписать число в ячейке?

[@LineageL2ad]

@@wolf_code можно использовать множество - добавлять элемент в него и при повторении удалять. В итоге останется 1 элемент множества - это и будет ответ. Сложность - линейная. Это про первую задачу)

[@LineageL2ad]

@@wolf_code все, вижу, вторая задача аналогична первой) И ты ее решил за О(N), так что норм)

[@user-kw4yf7gp5w]

@@LineageL2ad Это решение значительно быстрее, чем придуманное автором №1. Почему-то, автор считает, что функция .sorted чудесным образом не расходует ресурсы.

[@SimplewerCh]

думал, что это собеседование в яндекс такси, а тут цифры какие-то да буквы не понятные....

[@MindSkyaRocket]

Нат, это курьерам в Яндекс.Еда теперь такие тесты сделали, много претендентов на вакансии стало

[@wolf_code]

@@MindSkyaRocket еще в я.такси слышал цифры не юзают и буквы тоже, там само собой на магии сервера работают

[@mikemerinoff]

В доставку, очевидно, спрашивают задачу коммивояжёра

[@wolf_code]

@@mikemerinoff скорее алгоритм дейкстры

[@chloe_koshkina]

@@mikemerinoff единственное, что помню с 1-го курса, ахах Всё, можно не в мак, а в такси

[@kirillfox5958]

Первое решил как у тебя, а улучшил потом подумав над xor а вот второе решение себе запомнил, спасибо

[@counter_helix]

Канал - супер! Спасибо за контент

[@DmitriiRepnikov]

Первое решение которое мне пришло в голову после прочтения условия (пишу на js): 1. Завел мапу isUnique 2. Пробегаясь по массиву чисел: а) Если нет в мапе isUnique ключа с таким числом - добавляю его б) Если есть в мапе isUnique ключ с таким числом - удаляю его 3. Единственный оставшийся ключ в мапе это и есть нужное нам число, возвращаю его в качестве результата. (т.к. доступ по ключу это быстрая операция, то считаю алгоритм не особо жадным, на вопрос о том, как обойтись без дополнительных структур, тоже бы не ответил)

[@ZlataDobrovolny]

Спасибо, что делитесь!

[@tachik0ma461]

Не бросай, продолжай снимать) У тебя хорошо получается, да и по скале мало хороших видео.

[@user-qu5ch6rl4f]

Первая задача решается без изменения массива двумя циклами ( i = от 0 до

[@wolf_code]

Прошу прочесть закрепленный коммент и ознакомиться с понятием сложности алгоритма

[@ilias3624]

Решается, только решение очень плохое по времени

[@user-en3gy5ue4q]

Извините за глупый вопрос, но что такое val в вашем коде?) Для чего вы пишите перед переменной val?

[@belov_dev]

Вааауу, мега круто !

[@user-vr9uo3vb1w]

На питоне решение в одну строку кода: arr = [какой-то массив] print(2*sum(set(arr)) - sum(arr)) С помощью множества получаем уникальную коллекцию, то есть все элементы по одному разу. Ищем ее сумму с помощью функции sum и удваиваем. Получаем сумму всех элементов массива по 2 раза и вычтем из этого сумму исходного массива. Число найдено

[@wolf_code]

кажется надо поделить на 2 в конце хотя нет, все норм

[@user-nu8ru5uz2h]

И жрём память и время...

[@user-vr9uo3vb1w]

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

[@rvnclaw9914]

Канфетки жрем. Скок жрем то, какая сложность получается, подскажи? @@user-nu8ru5uz2h

[@rvnclaw9914]

Я просто тупой сори. ВОт смари set и sum это O(n). Эт получается O(n)+O(n)?

[@TheSanSanch]

прикольно. сразу подумал про xor, только первым пришло решение, аналогичное подходу с множеством, но вместо множества использовать битсет, где xor-ить i-й элемент. тогда после прохода по всем элементам массива только в одной позиции битсета останется 1 - его позиция - это ответ.

[@user-dv1nc2xo2w]

А зачем множество, если после сортировки можно идти по циклу с шагом 2, а в цикле проверять arr[i]==arr[i+1], только нужно учесть, что если i=n-1, то мы завершаем цикл.

[@TheSanSanch]

​@@user-dv1nc2xo2w затем, чтобы не делать сортировку)))

[@iceone365]

я новичок в пайтон, я когда смотрю такие видосы, пытаюсь сначала решить задачу сам. И вроде получается, но потом когда смотрю решение, понимаю что я чего-то не понимаю n = int(input()) s = [int(input()) for i in range(n)] for i in s: if s.count(i)

[@danilgorlov8803]

На собеседования я в те давние времена приходил так, что это я их выбирал, смогу ли я, хочу ли я работать с этими людьми. И при таком отношении даже если меня не брали, то это я их не выбирал. И моя самооценка всегда была N+1.

[@dieff_automation]

и не получал денег и сидел в жопе

[@andrewmurruvyov4359]

Настоящие программисты получают деньги, не работая, а программы составляют для души

[@user-hi9lb2wr2v]

Разве сначала не придётся обойти массив и преобразовать в биты каждое десятичное число? Конечно процессор оперирует битами, но люди оперируют типами данных на более высоком уровне, и десятичное число нужно же всё равно преобразовать в бинарный тип, или оператор xor в скала сразу можно применять к int и будет работать напрямую с битами?

[@wolf_code]

Сразу с битами

[@user-yb2zj6bf1v]

Чел, у тебя круто получается

[@BarbosJeka]

А reduce на пустом массиве разве не свалится с ошибкой? Может лучше fold использовать, с начальным нулем

[@wolf_code]

Очень тонко подмечено, все ждал когда же это ктото заметит))) Отлично - так держать! Да решение свалится, но у нас по условию каждое число встречается ровно 2 раза и только одно 1 раз, получается числа все таки встречаются Это даже хорошо что reduce свалится с ошибкой, ведь мы не знаем какой ответ мы должны вернуть для пустого списка. 0 в таком случае это неверный ответ - ведь это будет означать что в пустом массиве ответ равен 0 - что конечно неверно, там 0 не встречается 1 раз Тут лучше вернуть None

[@torburgmax]

@@wolf_code какой странный редьюс в скале. ведь эта функция априори должна аккумулировать значения, а значит иметь что-то в качестве начального значения

[@wolf_code]

@@torburgmax для этого там служит другая функция: foldLeft

[@alexjuly7097]

0:12 УДОБНЫЙ способ ВЫЙТИ из зоны комфорта )) звучит забавно

[@wolf_code]

Так и есть, достаточно сказать запишите на собес и в какой то день мне просто надо будет за компом не кску запустить, а zoom)

[@litvinenkow]

а что при использовании XOR разве не потребляется столько же памяти, как размер самого массива или этот массив на Луне находится?

[@wolf_code]

мы ведь не целиком массив xorим

[@MichailLLevin]

а разве set работает не за логарифмическое время? Для целых чисел можно написать сортировку за линейное время. Или использовать множество с хэшем.

[@wolf_code]

set это множество с хэшем в скала как я помню, под капотом это плоские хэш таблицы

[@madkir8206]

Первое, что пришло в голову: Я бы в хэш табле запоминала, какие цифры у нас встречались в качестве ключей, значением сохраняла бы 0 если единожды встретилось число, 1 если встретилось второй раз, и таким образом просто вернула бы ключ, у которого значение 0 :) Но я конечно новичок в алгоритмах, так что это может и не самая лучшая мысля

[@akhmedumarov3944]

Пройтись по массиву, в случае если число попалось впервые закинуть его в map с ключом значения а в значение тру, проверяется впервые или нет, тем что есть ли такое свойство в map, если же оно есть то удаляется свойство. Потом просто находит единственнле свойство map. Сложность O(1)

[@forgotten_forbidden]

O(n)

[@paaapoooi]

Только программирование начал учить, для меня тут происходит что-то гениальное и страшное, но интересное 0.0

[@user-tp6mn4kl6s]

Если только начал учить, то не забивай себе голову видосами про собесы в топовые компании. Это все красиво, но такие решения в боевых проектах я за 6 лет видел 2-3 раза и делались они исключительно из спортивного интереса

[@wolf_code]

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

[@holovkevych]

@@user-tp6mn4kl6s такие задачки, это как математика - для общего развития)

[@Disorrder]

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

[@___________S_t_a_s___________]

К элегантным надо стремиться, пока не начинает гореть дед лайн. ))

[@kirillkirillov7842]

Привет, интересен результат собеседования, взяли (бы) они тебя на работу, или нет? И на какую позицию проходил собеседование?

[@wolf_code]

Не взяли, 3й этап завалил Мидл бэкенд

[@rosel_1337]

можно у вас спросить, вы имеете высшее образование ну или любое и желательно ли это для рынка труда?

[@wolf_code]

У меня есть диплом бакалавра по направлению ПОВТиАС Диплом у меня нигде не спрашивали

[@ishitharajapakse9675]

Very similar to leetcode 540. Single Element in a Sorted Array. First sort and then solution for leetcode for 540(complexity log n, binary search): def my_func(l): left = 0 right = len(l) - 1 while left

[@vanvancich9live]

Так set же работает за log n, поэтому сложность остаётся такая же, как на сортировке, разве нет?

[@wolf_code]

Как устроен сет в скала?

[@lepaxtwin]

0:58 Сгруппировать по значению, и найти запись с количеством вхождений 1.

[@wolf_code]

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

[@user-bk8gt2hs4e]

Если работаешь 5/2, когда ходить по собеседованиям?

[@leonovgleb8535]

Решение с XOR крутое, так сразу в голову не придёт.

[@m.ya.yakovlev]

Хорошая задача. Я её даю своим студентам (самым сильным) - но пока ни один не додумался до решения за один проход (через "исключающее или").

[@user-kj4bv2sv4t]

есть решение через словарь за один проход (o(n)), добавлять значение из массива в словарь и после повторного нахождения удалять, затем вернуть единственный ключ из словаря, по сути один проход + 1 раз сходить в словарь

[@ilias3624]

@@user-kj4bv2sv4t Так память же лишняя требуется, в идеале без нее. У автора в видео было множество, то же самое, что словарь почти по памяти

[@aleksandrkim550]

@@ilias3624 память через словарь меньше занимает. Так как удаляются по ходу решения

[@7Denial7]

А я за 5 минут вышел в голове на это решение, пока на работу ехал)) приятно

[@KirillKlenov]

Ловкий трюк

[@interfi4650]

можно вопрос, почему не подсчитать количество вхождений числа через функцию count? x = [1,2,3,4,5,4,3,2,1] for i in x: if x.count(i) == 1: print(i)

[@wolf_code]

Функция count будет делать n операций, а запускаете вы ее в цикле Получаем общую сложность О(n^2) Это очень долго

[@jjj78ean]

импортируем Counter и через List comprehension выбираем ключ, где значение = 2

[@wolf_code]

как это будет в коде?

[@jjj78ean]

@@wolf_code dict_ = Counter(arr) number = [k for k in dict_ if dict_[k] ==2 ]

[@wolf_code]

@@jjj78ean как быстро строится Counter?

[@nurgisazhumashev1275]

for i in lst: x = lst[0] for r in lst[1:]: if r == x: lst.remove(r) lst.remove(x) print(lst[0]) Решил вот так. Все работает. Верно ли это? Быстро или долго? Можете подсказать?

[@wolf_code]

Верно - но долго - советую прочитать закрепленный комментарий

[@ValihanJumadilov]

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

[@wolf_code]

Тогда они не уникальны

[@user-lh6ou6de6l]

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

[@wolf_code]

Абсолютно согласен Я бы тогда наверное пошел к ним работать, но не прошел все 5 этапов + Тратить время людей не вижу смысла - поэтому сейчас ищу другие способы узнать про задачи с собеседований

[@Anton-ki7ch]

@@wolf_code leetcode?

[@wolf_code]

@@Anton-ki7ch ага, в новом видео про литкод

[@alekseyl]

не назвал бы это «красивым» решением эта задачка придумана вокруг этого решения любое минимальное изменение условий (например, множественные дубли чисел) и оно перестанет работать на практике в общем классика жанра: головоломка ради головоломки

[@wolf_code]

согласен

[@Disorrder]

важно не столько решение, сколько процесс

[@ThemrGhost1905]

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

[@user-nw8gn2xh2v]

Решение конечно вообще неожиданное

[@OpalGooDog]

Создал словарь, пробежался бы циклом по массиву, на каждом новом элементе проверяю содержит ли словарь такое значение по индексу, если да то значение ключа становится на один больше, если нет то добавляем и значение делаем 1, в конце просто ищу в словаре по значению и отдаю этот ключ, Второе решение: преобразую массив в динамический массив, далее буду бежать по нему циклом, на каждом элементе удаляю и проверяю содержится ещё ли такой элемент, если да тоже удаляю если вдруг встретится когда не будет второго вхождения , присваиваем в переменную result и делаем break ,первые решения что пришло в голову и за алгоритмы не шарю, мимо жуниор самоучка

[@alexein6631]

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

[@OpalGooDog]

@@alexein6631 xor вариант в случае 2 только первых вхождений, или к случае 3 вхождений не даст правильный вариант ответа( хотя решение только 1 варианта вхождения одного элемента и 2 других, очень красивое, но боюсь очень редкий кейз

[@alexein6631]

@@OpalGooDog у меня на проекте redis фильтры таким образом в битмап записывает и вычисляет совпадения. Я только сейчас понял как он это делает у себя под капотом.

[@CyberGenius777]

на js можно так решить: const x = [1,2,3,4,5,6,7,6,5,4,3,2,1] const result = x.filter(elem => x.indexOf(elem) === x.lastIndexOf(elem)) console.log(result) // 7 Получается так: если индекс начального и конечного элемента равны, то вернуть этот элемент

[@wolf_code]

Решение будет работать - но советую почитать в закрепленном комменте почему такой подход неэффективен В Вашем решении вы заменили count на indexOf, но сложность будет такой же O(N^2)

[@CyberGenius777]

@@wolf_code да, я это понимаю) Просто решил эту задачу на js написать, просто в комментариях не заметил, чтобы ее на js реализовывали

[@danielrossy7453]

@@wolf_code Ну это как посмотреть :) На JS большинство задач именно так и решается т.к. если на каждый подобный пример разработчик будет тратить ресурсы на поиск решения, то во первых в 9 из 10 случаев это никак не скажется на объёктивных метриках перформанса web app, во вторых потратит гораздо больше времени на имплементацию, а в третьих код станет сложнее с точки зрения понимания и поддержки для других разработчиков. Итого, с точки зрения бизнеса и конечного результата такие примеры сильно далеки от реальной жизни. Тут я не умоляю важность умения решать алгоритмические задачи, но умоляю их ценность при проведении собеседований, которая переоценена.

[@wolf_code]

@@danielrossy7453 тут и не поднимается вопрос о практической ценности задачи а о том что нужно ли по алгоритмам гонять на собесах уже исписано много пабликов - давайте тут не разводить

[@user-yt9jp2ut2t]

одна операция в set O(logN) => решение с сетом работает за O(NlogN)

[@wolf_code]

А если сет на основе хэш таблиц?

[@user-ur2id1ut9k]

Сложить все уникальные элементы умножить на 2 и отнять сумму всех чисел

[@user-dz9oq7ct2o]

Правильно ли понимаю, что значения добавляются по обе стороны и затем сравниваются?

[@wolf_code]

Вы про какой из подходов?

[@user-dz9oq7ct2o]

@@wolf_code Я про само решение Яндекса.

[@wolf_code]

@@user-dz9oq7ct2o в решении через xor никакий сравнений нету - достаточно просто пробежаться по массиву и проиксорить каждое число с переменной Если еще есть вопросы - смело пишите - разберем)

[@cdeblog]

Писал бы на си или на плюсах, решение с ксором пришло бы в голову первым 😉

[@MrVlad3d]

Первое решение работает за О(n), если бы сортировка вызывалась в цикле, то было бы n * log(n). Разве не так?

[@wolf_code]

В первом решении сначала отрабатывает сортировка за O(n log n) затем работает наш проход за O(n) Вспоминаем складывание асимптотик получаем O(n log n + n) = O(n log n) Если бы сортировка вызывалась в каждой итерации цикла было бы O(n (log n) * n) = O(n^2 log n)

[@MrVlad3d]

@@wolf_code точно, спасибо, почему-то перепутал сложность сортировки

[@ReAgent003]

В самом конце ролика вставляй пожалуйста чёрный экран чтобы на его фоне всплывали рекомендованные видео, а то в данном случае превьюшки других твоих роликов закрыли код (09:09)

[@wolf_code]

Отличная идея!

[@user-fl7gg5jd8u]

Привет. Мы перевели всё числа в двоичную систему а как найти лишнее не совсем понял. Спасибо.

[@wolf_code]

Привет Знаешь как работает xor? "ислючающее или" на русском

[@user-fl7gg5jd8u]

@@wolf_code Да, все дошло до меня)))) с работы посмотрел не отдохнувшим :D

[@alexandergrigorev4518]

Почему второе решение считается что за линейное время? Тут не учитывается что под капотом у реализации множества?

[@wolf_code]

А как под капотом реализован Set в Scala?

[@alexandergrigorev4518]

@@wolf_code конкретно в скала не знаю но вот сейчас подумал что наверняка за о(1) 😁

[@wolf_code]

@@alexandergrigorev4518 я гдето в комментах кому то отвечал на этот вопрос, вкратце есть такая структура данных как HAMT, ее еще называют идеальная хэш таблица, можно почитать статью про ее принцип работы если погуглить сразу найдется

[@alexandergrigorev4518]

@@wolf_code о, спасибо!

[@alexandergrigorev4518]

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

[@ilyabikmeev]

Придумал решение за О(N) сначала, но оно требует O(N) памяти. Заводим массив b, где b[i] = количество вхождений числа i в исходный массив. Далее, нам надо по исходному массиву пройтись и для каждого x сделать b[x]++. Далее, проходимся в конце по массиву b и где количество =1 - это ответ.

[@Khashimova_wellness]

А если в массиве будут большие числа, например 1000000000, придется создать массив длиной в миллиард элементов

[@wolf_code]

@@Khashimova_wellness согласен - получается будет не линейное время а O(NM), где M максимальное значение в списке Алгоритм отработает линейно при условии если значения в массиве будут маленькими

[@ilyabikmeev]

@@wolf_code Всмысле) Он всегда линейно работает, мы один проход делаем по массиву при подсчете, у нас цикл что то вроде for(int i = 0; i < n; ++i) b[a[i]]++; И потом один проход по массиву посчитанному for(int i = 0; i < n; ++i) if(b[i] == 1) //Мы нашли число

[@ilyabikmeev]

@@wolf_code То, что потребуется больше памяти, я согласен. И то, что алгоритм будет работать за O(m), где m- максимум в изначальном массиве тоже согласен, но никак не за O(nm). Это просто решение, которое пришло в голову сразу, через xor конечно элегантнее и лучше)

[@wolf_code]

@@ilyabikmeev точно - тупанул)) мы же не внутри цикла ходим да будет тогда скорее так O(max(M, N)) Признаю - ошибся

[@user-iq9ll8lz9m]

Как вариант из массива создать хеш-карту, ключ - число, значение - количество вхождений и в итоге найти ключ, значение которого равно один. Плюсы, универсальность, если изменится условие и одинокий элемент будет не один, то меняется вариант вывода результата на массив. Если в видео было данное решение, то извините)

[@wolf_code]

Прикольно! Получится сложность O(N), но потребуется O(N) памяти так же для хранения хэштаблицы

[@user-iq9ll8lz9m]

@@wolf_code в итоге как и у любого решения, свои плюсы и минусы. Кроме побитовых операций, там без минусов)

[@wolf_code]

@@user-iq9ll8lz9m согласен

[@ArthurMudrick]

в реальной жизни именно так я бы и написал, т.к. условие сто процентов бы изменилось :)

[@wolf_code]

@@ArthurMudrick реальные задачи согласен - лучше решать без ухищрений понятными способами

[@user-rc1ms5zz6u]

А есть возможность сделать такое тестирование, когда над душой не стоят. Я терпеть не могу когда смотрят, когда я сру. Если не устроюсь разработку вернусь в поставки коптеров и военного снаряжения из Китая, хорошо что китйский язык учил 🙏

[@Gaymernumbe1]

2 решение не за линию. Поиск и добавление в множество не единица, а log(n)(во всяком случае в c++ и java), так что решение и не ускорилось и стало потреблять больше памяти

[@wolf_code]

Советую почитать про HAMT и как реализованы хэштаблицы в scala (иммутабельные хэштаблицы)

[@wolf_code]

да и в спецификации джава сказано что хэштаблицы работают за константу docs.oracle.com/javase/7/docs/api/java/util/HashSet.html#add(E) Вы какой либой пользуетесь?

[@wolf_code]

да в плюсах написано что константное время en.cppreference.com/w/cpp/container/unordered_set )

[@Gaymernumbe1]

Я имел ввиду множества на самобалансирующихся деревьях типа tree set в java и обычный set в плюсах, но идея с hash map - и в правду верная

[@Gaymernumbe1]

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

[@liOnka911]

За сколько времени самообучения ты вышел на такой уровень знаний?

[@wolf_code]

Не скажу что уровень высокий, программированием занимаюсь лет 5

[@alexnovik6223]

Задача: нарисовать все возможные иконки 3 на 3 пикселя в 8 битном исполнении.

[@wolf_code]

Хорошая тема для нового выпуска)) Запилю видос

[@wolf_code]

а что значит в 8 битном исполнении?

[@alexnovik6223]

@@wolf_code 8 бит = 1 байт = диапазон [0, 255] Т.е. результат в виде всех двумерных массивов 3 на 3 где каждая ячейка от 0 до 255. Сложность, время, потребление памяти )))

[@URobotics]

Это 9 ^256 ?

[@wolf_code]

@@URobotics скорее наоборот 9 пикселей по 256 значений принимает каждый, получаем 256^9 = (2^8)^9 = 2^72 2^72 байта это 2^42 терабайта, столько памяти нет думаю нигде))

[@sdhfdsfh2413]

как можно сделать цветные скобки, как в видео?

[@wolf_code]

плагин rainbow bracket

[@user-oj7lo6mv7h]

9:05 надо посмотреть, как такую задачу можно решить на питоне/java и пр

[@user-oh8oq4oz7d]

А какое решение будет, если надо отыскать все уникальные числа?

[@wolf_code]

Всм? Уникальное число одно по условию

[@StanleyOzzy]

Вот мое решение с рекурсией на python, но оно конечно не лучшее из предложенных: def only_single(my_list): for n, i in enumerate(my_list[1:]): if my_list[0] == i: my_list.pop(0) my_list.pop(n) return only_single(my_list) return my_list[0] P.s. за отступы прошу прощения, с мобильника писал

[@foundersl]

Это ужасно разрушать исходное состояние переданного объекта. Не надо так.

[@dmitrievsergey]

С xor ящетаю, гениально!

[@wolf_code]

тоже так подумал когда узнал про это решение)

[@sergeyivanov3351]

Просьба - пишите название языка на который вы собеседовались.

[@wolf_code]

Спасибо за коммент В будущем учту, скорее просто добавлю в описании канал. Я специализируюсь только на языке скала А у яндекса нет привязки к языку в собесах, можно даже на псевдокоде, по крайней было так на моих собесах

[@user-bm1jf2tq2n]

Так какой язык-то? Подскажите, пожалуйста, любопытно

[@wolf_code]

@@user-bm1jf2tq2n scala

[@user-bm1jf2tq2n]

@@wolf_code благодарю

[@timofeev.vadim.96]

Интересно, зачем вообще так углубляться в скорость решения задачи, если питон вообще не про скорость?) во всяком случае лезть в бинарный код перебор по-моему) Вы и так решили здорово, главное хоть как-то решить, и желательно, не O(n^2).

[@zhenshuang]

Задача в пару действий. 1. делаешь из списка сет, считаешь полную сумму и умножаешь на два. 2. вычитаешь из полученного числа сумму первого списка. Фактически это и есть XOR

[@wolf_code]

допустим дано {1, 2, 2} Вычисляем сумму = 5 Умножаем ее на 2: 5*2 = 10 Вычитаем сумму списка: 10 - 5 = 5 Ответ 5? UPD понял - ну да с сетом там все сходится

[@alexanderfedintsev9570]

действий надо побольше: 1. Считаем сумму всех элементов массива, она равна 2S + x 2. Преобразуем массив в сет и считаем сумму, она равна S + x 3. Вычитаем из первого второе, получаем S 4. Умножаем S на 2 и вычитаем из первой суммы Но это решение все равно требует O(n) памяти и ничем не лучше варианта с множеством

[@manul74]

@@wolf_code a = [1,1,2,2,3,3,4,4,5,5,7] print( sum(set(a)) * 2 - sum(a) )

[@w01fer86]

Фактически для любого серьёзного N (для которого имеет смысл реализовывать линейный алгоритм вместо квадратичного) сумма элементов списка не будет помещаться в числовую переменную.

[@Antonigin1995]

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

[@PlaySiksShow]

Похожее решали в универе на втором курсе, когда с Паскалем знакомились)

[@wolf_code]

задача довольно простая и известная - в собесе можно сказать была разминочной

[@idontknow_]

def find_uniq(nums: list[int]) -> int: nums_table = set() for i in nums: if i not in nums_table: nums_table.add(i) else: nums_table.remove(i) return list(nums_table)[0] сразу написал сет, но до xor так же не догадался :\

[@user-yz1mv6lk8c]

А в какой программе ты ходишь?

[@wolf_code]

www.jetbrains.com/idea/ + scalaplugin

[@user-yz1mv6lk8c]

@@wolf_code он как я понял платный посоветуй редактор кода на Линукс ?

[@wolf_code]

@@user-yz1mv6lk8c community версия бесплатная, я ей пользуюсь можно еще попробовать vs-code, neo-vim

[@user-xi3nh8lg8i]

Мне сразу пришло в голову решение def get_n(lst): return min(lst, key=lambda x: lst.count(x))

[@wolf_code]

сразу пришло решение которое работает очень медленно)

[@Disorrder]

В чём смысл сортировать массив, если можно решить без сортировки? Сортировка работает за N * log N, после этого придётся сделать полный проход за N. Зачем, когда можно создать хэш-мап и записывать туда все найденные числа. Но перед записью сделать проверку, если оно там есть, то удалить его от туда. В итоге останется только одно число, которое будет являться ответом. При этом сложность алгоритма будет N ещё и за 1 проход P.S. А, ну это второй вариант, ок 3:25 Ты пробегаешь по каждому элементу отсортированного массива, при том, что они идут парами?! Выглядит не очень Решение с xor и правда очень красивое

[@wolf_code]

А второе решение смотрели дальше?

[@homehome-hl9do]

О, а я догадался до xor-a. Где тут контракты подписывают? 😊

[@igrillla]

Что за должность? Что за язык программирования?

[@wolf_code]

Я шел на backend разработчика, язык scala

[@crane5922]

Проблема Яндекс собеседования, что им нужно их решение, а не то что можно рассуждать.

[@user-kj4bv2sv4t]

решение на го: func search(ar []int) int { m := make(map[int]struct{}) for i :=0; i < len(ar); i++ { if _, ok := m[ar[i]]; ok { delete(m, ar[i]) } else { m[ar[i]] = struct{}{} } } for k := range m { return k } return 0 } если у нас гарантировано есть 1 не дубль число в массиве, то мы его вернем, так как оно единственное будет лежать в мапе (словаре)

[@wolf_code]

Лучший!

[@stepandemin5836]

Ничего подобного: в яндексе просьба о помощи насцениваеться как подсказка и идёт в минус

[@user-wy2qf5vr2s]

Какой язык программирования?

[@wolf_code]

скала

[@user-rn7jq7lm9b]

Я конечно не программист, но на Python решается просто через множества (class 'set') Решение: искомое число = 2 * sum(set(s)) - sum(s) где: s - начальное множество 2 * sum(set(s)) - удвоенное сумма эл-в без повтора sum(s) - сумма элементов изначально

[@wolf_code]

Как думаете - где ошибка в Вашем решении?

[@user-rn7jq7lm9b]

@@wolf_code Буду благодарен если поделитесь. Понимаю, что такой вариант не сработает, если элементы множества это не числа.

[@wolf_code]

@@user-rn7jq7lm9b хотя нет, вроде все норм, я ошибался

[@wolf_code]

@@user-rn7jq7lm9b Ваше решение не сработает если в массиве большие числа, сумма вылезет за int

[@user-rn7jq7lm9b]

@@wolf_code Спасибо

[@yaroslavqwerty8609]

Вот на JS, вроде сложность O(3n) -> O(n), решил за 2 минуты const arr = [1,3,4,3,1,2,4,] const obj = arr.reduce((ac, el)=>{ if(el in ac) ac[el] += 1 else ac[el] = 1 return ac }, {}) console.log(Object.keys(obj).find((el) => obj[el] === 1))

[@wolf_code]

Красавчик

[@yaroslavqwerty8609]

@@wolf_code как неожиданно и приятно)

[@user-mn2po8ns2z]

нука ткните меня как начинающего в чём проблема такого решения ? arr.forEach(num => { let temp = arr.filter((item) => item === num) if (temp.length === 1) { console.log(temp[0]); } });

[@wolf_code]

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

[@user-mn2po8ns2z]

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

[@wolf_code]

@@user-mn2po8ns2z типа того допустим при размере входного массива в 100к элементов ваше решение произведет ~100k^2 операций если предположить что современный процессор делает миллиард операций в секунду - то ваше решение грубо говоря отработает за 10 секунд - что довольно долго

[@MuxaL]

Можно решить так: заводить переменную m = 1 и бежишь по массиву: если число m делится на элемент i, то мы его делим, а если нет - то перемножаем. В итоге m окажется нашим ответом

[@MuxaL]

(я питонист, мне можно работать с нормальными православными интами)

[@wolf_code]

допустим список такой (1, 3, 3) 1 не делится ни на одно число из списка, ответ равен 9?

[@MuxaL]

@@wolf_code 1) 1 // 1 2) 1 * 3 3) 3 // 3 = 1

[@MuxaL]

@@wolf_code Хотя нет, я нашёл ошибку. На случае 3 9 27 9 3 выведет 3

[@igortunev6163]

Решение 2 не совсем линейно. Даже в лучшем случае, если реализация сет через хэш таблицы, то линейность только по вероятности.

[@wolf_code]

Если не линейное, то какое?

[@igortunev6163]

​@@wolf_code, по умолчанию под сложностью подразумевают сложность для ДМТ (детерминированная машина Тьюринга). Самый быстрый алгоритм реализации, известный мне, это дерево, с которым сложность 2го алгоритма n log n С хэш таблицами в худшем случае может получиться n^2 (на сколько понимаю). Худший случай и определяет сложность реализации. Если бы Вас просили написать алгоритм линейный в среднем (по вероятности), то решение корректно. Но тогда нужно было об этом было сказать в видео.

[@igortunev6163]

@@wolf_code, хотя и хэш таблицу можно модифицировать до log n (в худшем случае) при вставке/удалении/проверке.

[@wolf_code]

@@igortunev6163 как работает хэш таблица по вашему? Конкретно реализация ее в библиотеке java? Там никак невозможна деградация поиска и вставки до линейного времени

[@igortunev6163]

@@wolf_code, теоретическая модель допускает линейность. В java, видимо, модифицированная версия. Например, можно подобрать множество чисел, на котором хэш функция будет выдавать один и тот же адрес (на список). Тогда значения придётся класть в один список, сложность поиска в котором линейна от его длины (поиск необходим для сетов даже при вставке). Отсюда и линейность в худшем случае. Но можно вместо списка использовать, опять же, дерево или вложенный хэш и рассуждения повторяются. Те операции быстрее чем за log n, скорей всего не реализуете (мне такого не известно). Ну, или предложите тогда?

[@happer2009]

Прикольно. Я бы сбросил массив в двумерный, во второе измерение проставил единички, свернул по первому измерению сложив значения второго, отсортировал по второму измерению, верхнее число - ответ. И не важно число это или строка, пофиг. :-) Как вам такой изврат ? :-)

[@wolf_code]

Не совсем понятно что значит "сбросил массив в двумерный" - это значит разложить значения в массиве по оси x? а проставите единички по оси y?

[@violetjellyfish2089]

Я на кодварс видела такую задачу

[@user-ir3dg4li4s]

а как выглядело решение в коде?

[@wolf_code]

Как-то так: 3:38, 6:22, 9:02 )

[@user-ir3dg4li4s]

@@wolf_code ой, просто не досмотрел последние секунды видео, сорян за невнимательность и спасибо за ответ!)

[@user-ml6bc4qm1q]

Что за программа?

[@wolf_code]

Какая? Если про среду разработки intellij idea

[@avpmk]

Random access по листу не константа, у первого решения выше сложность.

[@wolf_code]

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

[@avpmk]

@@wolf_code 3:06 Я про доступ к уже отсортированному листу b, строчки 5 и 6

[@wolf_code]

@@avpmk тут да согласен, надо было конвертнуть в vector

[@maximbka4083]

a = [1, 1, 2, 2, 3, 5, 5, 8, 8, 13, 13] for e1 in a: cn = 0 for e2 in a: if e1 == e2: cn += 1 if cn == 1: print(e1) Вот так решил

[@user-qq5dr5mi4q]

ЖОСКО

[@wolf_code]

собесы яндекс проводит жестко согласен))

[@NameXss]

contains не использует ли цикл?

[@wolf_code]

скорее всего

[@NameXss]

@@wolf_code т.е. получается там квадратичное время, а не линейное?

[@wolf_code]

@@NameXss я почему-то подумал что вы спрашиваете про contains у List-а, у Set contains работает за O(1)

[@NameXss]

@@wolf_code очень интересно как так реализовано :)

[@NameXss]

@@wolf_code ах, там хеши, понятно)

[@ErhoSen]

def find_unique_number(arr: List[int]) -> int: return sum(set(arr)) * 2 - sum(arr)

[@wolf_code]

А если сумма не поместится в int? Твое решение выдаст неверный ответ

[@ErhoSen]

@@wolf_code В питонах скорее всего будет Exception. Каждый раз удивляюсь задачам на собеседованиях Яндекса. Дрочат тебя по памяти и сложности алгоритмов - а на работе ты будешь скадывать джейсоны в базу. И в чём смысл? 2 раза собесился, оба раза не проходил. Сейчас рекрутеры стучатся в третий. Зачем? Я за это время прокачался как бэкендер, но остался на университетских знаниях в алгоритмах

[@wolf_code]

@@ErhoSen запустите свое решение - оно неверно работает))

[@Levelord92]

Дай угадаю концовку: после 100 разных решений ты пришёл к решению со сложностью O(1), и спустя ещё 40 этапов собеседования они прислали оффер на 50 тысяч рублей? Очень в стиле яндекса

[@wolf_code]

Хехе

[@44magnum84]

Решение с XOR - просто читерство какое-то

[@wolf_code]

есть такое

[@w01fer86]

По названию ролика хотел возмутиться, мол палить задачи некрасиво. Но посмотрел, ровно эту задачу у меня спрашивали при устройстве в Яндекс в 2016)) она же в куче вариантов на всяких литкодах лежит... В общем, никаких претензий)

[@wolf_code]

Да - кмк эта задача уже давно стала некой классикой в программировании, как допустим быстрая сортировка или поиск в ширину

[@w01fer86]

@@wolf_code тем удивительнее, что такой процент людей в комментах может написать решение в одну строку, но не думает об алгоритмической оптимальности вовсе

[@0yustas0]

@@w01fer86 я, если честно не совсем девелопер, но иногда балуюсь. Хотелось бы вступится за решения "в одну строчку" ибо чем проще написано и чем больше, при возможности, в БД спихнули на выполнения- тем лучше. Старина Том Кайт врать не будет :) Ну и мое однострочечное решение- его критике буду рад. def foo(l, xor_sum= 0): for i in l: xor_sum ^=i return xor_sum

[@w01fer86]

@@0yustas0 "В одну строчку" не тождественно "плохое". Я имел ввиду, что люди достаточно хорошо знают возможности языка (раз могут написать короткое решение), т.е. не совсем начинающие, но не думают об алгоритмической эффективности. Ваше решение алгоритмически оптимально (так что для хорошего результата на собеседовании подойдёт), но не пройдёт ревью в реальной жизни в соответствии с большинством стайлгайдов, т.к. (не беря в расчёт расположение пробелов): 1. в функцию добавлен ненужный параметр. Зачем кому-то вызывать foo(l, 25)? Кажется, незачем, но у каждого читающего функцию будет такой вопрос. Ну и добавляется шанс вместо функции fo, принимающей два параметра, случайно вызвать foo и долго дебажить возникшую проблему. Так что xor_sum=0 лучше вынести отдельной строкой. 2. Условие for и тело цикла должны быть на разных строчках даже если тело состоит из одной строки. Опять же это проще читать. Вот и получается, что ваш "однострочник" из двух строк будет более понятен, если записать его в 4 строки.

[@akiragosu]

какое обидное поражение КПХФ от НИП…😢😭 Молодые из Флэймс заслуживали эту победу больше Ниндзей (((

[@smokehappiest9005]

чеееел) тыыы)))) аукзахухкахукхаукха я смотрел вчера этот матч бляяя,... ты как тут оказался

[@akiragosu]

@@smokehappiest9005 аххахахахаха наугад тыкнул, шоб с эмоциями поделиться🤣🤣

[@smokehappiest9005]

@@akiragosu наугад на видео про собес в яндекс?))))

[@akiragosu]

@@smokehappiest9005 да чет приуныл чутка, че было первое нажал😁😏

[@user-iCuaebtAi926]

очень классно, но никому не нужно, театр абсурда

[@0yustas0]

У меня в голову в такой последовательности решения приходили... def spam(x): d= {} for i in x: d.update({i:d.get(i,0)+1}) if d.get(i)==2: d.pop(i) return list(d.items())[0][0] ham = lambda x: sum(set(x))*2-sum(x) def eggs(l, xor_sum= 0): for i in l: xor_sum ^=i return xor_sum a = [9,1,2,7,5,1,7,9,2] print(spam(a)) print(ham(a)) print(eggs(a)) но я лет 15 SQL пишу:)

[@wolf_code]

а на SQL решение оч интересно глянуть

[@0yustas0]

@@wolf_code не вопрос. Но под рукой у меня сейчас только hive на tez (ох как меня он печалит). Да и 2AM уже - пора спать :) Если не забуду, завтра добавлю намного сипотичнее на Spark+Scala или Snowflake(опять же что под рукой будет) WITH game_at_2am AS (SELECT '["9","1","2","7","5","1","7","9","2"]' AS i_want_sleep), more_beer AS (SELECT split(regexp_extract(i_want_sleep,'^\\["(.*)\\"]$',1),'","') AS c1 FROM game_at_2am), relax AS (SELECT x FROM more_beer LATERAL VIEW EXPLODE (c1) b AS x) SELECT x FROM relax; дальше джавист любой уже GROUP BY и HAVING COUNT(*) допишет, а я спать :) переварит как символы, так и инты

[@0yustas0]

@@wolf_code вот пример однострочника Spark пока стою в пробке) val df = Seq((Seq(9,1,2,7,5,1,7,9,2))).toDF("c1") df.withColumn("c2", array_distinct($"c1")).selectExpr("2* aggregate(c2, 0, (x, y) -> x + y) - aggregate(c1, 0, (x, y) -> x + y) AS result").show()

[@0yustas0]

@@wolf_code сел полистать питоновский мануал... мне пришел в голову еще один однострочник from functools import reduce src = reduce(lambda x,y: x^y, [1,2,3,7,3,2,1]) :)

[@wolf_code]

@@0yustas0 очень похоже на 3е решение в видео

[@siroziro6672]

как же вы тихо говорите )

[@0yustas0]

А ведь через XOR даже для стороки работает... s = "a@NddNss?@a" def foo(x): sm = 0 for i in x: sm^=ord(i) return chr(sm) print(foo(s))

[@wolf_code]

Ага строка это по сути ведь массив байтов

[@MrNarutorengun]

*ред. язык: python целый час е*лся с 1 задачей пишу до того как увидел результат автора: def sing_finder(a): res = 0 for i in range(0, len(a)): b = a[i] q = 0 for j in range(0, len(a)): if b == a[j]: q = q+1 if q == 1: print('i: ',b, 'q: ',q) res = b else: pass return res print('result: ',sing_finder(a))

[@MrNarutorengun]

P.S. только только повторил/прошёл основы синтаксиса))

[@wolf_code]

@@MrNarutorengun Вы написали на питоне, ну ок может и хотели на нем ваше решение неэффективное - прошу прочесть закреп. коммент но все равно красавчик - огромный респект за упорство

[@MrNarutorengun]

ответ реально крутой, мне теперь страшно представить насколько более громоздко моё решение))

[@dimape.4180]

А вот так на JS?)))) const fn = (ar) => { let c =[]; ar.forEach((el) => { let z = ar.filter(e=>{ return el == e }) if (z.length < 2) { return c.push(z[0]) } }) return c }

[@wolf_code]

Советую читать закрепы

[@wolfgame0]

Неплохо - но надо поработать над дикцией Продолжай пилить

[@wolf_code]

Согласен - лучшая речь в видосе на 0:19))