Ребят перед написанием комментария прошу прочесть Очень часто в комментариях пишут такой код: 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 тысяч шагов
Но ты же мог просто взять и записывать уникальное число в 1 ячейку памяти и просто пройти весь массив за N. Если число повторяется, то зануляй результат. Зачем изобретать велосипеды? Удаление из массива это тоже лишние операции, работа с масками конечно красиво, но абсолютно излишнее решение
@@wolf_code можно использовать множество - добавлять элемент в него и при повторении удалять. В итоге останется 1 элемент множества - это и будет ответ. Сложность - линейная. Это про первую задачу)
@@LineageL2ad Это решение значительно быстрее, чем придуманное автором №1. Почему-то, автор считает, что функция .sorted чудесным образом не расходует ресурсы.
Первое решение которое мне пришло в голову после прочтения условия (пишу на js): 1. Завел мапу isUnique 2. Пробегаясь по массиву чисел: а) Если нет в мапе isUnique ключа с таким числом - добавляю его б) Если есть в мапе isUnique ключ с таким числом - удаляю его 3. Единственный оставшийся ключ в мапе это и есть нужное нам число, возвращаю его в качестве результата. (т.к. доступ по ключу это быстрая операция, то считаю алгоритм не особо жадным, на вопрос о том, как обойтись без дополнительных структур, тоже бы не ответил)
На собеседования я в те давние времена приходил так, что это я их выбирал, смогу ли я, хочу ли я работать с этими людьми. И при таком отношении даже если меня не брали, то это я их не выбирал. И моя самооценка всегда была N+1.
На питоне решение в одну строку кода: arr = [какой-то массив] print(2*sum(set(arr)) - sum(arr)) С помощью множества получаем уникальную коллекцию, то есть все элементы по одному разу. Ищем ее сумму с помощью функции sum и удваиваем. Получаем сумму всех элементов массива по 2 раза и вычтем из этого сумму исходного массива. Число найдено
@@АлександрКуликов-ж8к никто и не говорил, что это оптимальное решение. Просто я был заинтересован в поиске как можно большего количества разных подходов к задаче, и изложил тот, который не был нигде представлен.
Если только начал учить, то не забивай себе голову видосами про собесы в топовые компании. Это все красиво, но такие решения в боевых проектах я за 6 лет видел 2-3 раза и делались они исключительно из спортивного интереса
Согласен с Евгением, если цель в кратчайшие сроки научиться писать практический код то лучше сделать упор на изучение библиотек и инфраструктуры По алгоритмам азы только - типа О-большое и др.
не согласен с Евгением. Такие задачи важно решать самостоятельно. Как только увидел условие, ставь видео на паузу и попробуй написать код. Это не займёт много времени, а ты заодно научишься придумывать алгоритмы, что важно. И только того, как ты полностью понял суть задачи, можно смотреть продолжение и тебе расскажут как сделать лучше. И ты скорее всего даже поймёшь почему оно лучше. А может, не поймёшь. Но по крайней мере, решишь всё сам.
Первое, что пришло в голову: Я бы в хэш табле запоминала, какие цифры у нас встречались в качестве ключей, значением сохраняла бы 0 если единожды встретилось число, 1 если встретилось второй раз, и таким образом просто вернула бы ключ, у которого значение 0 :) Но я конечно новичок в алгоритмах, так что это может и не самая лучшая мысля
Задача в пару действий. 1. делаешь из списка сет, считаешь полную сумму и умножаешь на два. 2. вычитаешь из полученного числа сумму первого списка. Фактически это и есть XOR
допустим дано {1, 2, 2} Вычисляем сумму = 5 Умножаем ее на 2: 5*2 = 10 Вычитаем сумму списка: 10 - 5 = 5 Ответ 5? UPD понял - ну да с сетом там все сходится
действий надо побольше: 1. Считаем сумму всех элементов массива, она равна 2S + x 2. Преобразуем массив в сет и считаем сумму, она равна S + x 3. Вычитаем из первого второе, получаем S 4. Умножаем S на 2 и вычитаем из первой суммы Но это решение все равно требует O(n) памяти и ничем не лучше варианта с множеством
Фактически для любого серьёзного N (для которого имеет смысл реализовывать линейный алгоритм вместо квадратичного) сумма элементов списка не будет помещаться в числовую переменную.
не назвал бы это «красивым» решением эта задачка придумана вокруг этого решения любое минимальное изменение условий (например, множественные дубли чисел) и оно перестанет работать на практике в общем классика жанра: головоломка ради головоломки
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
Создал словарь, пробежался бы циклом по массиву, на каждом новом элементе проверяю содержит ли словарь такое значение по индексу, если да то значение ключа становится на один больше, если нет то добавляем и значение делаем 1, в конце просто ищу в словаре по значению и отдаю этот ключ, Второе решение: преобразую массив в динамический массив, далее буду бежать по нему циклом, на каждом элементе удаляю и проверяю содержится ещё ли такой элемент, если да тоже удаляю если вдруг встретится когда не будет второго вхождения , присваиваем в переменную result и делаем break ,первые решения что пришло в голову и за алгоритмы не шарю, мимо жуниор самоучка
Теже идеи с циклом пришли в голову. Но его минус в том, что если массив на много миллионов итераций, да ещё и часто вызывается - то можно нефигово так нагрузить железо. Но наверное в рамках интервью можно это упомянуть, но не учитывать в условие задачи.
@@alexein6631 xor вариант в случае 2 только первых вхождений, или к случае 3 вхождений не даст правильный вариант ответа( хотя решение только 1 варианта вхождения одного элемента и 2 других, очень красивое, но боюсь очень редкий кейз
@@OpalGooDog у меня на проекте redis фильтры таким образом в битмап записывает и вычисляет совпадения. Я только сейчас понял как он это делает у себя под капотом.
прикольно. сразу подумал про xor, только первым пришло решение, аналогичное подходу с множеством, но вместо множества использовать битсет, где xor-ить i-й элемент. тогда после прохода по всем элементам массива только в одной позиции битсета останется 1 - его позиция - это ответ.
А зачем множество, если после сортировки можно идти по циклу с шагом 2, а в цикле проверять arr[i]==arr[i+1], только нужно учесть, что если i=n-1, то мы завершаем цикл.
В самом конце ролика вставляй пожалуйста чёрный экран чтобы на его фоне всплывали рекомендованные видео, а то в данном случае превьюшки других твоих роликов закрыли код (09:09)
Пройтись по массиву, в случае если число попалось впервые закинуть его в map с ключом значения а в значение тру, проверяется впервые или нет, тем что есть ли такое свойство в map, если же оно есть то удаляется свойство. Потом просто находит единственнле свойство map. Сложность O(1)
2 решение не за линию. Поиск и добавление в множество не единица, а log(n)(во всяком случае в c++ и java), так что решение и не ускорилось и стало потреблять больше памяти
да и в спецификации джава сказано что хэштаблицы работают за константу docs.oracle.com/javase/7/docs/api/java/util/HashSet.html#add(E) Вы какой либой пользуетесь?
@@wolf_code 8 бит = 1 байт = диапазон [0, 255] Т.е. результат в виде всех двумерных массивов 3 на 3 где каждая ячейка от 0 до 255. Сложность, время, потребление памяти )))
@@URobotics скорее наоборот 9 пикселей по 256 значений принимает каждый, получаем 256^9 = (2^8)^9 = 2^72 2^72 байта это 2^42 терабайта, столько памяти нет думаю нигде))
есть решение через словарь за один проход (o(n)), добавлять значение из массива в словарь и после повторного нахождения удалять, затем вернуть единственный ключ из словаря, по сути один проход + 1 раз сходить в словарь
Придумал решение за О(N) сначала, но оно требует O(N) памяти. Заводим массив b, где b[i] = количество вхождений числа i в исходный массив. Далее, нам надо по исходному массиву пройтись и для каждого x сделать b[x]++. Далее, проходимся в конце по массиву b и где количество =1 - это ответ.
@@Khashimova_wellness согласен - получается будет не линейное время а O(NM), где M максимальное значение в списке Алгоритм отработает линейно при условии если значения в массиве будут маленькими
@@wolf_code Всмысле) Он всегда линейно работает, мы один проход делаем по массиву при подсчете, у нас цикл что то вроде for(int i = 0; i < n; ++i) b[a[i]]++; И потом один проход по массиву посчитанному for(int i = 0; i < n; ++i) if(b[i] == 1) //Мы нашли число
@@wolf_code То, что потребуется больше памяти, я согласен. И то, что алгоритм будет работать за O(m), где m- максимум в изначальном массиве тоже согласен, но никак не за O(nm). Это просто решение, которое пришло в голову сразу, через xor конечно элегантнее и лучше)
Как вариант из массива создать хеш-карту, ключ - число, значение - количество вхождений и в итоге найти ключ, значение которого равно один. Плюсы, универсальность, если изменится условие и одинокий элемент будет не один, то меняется вариант вывода результата на массив. Если в видео было данное решение, то извините)
Интересно, зачем вообще так углубляться в скорость решения задачи, если питон вообще не про скорость?) во всяком случае лезть в бинарный код перебор по-моему) Вы и так решили здорово, главное хоть как-то решить, и желательно, не O(n^2).
Можно решить так: заводить переменную m = 1 и бежишь по массиву: если число m делится на элемент i, то мы его делим, а если нет - то перемножаем. В итоге m окажется нашим ответом
В первом решении сначала отрабатывает сортировка за 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)
Дай угадаю концовку: после 100 разных решений ты пришёл к решению со сложностью O(1), и спустя ещё 40 этапов собеседования они прислали оффер на 50 тысяч рублей? Очень в стиле яндекса
Я конечно не программист, но на Python решается просто через множества (class 'set') Решение: искомое число = 2 * sum(set(s)) - sum(s) где: s - начальное множество 2 * sum(set(s)) - удвоенное сумма эл-в без повтора sum(s) - сумма элементов изначально
Привет, я еще совсем новичек в программировании, но считался бы этот черезчур простой код ответом на эту задачу? from collections import Counter a = [9,1,2,7,5,1,7,9,2] b = [key for key,value in Counter(a).items() if value == 1] print(*b)
на 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 Получается так: если индекс начального и конечного элемента равны, то вернуть этот элемент
Решение будет работать - но советую почитать в закрепленном комменте почему такой подход неэффективен В Вашем решении вы заменили count на indexOf, но сложность будет такой же O(N^2)
@@wolf_code Ну это как посмотреть :) На JS большинство задач именно так и решается т.к. если на каждый подобный пример разработчик будет тратить ресурсы на поиск решения, то во первых в 9 из 10 случаев это никак не скажется на объёктивных метриках перформанса web app, во вторых потратит гораздо больше времени на имплементацию, а в третьих код станет сложнее с точки зрения понимания и поддержки для других разработчиков. Итого, с точки зрения бизнеса и конечного результата такие примеры сильно далеки от реальной жизни. Тут я не умоляю важность умения решать алгоритмические задачи, но умоляю их ценность при проведении собеседований, которая переоценена.
@@danielrossy7453 тут и не поднимается вопрос о практической ценности задачи а о том что нужно ли по алгоритмам гонять на собесах уже исписано много пабликов - давайте тут не разводить
Очень тонко подмечено, все ждал когда же это ктото заметит))) Отлично - так держать! Да решение свалится, но у нас по условию каждое число встречается ровно 2 раза и только одно 1 раз, получается числа все таки встречаются Это даже хорошо что reduce свалится с ошибкой, ведь мы не знаем какой ответ мы должны вернуть для пустого списка. 0 в таком случае это неверный ответ - ведь это будет означать что в пустом массиве ответ равен 0 - что конечно неверно, там 0 не встречается 1 раз Тут лучше вернуть None
@@wolf_code какой странный редьюс в скале. ведь эта функция априори должна аккумулировать значения, а значит иметь что-то в качестве начального значения
В чём смысл сортировать массив, если можно решить без сортировки? Сортировка работает за N * log N, после этого придётся сделать полный проход за N. Зачем, когда можно создать хэш-мап и записывать туда все найденные числа. Но перед записью сделать проверку, если оно там есть, то удалить его от туда. В итоге останется только одно число, которое будет являться ответом. При этом сложность алгоритма будет N ещё и за 1 проход P.S. А, ну это второй вариант, ок 3:25 Ты пробегаешь по каждому элементу отсортированного массива, при том, что они идут парами?! Выглядит не очень Решение с xor и правда очень красивое
решение на го: 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 не дубль число в массиве, то мы его вернем, так как оно единственное будет лежать в мапе (словаре)
Вот мое решение с рекурсией на 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. за отступы прошу прощения, с мобильника писал
Блин серьезно? 21 век, сервера поддерживают до нескольких терабайт оперативы, зилион-ядерные процессоры, датацентры размером с дом, приложения того же яндекса которые показывают 2 формочки весит 200мб. А в итоге ксорим сраный числовой массив чтобы сэкономить 2 байта памяти... Бред да и только. Я конечно понимаю что это задача далека от реальности и в реальность(особенно в яндексе) никто этим бредом заниматься не будет, но каждый раз когда я вижу такие задания на собесах - просто жопа горит....
А вот и не правда. Я проработал в этой компании достаточно долго и могу с уверенностью сказать - все эти терабайты оперативы и зилион-ядерные процы в множествах датацентрах размером с дом кончаются не начавшись, если везде писать квадратичный по сложности код, а кода ну очень много. Вы не представляете какие порой бывают нагрузки. На всяких конференциях с участием спикеров из подобных компаний можно подчерпнуть для себя множество примеров подобных задач, где нужно ну очень аккуратно писать с точки зрения оптимальности. При этом клиентские приложения в 200мб вообще нельзя сравнивать с тем, что крутится на серверах - это просто разные миры. Но согласен, у меня у самого иногда горит от излишней академичности задач и не все они к реальности имеют отношение, но они позволяют понять способности к размышлению и гибкость в рассуждениях, а именно это работадатель и ищет. Не решения с ксорами, а креативность и гибкость мысли. Ну и прощупывается опыт и кругозор, что тоже крайне важно.
@@foundersl спасибо за коммент, абсолютно с вами согласен глупо полагать что раз дали задачу про xor значит и на практике ждут xor мне как то давали задачу о хрустальных шарах - значит я на практике хрустальные шары кидать буду)) много я встречал на собесе людей, у которых 7+ опыта и требуют огромную ЗП, а спросишь что такое О-большое, или как работает хэштаблица - ни сном ни духом Зато умеют по методичке фигачить круд сервис)
@@wolf_code вот от фигачащих по методичке круды такие собесы и призваны спасать. Они выбивают из привычной колеи и ты либо умеешь думать, либо иди куда-то дальше сингл-нодные бекенды для одностраничных лендингов писать. В этом есть только один очень жирнючий минус - не всегда сами собеседующие, к сожалению, правильно представляют себе как такие академические задачи надо предлагать и как их проверять, на что именно надо смотреть и т.п. Потому что все люди и умение верно собеседовать, особенно на высоком уровне - это вообще из разряда софт скиллов, которое очень по разному у всех развито и плохо сочитается с люто вкаченными хард скиллами в одном человеке. Иногда обидно что из-за этого некоторые кандидаты отсеиваются по false-negative результату. Но это есть везде, к сожалению. Правда достаточно редко)
@@foundersl прекрасно представляю какие могут быть нагрузки, т.к. специализируюсь на хайлоаде, а то что вы столкнулись в яндексе с чемто большим чем перекладывание джейсонов это несомненно удача.
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 так же не догадался :\
b = a.sorted For i in b: If index(i) mod 2 == 0: If b[index(i)+1] - b[index(i)] != 0: print(i) Break; Сложность O(n), считая сортировку, в памяти только массив. Не уверен в синтаксисе, уже 2 года работаю только с sql, но мысль думаю понятна)
Прикольно. Я бы сбросил массив в двумерный, во второе измерение проставил единички, свернул по первому измерению сложив значения второго, отсортировал по второму измерению, верхнее число - ответ. И не важно число это или строка, пофиг. :-) Как вам такой изврат ? :-)
@@wolf_code, по умолчанию под сложностью подразумевают сложность для ДМТ (детерминированная машина Тьюринга). Самый быстрый алгоритм реализации, известный мне, это дерево, с которым сложность 2го алгоритма n log n С хэш таблицами в худшем случае может получиться n^2 (на сколько понимаю). Худший случай и определяет сложность реализации. Если бы Вас просили написать алгоритм линейный в среднем (по вероятности), то решение корректно. Но тогда нужно было об этом было сказать в видео.
@@igortunev6163 как работает хэш таблица по вашему? Конкретно реализация ее в библиотеке java? Там никак невозможна деградация поиска и вставки до линейного времени
@@wolf_code, теоретическая модель допускает линейность. В java, видимо, модифицированная версия. Например, можно подобрать множество чисел, на котором хэш функция будет выдавать один и тот же адрес (на список). Тогда значения придётся класть в один список, сложность поиска в котором линейна от его длины (поиск необходим для сетов даже при вставке). Отсюда и линейность в худшем случае. Но можно вместо списка использовать, опять же, дерево или вложенный хэш и рассуждения повторяются. Те операции быстрее чем за log n, скорей всего не реализуете (мне такого не известно). Ну, или предложите тогда?
А вот так на 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 }
я новичок в пайтон, я когда смотрю такие видосы, пытаюсь сначала решить задачу сам. И вроде получается, но потом когда смотрю решение, понимаю что я чего-то не понимаю n = int(input()) s = [int(input()) for i in range(n)] for i in s: if s.count(i)
нука ткните меня как начинающего в чём проблема такого решения ? arr.forEach(num => { let temp = arr.filter((item) => item === num) if (temp.length === 1) { console.log(temp[0]); } });
@@АлексейМелентьев-ч3в типа того допустим при размере входного массива в 100к элементов ваше решение произведет ~100k^2 операций если предположить что современный процессор делает миллиард операций в секунду - то ваше решение грубо говоря отработает за 10 секунд - что довольно долго
До сих пор несколько переживаю записываться на собесы если не собираюсь менять работу. Этож несколько синьор+ соберутся, чтобы со мной поговорить, а я даже идти к ним не хочу?
Абсолютно согласен Я бы тогда наверное пошел к ним работать, но не прошел все 5 этапов + Тратить время людей не вижу смысла - поэтому сейчас ищу другие способы узнать про задачи с собеседований
Разве сначала не придётся обойти массив и преобразовать в биты каждое десятичное число? Конечно процессор оперирует битами, но люди оперируют типами данных на более высоком уровне, и десятичное число нужно же всё равно преобразовать в бинарный тип, или оператор xor в скала сразу можно применять к int и будет работать напрямую с битами?
@@wolf_code дело в том, что словарь пробегает не по всему в ходящему списку, он затрагивает только неповторяющиеся элементы в нем. Это все равно, что создать множество и пробежаться по множеству а не по входному списку, но искать элементы во входном списке + можно сделать бреак если элемент найден
*ред. язык: 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 Вы написали на питоне, ну ок может и хотели на нем ваше решение неэффективное - прошу прочесть закреп. коммент но все равно красавчик - огромный респект за упорство
У меня в голову в такой последовательности решения приходили... 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 не вопрос. Но под рукой у меня сейчас только 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(*) допишет, а я спать :) переварит как символы, так и инты
@@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()
@@wolf_code сел полистать питоновский мануал... мне пришел в голову еще один однострочник from functools import reduce src = reduce(lambda x,y: x^y, [1,2,3,7,3,2,1]) :)
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 В питонах скорее всего будет Exception. Каждый раз удивляюсь задачам на собеседованиях Яндекса. Дрочат тебя по памяти и сложности алгоритмов - а на работе ты будешь скадывать джейсоны в базу. И в чём смысл? 2 раза собесился, оба раза не проходил. Сейчас рекрутеры стучатся в третий. Зачем? Я за это время прокачался как бэкендер, но остался на университетских знаниях в алгоритмах
По названию ролика хотел возмутиться, мол палить задачи некрасиво. Но посмотрел, ровно эту задачу у меня спрашивали при устройстве в Яндекс в 2016)) она же в куче вариантов на всяких литкодах лежит... В общем, никаких претензий)
@@wolf_code тем удивительнее, что такой процент людей в комментах может написать решение в одну строку, но не думает об алгоритмической оптимальности вовсе
@@w01fer86 я, если честно не совсем девелопер, но иногда балуюсь. Хотелось бы вступится за решения "в одну строчку" ибо чем проще написано и чем больше, при возможности, в БД спихнули на выполнения- тем лучше. Старина Том Кайт врать не будет :) Ну и мое однострочечное решение- его критике буду рад. def foo(l, xor_sum= 0): for i in l: xor_sum ^=i return xor_sum
@@0yustas0 "В одну строчку" не тождественно "плохое". Я имел ввиду, что люди достаточно хорошо знают возможности языка (раз могут написать короткое решение), т.е. не совсем начинающие, но не думают об алгоритмической эффективности. Ваше решение алгоритмически оптимально (так что для хорошего результата на собеседовании подойдёт), но не пройдёт ревью в реальной жизни в соответствии с большинством стайлгайдов, т.к. (не беря в расчёт расположение пробелов): 1. в функцию добавлен ненужный параметр. Зачем кому-то вызывать foo(l, 25)? Кажется, незачем, но у каждого читающего функцию будет такой вопрос. Ну и добавляется шанс вместо функции fo, принимающей два параметра, случайно вызвать foo и долго дебажить возникшую проблему. Так что xor_sum=0 лучше вынести отдельной строкой. 2. Условие for и тело цикла должны быть на разных строчках даже если тело состоит из одной строки. Опять же это проще читать. Вот и получается, что ваш "однострочник" из двух строк будет более понятен, если записать его в 4 строки.
Наброшу. Зачем это современному разработчику? Ну реально. Зачем? Кроме как потешить своё ЧСВ (если смог решить) либо ЧСВ интервьюера (если не смог). 99.99% вероятности, что ни чем подобным на работе заниматься не придётся. На дворе 21 год 21 века. Вы в каких настоящих задачах собрались числа в массиве ковырять?
Просто интересная задачка, а вы сразу зачем - почему)) Реального кода и скучных задач достаточно на практике. Чисто мое мнение, если дать человеку на собесе задачу на проектирование сервиса - собес продлится от часа и более, мне смотреть как он гуглит и собирает реальный проект по методичке? Лучше дать задачку которую можно сразу попробовать решить, а походу можно понять насколько человек свободно владеет языком, насколько быстро придумывает и реализовывает идею и вообще умеет кодить или копипастер со стековерфлоу Дальше можно поспрашивать про опыт работы и уже какие то вопросы практического характера
@@wolf_code так это собес навечно растянется. Зачем нормальному разработчику такой гемор? На рынке нынче и без этого с руками отрывают. Ответ очевиден - только затем, чтобы работодатель по итогу предложил хорошие деньги. Учитывая, как яндекс любит занижать уровень зп относительно рынка, смысл подобных фокусов теряется
Встретил такую задачу на leetcode. По правде говоря думал сложность первого решения O(n) поскольку там два цикла не зависят друг от друга. Первый перебор а второй поиск arr[I] arr[I+1]. Решал на js. Создаём объект и смотрим есть ли у него элемент массива, если есть то удаляем (дубликаты будут удалены, если элемент в массиве встречается два раза) , а если один раз то записываем в объект.
@@alexandergrigorev4518 я гдето в комментах кому то отвечал на этот вопрос, вкратце есть такая структура данных как HAMT, ее еще называют идеальная хэш таблица, можно почитать статью про ее принцип работы если погуглить сразу найдется
@@wolf_code до того как вы ответили я стал думать а как сделать множество за о(1) и подумал что самое тупое это огромный массив со смещением на нужное число, потом вспомнил что его делают через хеш с пересчетом по мере наполнения и все равно это о(1) в итоге. Очень полезно я к вам зашёл на канал, спасибо 😁
Ребят перед написанием комментария прошу прочесть
Очень часто в комментариях пишут такой код:
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 тысяч шагов
Но ты же мог просто взять и записывать уникальное число в 1 ячейку памяти и просто пройти весь массив за N. Если число повторяется, то зануляй результат. Зачем изобретать велосипеды? Удаление из массива это тоже лишние операции, работа с масками конечно красиво, но абсолютно излишнее решение
@@deathklaa вот встретил ты какоето число записал в ячейку, затем еще одно, и что дальше - перезаписать число в ячейке?
@@wolf_code можно использовать множество - добавлять элемент в него и при повторении удалять. В итоге останется 1 элемент множества - это и будет ответ. Сложность - линейная. Это про первую задачу)
@@wolf_code все, вижу, вторая задача аналогична первой) И ты ее решил за О(N), так что норм)
@@LineageL2ad Это решение значительно быстрее, чем придуманное автором №1. Почему-то, автор считает, что функция .sorted чудесным образом не расходует ресурсы.
думал, что это собеседование в яндекс такси, а тут цифры какие-то да буквы не понятные....
Нат, это курьерам в Яндекс.Еда теперь такие тесты сделали, много претендентов на вакансии стало
@@MindSkyaRocket еще в я.такси слышал цифры не юзают и буквы тоже, там само собой на магии сервера работают
В доставку, очевидно, спрашивают задачу коммивояжёра
@@mikemerinoff скорее алгоритм дейкстры
@@mikemerinoff единственное, что помню с 1-го курса, ахах
Всё, можно не в мак, а в такси
Первое решение которое мне пришло в голову после прочтения условия (пишу на js):
1. Завел мапу isUnique
2. Пробегаясь по массиву чисел:
а) Если нет в мапе isUnique ключа с таким числом - добавляю его
б) Если есть в мапе isUnique ключ с таким числом - удаляю его
3. Единственный оставшийся ключ в мапе это и есть нужное нам число, возвращаю его в качестве результата.
(т.к. доступ по ключу это быстрая операция, то считаю алгоритм не особо жадным, на вопрос о том, как обойтись без дополнительных структур, тоже бы не ответил)
На собеседования я в те давние времена приходил так, что это я их выбирал, смогу ли я, хочу ли я работать с этими людьми. И при таком отношении даже если меня не брали, то это я их не выбирал. И моя самооценка всегда была N+1.
и не получал денег и сидел в жопе
Настоящие программисты получают деньги, не работая, а программы составляют для души
Первое решил как у тебя, а улучшил потом подумав над xor
а вот второе решение себе запомнил, спасибо
На питоне решение в одну строку кода:
arr = [какой-то массив]
print(2*sum(set(arr)) - sum(arr))
С помощью множества получаем уникальную коллекцию, то есть все элементы по одному разу. Ищем ее сумму с помощью функции sum и удваиваем. Получаем сумму всех элементов массива по 2 раза и вычтем из этого сумму исходного массива. Число найдено
кажется надо поделить на 2 в конце
хотя нет, все норм
И жрём память и время...
@@АлександрКуликов-ж8к никто и не говорил, что это оптимальное решение. Просто я был заинтересован в поиске как можно большего количества разных подходов к задаче, и изложил тот, который не был нигде представлен.
Канфетки жрем. Скок жрем то, какая сложность получается, подскажи? @@АлександрКуликов-ж8к
Я просто тупой сори. ВОт смари set и sum это O(n). Эт получается O(n)+O(n)?
0:12 УДОБНЫЙ способ ВЫЙТИ из зоны комфорта )) звучит забавно
Так и есть, достаточно сказать запишите на собес и в какой то день мне просто надо будет за компом не кску запустить, а zoom)
Только программирование начал учить, для меня тут происходит что-то гениальное и страшное, но интересное 0.0
Если только начал учить, то не забивай себе голову видосами про собесы в топовые компании. Это все красиво, но такие решения в боевых проектах я за 6 лет видел 2-3 раза и делались они исключительно из спортивного интереса
Согласен с Евгением, если цель в кратчайшие сроки научиться писать практический код то лучше сделать упор на изучение библиотек и инфраструктуры
По алгоритмам азы только - типа О-большое и др.
@@ЕвгенийСниховский-ь8ь такие задачки, это как математика - для общего развития)
не согласен с Евгением. Такие задачи важно решать самостоятельно. Как только увидел условие, ставь видео на паузу и попробуй написать код. Это не займёт много времени, а ты заодно научишься придумывать алгоритмы, что важно. И только того, как ты полностью понял суть задачи, можно смотреть продолжение и тебе расскажут как сделать лучше. И ты скорее всего даже поймёшь почему оно лучше. А может, не поймёшь. Но по крайней мере, решишь всё сам.
Первое, что пришло в голову: Я бы в хэш табле запоминала, какие цифры у нас встречались в качестве ключей, значением сохраняла бы 0 если единожды встретилось число, 1 если встретилось второй раз, и таким образом просто вернула бы ключ, у которого значение 0 :)
Но я конечно новичок в алгоритмах, так что это может и не самая лучшая мысля
Первая задача решается без изменения массива двумя циклами (
i = от 0 до
Прошу прочесть закрепленный коммент
и ознакомиться с понятием сложности алгоритма
Решается, только решение очень плохое по времени
Задача в пару действий.
1. делаешь из списка сет, считаешь полную сумму и умножаешь на два.
2. вычитаешь из полученного числа сумму первого списка.
Фактически это и есть XOR
допустим дано {1, 2, 2}
Вычисляем сумму = 5
Умножаем ее на 2: 5*2 = 10
Вычитаем сумму списка: 10 - 5 = 5
Ответ 5?
UPD
понял - ну да с сетом там все сходится
действий надо побольше:
1. Считаем сумму всех элементов массива, она равна 2S + x
2. Преобразуем массив в сет и считаем сумму, она равна S + x
3. Вычитаем из первого второе, получаем S
4. Умножаем S на 2 и вычитаем из первой суммы
Но это решение все равно требует O(n) памяти и ничем не лучше варианта с множеством
@@wolf_code
a = [1,1,2,2,3,3,4,4,5,5,7]
print( sum(set(a)) * 2 - sum(a) )
Фактически для любого серьёзного N (для которого имеет смысл реализовывать линейный алгоритм вместо квадратичного) сумма элементов списка не будет помещаться в числовую переменную.
низзя, умный какой)
через питонячьи инструменты любой дурак сделает, а ты попробуй на уровне простейшем это расписать.
не назвал бы это «красивым» решением
эта задачка придумана вокруг этого решения
любое минимальное изменение условий (например, множественные дубли чисел) и оно перестанет работать на практике
в общем классика жанра: головоломка ради головоломки
согласен
важно не столько решение, сколько процесс
Особенно больно, если наткнуться на такой код в проекте и без подсказки, что за функционал. Будет выглядеть как какая-то наитемнейшая магия.
Канал - супер! Спасибо за контент
Не бросай, продолжай снимать) У тебя хорошо получается, да и по скале мало хороших видео.
К элегантным надо стремиться, пока не начинает гореть дед лайн. ))
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
Создал словарь, пробежался бы циклом по массиву, на каждом новом элементе проверяю содержит ли словарь такое значение по индексу, если да то значение ключа становится на один больше, если нет то добавляем и значение делаем 1, в конце просто ищу в словаре по значению и отдаю этот ключ, Второе решение: преобразую массив в динамический массив, далее буду бежать по нему циклом, на каждом элементе удаляю и проверяю содержится ещё ли такой элемент, если да тоже удаляю если вдруг встретится когда не будет второго вхождения , присваиваем в переменную result и делаем break ,первые решения что пришло в голову и за алгоритмы не шарю, мимо жуниор самоучка
Теже идеи с циклом пришли в голову.
Но его минус в том, что если массив на много миллионов итераций, да ещё и часто вызывается - то можно нефигово так нагрузить железо. Но наверное в рамках интервью можно это упомянуть, но не учитывать в условие задачи.
@@alexein6631 xor вариант в случае 2 только первых вхождений, или к случае 3 вхождений не даст правильный вариант ответа( хотя решение только 1 варианта вхождения одного элемента и 2 других, очень красивое, но боюсь очень редкий кейз
@@OpalGooDog у меня на проекте redis фильтры таким образом в битмап записывает и вычисляет совпадения. Я только сейчас понял как он это делает у себя под капотом.
Вааауу, мега круто !
одна операция в set O(logN) => решение с сетом работает за O(NlogN)
А если сет на основе хэш таблиц?
прикольно. сразу подумал про xor, только первым пришло решение, аналогичное подходу с множеством, но вместо множества использовать битсет, где xor-ить i-й элемент. тогда после прохода по всем элементам массива только в одной позиции битсета останется 1 - его позиция - это ответ.
А зачем множество, если после сортировки можно идти по циклу с шагом 2, а в цикле проверять arr[i]==arr[i+1], только нужно учесть, что если i=n-1, то мы завершаем цикл.
@@АндрейВарин-р4г затем, чтобы не делать сортировку)))
В самом конце ролика вставляй пожалуйста чёрный экран чтобы на его фоне всплывали рекомендованные видео, а то в данном случае превьюшки других твоих роликов закрыли код (09:09)
Отличная идея!
Спасибо, что делитесь!
0:58 Сгруппировать по значению, и найти запись с количеством вхождений 1.
сложность какая у группировки по значениям?
Пройтись по массиву, в случае если число попалось впервые закинуть его в map с ключом значения а в значение тру, проверяется впервые или нет, тем что есть ли такое свойство в map, если же оно есть то удаляется свойство. Потом просто находит единственнле свойство map. Сложность O(1)
O(n)
2 решение не за линию. Поиск и добавление в множество не единица, а log(n)(во всяком случае в c++ и java), так что решение и не ускорилось и стало потреблять больше памяти
Советую почитать про HAMT и как реализованы хэштаблицы в scala (иммутабельные хэштаблицы)
да и в спецификации джава сказано что хэштаблицы работают за константу
docs.oracle.com/javase/7/docs/api/java/util/HashSet.html#add(E)
Вы какой либой пользуетесь?
да в плюсах написано что константное время en.cppreference.com/w/cpp/container/unordered_set
)
Я имел ввиду множества на самобалансирующихся деревьях типа tree set в java и обычный set в плюсах, но идея с hash map - и в правду верная
Тогда получается простейшая сортировка подсчётом, прикольно
Задача: нарисовать все возможные иконки 3 на 3 пикселя в 8 битном исполнении.
Хорошая тема для нового выпуска)) Запилю видос
а что значит в 8 битном исполнении?
@@wolf_code 8 бит = 1 байт = диапазон [0, 255] Т.е. результат в виде всех двумерных массивов 3 на 3 где каждая ячейка от 0 до 255. Сложность, время, потребление памяти )))
Это 9 ^256 ?
@@URobotics скорее наоборот
9 пикселей по 256 значений принимает каждый, получаем 256^9 = (2^8)^9 = 2^72
2^72 байта это 2^42 терабайта, столько памяти нет думаю нигде))
Хорошая задача. Я её даю своим студентам (самым сильным) - но пока ни один не додумался до решения за один проход (через "исключающее или").
есть решение через словарь за один проход (o(n)), добавлять значение из массива в словарь и после повторного нахождения удалять, затем вернуть единственный ключ из словаря, по сути один проход + 1 раз сходить в словарь
@@ТимофейГерасимов-ю4ь Так память же лишняя требуется, в идеале без нее. У автора в видео было множество, то же самое, что словарь почти по памяти
@@ilias3624 память через словарь меньше занимает. Так как удаляются по ходу решения
А я за 5 минут вышел в голове на это решение, пока на работу ехал)) приятно
Придумал решение за О(N) сначала, но оно требует O(N) памяти. Заводим массив b, где b[i] = количество вхождений числа i в исходный массив. Далее, нам надо по исходному массиву пройтись и для каждого x сделать b[x]++. Далее, проходимся в конце по массиву b и где количество =1 - это ответ.
А если в массиве будут большие числа, например 1000000000, придется создать массив длиной в миллиард элементов
@@Khashimova_wellness согласен - получается будет не линейное время а O(NM), где M максимальное значение в списке
Алгоритм отработает линейно при условии если значения в массиве будут маленькими
@@wolf_code Всмысле) Он всегда линейно работает, мы один проход делаем по массиву при подсчете, у нас цикл что то вроде
for(int i = 0; i < n; ++i)
b[a[i]]++;
И потом один проход по массиву посчитанному
for(int i = 0; i < n; ++i)
if(b[i] == 1)
//Мы нашли число
@@wolf_code То, что потребуется больше памяти, я согласен. И то, что алгоритм будет работать за O(m), где m- максимум в изначальном массиве тоже согласен, но никак не за O(nm). Это просто решение, которое пришло в голову сразу, через xor конечно элегантнее и лучше)
@@ilyabikmeev точно - тупанул))
мы же не внутри цикла ходим да будет тогда скорее так O(max(M, N))
Признаю - ошибся
Как вариант из массива создать хеш-карту, ключ - число, значение - количество вхождений и в итоге найти ключ, значение которого равно один. Плюсы, универсальность, если изменится условие и одинокий элемент будет не один, то меняется вариант вывода результата на массив. Если в видео было данное решение, то извините)
Прикольно! Получится сложность O(N), но потребуется O(N) памяти так же для хранения хэштаблицы
@@wolf_code в итоге как и у любого решения, свои плюсы и минусы. Кроме побитовых операций, там без минусов)
@@АндрейБочарников-х5ъ согласен
в реальной жизни именно так я бы и написал, т.к. условие сто процентов бы изменилось :)
@@ArthurMudrick реальные задачи согласен - лучше решать без ухищрений понятными способами
Проблема Яндекс собеседования, что им нужно их решение, а не то что можно рассуждать.
Интересно, зачем вообще так углубляться в скорость решения задачи, если питон вообще не про скорость?) во всяком случае лезть в бинарный код перебор по-моему) Вы и так решили здорово, главное хоть как-то решить, и желательно, не O(n^2).
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)
Вот так решил
Можно решить так: заводить переменную m = 1 и бежишь по массиву: если число m делится на элемент i, то мы его делим, а если нет - то перемножаем. В итоге m окажется нашим ответом
(я питонист, мне можно работать с нормальными православными интами)
допустим список такой (1, 3, 3)
1 не делится ни на одно число из списка, ответ равен 9?
@@wolf_code 1) 1 // 1
2) 1 * 3
3) 3 // 3 = 1
@@wolf_code Хотя нет, я нашёл ошибку. На случае 3 9 27 9 3 выведет 3
Первое решение работает за О(n), если бы сортировка вызывалась в цикле, то было бы n * log(n). Разве не так?
В первом решении сначала отрабатывает сортировка за 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)
@@wolf_code точно, спасибо, почему-то перепутал сложность сортировки
Дай угадаю концовку: после 100 разных решений ты пришёл к решению со сложностью O(1), и спустя ещё 40 этапов собеседования они прислали оффер на 50 тысяч рублей? Очень в стиле яндекса
Хехе
Я конечно не программист, но на Python решается просто через множества (class 'set')
Решение: искомое число = 2 * sum(set(s)) - sum(s)
где:
s - начальное множество
2 * sum(set(s)) - удвоенное сумма эл-в без повтора
sum(s) - сумма элементов изначально
Как думаете - где ошибка в Вашем решении?
@@wolf_code Буду благодарен если поделитесь. Понимаю, что такой вариант не сработает, если элементы множества это не числа.
@@АлексейЛукьянов-ф2ц хотя нет, вроде все норм, я ошибался
@@АлексейЛукьянов-ф2ц Ваше решение не сработает если в массиве большие числа, сумма вылезет за int
@@wolf_code Спасибо
Привет, я еще совсем новичек в программировании, но считался бы этот черезчур простой код ответом на эту задачу?
from collections import Counter
a = [9,1,2,7,5,1,7,9,2]
b = [key for key,value in Counter(a).items() if value == 1]
print(*b)
Сложить все уникальные элементы умножить на 2 и отнять сумму всех чисел
Решение с XOR крутое, так сразу в голову не придёт.
на 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
Получается так: если индекс начального и конечного элемента равны, то вернуть этот элемент
Решение будет работать - но советую почитать в закрепленном комменте почему такой подход неэффективен
В Вашем решении вы заменили count на indexOf, но сложность будет такой же O(N^2)
@@wolf_code да, я это понимаю) Просто решил эту задачу на js написать, просто в комментариях не заметил, чтобы ее на js реализовывали
@@wolf_code Ну это как посмотреть :) На JS большинство задач именно так и решается т.к. если на каждый подобный пример разработчик будет тратить ресурсы на поиск решения, то во первых в 9 из 10 случаев это никак не скажется на объёктивных метриках перформанса web app, во вторых потратит гораздо больше времени на имплементацию, а в третьих код станет сложнее с точки зрения понимания и поддержки для других разработчиков. Итого, с точки зрения бизнеса и конечного результата такие примеры сильно далеки от реальной жизни. Тут я не умоляю важность умения решать алгоритмические задачи, но умоляю их ценность при проведении собеседований, которая переоценена.
@@danielrossy7453 тут и не поднимается вопрос о практической ценности задачи
а о том что нужно ли по алгоритмам гонять на собесах уже исписано много пабликов - давайте тут не разводить
О, а я догадался до xor-a. Где тут контракты подписывают? 😊
А reduce на пустом массиве разве не свалится с ошибкой? Может лучше fold использовать, с начальным нулем
Очень тонко подмечено, все ждал когда же это ктото заметит))) Отлично - так держать!
Да решение свалится, но у нас по условию каждое число встречается ровно 2 раза и только одно 1 раз, получается числа все таки встречаются
Это даже хорошо что reduce свалится с ошибкой, ведь мы не знаем какой ответ мы должны вернуть для пустого списка. 0 в таком случае это неверный ответ - ведь это будет означать что в пустом массиве ответ равен 0 - что конечно неверно, там 0 не встречается 1 раз
Тут лучше вернуть None
@@wolf_code какой странный редьюс в скале. ведь эта функция априори должна аккумулировать значения, а значит иметь что-то в качестве начального значения
@@torburgmax для этого там служит другая функция: foldLeft
Писал бы на си или на плюсах, решение с ксором пришло бы в голову первым 😉
В чём смысл сортировать массив, если можно решить без сортировки?
Сортировка работает за N * log N, после этого придётся сделать полный проход за N.
Зачем, когда можно создать хэш-мап и записывать туда все найденные числа. Но перед записью сделать проверку, если оно там есть, то удалить его от туда. В итоге останется только одно число, которое будет являться ответом. При этом сложность алгоритма будет N ещё и за 1 проход
P.S. А, ну это второй вариант, ок
3:25 Ты пробегаешь по каждому элементу отсортированного массива, при том, что они идут парами?! Выглядит не очень
Решение с xor и правда очень красивое
А второе решение смотрели дальше?
решение на го:
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 не дубль число в массиве, то мы его вернем, так как оно единственное будет лежать в мапе (словаре)
Лучший!
Мне сразу пришло в голову решение
def get_n(lst):
return min(lst, key=lambda x: lst.count(x))
сразу пришло решение которое работает очень медленно)
какое обидное поражение КПХФ от НИП…😢😭 Молодые из Флэймс заслуживали эту победу больше Ниндзей (((
чеееел) тыыы)))) аукзахухкахукхаукха я смотрел вчера этот матч бляяя,... ты как тут оказался
@@smokehappiest9005 аххахахахаха
наугад тыкнул, шоб с эмоциями поделиться🤣🤣
@@akiragosu наугад на видео про собес в яндекс?))))
@@smokehappiest9005 да чет приуныл чутка, че было первое нажал😁😏
Ничего подобного: в яндексе просьба о помощи насцениваеться как подсказка и идёт в минус
Чел, у тебя круто получается
импортируем Counter и через List comprehension выбираем ключ, где значение = 2
как это будет в коде?
@@wolf_code
dict_ = Counter(arr)
number = [k for k in dict_ if dict_[k] ==2 ]
@@jjj78ean как быстро строится Counter?
Решение конечно вообще неожиданное
Вот мое решение с рекурсией на 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. за отступы прошу прощения, с мобильника писал
Это ужасно разрушать исходное состояние переданного объекта. Не надо так.
Ловкий трюк
Блин серьезно? 21 век, сервера поддерживают до нескольких терабайт оперативы, зилион-ядерные процессоры, датацентры размером с дом, приложения того же яндекса которые показывают 2 формочки весит 200мб. А в итоге ксорим сраный числовой массив чтобы сэкономить 2 байта памяти... Бред да и только. Я конечно понимаю что это задача далека от реальности и в реальность(особенно в яндексе) никто этим бредом заниматься не будет, но каждый раз когда я вижу такие задания на собесах - просто жопа горит....
Добро пожаловать в клуб
А вот и не правда. Я проработал в этой компании достаточно долго и могу с уверенностью сказать - все эти терабайты оперативы и зилион-ядерные процы в множествах датацентрах размером с дом кончаются не начавшись, если везде писать квадратичный по сложности код, а кода ну очень много. Вы не представляете какие порой бывают нагрузки. На всяких конференциях с участием спикеров из подобных компаний можно подчерпнуть для себя множество примеров подобных задач, где нужно ну очень аккуратно писать с точки зрения оптимальности.
При этом клиентские приложения в 200мб вообще нельзя сравнивать с тем, что крутится на серверах - это просто разные миры.
Но согласен, у меня у самого иногда горит от излишней академичности задач и не все они к реальности имеют отношение, но они позволяют понять способности к размышлению и гибкость в рассуждениях, а именно это работадатель и ищет. Не решения с ксорами, а креативность и гибкость мысли. Ну и прощупывается опыт и кругозор, что тоже крайне важно.
@@foundersl спасибо за коммент, абсолютно с вами согласен
глупо полагать что раз дали задачу про xor значит и на практике ждут xor
мне как то давали задачу о хрустальных шарах - значит я на практике хрустальные шары кидать буду))
много я встречал на собесе людей, у которых 7+ опыта и требуют огромную ЗП, а спросишь что такое О-большое, или как работает хэштаблица - ни сном ни духом
Зато умеют по методичке фигачить круд сервис)
@@wolf_code вот от фигачащих по методичке круды такие собесы и призваны спасать. Они выбивают из привычной колеи и ты либо умеешь думать, либо иди куда-то дальше сингл-нодные бекенды для одностраничных лендингов писать. В этом есть только один очень жирнючий минус - не всегда сами собеседующие, к сожалению, правильно представляют себе как такие академические задачи надо предлагать и как их проверять, на что именно надо смотреть и т.п. Потому что все люди и умение верно собеседовать, особенно на высоком уровне - это вообще из разряда софт скиллов, которое очень по разному у всех развито и плохо сочитается с люто вкаченными хард скиллами в одном человеке. Иногда обидно что из-за этого некоторые кандидаты отсеиваются по false-negative результату. Но это есть везде, к сожалению. Правда достаточно редко)
@@foundersl прекрасно представляю какие могут быть нагрузки, т.к. специализируюсь на хайлоаде, а то что вы столкнулись в яндексе с чемто большим чем перекладывание джейсонов это несомненно удача.
как же вы тихо говорите )
очень классно, но никому не нужно, театр абсурда
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 так же не догадался :\
Решение с XOR - просто читерство какое-то
есть такое
b = a.sorted
For i in b:
If index(i) mod 2 == 0:
If b[index(i)+1] - b[index(i)] != 0:
print(i)
Break;
Сложность O(n), считая сортировку, в памяти только массив.
Не уверен в синтаксисе, уже 2 года работаю только с sql, но мысль думаю понятна)
с чего вдруг сортировка за линейное время?
@@wolf_code Согласен, в pyton сортировка n*logn, не линейная, но тоже неплохо.
Выход за предел масива справа в коде.
Прикольно. Я бы сбросил массив в двумерный, во второе измерение проставил единички, свернул по первому измерению сложив значения второго, отсортировал по второму измерению, верхнее число - ответ. И не важно число это или строка, пофиг. :-) Как вам такой изврат ? :-)
Не совсем понятно что значит "сбросил массив в двумерный" - это значит разложить значения в массиве по оси x? а проставите единички по оси y?
Я на PHP таким образом сделал)
$holder = ['9', 'hey', '1', '2', 'hello', '7', '5', 'hey', '1', '7', 'hi', '9', '2', 'hello', 'oops'];
$res = array_keys(array_filter(array_count_values($holder), function($k) {
return $k == 1;
}));
array(1) { ["time"]=> float(1.0013580322266E-5) } array(1) { ["unic "]=> array(3) { [0]=> int(5) [1]=> string(2) "hi" [2]=> string(4) "oops" } }
0,00001001358
Дальше развил задание и искал из 20.000.000 данных 1000 уникальных значений, результат был 0.00028
Спасибо!) было интересно)
Random access по листу не константа, у первого решения выше сложность.
Предлагаю посмотреть видео про быструю сортировку списка на моем канале, там не используется доступ по индексу
@@wolf_code 3:06 Я про доступ к уже отсортированному листу b, строчки 5 и 6
@@avpmk тут да согласен, надо было конвертнуть в vector
Решение 2 не совсем линейно. Даже в лучшем случае, если реализация сет через хэш таблицы, то линейность только по вероятности.
Если не линейное, то какое?
@@wolf_code, по умолчанию под сложностью подразумевают сложность для ДМТ (детерминированная машина Тьюринга). Самый быстрый алгоритм реализации, известный мне, это дерево, с которым сложность 2го алгоритма n log n С хэш таблицами в худшем случае может получиться n^2 (на сколько понимаю). Худший случай и определяет сложность реализации.
Если бы Вас просили написать алгоритм линейный в среднем (по вероятности), то решение корректно. Но тогда нужно было об этом было сказать в видео.
@@wolf_code, хотя и хэш таблицу можно модифицировать до log n (в худшем случае) при вставке/удалении/проверке.
@@igortunev6163 как работает хэш таблица по вашему? Конкретно реализация ее в библиотеке java? Там никак невозможна деградация поиска и вставки до линейного времени
@@wolf_code, теоретическая модель допускает линейность. В java, видимо, модифицированная версия.
Например, можно подобрать множество чисел, на котором хэш функция будет выдавать один и тот же адрес (на список). Тогда значения придётся класть в один список, сложность поиска в котором линейна от его длины (поиск необходим для сетов даже при вставке). Отсюда и линейность в худшем случае.
Но можно вместо списка использовать, опять же, дерево или вложенный хэш и рассуждения повторяются.
Те операции быстрее чем за log n, скорей всего не реализуете (мне такого не известно). Ну, или предложите тогда?
Так set же работает за log n, поэтому сложность остаётся такая же, как на сортировке, разве нет?
Как устроен сет в скала?
А вот так на 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
}
Советую читать закрепы
С xor ящетаю, гениально!
тоже так подумал когда узнал про это решение)
я новичок в пайтон, я когда смотрю такие видосы, пытаюсь сначала решить задачу сам. И вроде получается, но потом когда смотрю решение, понимаю что я чего-то не понимаю
n = int(input())
s = [int(input()) for i in range(n)]
for i in s:
if s.count(i)
Извините за глупый вопрос, но что такое val в вашем коде?) Для чего вы пишите перед переменной val?
нука ткните меня как начинающего в чём проблема такого решения ?
arr.forEach(num => {
let temp = arr.filter((item) => item === num)
if (temp.length === 1) {
console.log(temp[0]);
}
});
какова зависимость количества операций от размера входного списка в Вашем решении?
@@wolf_code а, вы хочите сказать, что если входной массив будет гигантским, то решения мы не дождёмсе? может может вы и правы)
@@АлексейМелентьев-ч3в типа того
допустим при размере входного массива в 100к элементов ваше решение произведет ~100k^2 операций
если предположить что современный процессор делает миллиард операций в секунду - то ваше решение грубо говоря отработает за 10 секунд - что довольно долго
9:05 надо посмотреть, как такую задачу можно решить на питоне/java и пр
До сих пор несколько переживаю записываться на собесы если не собираюсь менять работу. Этож несколько синьор+ соберутся, чтобы со мной поговорить, а я даже идти к ним не хочу?
Абсолютно согласен
Я бы тогда наверное пошел к ним работать, но не прошел все 5 этапов
+ Тратить время людей не вижу смысла - поэтому сейчас ищу другие способы узнать про задачи с собеседований
@@wolf_code leetcode?
@@Anton-ki7ch ага, в новом видео про литкод
Вот на 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 как неожиданно и приятно)
а разве set работает не за логарифмическое время? Для целых чисел можно написать сортировку за линейное время. Или использовать множество с хэшем.
set это множество с хэшем в скала как я помню, под капотом это плоские хэш таблицы
А отказоустойчивость не предусматривается? Вдруг в массиве будет два уникальных числа?
Тогда они не уникальны
Разве сначала не придётся обойти массив и преобразовать в биты каждое десятичное число? Конечно процессор оперирует битами, но люди оперируют типами данных на более высоком уровне, и десятичное число нужно же всё равно преобразовать в бинарный тип, или оператор xor в скала сразу можно применять к int и будет работать напрямую с битами?
Сразу с битами
Попробуй сделать звук еще тише
Соседи просили не шуметь))
Но так конечно в будущем исправлю этот косяк - в последнем видео про 8 ферзей звук вроде получше
В 1 строку:
def find_single(input_list: list):
return {input_list.count(n): n for n in input_list}[1]
Прочитай закреп коммент
@@wolf_code дело в том, что словарь пробегает не по всему в ходящему списку, он затрагивает только неповторяющиеся элементы в нем. Это все равно, что создать множество и пробежаться по множеству а не по входному списку, но искать элементы во входном списке + можно сделать бреак если элемент найден
@@wolf_code здесь будет где-то O(n * sqrt(n))
@@msmesh5666 понял
@@msmesh5666 если убрать дубли получится не sqrt(n), а n/2
*ред. язык: 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))
P.S. только только повторил/прошёл основы синтаксиса))
@@MrNarutorengun Вы написали на питоне, ну ок может и хотели на нем
ваше решение неэффективное - прошу прочесть закреп. коммент
но все равно красавчик - огромный респект за упорство
ответ реально крутой, мне теперь страшно представить насколько более громоздко моё решение))
Как же это все сложно
если разобраться - то станет намного проще)
Это еще легкая задача. Сложные задачи на деревья с рекурсивным обходом и на динамическое программирование.
а что при использовании XOR разве не потребляется столько же памяти, как размер самого массива или этот массив на Луне находится?
мы ведь не целиком массив xorим
Привет, интересен результат собеседования, взяли (бы) они тебя на работу, или нет? И на какую позицию проходил собеседование?
Не взяли, 3й этап завалил
Мидл бэкенд
У меня в голову в такой последовательности решения приходили...
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 пишу:)
а на SQL решение оч интересно глянуть
@@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(*) допишет, а я спать :)
переварит как символы, так и инты
@@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()
@@wolf_code сел полистать питоновский мануал... мне пришел в голову еще один однострочник
from functools import reduce
src = reduce(lambda x,y: x^y, [1,2,3,7,3,2,1])
:)
@@0yustas0 очень похоже на 3е решение в видео
можно у вас спросить, вы имеете высшее образование ну или любое и желательно ли это для рынка труда?
У меня есть диплом бакалавра по направлению ПОВТиАС
Диплом у меня нигде не спрашивали
Да это же легчайшая задача, зачем 8 минут ролик? Просто прошлись по списку и написали условие если кол-во элемента == 1, выведите его. Всё😂
🤣🤣🤣 - тоже ржу - вот яндексы дебилы, да?
Есть просьба - глянь мельком на закрепленный коммент
Слишком громко говоришь! По тише в следующий раз.
Мелкий спал когда записывал
for i in lst:
x = lst[0]
for r in lst[1:]:
if r == x:
lst.remove(r)
lst.remove(x)
print(lst[0])
Решил вот так. Все работает. Верно ли это? Быстро или долго?
Можете подсказать?
Верно - но долго - советую прочитать закрепленный комментарий
Я на кодварс видела такую задачу
А ведь через XOR даже для стороки работает...
s = "a@NddNss?@a"
def foo(x):
sm = 0
for i in x: sm^=ord(i)
return chr(sm)
print(foo(s))
Ага строка это по сути ведь массив байтов
За сколько времени самообучения ты вышел на такой уровень знаний?
Не скажу что уровень высокий, программированием занимаюсь лет 5
Просьба - пишите название языка на который вы собеседовались.
Спасибо за коммент
В будущем учту, скорее просто добавлю в описании канал. Я специализируюсь только на языке скала
А у яндекса нет привязки к языку в собесах, можно даже на псевдокоде, по крайней было так на моих собесах
Так какой язык-то?
Подскажите, пожалуйста, любопытно
@@Влад-г2п2э scala
@@wolf_code благодарю
def find_unique_number(arr: List[int]) -> int:
return sum(set(arr)) * 2 - sum(arr)
А если сумма не поместится в int?
Твое решение выдаст неверный ответ
@@wolf_code В питонах скорее всего будет Exception.
Каждый раз удивляюсь задачам на собеседованиях Яндекса. Дрочат тебя по памяти и сложности алгоритмов - а на работе ты будешь скадывать джейсоны в базу. И в чём смысл?
2 раза собесился, оба раза не проходил. Сейчас рекрутеры стучатся в третий. Зачем? Я за это время прокачался как бэкендер, но остался на университетских знаниях в алгоритмах
@@ErhoSen запустите свое решение - оно неверно работает))
По названию ролика хотел возмутиться, мол палить задачи некрасиво. Но посмотрел, ровно эту задачу у меня спрашивали при устройстве в Яндекс в 2016)) она же в куче вариантов на всяких литкодах лежит... В общем, никаких претензий)
Да - кмк эта задача уже давно стала некой классикой в программировании, как допустим быстрая сортировка или поиск в ширину
@@wolf_code тем удивительнее, что такой процент людей в комментах может написать решение в одну строку, но не думает об алгоритмической оптимальности вовсе
@@w01fer86 я, если честно не совсем девелопер, но иногда балуюсь. Хотелось бы вступится за решения "в одну строчку" ибо чем проще написано и чем больше, при возможности, в БД спихнули на выполнения- тем лучше. Старина Том Кайт врать не будет :)
Ну и мое однострочечное решение- его критике буду рад.
def foo(l, xor_sum= 0):
for i in l: xor_sum ^=i
return xor_sum
@@0yustas0 "В одну строчку" не тождественно "плохое". Я имел ввиду, что люди достаточно хорошо знают возможности языка (раз могут написать короткое решение), т.е. не совсем начинающие, но не думают об алгоритмической эффективности.
Ваше решение алгоритмически оптимально (так что для хорошего результата на собеседовании подойдёт), но не пройдёт ревью в реальной жизни в соответствии с большинством стайлгайдов, т.к. (не беря в расчёт расположение пробелов):
1. в функцию добавлен ненужный параметр. Зачем кому-то вызывать foo(l, 25)? Кажется, незачем, но у каждого читающего функцию будет такой вопрос. Ну и добавляется шанс вместо функции fo, принимающей два параметра, случайно вызвать foo и долго дебажить возникшую проблему. Так что xor_sum=0 лучше вынести отдельной строкой.
2. Условие for и тело цикла должны быть на разных строчках даже если тело состоит из одной строки. Опять же это проще читать.
Вот и получается, что ваш "однострочник" из двух строк будет более понятен, если записать его в 4 строки.
Наброшу. Зачем это современному разработчику? Ну реально. Зачем? Кроме как потешить своё ЧСВ (если смог решить) либо ЧСВ интервьюера (если не смог). 99.99% вероятности, что ни чем подобным на работе заниматься не придётся.
На дворе 21 год 21 века. Вы в каких настоящих задачах собрались числа в массиве ковырять?
Просто интересная задачка, а вы сразу зачем - почему)) Реального кода и скучных задач достаточно на практике.
Чисто мое мнение, если дать человеку на собесе задачу на проектирование сервиса - собес продлится от часа и более, мне смотреть как он гуглит и собирает реальный проект по методичке?
Лучше дать задачку которую можно сразу попробовать решить, а походу можно понять насколько человек свободно владеет языком, насколько быстро придумывает и реализовывает идею и вообще умеет кодить или копипастер со стековерфлоу
Дальше можно поспрашивать про опыт работы и уже какие то вопросы практического характера
@@wolf_code так это собес навечно растянется. Зачем нормальному разработчику такой гемор? На рынке нынче и без этого с руками отрывают. Ответ очевиден - только затем, чтобы работодатель по итогу предложил хорошие деньги. Учитывая, как яндекс любит занижать уровень зп относительно рынка, смысл подобных фокусов теряется
@@dreamUserMe согласен тут индивидуально, конечно если будет человек с большим опытом нет смысла по такии темам гонять, а если человек без опыта?
Встретил такую задачу на leetcode. По правде говоря думал сложность первого решения O(n) поскольку там два цикла не зависят друг от друга. Первый перебор а второй поиск arr[I] arr[I+1]. Решал на js. Создаём объект и смотрим есть ли у него элемент массива, если есть то удаляем (дубликаты будут удалены, если элемент в массиве встречается два раза) , а если один раз то записываем в объект.
Вы наверное имели ввиду первый цикл - сортировка а не перебор
@@wolf_code да)
@@RICO-sr2fn сортировка то работает за O(n log n) поэтому получается O(n log n) + O(n) = O(n log n)
Что за должность? Что за язык программирования?
Я шел на backend разработчика, язык scala
Привет. Мы перевели всё числа в двоичную систему а как найти лишнее не совсем понял. Спасибо.
Привет
Знаешь как работает xor? "ислючающее или" на русском
@@wolf_code Да, все дошло до меня)))) с работы посмотрел не отдохнувшим :D
А какое решение будет, если надо отыскать все уникальные числа?
Всм? Уникальное число одно по условию
Неплохо - но надо поработать над дикцией
Продолжай пилить
Согласен - лучшая речь в видосе на 0:19))
Почему второе решение считается что за линейное время? Тут не учитывается что под капотом у реализации множества?
А как под капотом реализован Set в Scala?
@@wolf_code конкретно в скала не знаю но вот сейчас подумал что наверняка за о(1) 😁
@@alexandergrigorev4518 я гдето в комментах кому то отвечал на этот вопрос, вкратце есть такая структура данных как HAMT, ее еще называют идеальная хэш таблица, можно почитать статью про ее принцип работы
если погуглить сразу найдется
@@wolf_code о, спасибо!
@@wolf_code до того как вы ответили я стал думать а как сделать множество за о(1) и подумал что самое тупое это огромный массив со смещением на нужное число, потом вспомнил что его делают через хеш с пересчетом по мере наполнения и все равно это о(1) в итоге. Очень полезно я к вам зашёл на канал, спасибо 😁
А в какой программе ты ходишь?
www.jetbrains.com/idea/ + scalaplugin
@@wolf_code он как я понял платный посоветуй редактор кода на Линукс ?
@@crypt2040 community версия бесплатная, я ей пользуюсь
можно еще попробовать vs-code, neo-vim