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

  Рет қаралды 169,676

WolfCode

WolfCode

Күн бұрын

Пікірлер: 427
@wolf_code
@wolf_code 3 жыл бұрын
Ребят перед написанием комментария прошу прочесть Очень часто в комментариях пишут такой код: for i in list: if list.count(i) == 1: gotovo(i) Почему это хоть и простое - но плохое решение? Дело в том что мы запускаем цикл N раз (N = длина списка) В каждой итерации цикла - мы выполняем N операций (count пробегает по всему списку чтобы посчитать) Получается итоговая сложность алгоритма O(N^2) Что намного медленее чем O(N log N), а уж тем более чем O(N) Для сравнения: если N = 10k N^2 = 100kk = 100 миллионов шагов N log N ~ 130k = 130 тысяч шагов N = 10k = 10 тысяч шагов
@deathklaa
@deathklaa 3 жыл бұрын
Но ты же мог просто взять и записывать уникальное число в 1 ячейку памяти и просто пройти весь массив за N. Если число повторяется, то зануляй результат. Зачем изобретать велосипеды? Удаление из массива это тоже лишние операции, работа с масками конечно красиво, но абсолютно излишнее решение
@wolf_code
@wolf_code 3 жыл бұрын
@@deathklaa вот встретил ты какоето число записал в ячейку, затем еще одно, и что дальше - перезаписать число в ячейке?
@LineageL2ad
@LineageL2ad 3 жыл бұрын
@@wolf_code можно использовать множество - добавлять элемент в него и при повторении удалять. В итоге останется 1 элемент множества - это и будет ответ. Сложность - линейная. Это про первую задачу)
@LineageL2ad
@LineageL2ad 3 жыл бұрын
@@wolf_code все, вижу, вторая задача аналогична первой) И ты ее решил за О(N), так что норм)
@УсамаСамо
@УсамаСамо 3 жыл бұрын
@@LineageL2ad Это решение значительно быстрее, чем придуманное автором №1. Почему-то, автор считает, что функция .sorted чудесным образом не расходует ресурсы.
@SimplewerCh
@SimplewerCh 3 жыл бұрын
думал, что это собеседование в яндекс такси, а тут цифры какие-то да буквы не понятные....
@MindSkyaRocket
@MindSkyaRocket 3 жыл бұрын
Нат, это курьерам в Яндекс.Еда теперь такие тесты сделали, много претендентов на вакансии стало
@wolf_code
@wolf_code 3 жыл бұрын
@@MindSkyaRocket еще в я.такси слышал цифры не юзают и буквы тоже, там само собой на магии сервера работают
@mikemerinoff
@mikemerinoff 3 жыл бұрын
В доставку, очевидно, спрашивают задачу коммивояжёра
@wolf_code
@wolf_code 3 жыл бұрын
@@mikemerinoff скорее алгоритм дейкстры
@chloe_koshkina
@chloe_koshkina 3 жыл бұрын
@@mikemerinoff единственное, что помню с 1-го курса, ахах Всё, можно не в мак, а в такси
@DmitriiRepnikov
@DmitriiRepnikov 2 жыл бұрын
Первое решение которое мне пришло в голову после прочтения условия (пишу на js): 1. Завел мапу isUnique 2. Пробегаясь по массиву чисел: а) Если нет в мапе isUnique ключа с таким числом - добавляю его б) Если есть в мапе isUnique ключ с таким числом - удаляю его 3. Единственный оставшийся ключ в мапе это и есть нужное нам число, возвращаю его в качестве результата. (т.к. доступ по ключу это быстрая операция, то считаю алгоритм не особо жадным, на вопрос о том, как обойтись без дополнительных структур, тоже бы не ответил)
@СергейПавленко-х5я
@СергейПавленко-х5я Жыл бұрын
На питоне решение в одну строку кода: arr = [какой-то массив] print(2*sum(set(arr)) - sum(arr)) С помощью множества получаем уникальную коллекцию, то есть все элементы по одному разу. Ищем ее сумму с помощью функции sum и удваиваем. Получаем сумму всех элементов массива по 2 раза и вычтем из этого сумму исходного массива. Число найдено
@wolf_code
@wolf_code Жыл бұрын
кажется надо поделить на 2 в конце хотя нет, все норм
@АлександрКуликов-ж8к
@АлександрКуликов-ж8к Жыл бұрын
И жрём память и время...
@СергейПавленко-х5я
@СергейПавленко-х5я Жыл бұрын
@@АлександрКуликов-ж8к никто и не говорил, что это оптимальное решение. Просто я был заинтересован в поиске как можно большего количества разных подходов к задаче, и изложил тот, который не был нигде представлен.
@rvnclaw9914
@rvnclaw9914 Жыл бұрын
Канфетки жрем. Скок жрем то, какая сложность получается, подскажи? @@АлександрКуликов-ж8к
@rvnclaw9914
@rvnclaw9914 Жыл бұрын
Я просто тупой сори. ВОт смари set и sum это O(n). Эт получается O(n)+O(n)?
@danilgorlov8803
@danilgorlov8803 3 жыл бұрын
На собеседования я в те давние времена приходил так, что это я их выбирал, смогу ли я, хочу ли я работать с этими людьми. И при таком отношении даже если меня не брали, то это я их не выбирал. И моя самооценка всегда была N+1.
@dieff_automation
@dieff_automation 2 жыл бұрын
и не получал денег и сидел в жопе
@andrewmurruvyov4359
@andrewmurruvyov4359 Жыл бұрын
Настоящие программисты получают деньги, не работая, а программы составляют для души
@kirillfox5958
@kirillfox5958 3 жыл бұрын
Первое решил как у тебя, а улучшил потом подумав над xor а вот второе решение себе запомнил, спасибо
@madkir8206
@madkir8206 9 ай бұрын
Первое, что пришло в голову: Я бы в хэш табле запоминала, какие цифры у нас встречались в качестве ключей, значением сохраняла бы 0 если единожды встретилось число, 1 если встретилось второй раз, и таким образом просто вернула бы ключ, у которого значение 0 :) Но я конечно новичок в алгоритмах, так что это может и не самая лучшая мысля
@vnztvnzt
@vnztvnzt 3 жыл бұрын
Только программирование начал учить, для меня тут происходит что-то гениальное и страшное, но интересное 0.0
@ЕвгенийСниховский-ь8ь
@ЕвгенийСниховский-ь8ь 3 жыл бұрын
Если только начал учить, то не забивай себе голову видосами про собесы в топовые компании. Это все красиво, но такие решения в боевых проектах я за 6 лет видел 2-3 раза и делались они исключительно из спортивного интереса
@wolf_code
@wolf_code 3 жыл бұрын
Согласен с Евгением, если цель в кратчайшие сроки научиться писать практический код то лучше сделать упор на изучение библиотек и инфраструктуры По алгоритмам азы только - типа О-большое и др.
@holovkevych
@holovkevych 3 жыл бұрын
@@ЕвгенийСниховский-ь8ь такие задачки, это как математика - для общего развития)
@Disorrder
@Disorrder 3 жыл бұрын
не согласен с Евгением. Такие задачи важно решать самостоятельно. Как только увидел условие, ставь видео на паузу и попробуй написать код. Это не займёт много времени, а ты заодно научишься придумывать алгоритмы, что важно. И только того, как ты полностью понял суть задачи, можно смотреть продолжение и тебе расскажут как сделать лучше. И ты скорее всего даже поймёшь почему оно лучше. А может, не поймёшь. Но по крайней мере, решишь всё сам.
@Сергей-т9д7в
@Сергей-т9д7в 3 жыл бұрын
Первая задача решается без изменения массива двумя циклами ( i = от 0 до
@wolf_code
@wolf_code 3 жыл бұрын
Прошу прочесть закрепленный коммент и ознакомиться с понятием сложности алгоритма
@ilias3624
@ilias3624 Жыл бұрын
Решается, только решение очень плохое по времени
@alexjuly7097
@alexjuly7097 3 жыл бұрын
0:12 УДОБНЫЙ способ ВЫЙТИ из зоны комфорта )) звучит забавно
@wolf_code
@wolf_code 3 жыл бұрын
Так и есть, достаточно сказать запишите на собес и в какой то день мне просто надо будет за компом не кску запустить, а zoom)
@zhenshuang
@zhenshuang 3 жыл бұрын
Задача в пару действий. 1. делаешь из списка сет, считаешь полную сумму и умножаешь на два. 2. вычитаешь из полученного числа сумму первого списка. Фактически это и есть XOR
@wolf_code
@wolf_code 3 жыл бұрын
допустим дано {1, 2, 2} Вычисляем сумму = 5 Умножаем ее на 2: 5*2 = 10 Вычитаем сумму списка: 10 - 5 = 5 Ответ 5? UPD понял - ну да с сетом там все сходится
@alexanderfedintsev9570
@alexanderfedintsev9570 3 жыл бұрын
действий надо побольше: 1. Считаем сумму всех элементов массива, она равна 2S + x 2. Преобразуем массив в сет и считаем сумму, она равна S + x 3. Вычитаем из первого второе, получаем S 4. Умножаем S на 2 и вычитаем из первой суммы Но это решение все равно требует O(n) памяти и ничем не лучше варианта с множеством
@manul74
@manul74 3 жыл бұрын
@@wolf_code a = [1,1,2,2,3,3,4,4,5,5,7] print( sum(set(a)) * 2 - sum(a) )
@w01fer86
@w01fer86 3 жыл бұрын
Фактически для любого серьёзного N (для которого имеет смысл реализовывать линейный алгоритм вместо квадратичного) сумма элементов списка не будет помещаться в числовую переменную.
@Antonigin1995
@Antonigin1995 Жыл бұрын
низзя, умный какой) через питонячьи инструменты любой дурак сделает, а ты попробуй на уровне простейшем это расписать.
@alekseyl
@alekseyl 3 жыл бұрын
не назвал бы это «красивым» решением эта задачка придумана вокруг этого решения любое минимальное изменение условий (например, множественные дубли чисел) и оно перестанет работать на практике в общем классика жанра: головоломка ради головоломки
@wolf_code
@wolf_code 3 жыл бұрын
согласен
@Disorrder
@Disorrder 3 жыл бұрын
важно не столько решение, сколько процесс
@ThemrGhost1905
@ThemrGhost1905 3 жыл бұрын
Особенно больно, если наткнуться на такой код в проекте и без подсказки, что за функционал. Будет выглядеть как какая-то наитемнейшая магия.
@legac1x955
@legac1x955 3 ай бұрын
Привет, я еще совсем новичек в программировании, но считался бы этот черезчур простой код ответом на эту задачу? 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)
@OpalGooDog
@OpalGooDog 3 жыл бұрын
Создал словарь, пробежался бы циклом по массиву, на каждом новом элементе проверяю содержит ли словарь такое значение по индексу, если да то значение ключа становится на один больше, если нет то добавляем и значение делаем 1, в конце просто ищу в словаре по значению и отдаю этот ключ, Второе решение: преобразую массив в динамический массив, далее буду бежать по нему циклом, на каждом элементе удаляю и проверяю содержится ещё ли такой элемент, если да тоже удаляю если вдруг встретится когда не будет второго вхождения , присваиваем в переменную result и делаем break ,первые решения что пришло в голову и за алгоритмы не шарю, мимо жуниор самоучка
@alexein6631
@alexein6631 3 жыл бұрын
Теже идеи с циклом пришли в голову. Но его минус в том, что если массив на много миллионов итераций, да ещё и часто вызывается - то можно нефигово так нагрузить железо. Но наверное в рамках интервью можно это упомянуть, но не учитывать в условие задачи.
@OpalGooDog
@OpalGooDog 3 жыл бұрын
@@alexein6631 xor вариант в случае 2 только первых вхождений, или к случае 3 вхождений не даст правильный вариант ответа( хотя решение только 1 варианта вхождения одного элемента и 2 других, очень красивое, но боюсь очень редкий кейз
@alexein6631
@alexein6631 3 жыл бұрын
@@OpalGooDog у меня на проекте redis фильтры таким образом в битмап записывает и вычисляет совпадения. Я только сейчас понял как он это делает у себя под капотом.
@counter_helix
@counter_helix 3 жыл бұрын
Канал - супер! Спасибо за контент
@akhmedumarov3944
@akhmedumarov3944 9 ай бұрын
Пройтись по массиву, в случае если число попалось впервые закинуть его в map с ключом значения а в значение тру, проверяется впервые или нет, тем что есть ли такое свойство в map, если же оно есть то удаляется свойство. Потом просто находит единственнле свойство map. Сложность O(1)
@forgotten_forbidden
@forgotten_forbidden 7 ай бұрын
O(n)
@MrVlad3d
@MrVlad3d 2 жыл бұрын
Первое решение работает за О(n), если бы сортировка вызывалась в цикле, то было бы n * log(n). Разве не так?
@wolf_code
@wolf_code 2 жыл бұрын
В первом решении сначала отрабатывает сортировка за O(n log n) затем работает наш проход за O(n) Вспоминаем складывание асимптотик получаем O(n log n + n) = O(n log n) Если бы сортировка вызывалась в каждой итерации цикла было бы O(n (log n) * n) = O(n^2 log n)
@MrVlad3d
@MrVlad3d 2 жыл бұрын
@@wolf_code точно, спасибо, почему-то перепутал сложность сортировки
@___________S_t_a_s___________
@___________S_t_a_s___________ 3 жыл бұрын
К элегантным надо стремиться, пока не начинает гореть дед лайн. ))
@ReAgent003
@ReAgent003 3 жыл бұрын
В самом конце ролика вставляй пожалуйста чёрный экран чтобы на его фоне всплывали рекомендованные видео, а то в данном случае превьюшки других твоих роликов закрыли код (09:09)
@wolf_code
@wolf_code 3 жыл бұрын
Отличная идея!
@tachik0ma461
@tachik0ma461 3 жыл бұрын
Не бросай, продолжай снимать) У тебя хорошо получается, да и по скале мало хороших видео.
@ZlataDobrovolny
@ZlataDobrovolny 2 жыл бұрын
Спасибо, что делитесь!
@АндрейСоловьев-ц6о
@АндрейСоловьев-ц6о Жыл бұрын
Чел, у тебя круто получается
@lepaxtwin
@lepaxtwin 11 ай бұрын
0:58 Сгруппировать по значению, и найти запись с количеством вхождений 1.
@wolf_code
@wolf_code 11 ай бұрын
сложность какая у группировки по значениям?
@m.ya.yakovlev
@m.ya.yakovlev Жыл бұрын
Хорошая задача. Я её даю своим студентам (самым сильным) - но пока ни один не додумался до решения за один проход (через "исключающее или").
@ТимофейГерасимов-ю4ь
@ТимофейГерасимов-ю4ь Жыл бұрын
есть решение через словарь за один проход (o(n)), добавлять значение из массива в словарь и после повторного нахождения удалять, затем вернуть единственный ключ из словаря, по сути один проход + 1 раз сходить в словарь
@ilias3624
@ilias3624 Жыл бұрын
@@ТимофейГерасимов-ю4ь Так память же лишняя требуется, в идеале без нее. У автора в видео было множество, то же самое, что словарь почти по памяти
@aleksandrkim550
@aleksandrkim550 Жыл бұрын
@@ilias3624 память через словарь меньше занимает. Так как удаляются по ходу решения
@7Denial7
@7Denial7 11 ай бұрын
А я за 5 минут вышел в голове на это решение, пока на работу ехал)) приятно
@dmitrievsergey
@dmitrievsergey 2 жыл бұрын
С xor ящетаю, гениально!
@wolf_code
@wolf_code 2 жыл бұрын
тоже так подумал когда узнал про это решение)
@ilyabikmeev
@ilyabikmeev 3 жыл бұрын
Придумал решение за О(N) сначала, но оно требует O(N) памяти. Заводим массив b, где b[i] = количество вхождений числа i в исходный массив. Далее, нам надо по исходному массиву пройтись и для каждого x сделать b[x]++. Далее, проходимся в конце по массиву b и где количество =1 - это ответ.
@Khashimova_wellness
@Khashimova_wellness 3 жыл бұрын
А если в массиве будут большие числа, например 1000000000, придется создать массив длиной в миллиард элементов
@wolf_code
@wolf_code 3 жыл бұрын
@@Khashimova_wellness согласен - получается будет не линейное время а O(NM), где M максимальное значение в списке Алгоритм отработает линейно при условии если значения в массиве будут маленькими
@ilyabikmeev
@ilyabikmeev 3 жыл бұрын
@@wolf_code Всмысле) Он всегда линейно работает, мы один проход делаем по массиву при подсчете, у нас цикл что то вроде for(int i = 0; i < n; ++i) b[a[i]]++; И потом один проход по массиву посчитанному for(int i = 0; i < n; ++i) if(b[i] == 1) //Мы нашли число
@ilyabikmeev
@ilyabikmeev 3 жыл бұрын
@@wolf_code То, что потребуется больше памяти, я согласен. И то, что алгоритм будет работать за O(m), где m- максимум в изначальном массиве тоже согласен, но никак не за O(nm). Это просто решение, которое пришло в голову сразу, через xor конечно элегантнее и лучше)
@wolf_code
@wolf_code 3 жыл бұрын
@@ilyabikmeev точно - тупанул)) мы же не внутри цикла ходим да будет тогда скорее так O(max(M, N)) Признаю - ошибся
@MichailLLevin
@MichailLLevin Жыл бұрын
а разве set работает не за логарифмическое время? Для целых чисел можно написать сортировку за линейное время. Или использовать множество с хэшем.
@wolf_code
@wolf_code Жыл бұрын
set это множество с хэшем в скала как я помню, под капотом это плоские хэш таблицы
@BarbosJeka
@BarbosJeka 3 жыл бұрын
А reduce на пустом массиве разве не свалится с ошибкой? Может лучше fold использовать, с начальным нулем
@wolf_code
@wolf_code 3 жыл бұрын
Очень тонко подмечено, все ждал когда же это ктото заметит))) Отлично - так держать! Да решение свалится, но у нас по условию каждое число встречается ровно 2 раза и только одно 1 раз, получается числа все таки встречаются Это даже хорошо что reduce свалится с ошибкой, ведь мы не знаем какой ответ мы должны вернуть для пустого списка. 0 в таком случае это неверный ответ - ведь это будет означать что в пустом массиве ответ равен 0 - что конечно неверно, там 0 не встречается 1 раз Тут лучше вернуть None
@torburgmax
@torburgmax Жыл бұрын
@@wolf_code какой странный редьюс в скале. ведь эта функция априори должна аккумулировать значения, а значит иметь что-то в качестве начального значения
@wolf_code
@wolf_code Жыл бұрын
@@torburgmax для этого там служит другая функция: foldLeft
@АлексейЛукьянов-ф2ц
@АлексейЛукьянов-ф2ц 3 жыл бұрын
Я конечно не программист, но на Python решается просто через множества (class 'set') Решение: искомое число = 2 * sum(set(s)) - sum(s) где: s - начальное множество 2 * sum(set(s)) - удвоенное сумма эл-в без повтора sum(s) - сумма элементов изначально
@wolf_code
@wolf_code 3 жыл бұрын
Как думаете - где ошибка в Вашем решении?
@АлексейЛукьянов-ф2ц
@АлексейЛукьянов-ф2ц 3 жыл бұрын
@@wolf_code Буду благодарен если поделитесь. Понимаю, что такой вариант не сработает, если элементы множества это не числа.
@wolf_code
@wolf_code 3 жыл бұрын
@@АлексейЛукьянов-ф2ц хотя нет, вроде все норм, я ошибался
@wolf_code
@wolf_code 3 жыл бұрын
@@АлексейЛукьянов-ф2ц Ваше решение не сработает если в массиве большие числа, сумма вылезет за int
@АлексейЛукьянов-ф2ц
@АлексейЛукьянов-ф2ц 3 жыл бұрын
@@wolf_code Спасибо
@АндрейБочарников-х5ъ
@АндрейБочарников-х5ъ 3 жыл бұрын
Как вариант из массива создать хеш-карту, ключ - число, значение - количество вхождений и в итоге найти ключ, значение которого равно один. Плюсы, универсальность, если изменится условие и одинокий элемент будет не один, то меняется вариант вывода результата на массив. Если в видео было данное решение, то извините)
@wolf_code
@wolf_code 3 жыл бұрын
Прикольно! Получится сложность O(N), но потребуется O(N) памяти так же для хранения хэштаблицы
@АндрейБочарников-х5ъ
@АндрейБочарников-х5ъ 3 жыл бұрын
@@wolf_code в итоге как и у любого решения, свои плюсы и минусы. Кроме побитовых операций, там без минусов)
@wolf_code
@wolf_code 3 жыл бұрын
@@АндрейБочарников-х5ъ согласен
@ArthurMudrick
@ArthurMudrick 3 жыл бұрын
в реальной жизни именно так я бы и написал, т.к. условие сто процентов бы изменилось :)
@wolf_code
@wolf_code 3 жыл бұрын
@@ArthurMudrick реальные задачи согласен - лучше решать без ухищрений понятными способами
@timofeev.vadim.96
@timofeev.vadim.96 Жыл бұрын
Интересно, зачем вообще так углубляться в скорость решения задачи, если питон вообще не про скорость?) во всяком случае лезть в бинарный код перебор по-моему) Вы и так решили здорово, главное хоть как-то решить, и желательно, не O(n^2).
@Gaymernumbe1
@Gaymernumbe1 3 жыл бұрын
2 решение не за линию. Поиск и добавление в множество не единица, а log(n)(во всяком случае в c++ и java), так что решение и не ускорилось и стало потреблять больше памяти
@wolf_code
@wolf_code 3 жыл бұрын
Советую почитать про HAMT и как реализованы хэштаблицы в scala (иммутабельные хэштаблицы)
@wolf_code
@wolf_code 3 жыл бұрын
да и в спецификации джава сказано что хэштаблицы работают за константу docs.oracle.com/javase/7/docs/api/java/util/HashSet.html#add(E) Вы какой либой пользуетесь?
@wolf_code
@wolf_code 3 жыл бұрын
да в плюсах написано что константное время en.cppreference.com/w/cpp/container/unordered_set )
@Gaymernumbe1
@Gaymernumbe1 3 жыл бұрын
Я имел ввиду множества на самобалансирующихся деревьях типа tree set в java и обычный set в плюсах, но идея с hash map - и в правду верная
@Gaymernumbe1
@Gaymernumbe1 3 жыл бұрын
Тогда получается простейшая сортировка подсчётом, прикольно
@персональныйиисус-я1ц
@персональныйиисус-я1ц 3 жыл бұрын
одна операция в set O(logN) => решение с сетом работает за O(NlogN)
@wolf_code
@wolf_code 3 жыл бұрын
А если сет на основе хэш таблиц?
@TheSanSanch
@TheSanSanch 3 жыл бұрын
прикольно. сразу подумал про xor, только первым пришло решение, аналогичное подходу с множеством, но вместо множества использовать битсет, где xor-ить i-й элемент. тогда после прохода по всем элементам массива только в одной позиции битсета останется 1 - его позиция - это ответ.
@АндрейВарин-р4г
@АндрейВарин-р4г 3 жыл бұрын
А зачем множество, если после сортировки можно идти по циклу с шагом 2, а в цикле проверять arr[i]==arr[i+1], только нужно учесть, что если i=n-1, то мы завершаем цикл.
@TheSanSanch
@TheSanSanch 3 жыл бұрын
​@@АндрейВарин-р4г затем, чтобы не делать сортировку)))
@ДанилаПлаксин-у6ъ
@ДанилаПлаксин-у6ъ Жыл бұрын
Решение конечно вообще неожиданное
@belov_dev
@belov_dev 3 жыл бұрын
Вааауу, мега круто !
@litvinenkow
@litvinenkow Жыл бұрын
а что при использовании XOR разве не потребляется столько же памяти, как размер самого массива или этот массив на Луне находится?
@wolf_code
@wolf_code Жыл бұрын
мы ведь не целиком массив xorим
@vanvancich9live
@vanvancich9live 3 жыл бұрын
Так set же работает за log n, поэтому сложность остаётся такая же, как на сортировке, разве нет?
@wolf_code
@wolf_code 3 жыл бұрын
Как устроен сет в скала?
@leonovgleb8535
@leonovgleb8535 2 жыл бұрын
Решение с XOR крутое, так сразу в голову не придёт.
@jjj78ean
@jjj78ean 3 жыл бұрын
импортируем Counter и через List comprehension выбираем ключ, где значение = 2
@wolf_code
@wolf_code 3 жыл бұрын
как это будет в коде?
@jjj78ean
@jjj78ean 3 жыл бұрын
@@wolf_code dict_ = Counter(arr) number = [k for k in dict_ if dict_[k] ==2 ]
@wolf_code
@wolf_code 3 жыл бұрын
@@jjj78ean как быстро строится Counter?
@wollkey
@wollkey 2 жыл бұрын
Разве сначала не придётся обойти массив и преобразовать в биты каждое десятичное число? Конечно процессор оперирует битами, но люди оперируют типами данных на более высоком уровне, и десятичное число нужно же всё равно преобразовать в бинарный тип, или оператор xor в скала сразу можно применять к int и будет работать напрямую с битами?
@wolf_code
@wolf_code 2 жыл бұрын
Сразу с битами
@ishitharajapakse9675
@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
@alexnovik6223
@alexnovik6223 3 жыл бұрын
Задача: нарисовать все возможные иконки 3 на 3 пикселя в 8 битном исполнении.
@wolf_code
@wolf_code 3 жыл бұрын
Хорошая тема для нового выпуска)) Запилю видос
@wolf_code
@wolf_code 3 жыл бұрын
а что значит в 8 битном исполнении?
@alexnovik6223
@alexnovik6223 3 жыл бұрын
@@wolf_code 8 бит = 1 байт = диапазон [0, 255] Т.е. результат в виде всех двумерных массивов 3 на 3 где каждая ячейка от 0 до 255. Сложность, время, потребление памяти )))
@URobotics
@URobotics 3 жыл бұрын
Это 9 ^256 ?
@wolf_code
@wolf_code 3 жыл бұрын
@@URobotics скорее наоборот 9 пикселей по 256 значений принимает каждый, получаем 256^9 = (2^8)^9 = 2^72 2^72 байта это 2^42 терабайта, столько памяти нет думаю нигде))
@ValihanJumadilov
@ValihanJumadilov Жыл бұрын
А отказоустойчивость не предусматривается? Вдруг в массиве будет два уникальных числа?
@wolf_code
@wolf_code Жыл бұрын
Тогда они не уникальны
@MuxaL
@MuxaL 3 жыл бұрын
Можно решить так: заводить переменную m = 1 и бежишь по массиву: если число m делится на элемент i, то мы его делим, а если нет - то перемножаем. В итоге m окажется нашим ответом
@MuxaL
@MuxaL 3 жыл бұрын
(я питонист, мне можно работать с нормальными православными интами)
@wolf_code
@wolf_code 3 жыл бұрын
допустим список такой (1, 3, 3) 1 не делится ни на одно число из списка, ответ равен 9?
@MuxaL
@MuxaL 3 жыл бұрын
@@wolf_code 1) 1 // 1 2) 1 * 3 3) 3 // 3 = 1
@MuxaL
@MuxaL 3 жыл бұрын
@@wolf_code Хотя нет, я нашёл ошибку. На случае 3 9 27 9 3 выведет 3
@ТимофейГерасимов-ю4ь
@ТимофейГерасимов-ю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
@wolf_code Жыл бұрын
Лучший!
@iceone365
@iceone365 11 ай бұрын
я новичок в пайтон, я когда смотрю такие видосы, пытаюсь сначала решить задачу сам. И вроде получается, но потом когда смотрю решение, понимаю что я чего-то не понимаю n = int(input()) s = [int(input()) for i in range(n)] for i in s: if s.count(i)
@ИванШалутов
@ИванШалутов 11 ай бұрын
Извините за глупый вопрос, но что такое val в вашем коде?) Для чего вы пишите перед переменной val?
@CyberGenius777
@CyberGenius777 3 жыл бұрын
на js можно так решить: const x = [1,2,3,4,5,6,7,6,5,4,3,2,1] const result = x.filter(elem => x.indexOf(elem) === x.lastIndexOf(elem)) console.log(result) // 7 Получается так: если индекс начального и конечного элемента равны, то вернуть этот элемент
@wolf_code
@wolf_code 3 жыл бұрын
Решение будет работать - но советую почитать в закрепленном комменте почему такой подход неэффективен В Вашем решении вы заменили count на indexOf, но сложность будет такой же O(N^2)
@CyberGenius777
@CyberGenius777 3 жыл бұрын
@@wolf_code да, я это понимаю) Просто решил эту задачу на js написать, просто в комментариях не заметил, чтобы ее на js реализовывали
@danielrossy7453
@danielrossy7453 2 жыл бұрын
@@wolf_code Ну это как посмотреть :) На JS большинство задач именно так и решается т.к. если на каждый подобный пример разработчик будет тратить ресурсы на поиск решения, то во первых в 9 из 10 случаев это никак не скажется на объёктивных метриках перформанса web app, во вторых потратит гораздо больше времени на имплементацию, а в третьих код станет сложнее с точки зрения понимания и поддержки для других разработчиков. Итого, с точки зрения бизнеса и конечного результата такие примеры сильно далеки от реальной жизни. Тут я не умоляю важность умения решать алгоритмические задачи, но умоляю их ценность при проведении собеседований, которая переоценена.
@wolf_code
@wolf_code 2 жыл бұрын
@@danielrossy7453 тут и не поднимается вопрос о практической ценности задачи а о том что нужно ли по алгоритмам гонять на собесах уже исписано много пабликов - давайте тут не разводить
@ЕгорКузьмин-б3ь
@ЕгорКузьмин-б3ь Жыл бұрын
Мне сразу пришло в голову решение def get_n(lst): return min(lst, key=lambda x: lst.count(x))
@wolf_code
@wolf_code Жыл бұрын
сразу пришло решение которое работает очень медленно)
@rosel_1337
@rosel_1337 2 жыл бұрын
можно у вас спросить, вы имеете высшее образование ну или любое и желательно ли это для рынка труда?
@wolf_code
@wolf_code 2 жыл бұрын
У меня есть диплом бакалавра по направлению ПОВТиАС Диплом у меня нигде не спрашивали
@Disorrder
@Disorrder 3 жыл бұрын
В чём смысл сортировать массив, если можно решить без сортировки? Сортировка работает за N * log N, после этого придётся сделать полный проход за N. Зачем, когда можно создать хэш-мап и записывать туда все найденные числа. Но перед записью сделать проверку, если оно там есть, то удалить его от туда. В итоге останется только одно число, которое будет являться ответом. При этом сложность алгоритма будет N ещё и за 1 проход P.S. А, ну это второй вариант, ок 3:25 Ты пробегаешь по каждому элементу отсортированного массива, при том, что они идут парами?! Выглядит не очень Решение с xor и правда очень красивое
@wolf_code
@wolf_code 3 жыл бұрын
А второе решение смотрели дальше?
@kirillkirillov7842
@kirillkirillov7842 3 жыл бұрын
Привет, интересен результат собеседования, взяли (бы) они тебя на работу, или нет? И на какую позицию проходил собеседование?
@wolf_code
@wolf_code 3 жыл бұрын
Не взяли, 3й этап завалил Мидл бэкенд
@alexandergrigorev4518
@alexandergrigorev4518 3 жыл бұрын
Почему второе решение считается что за линейное время? Тут не учитывается что под капотом у реализации множества?
@wolf_code
@wolf_code 3 жыл бұрын
А как под капотом реализован Set в Scala?
@alexandergrigorev4518
@alexandergrigorev4518 3 жыл бұрын
@@wolf_code конкретно в скала не знаю но вот сейчас подумал что наверняка за о(1) 😁
@wolf_code
@wolf_code 3 жыл бұрын
@@alexandergrigorev4518 я гдето в комментах кому то отвечал на этот вопрос, вкратце есть такая структура данных как HAMT, ее еще называют идеальная хэш таблица, можно почитать статью про ее принцип работы если погуглить сразу найдется
@alexandergrigorev4518
@alexandergrigorev4518 3 жыл бұрын
@@wolf_code о, спасибо!
@alexandergrigorev4518
@alexandergrigorev4518 3 жыл бұрын
@@wolf_code до того как вы ответили я стал думать а как сделать множество за о(1) и подумал что самое тупое это огромный массив со смещением на нужное число, потом вспомнил что его делают через хеш с пересчетом по мере наполнения и все равно это о(1) в итоге. Очень полезно я к вам зашёл на канал, спасибо 😁
@homehome-hl9do
@homehome-hl9do Жыл бұрын
О, а я догадался до xor-a. Где тут контракты подписывают? 😊
@akiragosu
@akiragosu 3 жыл бұрын
какое обидное поражение КПХФ от НИП…😢😭 Молодые из Флэймс заслуживали эту победу больше Ниндзей (((
@smokehappiest9005
@smokehappiest9005 3 жыл бұрын
чеееел) тыыы)))) аукзахухкахукхаукха я смотрел вчера этот матч бляяя,... ты как тут оказался
@akiragosu
@akiragosu 3 жыл бұрын
@@smokehappiest9005 аххахахахаха наугад тыкнул, шоб с эмоциями поделиться🤣🤣
@smokehappiest9005
@smokehappiest9005 3 жыл бұрын
@@akiragosu наугад на видео про собес в яндекс?))))
@akiragosu
@akiragosu 3 жыл бұрын
@@smokehappiest9005 да чет приуныл чутка, че было первое нажал😁😏
@АнарГусейнов-с5ы
@АнарГусейнов-с5ы 2 жыл бұрын
Сложить все уникальные элементы умножить на 2 и отнять сумму всех чисел
@igortunev6163
@igortunev6163 Жыл бұрын
Решение 2 не совсем линейно. Даже в лучшем случае, если реализация сет через хэш таблицы, то линейность только по вероятности.
@wolf_code
@wolf_code Жыл бұрын
Если не линейное, то какое?
@igortunev6163
@igortunev6163 Жыл бұрын
​@@wolf_code, по умолчанию под сложностью подразумевают сложность для ДМТ (детерминированная машина Тьюринга). Самый быстрый алгоритм реализации, известный мне, это дерево, с которым сложность 2го алгоритма n log n С хэш таблицами в худшем случае может получиться n^2 (на сколько понимаю). Худший случай и определяет сложность реализации. Если бы Вас просили написать алгоритм линейный в среднем (по вероятности), то решение корректно. Но тогда нужно было об этом было сказать в видео.
@igortunev6163
@igortunev6163 Жыл бұрын
@@wolf_code, хотя и хэш таблицу можно модифицировать до log n (в худшем случае) при вставке/удалении/проверке.
@wolf_code
@wolf_code Жыл бұрын
@@igortunev6163 как работает хэш таблица по вашему? Конкретно реализация ее в библиотеке java? Там никак невозможна деградация поиска и вставки до линейного времени
@igortunev6163
@igortunev6163 Жыл бұрын
@@wolf_code, теоретическая модель допускает линейность. В java, видимо, модифицированная версия. Например, можно подобрать множество чисел, на котором хэш функция будет выдавать один и тот же адрес (на список). Тогда значения придётся класть в один список, сложность поиска в котором линейна от его длины (поиск необходим для сетов даже при вставке). Отсюда и линейность в худшем случае. Но можно вместо списка использовать, опять же, дерево или вложенный хэш и рассуждения повторяются. Те операции быстрее чем за log n, скорей всего не реализуете (мне такого не известно). Ну, или предложите тогда?
@crane5922
@crane5922 Жыл бұрын
Проблема Яндекс собеседования, что им нужно их решение, а не то что можно рассуждать.
@ЮрийЧебышев-т1ф
@ЮрийЧебышев-т1ф 3 жыл бұрын
До сих пор несколько переживаю записываться на собесы если не собираюсь менять работу. Этож несколько синьор+ соберутся, чтобы со мной поговорить, а я даже идти к ним не хочу?
@wolf_code
@wolf_code 3 жыл бұрын
Абсолютно согласен Я бы тогда наверное пошел к ним работать, но не прошел все 5 этапов + Тратить время людей не вижу смысла - поэтому сейчас ищу другие способы узнать про задачи с собеседований
@Anton-ki7ch
@Anton-ki7ch 3 жыл бұрын
@@wolf_code leetcode?
@wolf_code
@wolf_code 3 жыл бұрын
@@Anton-ki7ch ага, в новом видео про литкод
@44magnum84
@44magnum84 2 жыл бұрын
Решение с XOR - просто читерство какое-то
@wolf_code
@wolf_code 2 жыл бұрын
есть такое
@nurgisazhumashev1275
@nurgisazhumashev1275 3 жыл бұрын
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
@wolf_code 3 жыл бұрын
Верно - но долго - советую прочитать закрепленный комментарий
@avpmk
@avpmk Жыл бұрын
Random access по листу не константа, у первого решения выше сложность.
@wolf_code
@wolf_code Жыл бұрын
Предлагаю посмотреть видео про быструю сортировку списка на моем канале, там не используется доступ по индексу
@avpmk
@avpmk Жыл бұрын
@@wolf_code 3:06 Я про доступ к уже отсортированному листу b, строчки 5 и 6
@wolf_code
@wolf_code Жыл бұрын
@@avpmk тут да согласен, надо было конвертнуть в vector
@KirillKlenov
@KirillKlenov 3 жыл бұрын
Ловкий трюк
@Александр-р6щ6э
@Александр-р6щ6э 3 жыл бұрын
Привет. Мы перевели всё числа в двоичную систему а как найти лишнее не совсем понял. Спасибо.
@wolf_code
@wolf_code 3 жыл бұрын
Привет Знаешь как работает xor? "ислючающее или" на русском
@Александр-р6щ6э
@Александр-р6щ6э 3 жыл бұрын
@@wolf_code Да, все дошло до меня)))) с работы посмотрел не отдохнувшим :D
@happer2009
@happer2009 3 жыл бұрын
Прикольно. Я бы сбросил массив в двумерный, во второе измерение проставил единички, свернул по первому измерению сложив значения второго, отсортировал по второму измерению, верхнее число - ответ. И не важно число это или строка, пофиг. :-) Как вам такой изврат ? :-)
@wolf_code
@wolf_code 3 жыл бұрын
Не совсем понятно что значит "сбросил массив в двумерный" - это значит разложить значения в массиве по оси x? а проставите единички по оси y?
@sergiopuccini
@sergiopuccini 3 жыл бұрын
Просьба - пишите название языка на который вы собеседовались.
@wolf_code
@wolf_code 3 жыл бұрын
Спасибо за коммент В будущем учту, скорее просто добавлю в описании канал. Я специализируюсь только на языке скала А у яндекса нет привязки к языку в собесах, можно даже на псевдокоде, по крайней было так на моих собесах
@Влад-г2п2э
@Влад-г2п2э 3 жыл бұрын
Так какой язык-то? Подскажите, пожалуйста, любопытно
@wolf_code
@wolf_code 3 жыл бұрын
@@Влад-г2п2э scala
@Влад-г2п2э
@Влад-г2п2э 3 жыл бұрын
@@wolf_code благодарю
@stepandemin5836
@stepandemin5836 6 ай бұрын
Ничего подобного: в яндексе просьба о помощи насцениваеться как подсказка и идёт в минус
@StanleyOzzy
@StanleyOzzy 3 жыл бұрын
Вот мое решение с рекурсией на python, но оно конечно не лучшее из предложенных: def only_single(my_list): for n, i in enumerate(my_list[1:]): if my_list[0] == i: my_list.pop(0) my_list.pop(n) return only_single(my_list) return my_list[0] P.s. за отступы прошу прощения, с мобильника писал
@foundersl
@foundersl 2 жыл бұрын
Это ужасно разрушать исходное состояние переданного объекта. Не надо так.
@ЯнФокин
@ЯнФокин 3 жыл бұрын
Правильно ли понимаю, что значения добавляются по обе стороны и затем сравниваются?
@wolf_code
@wolf_code 3 жыл бұрын
Вы про какой из подходов?
@ЯнФокин
@ЯнФокин 3 жыл бұрын
@@wolf_code Я про само решение Яндекса.
@wolf_code
@wolf_code 3 жыл бұрын
@@ЯнФокин в решении через xor никакий сравнений нету - достаточно просто пробежаться по массиву и проиксорить каждое число с переменной Если еще есть вопросы - смело пишите - разберем)
@user-alzKfArQ8
@user-alzKfArQ8 Жыл бұрын
очень классно, но никому не нужно, театр абсурда
@UnityHomeStudio
@UnityHomeStudio 10 ай бұрын
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
@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
@wolf_code Жыл бұрын
с чего вдруг сортировка за линейное время?
@nikitahffthvdestggfdry
@nikitahffthvdestggfdry Жыл бұрын
@@wolf_code Согласен, в pyton сортировка n*logn, не линейная, но тоже неплохо.
@INesterov
@INesterov Жыл бұрын
Выход за предел масива справа в коде.
@cdeblog
@cdeblog 3 жыл бұрын
Писал бы на си или на плюсах, решение с ксором пришло бы в голову первым 😉
@Levelord92
@Levelord92 3 жыл бұрын
Дай угадаю концовку: после 100 разных решений ты пришёл к решению со сложностью O(1), и спустя ещё 40 этапов собеседования они прислали оффер на 50 тысяч рублей? Очень в стиле яндекса
@wolf_code
@wolf_code 3 жыл бұрын
Хехе
@sdhfdsfh2413
@sdhfdsfh2413 3 жыл бұрын
как можно сделать цветные скобки, как в видео?
@wolf_code
@wolf_code 3 жыл бұрын
плагин rainbow bracket
@igrillla
@igrillla 3 жыл бұрын
Что за должность? Что за язык программирования?
@wolf_code
@wolf_code 3 жыл бұрын
Я шел на backend разработчика, язык scala
@crypt2040
@crypt2040 3 жыл бұрын
А в какой программе ты ходишь?
@wolf_code
@wolf_code 3 жыл бұрын
www.jetbrains.com/idea/ + scalaplugin
@crypt2040
@crypt2040 3 жыл бұрын
@@wolf_code он как я понял платный посоветуй редактор кода на Линукс ?
@wolf_code
@wolf_code 3 жыл бұрын
@@crypt2040 community версия бесплатная, я ей пользуюсь можно еще попробовать vs-code, neo-vim
@АлексейМелентьев-ч3в
@АлексейМелентьев-ч3в 3 жыл бұрын
нука ткните меня как начинающего в чём проблема такого решения ? arr.forEach(num => { let temp = arr.filter((item) => item === num) if (temp.length === 1) { console.log(temp[0]); } });
@wolf_code
@wolf_code 3 жыл бұрын
какова зависимость количества операций от размера входного списка в Вашем решении?
@АлексейМелентьев-ч3в
@АлексейМелентьев-ч3в 3 жыл бұрын
@@wolf_code а, вы хочите сказать, что если входной массив будет гигантским, то решения мы не дождёмсе? может может вы и правы)
@wolf_code
@wolf_code 3 жыл бұрын
@@АлексейМелентьев-ч3в типа того допустим при размере входного массива в 100к элементов ваше решение произведет ~100k^2 операций если предположить что современный процессор делает миллиард операций в секунду - то ваше решение грубо говоря отработает за 10 секунд - что довольно долго
@МаксимМаксимов-ч9т
@МаксимМаксимов-ч9т 3 жыл бұрын
А какое решение будет, если надо отыскать все уникальные числа?
@wolf_code
@wolf_code 3 жыл бұрын
Всм? Уникальное число одно по условию
@interfi4650
@interfi4650 3 жыл бұрын
можно вопрос, почему не подсчитать количество вхождений числа через функцию count? x = [1,2,3,4,5,4,3,2,1] for i in x: if x.count(i) == 1: print(i)
@wolf_code
@wolf_code 3 жыл бұрын
Функция count будет делать n операций, а запускаете вы ее в цикле Получаем общую сложность О(n^2) Это очень долго
@idontknow_
@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 так же не догадался :\
@liOnka911
@liOnka911 2 жыл бұрын
За сколько времени самообучения ты вышел на такой уровень знаний?
@wolf_code
@wolf_code 2 жыл бұрын
Не скажу что уровень высокий, программированием занимаюсь лет 5
@Super-fruja
@Super-fruja 3 жыл бұрын
Какой язык программирования?
@wolf_code
@wolf_code 3 жыл бұрын
скала
@yaroslav8609
@yaroslav8609 3 жыл бұрын
Вот на 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
@wolf_code 3 жыл бұрын
Красавчик
@yaroslav8609
@yaroslav8609 3 жыл бұрын
@@wolf_code как неожиданно и приятно)
@ДенисЧеб-м6ф
@ДенисЧеб-м6ф 3 жыл бұрын
а как выглядело решение в коде?
@wolf_code
@wolf_code 3 жыл бұрын
Как-то так: 3:38, 6:22, 9:02 )
@ДенисЧеб-м6ф
@ДенисЧеб-м6ф 3 жыл бұрын
@@wolf_code ой, просто не досмотрел последние секунды видео, сорян за невнимательность и спасибо за ответ!)
@msmesh5666
@msmesh5666 3 жыл бұрын
В 1 строку: def find_single(input_list: list): return {input_list.count(n): n for n in input_list}[1]
@wolf_code
@wolf_code 3 жыл бұрын
Прочитай закреп коммент
@msmesh5666
@msmesh5666 3 жыл бұрын
@@wolf_code дело в том, что словарь пробегает не по всему в ходящему списку, он затрагивает только неповторяющиеся элементы в нем. Это все равно, что создать множество и пробежаться по множеству а не по входному списку, но искать элементы во входном списке + можно сделать бреак если элемент найден
@msmesh5666
@msmesh5666 3 жыл бұрын
@@wolf_code здесь будет где-то O(n * sqrt(n))
@wolf_code
@wolf_code 3 жыл бұрын
@@msmesh5666 понял
@wolf_code
@wolf_code 3 жыл бұрын
@@msmesh5666 если убрать дубли получится не sqrt(n), а n/2
@АндрейАверин-д1к
@АндрейАверин-д1к 3 жыл бұрын
Что за программа?
@wolf_code
@wolf_code 3 жыл бұрын
Какая? Если про среду разработки intellij idea
@NameXss
@NameXss 3 жыл бұрын
contains не использует ли цикл?
@wolf_code
@wolf_code 3 жыл бұрын
скорее всего
@NameXss
@NameXss 3 жыл бұрын
@@wolf_code т.е. получается там квадратичное время, а не линейное?
@wolf_code
@wolf_code 3 жыл бұрын
@@NameXss я почему-то подумал что вы спрашиваете про contains у List-а, у Set contains работает за O(1)
@NameXss
@NameXss 3 жыл бұрын
@@wolf_code очень интересно как так реализовано :)
@NameXss
@NameXss 3 жыл бұрын
@@wolf_code ах, там хеши, понятно)
@0yustas0
@0yustas0 2 жыл бұрын
У меня в голову в такой последовательности решения приходили... 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
@wolf_code 2 жыл бұрын
а на SQL решение оч интересно глянуть
@0yustas0
@0yustas0 2 жыл бұрын
@@wolf_code не вопрос. Но под рукой у меня сейчас только hive на tez (ох как меня он печалит). Да и 2AM уже - пора спать :) Если не забуду, завтра добавлю намного сипотичнее на Spark+Scala или Snowflake(опять же что под рукой будет) WITH game_at_2am AS (SELECT '["9","1","2","7","5","1","7","9","2"]' AS i_want_sleep), more_beer AS (SELECT split(regexp_extract(i_want_sleep,'^\\["(.*)\\"]$',1),'","') AS c1 FROM game_at_2am), relax AS (SELECT x FROM more_beer LATERAL VIEW EXPLODE (c1) b AS x) SELECT x FROM relax; дальше джавист любой уже GROUP BY и HAVING COUNT(*) допишет, а я спать :) переварит как символы, так и инты
@0yustas0
@0yustas0 2 жыл бұрын
@@wolf_code вот пример однострочника Spark пока стою в пробке) val df = Seq((Seq(9,1,2,7,5,1,7,9,2))).toDF("c1") df.withColumn("c2", array_distinct($"c1")).selectExpr("2* aggregate(c2, 0, (x, y) -> x + y) - aggregate(c1, 0, (x, y) -> x + y) AS result").show()
@0yustas0
@0yustas0 2 жыл бұрын
@@wolf_code сел полистать питоновский мануал... мне пришел в голову еще один однострочник from functools import reduce src = reduce(lambda x,y: x^y, [1,2,3,7,3,2,1]) :)
@wolf_code
@wolf_code 2 жыл бұрын
@@0yustas0 очень похоже на 3е решение в видео
@dimape.4180
@dimape.4180 3 жыл бұрын
А вот так на JS?)))) const fn = (ar) => { let c =[]; ar.forEach((el) => { let z = ar.filter(e=>{ return el == e }) if (z.length < 2) { return c.push(z[0]) } }) return c }
@wolf_code
@wolf_code 3 жыл бұрын
Советую читать закрепы
@MrNarutorengun
@MrNarutorengun 3 жыл бұрын
*ред. язык: 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
@MrNarutorengun 3 жыл бұрын
P.S. только только повторил/прошёл основы синтаксиса))
@wolf_code
@wolf_code 3 жыл бұрын
@@MrNarutorengun Вы написали на питоне, ну ок может и хотели на нем ваше решение неэффективное - прошу прочесть закреп. коммент но все равно красавчик - огромный респект за упорство
@MrNarutorengun
@MrNarutorengun 3 жыл бұрын
ответ реально крутой, мне теперь страшно представить насколько более громоздко моё решение))
@IlyaZherebtsov
@IlyaZherebtsov 2 жыл бұрын
9:05 надо посмотреть, как такую задачу можно решить на питоне/java и пр
@siroziro6672
@siroziro6672 Жыл бұрын
как же вы тихо говорите )
@violetjellyfish2089
@violetjellyfish2089 2 жыл бұрын
Я на кодварс видела такую задачу
@soncemvo
@soncemvo 3 жыл бұрын
Блин серьезно? 21 век, сервера поддерживают до нескольких терабайт оперативы, зилион-ядерные процессоры, датацентры размером с дом, приложения того же яндекса которые показывают 2 формочки весит 200мб. А в итоге ксорим сраный числовой массив чтобы сэкономить 2 байта памяти... Бред да и только. Я конечно понимаю что это задача далека от реальности и в реальность(особенно в яндексе) никто этим бредом заниматься не будет, но каждый раз когда я вижу такие задания на собесах - просто жопа горит....
@wolf_code
@wolf_code 3 жыл бұрын
Добро пожаловать в клуб
@foundersl
@foundersl 2 жыл бұрын
А вот и не правда. Я проработал в этой компании достаточно долго и могу с уверенностью сказать - все эти терабайты оперативы и зилион-ядерные процы в множествах датацентрах размером с дом кончаются не начавшись, если везде писать квадратичный по сложности код, а кода ну очень много. Вы не представляете какие порой бывают нагрузки. На всяких конференциях с участием спикеров из подобных компаний можно подчерпнуть для себя множество примеров подобных задач, где нужно ну очень аккуратно писать с точки зрения оптимальности. При этом клиентские приложения в 200мб вообще нельзя сравнивать с тем, что крутится на серверах - это просто разные миры. Но согласен, у меня у самого иногда горит от излишней академичности задач и не все они к реальности имеют отношение, но они позволяют понять способности к размышлению и гибкость в рассуждениях, а именно это работадатель и ищет. Не решения с ксорами, а креативность и гибкость мысли. Ну и прощупывается опыт и кругозор, что тоже крайне важно.
@wolf_code
@wolf_code 2 жыл бұрын
@@foundersl спасибо за коммент, абсолютно с вами согласен глупо полагать что раз дали задачу про xor значит и на практике ждут xor мне как то давали задачу о хрустальных шарах - значит я на практике хрустальные шары кидать буду)) много я встречал на собесе людей, у которых 7+ опыта и требуют огромную ЗП, а спросишь что такое О-большое, или как работает хэштаблица - ни сном ни духом Зато умеют по методичке фигачить круд сервис)
@foundersl
@foundersl 2 жыл бұрын
@@wolf_code вот от фигачащих по методичке круды такие собесы и призваны спасать. Они выбивают из привычной колеи и ты либо умеешь думать, либо иди куда-то дальше сингл-нодные бекенды для одностраничных лендингов писать. В этом есть только один очень жирнючий минус - не всегда сами собеседующие, к сожалению, правильно представляют себе как такие академические задачи надо предлагать и как их проверять, на что именно надо смотреть и т.п. Потому что все люди и умение верно собеседовать, особенно на высоком уровне - это вообще из разряда софт скиллов, которое очень по разному у всех развито и плохо сочитается с люто вкаченными хард скиллами в одном человеке. Иногда обидно что из-за этого некоторые кандидаты отсеиваются по false-negative результату. Но это есть везде, к сожалению. Правда достаточно редко)
@soncemvo
@soncemvo 2 жыл бұрын
@@foundersl прекрасно представляю какие могут быть нагрузки, т.к. специализируюсь на хайлоаде, а то что вы столкнулись в яндексе с чемто большим чем перекладывание джейсонов это несомненно удача.
@w01fer86
@w01fer86 3 жыл бұрын
По названию ролика хотел возмутиться, мол палить задачи некрасиво. Но посмотрел, ровно эту задачу у меня спрашивали при устройстве в Яндекс в 2016)) она же в куче вариантов на всяких литкодах лежит... В общем, никаких претензий)
@wolf_code
@wolf_code 3 жыл бұрын
Да - кмк эта задача уже давно стала некой классикой в программировании, как допустим быстрая сортировка или поиск в ширину
@w01fer86
@w01fer86 3 жыл бұрын
@@wolf_code тем удивительнее, что такой процент людей в комментах может написать решение в одну строку, но не думает об алгоритмической оптимальности вовсе
@0yustas0
@0yustas0 2 жыл бұрын
@@w01fer86 я, если честно не совсем девелопер, но иногда балуюсь. Хотелось бы вступится за решения "в одну строчку" ибо чем проще написано и чем больше, при возможности, в БД спихнули на выполнения- тем лучше. Старина Том Кайт врать не будет :) Ну и мое однострочечное решение- его критике буду рад. def foo(l, xor_sum= 0): for i in l: xor_sum ^=i return xor_sum
@w01fer86
@w01fer86 2 жыл бұрын
@@0yustas0 "В одну строчку" не тождественно "плохое". Я имел ввиду, что люди достаточно хорошо знают возможности языка (раз могут написать короткое решение), т.е. не совсем начинающие, но не думают об алгоритмической эффективности. Ваше решение алгоритмически оптимально (так что для хорошего результата на собеседовании подойдёт), но не пройдёт ревью в реальной жизни в соответствии с большинством стайлгайдов, т.к. (не беря в расчёт расположение пробелов): 1. в функцию добавлен ненужный параметр. Зачем кому-то вызывать foo(l, 25)? Кажется, незачем, но у каждого читающего функцию будет такой вопрос. Ну и добавляется шанс вместо функции fo, принимающей два параметра, случайно вызвать foo и долго дебажить возникшую проблему. Так что xor_sum=0 лучше вынести отдельной строкой. 2. Условие for и тело цикла должны быть на разных строчках даже если тело состоит из одной строки. Опять же это проще читать. Вот и получается, что ваш "однострочник" из двух строк будет более понятен, если записать его в 4 строки.
@wolfgame0
@wolfgame0 3 жыл бұрын
Неплохо - но надо поработать над дикцией Продолжай пилить
@wolf_code
@wolf_code 3 жыл бұрын
Согласен - лучшая речь в видосе на 0:19))
@lmslayer
@lmslayer 3 жыл бұрын
Попробуй сделать звук еще тише
@wolf_code
@wolf_code 3 жыл бұрын
Соседи просили не шуметь)) Но так конечно в будущем исправлю этот косяк - в последнем видео про 8 ферзей звук вроде получше
@RICO-sr2fn
@RICO-sr2fn 3 жыл бұрын
Встретил такую задачу на leetcode. По правде говоря думал сложность первого решения O(n) поскольку там два цикла не зависят друг от друга. Первый перебор а второй поиск arr[I] arr[I+1]. Решал на js. Создаём объект и смотрим есть ли у него элемент массива, если есть то удаляем (дубликаты будут удалены, если элемент в массиве встречается два раза) , а если один раз то записываем в объект.
@wolf_code
@wolf_code 3 жыл бұрын
Вы наверное имели ввиду первый цикл - сортировка а не перебор
@RICO-sr2fn
@RICO-sr2fn 3 жыл бұрын
@@wolf_code да)
@wolf_code
@wolf_code 3 жыл бұрын
@@RICO-sr2fn сортировка то работает за O(n log n) поэтому получается O(n log n) + O(n) = O(n log n)
Kluster Duo #настольныеигры #boardgames #игры #games #настолки #настольные_игры
00:47
World’s strongest WOMAN vs regular GIRLS
00:56
A4
Рет қаралды 8 МЛН
Человек паук уже не тот
00:32
Miracle
Рет қаралды 2,9 МЛН
Задача из Собеседования на 160,000 Евро в Год
13:27
Саша Лукин
Рет қаралды 1,1 МЛН
ВСЕ ПРО СТАЖИРОВКУ В ЯНДЕКСЕ!!
43:22
Поступашки - ШАД, Стажировки и Магистратура
Рет қаралды 50 М.
Советский мультфильм про нашу жизнь !
13:49
Дедушка Аргентинца
Рет қаралды 6 МЛН
Как Linux рисует окна?
48:46
Студенческие клубы разработки КНиИТ СГУ
Рет қаралды 48 М.
Kluster Duo #настольныеигры #boardgames #игры #games #настолки #настольные_игры
00:47