Ребят перед написанием комментария прошу прочесть Очень часто в комментариях пишут такой код: 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 тысяч шагов
@deathklaa3 жыл бұрын
Но ты же мог просто взять и записывать уникальное число в 1 ячейку памяти и просто пройти весь массив за N. Если число повторяется, то зануляй результат. Зачем изобретать велосипеды? Удаление из массива это тоже лишние операции, работа с масками конечно красиво, но абсолютно излишнее решение
@wolf_code3 жыл бұрын
@@deathklaa вот встретил ты какоето число записал в ячейку, затем еще одно, и что дальше - перезаписать число в ячейке?
@LineageL2ad3 жыл бұрын
@@wolf_code можно использовать множество - добавлять элемент в него и при повторении удалять. В итоге останется 1 элемент множества - это и будет ответ. Сложность - линейная. Это про первую задачу)
@LineageL2ad3 жыл бұрын
@@wolf_code все, вижу, вторая задача аналогична первой) И ты ее решил за О(N), так что норм)
@УсамаСамо3 жыл бұрын
@@LineageL2ad Это решение значительно быстрее, чем придуманное автором №1. Почему-то, автор считает, что функция .sorted чудесным образом не расходует ресурсы.
@SimplewerCh3 жыл бұрын
думал, что это собеседование в яндекс такси, а тут цифры какие-то да буквы не понятные....
@MindSkyaRocket3 жыл бұрын
Нат, это курьерам в Яндекс.Еда теперь такие тесты сделали, много претендентов на вакансии стало
@wolf_code3 жыл бұрын
@@MindSkyaRocket еще в я.такси слышал цифры не юзают и буквы тоже, там само собой на магии сервера работают
@mikemerinoff3 жыл бұрын
В доставку, очевидно, спрашивают задачу коммивояжёра
@wolf_code3 жыл бұрын
@@mikemerinoff скорее алгоритм дейкстры
@chloe_koshkina3 жыл бұрын
@@mikemerinoff единственное, что помню с 1-го курса, ахах Всё, можно не в мак, а в такси
@DmitriiRepnikov2 жыл бұрын
Первое решение которое мне пришло в голову после прочтения условия (пишу на js): 1. Завел мапу isUnique 2. Пробегаясь по массиву чисел: а) Если нет в мапе isUnique ключа с таким числом - добавляю его б) Если есть в мапе isUnique ключ с таким числом - удаляю его 3. Единственный оставшийся ключ в мапе это и есть нужное нам число, возвращаю его в качестве результата. (т.к. доступ по ключу это быстрая операция, то считаю алгоритм не особо жадным, на вопрос о том, как обойтись без дополнительных структур, тоже бы не ответил)
@СергейПавленко-х5я Жыл бұрын
На питоне решение в одну строку кода: arr = [какой-то массив] print(2*sum(set(arr)) - sum(arr)) С помощью множества получаем уникальную коллекцию, то есть все элементы по одному разу. Ищем ее сумму с помощью функции sum и удваиваем. Получаем сумму всех элементов массива по 2 раза и вычтем из этого сумму исходного массива. Число найдено
@wolf_code Жыл бұрын
кажется надо поделить на 2 в конце хотя нет, все норм
@АлександрКуликов-ж8к Жыл бұрын
И жрём память и время...
@СергейПавленко-х5я Жыл бұрын
@@АлександрКуликов-ж8к никто и не говорил, что это оптимальное решение. Просто я был заинтересован в поиске как можно большего количества разных подходов к задаче, и изложил тот, который не был нигде представлен.
@rvnclaw9914 Жыл бұрын
Канфетки жрем. Скок жрем то, какая сложность получается, подскажи? @@АлександрКуликов-ж8к
@rvnclaw9914 Жыл бұрын
Я просто тупой сори. ВОт смари set и sum это O(n). Эт получается O(n)+O(n)?
@danilgorlov88033 жыл бұрын
На собеседования я в те давние времена приходил так, что это я их выбирал, смогу ли я, хочу ли я работать с этими людьми. И при таком отношении даже если меня не брали, то это я их не выбирал. И моя самооценка всегда была N+1.
@dieff_automation2 жыл бұрын
и не получал денег и сидел в жопе
@andrewmurruvyov4359 Жыл бұрын
Настоящие программисты получают деньги, не работая, а программы составляют для души
@kirillfox59583 жыл бұрын
Первое решил как у тебя, а улучшил потом подумав над xor а вот второе решение себе запомнил, спасибо
@madkir82069 ай бұрын
Первое, что пришло в голову: Я бы в хэш табле запоминала, какие цифры у нас встречались в качестве ключей, значением сохраняла бы 0 если единожды встретилось число, 1 если встретилось второй раз, и таким образом просто вернула бы ключ, у которого значение 0 :) Но я конечно новичок в алгоритмах, так что это может и не самая лучшая мысля
@vnztvnzt3 жыл бұрын
Только программирование начал учить, для меня тут происходит что-то гениальное и страшное, но интересное 0.0
@ЕвгенийСниховский-ь8ь3 жыл бұрын
Если только начал учить, то не забивай себе голову видосами про собесы в топовые компании. Это все красиво, но такие решения в боевых проектах я за 6 лет видел 2-3 раза и делались они исключительно из спортивного интереса
@wolf_code3 жыл бұрын
Согласен с Евгением, если цель в кратчайшие сроки научиться писать практический код то лучше сделать упор на изучение библиотек и инфраструктуры По алгоритмам азы только - типа О-большое и др.
@holovkevych3 жыл бұрын
@@ЕвгенийСниховский-ь8ь такие задачки, это как математика - для общего развития)
@Disorrder3 жыл бұрын
не согласен с Евгением. Такие задачи важно решать самостоятельно. Как только увидел условие, ставь видео на паузу и попробуй написать код. Это не займёт много времени, а ты заодно научишься придумывать алгоритмы, что важно. И только того, как ты полностью понял суть задачи, можно смотреть продолжение и тебе расскажут как сделать лучше. И ты скорее всего даже поймёшь почему оно лучше. А может, не поймёшь. Но по крайней мере, решишь всё сам.
@Сергей-т9д7в3 жыл бұрын
Первая задача решается без изменения массива двумя циклами ( i = от 0 до
@wolf_code3 жыл бұрын
Прошу прочесть закрепленный коммент и ознакомиться с понятием сложности алгоритма
@ilias3624 Жыл бұрын
Решается, только решение очень плохое по времени
@alexjuly70973 жыл бұрын
0:12 УДОБНЫЙ способ ВЫЙТИ из зоны комфорта )) звучит забавно
@wolf_code3 жыл бұрын
Так и есть, достаточно сказать запишите на собес и в какой то день мне просто надо будет за компом не кску запустить, а zoom)
@zhenshuang3 жыл бұрын
Задача в пару действий. 1. делаешь из списка сет, считаешь полную сумму и умножаешь на два. 2. вычитаешь из полученного числа сумму первого списка. Фактически это и есть XOR
@wolf_code3 жыл бұрын
допустим дано {1, 2, 2} Вычисляем сумму = 5 Умножаем ее на 2: 5*2 = 10 Вычитаем сумму списка: 10 - 5 = 5 Ответ 5? UPD понял - ну да с сетом там все сходится
@alexanderfedintsev95703 жыл бұрын
действий надо побольше: 1. Считаем сумму всех элементов массива, она равна 2S + x 2. Преобразуем массив в сет и считаем сумму, она равна S + x 3. Вычитаем из первого второе, получаем S 4. Умножаем S на 2 и вычитаем из первой суммы Но это решение все равно требует O(n) памяти и ничем не лучше варианта с множеством
Фактически для любого серьёзного N (для которого имеет смысл реализовывать линейный алгоритм вместо квадратичного) сумма элементов списка не будет помещаться в числовую переменную.
@Antonigin1995 Жыл бұрын
низзя, умный какой) через питонячьи инструменты любой дурак сделает, а ты попробуй на уровне простейшем это расписать.
@alekseyl3 жыл бұрын
не назвал бы это «красивым» решением эта задачка придумана вокруг этого решения любое минимальное изменение условий (например, множественные дубли чисел) и оно перестанет работать на практике в общем классика жанра: головоломка ради головоломки
@wolf_code3 жыл бұрын
согласен
@Disorrder3 жыл бұрын
важно не столько решение, сколько процесс
@ThemrGhost19053 жыл бұрын
Особенно больно, если наткнуться на такой код в проекте и без подсказки, что за функционал. Будет выглядеть как какая-то наитемнейшая магия.
@legac1x9553 ай бұрын
Привет, я еще совсем новичек в программировании, но считался бы этот черезчур простой код ответом на эту задачу? 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)
@OpalGooDog3 жыл бұрын
Создал словарь, пробежался бы циклом по массиву, на каждом новом элементе проверяю содержит ли словарь такое значение по индексу, если да то значение ключа становится на один больше, если нет то добавляем и значение делаем 1, в конце просто ищу в словаре по значению и отдаю этот ключ, Второе решение: преобразую массив в динамический массив, далее буду бежать по нему циклом, на каждом элементе удаляю и проверяю содержится ещё ли такой элемент, если да тоже удаляю если вдруг встретится когда не будет второго вхождения , присваиваем в переменную result и делаем break ,первые решения что пришло в голову и за алгоритмы не шарю, мимо жуниор самоучка
@alexein66313 жыл бұрын
Теже идеи с циклом пришли в голову. Но его минус в том, что если массив на много миллионов итераций, да ещё и часто вызывается - то можно нефигово так нагрузить железо. Но наверное в рамках интервью можно это упомянуть, но не учитывать в условие задачи.
@OpalGooDog3 жыл бұрын
@@alexein6631 xor вариант в случае 2 только первых вхождений, или к случае 3 вхождений не даст правильный вариант ответа( хотя решение только 1 варианта вхождения одного элемента и 2 других, очень красивое, но боюсь очень редкий кейз
@alexein66313 жыл бұрын
@@OpalGooDog у меня на проекте redis фильтры таким образом в битмап записывает и вычисляет совпадения. Я только сейчас понял как он это делает у себя под капотом.
@counter_helix3 жыл бұрын
Канал - супер! Спасибо за контент
@akhmedumarov39449 ай бұрын
Пройтись по массиву, в случае если число попалось впервые закинуть его в map с ключом значения а в значение тру, проверяется впервые или нет, тем что есть ли такое свойство в map, если же оно есть то удаляется свойство. Потом просто находит единственнле свойство map. Сложность O(1)
@forgotten_forbidden7 ай бұрын
O(n)
@MrVlad3d2 жыл бұрын
Первое решение работает за О(n), если бы сортировка вызывалась в цикле, то было бы n * log(n). Разве не так?
@wolf_code2 жыл бұрын
В первом решении сначала отрабатывает сортировка за 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)
К элегантным надо стремиться, пока не начинает гореть дед лайн. ))
@ReAgent0033 жыл бұрын
В самом конце ролика вставляй пожалуйста чёрный экран чтобы на его фоне всплывали рекомендованные видео, а то в данном случае превьюшки других твоих роликов закрыли код (09:09)
@wolf_code3 жыл бұрын
Отличная идея!
@tachik0ma4613 жыл бұрын
Не бросай, продолжай снимать) У тебя хорошо получается, да и по скале мало хороших видео.
@ZlataDobrovolny2 жыл бұрын
Спасибо, что делитесь!
@АндрейСоловьев-ц6о Жыл бұрын
Чел, у тебя круто получается
@lepaxtwin11 ай бұрын
0:58 Сгруппировать по значению, и найти запись с количеством вхождений 1.
@wolf_code11 ай бұрын
сложность какая у группировки по значениям?
@m.ya.yakovlev Жыл бұрын
Хорошая задача. Я её даю своим студентам (самым сильным) - но пока ни один не додумался до решения за один проход (через "исключающее или").
@ТимофейГерасимов-ю4ь Жыл бұрын
есть решение через словарь за один проход (o(n)), добавлять значение из массива в словарь и после повторного нахождения удалять, затем вернуть единственный ключ из словаря, по сути один проход + 1 раз сходить в словарь
@ilias3624 Жыл бұрын
@@ТимофейГерасимов-ю4ь Так память же лишняя требуется, в идеале без нее. У автора в видео было множество, то же самое, что словарь почти по памяти
@aleksandrkim550 Жыл бұрын
@@ilias3624 память через словарь меньше занимает. Так как удаляются по ходу решения
@7Denial711 ай бұрын
А я за 5 минут вышел в голове на это решение, пока на работу ехал)) приятно
@dmitrievsergey2 жыл бұрын
С xor ящетаю, гениально!
@wolf_code2 жыл бұрын
тоже так подумал когда узнал про это решение)
@ilyabikmeev3 жыл бұрын
Придумал решение за О(N) сначала, но оно требует O(N) памяти. Заводим массив b, где b[i] = количество вхождений числа i в исходный массив. Далее, нам надо по исходному массиву пройтись и для каждого x сделать b[x]++. Далее, проходимся в конце по массиву b и где количество =1 - это ответ.
@Khashimova_wellness3 жыл бұрын
А если в массиве будут большие числа, например 1000000000, придется создать массив длиной в миллиард элементов
@wolf_code3 жыл бұрын
@@Khashimova_wellness согласен - получается будет не линейное время а O(NM), где M максимальное значение в списке Алгоритм отработает линейно при условии если значения в массиве будут маленькими
@ilyabikmeev3 жыл бұрын
@@wolf_code Всмысле) Он всегда линейно работает, мы один проход делаем по массиву при подсчете, у нас цикл что то вроде for(int i = 0; i < n; ++i) b[a[i]]++; И потом один проход по массиву посчитанному for(int i = 0; i < n; ++i) if(b[i] == 1) //Мы нашли число
@ilyabikmeev3 жыл бұрын
@@wolf_code То, что потребуется больше памяти, я согласен. И то, что алгоритм будет работать за O(m), где m- максимум в изначальном массиве тоже согласен, но никак не за O(nm). Это просто решение, которое пришло в голову сразу, через xor конечно элегантнее и лучше)
@wolf_code3 жыл бұрын
@@ilyabikmeev точно - тупанул)) мы же не внутри цикла ходим да будет тогда скорее так O(max(M, N)) Признаю - ошибся
@MichailLLevin Жыл бұрын
а разве set работает не за логарифмическое время? Для целых чисел можно написать сортировку за линейное время. Или использовать множество с хэшем.
@wolf_code Жыл бұрын
set это множество с хэшем в скала как я помню, под капотом это плоские хэш таблицы
@BarbosJeka3 жыл бұрын
А reduce на пустом массиве разве не свалится с ошибкой? Может лучше fold использовать, с начальным нулем
@wolf_code3 жыл бұрын
Очень тонко подмечено, все ждал когда же это ктото заметит))) Отлично - так держать! Да решение свалится, но у нас по условию каждое число встречается ровно 2 раза и только одно 1 раз, получается числа все таки встречаются Это даже хорошо что reduce свалится с ошибкой, ведь мы не знаем какой ответ мы должны вернуть для пустого списка. 0 в таком случае это неверный ответ - ведь это будет означать что в пустом массиве ответ равен 0 - что конечно неверно, там 0 не встречается 1 раз Тут лучше вернуть None
@torburgmax Жыл бұрын
@@wolf_code какой странный редьюс в скале. ведь эта функция априори должна аккумулировать значения, а значит иметь что-то в качестве начального значения
@wolf_code Жыл бұрын
@@torburgmax для этого там служит другая функция: foldLeft
@АлексейЛукьянов-ф2ц3 жыл бұрын
Я конечно не программист, но на Python решается просто через множества (class 'set') Решение: искомое число = 2 * sum(set(s)) - sum(s) где: s - начальное множество 2 * sum(set(s)) - удвоенное сумма эл-в без повтора sum(s) - сумма элементов изначально
@wolf_code3 жыл бұрын
Как думаете - где ошибка в Вашем решении?
@АлексейЛукьянов-ф2ц3 жыл бұрын
@@wolf_code Буду благодарен если поделитесь. Понимаю, что такой вариант не сработает, если элементы множества это не числа.
@wolf_code3 жыл бұрын
@@АлексейЛукьянов-ф2ц хотя нет, вроде все норм, я ошибался
@wolf_code3 жыл бұрын
@@АлексейЛукьянов-ф2ц Ваше решение не сработает если в массиве большие числа, сумма вылезет за int
@АлексейЛукьянов-ф2ц3 жыл бұрын
@@wolf_code Спасибо
@АндрейБочарников-х5ъ3 жыл бұрын
Как вариант из массива создать хеш-карту, ключ - число, значение - количество вхождений и в итоге найти ключ, значение которого равно один. Плюсы, универсальность, если изменится условие и одинокий элемент будет не один, то меняется вариант вывода результата на массив. Если в видео было данное решение, то извините)
@wolf_code3 жыл бұрын
Прикольно! Получится сложность O(N), но потребуется O(N) памяти так же для хранения хэштаблицы
@АндрейБочарников-х5ъ3 жыл бұрын
@@wolf_code в итоге как и у любого решения, свои плюсы и минусы. Кроме побитовых операций, там без минусов)
@wolf_code3 жыл бұрын
@@АндрейБочарников-х5ъ согласен
@ArthurMudrick3 жыл бұрын
в реальной жизни именно так я бы и написал, т.к. условие сто процентов бы изменилось :)
@wolf_code3 жыл бұрын
@@ArthurMudrick реальные задачи согласен - лучше решать без ухищрений понятными способами
@timofeev.vadim.96 Жыл бұрын
Интересно, зачем вообще так углубляться в скорость решения задачи, если питон вообще не про скорость?) во всяком случае лезть в бинарный код перебор по-моему) Вы и так решили здорово, главное хоть как-то решить, и желательно, не O(n^2).
@Gaymernumbe13 жыл бұрын
2 решение не за линию. Поиск и добавление в множество не единица, а log(n)(во всяком случае в c++ и java), так что решение и не ускорилось и стало потреблять больше памяти
@wolf_code3 жыл бұрын
Советую почитать про HAMT и как реализованы хэштаблицы в scala (иммутабельные хэштаблицы)
@wolf_code3 жыл бұрын
да и в спецификации джава сказано что хэштаблицы работают за константу docs.oracle.com/javase/7/docs/api/java/util/HashSet.html#add(E) Вы какой либой пользуетесь?
@wolf_code3 жыл бұрын
да в плюсах написано что константное время en.cppreference.com/w/cpp/container/unordered_set )
@Gaymernumbe13 жыл бұрын
Я имел ввиду множества на самобалансирующихся деревьях типа tree set в java и обычный set в плюсах, но идея с hash map - и в правду верная
@Gaymernumbe13 жыл бұрын
Тогда получается простейшая сортировка подсчётом, прикольно
@персональныйиисус-я1ц3 жыл бұрын
одна операция в set O(logN) => решение с сетом работает за O(NlogN)
@wolf_code3 жыл бұрын
А если сет на основе хэш таблиц?
@TheSanSanch3 жыл бұрын
прикольно. сразу подумал про xor, только первым пришло решение, аналогичное подходу с множеством, но вместо множества использовать битсет, где xor-ить i-й элемент. тогда после прохода по всем элементам массива только в одной позиции битсета останется 1 - его позиция - это ответ.
@АндрейВарин-р4г3 жыл бұрын
А зачем множество, если после сортировки можно идти по циклу с шагом 2, а в цикле проверять arr[i]==arr[i+1], только нужно учесть, что если i=n-1, то мы завершаем цикл.
@TheSanSanch3 жыл бұрын
@@АндрейВарин-р4г затем, чтобы не делать сортировку)))
@ДанилаПлаксин-у6ъ Жыл бұрын
Решение конечно вообще неожиданное
@belov_dev3 жыл бұрын
Вааауу, мега круто !
@litvinenkow Жыл бұрын
а что при использовании XOR разве не потребляется столько же памяти, как размер самого массива или этот массив на Луне находится?
@wolf_code Жыл бұрын
мы ведь не целиком массив xorим
@vanvancich9live3 жыл бұрын
Так set же работает за log n, поэтому сложность остаётся такая же, как на сортировке, разве нет?
@wolf_code3 жыл бұрын
Как устроен сет в скала?
@leonovgleb85352 жыл бұрын
Решение с XOR крутое, так сразу в голову не придёт.
@jjj78ean3 жыл бұрын
импортируем Counter и через List comprehension выбираем ключ, где значение = 2
@wolf_code3 жыл бұрын
как это будет в коде?
@jjj78ean3 жыл бұрын
@@wolf_code dict_ = Counter(arr) number = [k for k in dict_ if dict_[k] ==2 ]
@wolf_code3 жыл бұрын
@@jjj78ean как быстро строится Counter?
@wollkey2 жыл бұрын
Разве сначала не придётся обойти массив и преобразовать в биты каждое десятичное число? Конечно процессор оперирует битами, но люди оперируют типами данных на более высоком уровне, и десятичное число нужно же всё равно преобразовать в бинарный тип, или оператор xor в скала сразу можно применять к int и будет работать напрямую с битами?
@wolf_code2 жыл бұрын
Сразу с битами
@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
@alexnovik62233 жыл бұрын
Задача: нарисовать все возможные иконки 3 на 3 пикселя в 8 битном исполнении.
@wolf_code3 жыл бұрын
Хорошая тема для нового выпуска)) Запилю видос
@wolf_code3 жыл бұрын
а что значит в 8 битном исполнении?
@alexnovik62233 жыл бұрын
@@wolf_code 8 бит = 1 байт = диапазон [0, 255] Т.е. результат в виде всех двумерных массивов 3 на 3 где каждая ячейка от 0 до 255. Сложность, время, потребление памяти )))
@URobotics3 жыл бұрын
Это 9 ^256 ?
@wolf_code3 жыл бұрын
@@URobotics скорее наоборот 9 пикселей по 256 значений принимает каждый, получаем 256^9 = (2^8)^9 = 2^72 2^72 байта это 2^42 терабайта, столько памяти нет думаю нигде))
@ValihanJumadilov Жыл бұрын
А отказоустойчивость не предусматривается? Вдруг в массиве будет два уникальных числа?
@wolf_code Жыл бұрын
Тогда они не уникальны
@MuxaL3 жыл бұрын
Можно решить так: заводить переменную m = 1 и бежишь по массиву: если число m делится на элемент i, то мы его делим, а если нет - то перемножаем. В итоге m окажется нашим ответом
@MuxaL3 жыл бұрын
(я питонист, мне можно работать с нормальными православными интами)
@wolf_code3 жыл бұрын
допустим список такой (1, 3, 3) 1 не делится ни на одно число из списка, ответ равен 9?
@MuxaL3 жыл бұрын
@@wolf_code 1) 1 // 1 2) 1 * 3 3) 3 // 3 = 1
@MuxaL3 жыл бұрын
@@wolf_code Хотя нет, я нашёл ошибку. На случае 3 9 27 9 3 выведет 3
@ТимофейГерасимов-ю4ь Жыл бұрын
решение на го: 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 Жыл бұрын
Лучший!
@iceone36511 ай бұрын
я новичок в пайтон, я когда смотрю такие видосы, пытаюсь сначала решить задачу сам. И вроде получается, но потом когда смотрю решение, понимаю что я чего-то не понимаю n = int(input()) s = [int(input()) for i in range(n)] for i in s: if s.count(i)
@ИванШалутов11 ай бұрын
Извините за глупый вопрос, но что такое val в вашем коде?) Для чего вы пишите перед переменной val?
@CyberGenius7773 жыл бұрын
на 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_code3 жыл бұрын
Решение будет работать - но советую почитать в закрепленном комменте почему такой подход неэффективен В Вашем решении вы заменили count на indexOf, но сложность будет такой же O(N^2)
@CyberGenius7773 жыл бұрын
@@wolf_code да, я это понимаю) Просто решил эту задачу на js написать, просто в комментариях не заметил, чтобы ее на js реализовывали
@danielrossy74532 жыл бұрын
@@wolf_code Ну это как посмотреть :) На JS большинство задач именно так и решается т.к. если на каждый подобный пример разработчик будет тратить ресурсы на поиск решения, то во первых в 9 из 10 случаев это никак не скажется на объёктивных метриках перформанса web app, во вторых потратит гораздо больше времени на имплементацию, а в третьих код станет сложнее с точки зрения понимания и поддержки для других разработчиков. Итого, с точки зрения бизнеса и конечного результата такие примеры сильно далеки от реальной жизни. Тут я не умоляю важность умения решать алгоритмические задачи, но умоляю их ценность при проведении собеседований, которая переоценена.
@wolf_code2 жыл бұрын
@@danielrossy7453 тут и не поднимается вопрос о практической ценности задачи а о том что нужно ли по алгоритмам гонять на собесах уже исписано много пабликов - давайте тут не разводить
@ЕгорКузьмин-б3ь Жыл бұрын
Мне сразу пришло в голову решение def get_n(lst): return min(lst, key=lambda x: lst.count(x))
@wolf_code Жыл бұрын
сразу пришло решение которое работает очень медленно)
@rosel_13372 жыл бұрын
можно у вас спросить, вы имеете высшее образование ну или любое и желательно ли это для рынка труда?
@wolf_code2 жыл бұрын
У меня есть диплом бакалавра по направлению ПОВТиАС Диплом у меня нигде не спрашивали
@Disorrder3 жыл бұрын
В чём смысл сортировать массив, если можно решить без сортировки? Сортировка работает за N * log N, после этого придётся сделать полный проход за N. Зачем, когда можно создать хэш-мап и записывать туда все найденные числа. Но перед записью сделать проверку, если оно там есть, то удалить его от туда. В итоге останется только одно число, которое будет являться ответом. При этом сложность алгоритма будет N ещё и за 1 проход P.S. А, ну это второй вариант, ок 3:25 Ты пробегаешь по каждому элементу отсортированного массива, при том, что они идут парами?! Выглядит не очень Решение с xor и правда очень красивое
@wolf_code3 жыл бұрын
А второе решение смотрели дальше?
@kirillkirillov78423 жыл бұрын
Привет, интересен результат собеседования, взяли (бы) они тебя на работу, или нет? И на какую позицию проходил собеседование?
@wolf_code3 жыл бұрын
Не взяли, 3й этап завалил Мидл бэкенд
@alexandergrigorev45183 жыл бұрын
Почему второе решение считается что за линейное время? Тут не учитывается что под капотом у реализации множества?
@wolf_code3 жыл бұрын
А как под капотом реализован Set в Scala?
@alexandergrigorev45183 жыл бұрын
@@wolf_code конкретно в скала не знаю но вот сейчас подумал что наверняка за о(1) 😁
@wolf_code3 жыл бұрын
@@alexandergrigorev4518 я гдето в комментах кому то отвечал на этот вопрос, вкратце есть такая структура данных как HAMT, ее еще называют идеальная хэш таблица, можно почитать статью про ее принцип работы если погуглить сразу найдется
@alexandergrigorev45183 жыл бұрын
@@wolf_code о, спасибо!
@alexandergrigorev45183 жыл бұрын
@@wolf_code до того как вы ответили я стал думать а как сделать множество за о(1) и подумал что самое тупое это огромный массив со смещением на нужное число, потом вспомнил что его делают через хеш с пересчетом по мере наполнения и все равно это о(1) в итоге. Очень полезно я к вам зашёл на канал, спасибо 😁
@homehome-hl9do Жыл бұрын
О, а я догадался до xor-a. Где тут контракты подписывают? 😊
@akiragosu3 жыл бұрын
какое обидное поражение КПХФ от НИП…😢😭 Молодые из Флэймс заслуживали эту победу больше Ниндзей (((
@smokehappiest90053 жыл бұрын
чеееел) тыыы)))) аукзахухкахукхаукха я смотрел вчера этот матч бляяя,... ты как тут оказался
@akiragosu3 жыл бұрын
@@smokehappiest9005 аххахахахаха наугад тыкнул, шоб с эмоциями поделиться🤣🤣
@smokehappiest90053 жыл бұрын
@@akiragosu наугад на видео про собес в яндекс?))))
@akiragosu3 жыл бұрын
@@smokehappiest9005 да чет приуныл чутка, че было первое нажал😁😏
@АнарГусейнов-с5ы2 жыл бұрын
Сложить все уникальные элементы умножить на 2 и отнять сумму всех чисел
@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, скорей всего не реализуете (мне такого не известно). Ну, или предложите тогда?
@crane5922 Жыл бұрын
Проблема Яндекс собеседования, что им нужно их решение, а не то что можно рассуждать.
@ЮрийЧебышев-т1ф3 жыл бұрын
До сих пор несколько переживаю записываться на собесы если не собираюсь менять работу. Этож несколько синьор+ соберутся, чтобы со мной поговорить, а я даже идти к ним не хочу?
@wolf_code3 жыл бұрын
Абсолютно согласен Я бы тогда наверное пошел к ним работать, но не прошел все 5 этапов + Тратить время людей не вижу смысла - поэтому сейчас ищу другие способы узнать про задачи с собеседований
@Anton-ki7ch3 жыл бұрын
@@wolf_code leetcode?
@wolf_code3 жыл бұрын
@@Anton-ki7ch ага, в новом видео про литкод
@44magnum842 жыл бұрын
Решение с XOR - просто читерство какое-то
@wolf_code2 жыл бұрын
есть такое
@nurgisazhumashev12753 жыл бұрын
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_code3 жыл бұрын
Верно - но долго - советую прочитать закрепленный комментарий
@avpmk Жыл бұрын
Random access по листу не константа, у первого решения выше сложность.
@wolf_code Жыл бұрын
Предлагаю посмотреть видео про быструю сортировку списка на моем канале, там не используется доступ по индексу
@avpmk Жыл бұрын
@@wolf_code 3:06 Я про доступ к уже отсортированному листу b, строчки 5 и 6
@wolf_code Жыл бұрын
@@avpmk тут да согласен, надо было конвертнуть в vector
@KirillKlenov3 жыл бұрын
Ловкий трюк
@Александр-р6щ6э3 жыл бұрын
Привет. Мы перевели всё числа в двоичную систему а как найти лишнее не совсем понял. Спасибо.
@wolf_code3 жыл бұрын
Привет Знаешь как работает xor? "ислючающее или" на русском
@Александр-р6щ6э3 жыл бұрын
@@wolf_code Да, все дошло до меня)))) с работы посмотрел не отдохнувшим :D
@happer20093 жыл бұрын
Прикольно. Я бы сбросил массив в двумерный, во второе измерение проставил единички, свернул по первому измерению сложив значения второго, отсортировал по второму измерению, верхнее число - ответ. И не важно число это или строка, пофиг. :-) Как вам такой изврат ? :-)
@wolf_code3 жыл бұрын
Не совсем понятно что значит "сбросил массив в двумерный" - это значит разложить значения в массиве по оси x? а проставите единички по оси y?
@sergiopuccini3 жыл бұрын
Просьба - пишите название языка на который вы собеседовались.
@wolf_code3 жыл бұрын
Спасибо за коммент В будущем учту, скорее просто добавлю в описании канал. Я специализируюсь только на языке скала А у яндекса нет привязки к языку в собесах, можно даже на псевдокоде, по крайней было так на моих собесах
@Влад-г2п2э3 жыл бұрын
Так какой язык-то? Подскажите, пожалуйста, любопытно
@wolf_code3 жыл бұрын
@@Влад-г2п2э scala
@Влад-г2п2э3 жыл бұрын
@@wolf_code благодарю
@stepandemin58366 ай бұрын
Ничего подобного: в яндексе просьба о помощи насцениваеться как подсказка и идёт в минус
@StanleyOzzy3 жыл бұрын
Вот мое решение с рекурсией на 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. за отступы прошу прощения, с мобильника писал
@foundersl2 жыл бұрын
Это ужасно разрушать исходное состояние переданного объекта. Не надо так.
@ЯнФокин3 жыл бұрын
Правильно ли понимаю, что значения добавляются по обе стороны и затем сравниваются?
@wolf_code3 жыл бұрын
Вы про какой из подходов?
@ЯнФокин3 жыл бұрын
@@wolf_code Я про само решение Яндекса.
@wolf_code3 жыл бұрын
@@ЯнФокин в решении через xor никакий сравнений нету - достаточно просто пробежаться по массиву и проиксорить каждое число с переменной Если еще есть вопросы - смело пишите - разберем)
@user-alzKfArQ8 Жыл бұрын
очень классно, но никому не нужно, театр абсурда
@UnityHomeStudio10 ай бұрын
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) Вот так решил
@nikitahffthvdestggfdry Жыл бұрын
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 Жыл бұрын
с чего вдруг сортировка за линейное время?
@nikitahffthvdestggfdry Жыл бұрын
@@wolf_code Согласен, в pyton сортировка n*logn, не линейная, но тоже неплохо.
@INesterov Жыл бұрын
Выход за предел масива справа в коде.
@cdeblog3 жыл бұрын
Писал бы на си или на плюсах, решение с ксором пришло бы в голову первым 😉
@Levelord923 жыл бұрын
Дай угадаю концовку: после 100 разных решений ты пришёл к решению со сложностью O(1), и спустя ещё 40 этапов собеседования они прислали оффер на 50 тысяч рублей? Очень в стиле яндекса
@wolf_code3 жыл бұрын
Хехе
@sdhfdsfh24133 жыл бұрын
как можно сделать цветные скобки, как в видео?
@wolf_code3 жыл бұрын
плагин rainbow bracket
@igrillla3 жыл бұрын
Что за должность? Что за язык программирования?
@wolf_code3 жыл бұрын
Я шел на backend разработчика, язык scala
@crypt20403 жыл бұрын
А в какой программе ты ходишь?
@wolf_code3 жыл бұрын
www.jetbrains.com/idea/ + scalaplugin
@crypt20403 жыл бұрын
@@wolf_code он как я понял платный посоветуй редактор кода на Линукс ?
@wolf_code3 жыл бұрын
@@crypt2040 community версия бесплатная, я ей пользуюсь можно еще попробовать vs-code, neo-vim
@АлексейМелентьев-ч3в3 жыл бұрын
нука ткните меня как начинающего в чём проблема такого решения ? arr.forEach(num => { let temp = arr.filter((item) => item === num) if (temp.length === 1) { console.log(temp[0]); } });
@wolf_code3 жыл бұрын
какова зависимость количества операций от размера входного списка в Вашем решении?
@АлексейМелентьев-ч3в3 жыл бұрын
@@wolf_code а, вы хочите сказать, что если входной массив будет гигантским, то решения мы не дождёмсе? может может вы и правы)
@wolf_code3 жыл бұрын
@@АлексейМелентьев-ч3в типа того допустим при размере входного массива в 100к элементов ваше решение произведет ~100k^2 операций если предположить что современный процессор делает миллиард операций в секунду - то ваше решение грубо говоря отработает за 10 секунд - что довольно долго
@МаксимМаксимов-ч9т3 жыл бұрын
А какое решение будет, если надо отыскать все уникальные числа?
@wolf_code3 жыл бұрын
Всм? Уникальное число одно по условию
@interfi46503 жыл бұрын
можно вопрос, почему не подсчитать количество вхождений числа через функцию count? x = [1,2,3,4,5,4,3,2,1] for i in x: if x.count(i) == 1: print(i)
@wolf_code3 жыл бұрын
Функция count будет делать n операций, а запускаете вы ее в цикле Получаем общую сложность О(n^2) Это очень долго
@idontknow_9 ай бұрын
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 так же не догадался :\
@liOnka9112 жыл бұрын
За сколько времени самообучения ты вышел на такой уровень знаний?
@wolf_code2 жыл бұрын
Не скажу что уровень высокий, программированием занимаюсь лет 5
@Super-fruja3 жыл бұрын
Какой язык программирования?
@wolf_code3 жыл бұрын
скала
@yaroslav86093 жыл бұрын
Вот на 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_code3 жыл бұрын
Красавчик
@yaroslav86093 жыл бұрын
@@wolf_code как неожиданно и приятно)
@ДенисЧеб-м6ф3 жыл бұрын
а как выглядело решение в коде?
@wolf_code3 жыл бұрын
Как-то так: 3:38, 6:22, 9:02 )
@ДенисЧеб-м6ф3 жыл бұрын
@@wolf_code ой, просто не досмотрел последние секунды видео, сорян за невнимательность и спасибо за ответ!)
@msmesh56663 жыл бұрын
В 1 строку: def find_single(input_list: list): return {input_list.count(n): n for n in input_list}[1]
@wolf_code3 жыл бұрын
Прочитай закреп коммент
@msmesh56663 жыл бұрын
@@wolf_code дело в том, что словарь пробегает не по всему в ходящему списку, он затрагивает только неповторяющиеся элементы в нем. Это все равно, что создать множество и пробежаться по множеству а не по входному списку, но искать элементы во входном списке + можно сделать бреак если элемент найден
@msmesh56663 жыл бұрын
@@wolf_code здесь будет где-то O(n * sqrt(n))
@wolf_code3 жыл бұрын
@@msmesh5666 понял
@wolf_code3 жыл бұрын
@@msmesh5666 если убрать дубли получится не sqrt(n), а n/2
@АндрейАверин-д1к3 жыл бұрын
Что за программа?
@wolf_code3 жыл бұрын
Какая? Если про среду разработки intellij idea
@NameXss3 жыл бұрын
contains не использует ли цикл?
@wolf_code3 жыл бұрын
скорее всего
@NameXss3 жыл бұрын
@@wolf_code т.е. получается там квадратичное время, а не линейное?
@wolf_code3 жыл бұрын
@@NameXss я почему-то подумал что вы спрашиваете про contains у List-а, у Set contains работает за O(1)
@NameXss3 жыл бұрын
@@wolf_code очень интересно как так реализовано :)
@NameXss3 жыл бұрын
@@wolf_code ах, там хеши, понятно)
@0yustas02 жыл бұрын
У меня в голову в такой последовательности решения приходили... 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_code2 жыл бұрын
а на SQL решение оч интересно глянуть
@0yustas02 жыл бұрын
@@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(*) допишет, а я спать :) переварит как символы, так и инты
@0yustas02 жыл бұрын
@@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()
@0yustas02 жыл бұрын
@@wolf_code сел полистать питоновский мануал... мне пришел в голову еще один однострочник from functools import reduce src = reduce(lambda x,y: x^y, [1,2,3,7,3,2,1]) :)
@wolf_code2 жыл бұрын
@@0yustas0 очень похоже на 3е решение в видео
@dimape.41803 жыл бұрын
А вот так на 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_code3 жыл бұрын
Советую читать закрепы
@MrNarutorengun3 жыл бұрын
*ред. язык: 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))
@MrNarutorengun3 жыл бұрын
P.S. только только повторил/прошёл основы синтаксиса))
@wolf_code3 жыл бұрын
@@MrNarutorengun Вы написали на питоне, ну ок может и хотели на нем ваше решение неэффективное - прошу прочесть закреп. коммент но все равно красавчик - огромный респект за упорство
@MrNarutorengun3 жыл бұрын
ответ реально крутой, мне теперь страшно представить насколько более громоздко моё решение))
@IlyaZherebtsov2 жыл бұрын
9:05 надо посмотреть, как такую задачу можно решить на питоне/java и пр
@siroziro6672 Жыл бұрын
как же вы тихо говорите )
@violetjellyfish20892 жыл бұрын
Я на кодварс видела такую задачу
@soncemvo3 жыл бұрын
Блин серьезно? 21 век, сервера поддерживают до нескольких терабайт оперативы, зилион-ядерные процессоры, датацентры размером с дом, приложения того же яндекса которые показывают 2 формочки весит 200мб. А в итоге ксорим сраный числовой массив чтобы сэкономить 2 байта памяти... Бред да и только. Я конечно понимаю что это задача далека от реальности и в реальность(особенно в яндексе) никто этим бредом заниматься не будет, но каждый раз когда я вижу такие задания на собесах - просто жопа горит....
@wolf_code3 жыл бұрын
Добро пожаловать в клуб
@foundersl2 жыл бұрын
А вот и не правда. Я проработал в этой компании достаточно долго и могу с уверенностью сказать - все эти терабайты оперативы и зилион-ядерные процы в множествах датацентрах размером с дом кончаются не начавшись, если везде писать квадратичный по сложности код, а кода ну очень много. Вы не представляете какие порой бывают нагрузки. На всяких конференциях с участием спикеров из подобных компаний можно подчерпнуть для себя множество примеров подобных задач, где нужно ну очень аккуратно писать с точки зрения оптимальности. При этом клиентские приложения в 200мб вообще нельзя сравнивать с тем, что крутится на серверах - это просто разные миры. Но согласен, у меня у самого иногда горит от излишней академичности задач и не все они к реальности имеют отношение, но они позволяют понять способности к размышлению и гибкость в рассуждениях, а именно это работадатель и ищет. Не решения с ксорами, а креативность и гибкость мысли. Ну и прощупывается опыт и кругозор, что тоже крайне важно.
@wolf_code2 жыл бұрын
@@foundersl спасибо за коммент, абсолютно с вами согласен глупо полагать что раз дали задачу про xor значит и на практике ждут xor мне как то давали задачу о хрустальных шарах - значит я на практике хрустальные шары кидать буду)) много я встречал на собесе людей, у которых 7+ опыта и требуют огромную ЗП, а спросишь что такое О-большое, или как работает хэштаблица - ни сном ни духом Зато умеют по методичке фигачить круд сервис)
@foundersl2 жыл бұрын
@@wolf_code вот от фигачащих по методичке круды такие собесы и призваны спасать. Они выбивают из привычной колеи и ты либо умеешь думать, либо иди куда-то дальше сингл-нодные бекенды для одностраничных лендингов писать. В этом есть только один очень жирнючий минус - не всегда сами собеседующие, к сожалению, правильно представляют себе как такие академические задачи надо предлагать и как их проверять, на что именно надо смотреть и т.п. Потому что все люди и умение верно собеседовать, особенно на высоком уровне - это вообще из разряда софт скиллов, которое очень по разному у всех развито и плохо сочитается с люто вкаченными хард скиллами в одном человеке. Иногда обидно что из-за этого некоторые кандидаты отсеиваются по false-negative результату. Но это есть везде, к сожалению. Правда достаточно редко)
@soncemvo2 жыл бұрын
@@foundersl прекрасно представляю какие могут быть нагрузки, т.к. специализируюсь на хайлоаде, а то что вы столкнулись в яндексе с чемто большим чем перекладывание джейсонов это несомненно удача.
@w01fer863 жыл бұрын
По названию ролика хотел возмутиться, мол палить задачи некрасиво. Но посмотрел, ровно эту задачу у меня спрашивали при устройстве в Яндекс в 2016)) она же в куче вариантов на всяких литкодах лежит... В общем, никаких претензий)
@wolf_code3 жыл бұрын
Да - кмк эта задача уже давно стала некой классикой в программировании, как допустим быстрая сортировка или поиск в ширину
@w01fer863 жыл бұрын
@@wolf_code тем удивительнее, что такой процент людей в комментах может написать решение в одну строку, но не думает об алгоритмической оптимальности вовсе
@0yustas02 жыл бұрын
@@w01fer86 я, если честно не совсем девелопер, но иногда балуюсь. Хотелось бы вступится за решения "в одну строчку" ибо чем проще написано и чем больше, при возможности, в БД спихнули на выполнения- тем лучше. Старина Том Кайт врать не будет :) Ну и мое однострочечное решение- его критике буду рад. def foo(l, xor_sum= 0): for i in l: xor_sum ^=i return xor_sum
@w01fer862 жыл бұрын
@@0yustas0 "В одну строчку" не тождественно "плохое". Я имел ввиду, что люди достаточно хорошо знают возможности языка (раз могут написать короткое решение), т.е. не совсем начинающие, но не думают об алгоритмической эффективности. Ваше решение алгоритмически оптимально (так что для хорошего результата на собеседовании подойдёт), но не пройдёт ревью в реальной жизни в соответствии с большинством стайлгайдов, т.к. (не беря в расчёт расположение пробелов): 1. в функцию добавлен ненужный параметр. Зачем кому-то вызывать foo(l, 25)? Кажется, незачем, но у каждого читающего функцию будет такой вопрос. Ну и добавляется шанс вместо функции fo, принимающей два параметра, случайно вызвать foo и долго дебажить возникшую проблему. Так что xor_sum=0 лучше вынести отдельной строкой. 2. Условие for и тело цикла должны быть на разных строчках даже если тело состоит из одной строки. Опять же это проще читать. Вот и получается, что ваш "однострочник" из двух строк будет более понятен, если записать его в 4 строки.
@wolfgame03 жыл бұрын
Неплохо - но надо поработать над дикцией Продолжай пилить
@wolf_code3 жыл бұрын
Согласен - лучшая речь в видосе на 0:19))
@lmslayer3 жыл бұрын
Попробуй сделать звук еще тише
@wolf_code3 жыл бұрын
Соседи просили не шуметь)) Но так конечно в будущем исправлю этот косяк - в последнем видео про 8 ферзей звук вроде получше
@RICO-sr2fn3 жыл бұрын
Встретил такую задачу на leetcode. По правде говоря думал сложность первого решения O(n) поскольку там два цикла не зависят друг от друга. Первый перебор а второй поиск arr[I] arr[I+1]. Решал на js. Создаём объект и смотрим есть ли у него элемент массива, если есть то удаляем (дубликаты будут удалены, если элемент в массиве встречается два раза) , а если один раз то записываем в объект.
@wolf_code3 жыл бұрын
Вы наверное имели ввиду первый цикл - сортировка а не перебор
@RICO-sr2fn3 жыл бұрын
@@wolf_code да)
@wolf_code3 жыл бұрын
@@RICO-sr2fn сортировка то работает за O(n log n) поэтому получается O(n log n) + O(n) = O(n log n)