Больше информации и примеры задач в нашей статье на Хабре: habr.com/ru/company/yandex/bl...
Пікірлер: 177
@user-vn2nx1yq9e3 жыл бұрын
меня пугает когда он подходит
@suka112262 жыл бұрын
Беги
@qaLex455 Жыл бұрын
))
@juliaastra4345Ай бұрын
😂
@alexmiller6844 Жыл бұрын
return Counter(a) == Counter(b)
@protasovse Жыл бұрын
Зачем в анаграммах находить разницу Counter-ов, если можно их сравнить (Conter1==Counter2)?
@RusShbreak1 Жыл бұрын
Да! И более того, как можно ее найти, если оператор вычитания не поддерживается диктом...
@alloyoshi3 жыл бұрын
Проблема в том, что задаются на собеседованиях задачи В РАЗЫ сложнее, чем упомянутые.
@sevenb1t Жыл бұрын
Решай leetcode - там есть задачи сопостовимой сложности. Вопрос тренировки - без подготовки, конечно, пройти сложно алгоритмический уровень.
@whitehaker Жыл бұрын
Было бы странно, если бы на собесах давали задачи такого уровня, на видео показан пример процесса и типичные ошибки. Задачу со скобками мне дали в седьмом классе, при отборе на школьную олимпиаду по программированию, как-раз на листке писал)
@dmitrypetrov8491 Жыл бұрын
В основном задачи на собеседованиях задаются уровня easy-medium с leetcode. Но некоторые кандидаты и это решить не могут.
@user-chf7z61vnd6h8v Жыл бұрын
@@dmitrypetrov8491 зачем это человеку, который пишет фронт, и может ещё бэк на уровне обработать входящие запросы и сделать запрос в БД? Более 5 лет работу фулстеком с јѕ ни разу эта олимпиалная бредятина не пригодилась. Если ты пишешь игры или что-то требующее математики, то может оно и нужно, но большинству это нахер не всралось для веба, только мозги на собесе иметь собеседуемому
@Prof-Shor10 ай бұрын
@@user-chf7z61vnd6h8v Воистину!
@user-bh4oj3hn4s2 жыл бұрын
А есть такая же футботка, только немного поярче?)
@MajinSaha Жыл бұрын
Так, а где тесты перед решением первой задачи? В первом видео на тесты же напирали.
@MajesticNut3 жыл бұрын
Как правильно вычислить временную сложность для последней задачи со скобками?
@aslanator3 жыл бұрын
поидеи линейная
@MarkWaner2 жыл бұрын
@@aslanator точно не линейная. Экспоненциальная с базой экспоненты < 4 и > 2 Ну или суб-экспоненциальная. Там непросто вычислить из-за условий
@user-cg3wl9hl6t3 жыл бұрын
У второй задачи пропущена секция с определением сложности алгоритма
@uncle-xxi4 жыл бұрын
так там скрытых вычислений хватает :) даром что коротко и красиво :)
@user-zf2rp6vb4t3 жыл бұрын
Тут же O нотация только интересна
@okke002 жыл бұрын
Никогда не понимал зачем писать код на доске? Почему не на бересте например или долотом на камне высекать? Все одно с реальной работой не пересекается
@uvencosuper347124 күн бұрын
Если экстраполировать дальше, то почему бы не разрешить подгугливать синтаксис особо редковстречающихся конструкций, типа предполагается, что стековерфлоу в яндексе отключил злой одмин что ли?
@FakePlv5 жыл бұрын
Мм, один момент не ясен: был написан тест: parents(3)== { "((( )))", "()()()", "(())()", "()(())", "(()())" }. Но код на доске генерирует только "((( )))", так ведь? Более того в статье Яндекса на хабре про эту задачу также сказано "Вывести последовательности в лексикографическом порядке(правильный алгоритм по-умолчанию выводит их в нужном порядке)" и указана ссылка на это видео как разбор задачи. Получается то, что на доске попроще будет, чем то что на собеседовании по словам из статьи.
@nevmem6715 жыл бұрын
Нет не так код на доске генерирует ровно то, что нужно то есть НЕ одну последовательность, там же рекурсивные запуски, которые например уже на второй итерации могут на префикс построить строки "((" и "()", так как эти последовательности никак не противоречат написанному коду
@FakePlv5 жыл бұрын
@@nevmem671 Да, вы абсолютно правы, я был невнимателен(забыл вернуться к первому вызову в стеке). Вы писали ниже, что это решение первым приходит в голову. Мне же первым в голову пришло создание класса или же дерево. Расскажите, как вы понимаете, что начать рассуждения надо с рекурсии?
@slavanikulin80693 жыл бұрын
@@FakePlv рекурсия тут никак не может первая прийти в голову, имхо. Никто и никогда в здравом уме не делает двойную рекурсию в продакшене: это нечитабильно и забирает лишнюю память. Это все снобистские вые*боны олимпиадников, из которых яндекс почти весь и состоит))) Т.к. это NP-полная задача, то первое, что тут приходит в голову - жадный алгоритм построения дерева, как вы и говорите. А рекурсия - развитие этой идеи ради сокращения кол-ва строчек кода и надр*ачивания своего ЧСВ в последствии. Ради этого видео и записывалось)) PS. извиняюсь перед коммьюнити за токсичность, но тут крик души уже) PPS. Вот вариант с деревом и очередью на всякий. Само дерево не хранится. Если посмотрите, то рекурсия сама напрашивается, но делать её, конечно, не надо: import queue def generate(n): q = queue.Queue() q.put_nowait({ 'str': '(', 'left_count': 1, 'right_count': 0 }) while not q.empty(): el = q.get_nowait() if len(el['str']) == 2 * n: print(el['str']) continue if el['left_count'] < n: q.put_nowait({ 'str': el['str'] + '(', 'left_count': el['left_count'] + 1, 'right_count': el['right_count'] }) if el['right_count'] < el['left_count']: q.put_nowait({ 'str': el['str'] + ')', 'left_count': el['left_count'], 'right_count': el['right_count'] + 1 })
@FakePlv3 жыл бұрын
@@slavanikulin8069 Уже не помню, честно говоря, о чем шла речь, но да рекурсия обычно напрашивается первой, избавиться от неё обычно проблемнее, чем её применить. Как раз год назад пытался пройти контест, где было 4 олимпиадные задачи из 6(вроде шесть задач было:) ).. короче до собеседования дело даже не дошло)) У меня много вопросов возникало про адекватность формулировок, но, отвечали мне на них - никак(сам дурак). Была там задачка и про поиск множителей, где нужно было найти нужную комбинацию для заданного произведения. Алгоритм дерева был весьма кстати, правда, обходить пришлось без рекурсии, т.к. не проходил по времени. Разница в скорости алгоритма значительна, например 2ms/636Kb против рекурсивных 56ms/896Kb(метрика контеста). Так что да, в здравом уме и адекватной обстановке, рекурсия не должна приходить в голову, однако на собеседовании(до которого дело дойдет только у олимпиадников), проще сделать ей и решить задачу, чем допускать мелкие ошибки и ожидать подсказок от интервьюера. По поводу крика души. У меня тоже есть, что сказать. Жаль, конечно, что не удалось устроиться в Яндекс, хотя может оно и к лучшему. Скажу одно, у каждого свои способности и лучшие стороны, если Яндекс планирует использовать лишь скорость применение шаблона и их объем в голове разработчика, то когда-нибудь это аукнется. В универе была группа по спортивному программированию, которая занимала призовые места на мировых олимпиадах, только вот экзамен по программированию сдавал за них я, ибо по какой-то причине им не удалось осилить задачки препода. Я это к тому, что не все задачи требуют хитромудрую формулу для поиска части окружности из миллиарда окружностей, и шаблоны не помогают найти решение проблемы, они лишь пытаются её решить стандартным способом. Чтобы решать проблему надо думать. Чтобы использовать шаблон, надо его помнить. Сейчас я системный программист, занимаюсь разработкой ОС в коммерческой фирме, есть тонна задач, которые не требуют математики, но требуют очень развитой интуиции, смекалки и аналитического склада ума, что бы быстро уметь анализировать тонны опенсурсных систем и чужого кода на всевозможных языках. Наверное, таким не место в Яндексе, раз у таких дело даже до собеседования не доходит(да, разрабочик интерфейсов каких-нибудь тоже должен решить олимпиадные задачи). ps: пытался решать задачи честно - самостоятельно, не заглядывая в готовые алгоритмы.
@slavanikulin80693 жыл бұрын
Kernel Plevitsky Справедливости ради стоит сказать, что весь этот алгоритмически-олимпиадный ад стоит того, тк в Яндексе очень благоприятная среда, способствующая быстрому росту. Но если не получится пройти, то ничего страшного) Здорово, рад за вас, что нашли своё призвание и место!
@user-gk3np5nr3b2 жыл бұрын
Спасибо, видео помогло разобраться с рекурсией при помощи визуализатора, добавил return после 3го if-a так нагляднее.
@DaniilK-hq5go Жыл бұрын
А почему N log N если после сортировки нужно будет ещё сравнить строки? Это уже O(N)
@uvencosuper347124 күн бұрын
invert_string = string[::-1] return True if string == invert_string else False подглядывал только синтаксис среза, что бы инвертнуть строку, сам алгоритм сходу придумал. Вытирал бы доску сто раз, могу я приходить на собес в яндекс или мал еще?
@sananyuzb4 жыл бұрын
По первой задаче маленькая ошибка : Для 3 варианта решения задачи (про анаграммы) - использование памяти констатное - O(1) - т.к набор букв всегда постоянный - т.е если у нас строка состоит из сторчных латиских букв - то длина массива будет 26. Т.е. вне зависимости от того насколько длинная у нас строка - размер массива всегда будет одинаковый, т.е размер массива не зависит от входного параметра, соответственно сложность по памяти O(1).
@ignostik23284 жыл бұрын
Вы были бы абсолютно правы, если бы не еще одно маленькое обстоятельство: кол-во памяти для хранение счетчиков количества символов все-таки зависит от длины входных данных, а именно для хранения числа n нужно log_2(n) с округлением бит информации. Поэтому с увеличением n, затраты по памяти также растут (хотя на данный момент те порядки, при которых рост памяти будет существенным, просто недостижимы). Поэтому, строго говоря, сложность по памяти (log_2(n)).
@sananyuzb4 жыл бұрын
@@ignostik2328 Да. Но ассимптотика не считает количество памяти которую и чпользует программа, а показывает как используемые ресурсы изменяются в зависисости от входных данных. Мы можем создать массив из 16000 элементов, который поместит в себе все возможные символы. Соответственно ассимптотика использования памяти будет постоянная. Да, реальное использование памяти будет разное, но ассимптотика будет постоянная.
@alleycat1231231234 жыл бұрын
@@sananyuzb Не понял поинт про 16000 элементов. Насколько я понял Анатолий имеет в виду что будет просходить для строк: 1) 2^8 символов "a" 2) 2^16 символов "a" 3) 2^24 символов "a" 4) 2^32 символов "a" В этом случае между каждым из этих вариантов будет разница 1 байт, и память растет как O(log(n))
@user-mr-m123124 жыл бұрын
@@alleycat123123123 речь шла о случае, когда строки состоят из строчных латинских букв, в таком случае мы можем использовать массив из 26 элементов, где индекс массива соответствует букве алфавита, а значение - количеству вхождений буквы в строке. В этом случае затраты по памяти будут 26*4байта, то есть О(1), так как не зависят от размера строки.
@serhiisakhno845 жыл бұрын
А если использовать ord? Коды символов одной строки прибавляем к переменной, коды второй соответственно вычитаем?
@mixwheels5 жыл бұрын
что за глупость? причем тут ord? замени скобки на 1/0 и ищи решение
@minmanr5 жыл бұрын
Не будет работать, суммы кодов символов строк "bb" и "ac" равны, но они не являются анаграммами
@serhiisakhno845 жыл бұрын
@@mixwheels я имел ввиду задачу про анаграммы. Но да, моя ошибка. что не уточнил о какой задаче речь.
@serhiisakhno845 жыл бұрын
@@minmanr , утром я это уж тоже понял)
@hlystomv5 жыл бұрын
может сложение на xor заменить?
@ZzooD3 жыл бұрын
Какие типы данных могут быть в строке кроме char? 7:48
@gologames3 жыл бұрын
Мб wchar в C++
@ffelicius3 жыл бұрын
Тут скорее оговорка, не в строке, а во входной последовательности данных. Задача ведь искусственная. Обычно подобные задачи требуют не строки проверить на "анаграмность", а коллекции каких угодно объектов. Словари из объектов можно создать, а вот массивы объектами индексировать - не очень удобно)
@rusfungame2 жыл бұрын
А если я устроюсь в яндекс, футболки выдадут?
@tarasg71222 жыл бұрын
да, ты и будешь тем кто их будет выдавать)
@hlystomv5 жыл бұрын
1. Научить по видео писать алгоритмы невозможно. 2. Показать, как писать на доске алгоритм - бессмысленно. Таких видео очень много (лекции). Все они постановочные, а не документальные, в том смысле, что актер знает роль и пишет на доске заранее срежиссированный текст, делает постановочные ошибки и т.п. В реальности на собеседовании гормональный фон собеседуемого не такой, ведет он себя не так как демонстрирует видео, стремится не к тому, чтобы заученный текст с бумажки переписать, а к тому, чтобы сосредоточится и выдавить из себя хоть что-то. 3. Доска как инструмент нужна для обмена идеями. Для этого подходят рисунки, а не код.
@vladtokarev146Ай бұрын
Там память не О(n) в третьем случае, а O(2a), где а размер алфавита. Для строчных английских букв это 26
@Sevenvad4 жыл бұрын
То чувство, когда задача посложнее оказалась легче, чем задача полегче.
@rustyhex9899 Жыл бұрын
на литкоде такое постоянно... медиум иногда легче чем изи
@user-ty3tc4ee3z11 ай бұрын
Задача со скобочками на джаве в таком виде не принимается в вашем же контесте. не проходит по ограничению памяти (наверное слишком много занимает рекурсивный стек вызова). Убил всю голову, пока не нашел уже решенный вариант на гитхабе. и там алгоритм очень потный вышел. я его так и не понял
@andreyokoch5 жыл бұрын
I didn't get how one would decide after the first two examples that number of sequences grows like 2^n. 2^1 and 2^2 are not the numbers you get.
@MsCoolJohnny4 жыл бұрын
You should always start counting from zero ;)
@user-cq1zp5ui8h3 жыл бұрын
В третьем подходе к первой задаче тратится ведь константное количество памяти
@levp18013 жыл бұрын
мы создаём 4*n дополнительной памяти для хранения пар символ - количество,; а когда поправил зависит от того, сколько там памяти этот хипстерский метод берёт
@AlexosYou4 жыл бұрын
Вы говорите об оптимальном решении и пишете код на пайтоне со встроенными функциями, чей код закрыт. По крайней мере вы не говорите как реализованы counter или defaultdict и какова их производительность (асимптотика и память). Из очевидных вариантов defaultdict это либо массив, либо map. В обоих случаях для оценки памяти и производительности необходимо брать в расчёт не только длину входной последовательности N, но и размер алфавита M. Если defaultdict реализован через вектор, то получим время O(N) и память O(M), не считая, конечно, памяти для входных строк. Если defaultdict реализован через map, то получим время O(N*log(M)) и память O(M). Причём, если быть дотошным, тут память примерно в 2 раза будет больше, чем в случае с вектором. Однако автор прокритиковал решение через массивы, так что, наверное, defaultdict не реализован через них. Но и решение через map не даёт искомой асимптотики. Так что, объясните пожалуйста что такое это этот ваш defaultdict, иначе не говорите, что это эффективное решение.
@misana774 жыл бұрын
Во-первых: > defaultdict это либо массив, либо map map - это не структура данных, а абстрактный тип данных (АТД), который называется ассоциативный массив, пришедший из дискретной математики. С математического английского map переводится как "отображение". АТД map может быть реализован как минимум двумя способами, на примере С++: * std::map - по сложности операций оно соответствует бинарному дереву поиска (обычно в реализации используется красно-чёрное дерево) * std::unordered_map - по сложности операций оно соответствует хеш-таблице, причём реализованной методом цепочек для избежания коллизий Во-вторых: Сложность операций обычного dict соответствует сложности операций хеш-таблицы: wiki.python.org/moin/TimeComplexity При этом defaultdict является подклассом dict, переопределяющий часть поведения обычного dict, но не трогающий имплементацию остальных операций над ним: docs.python.org/3.8/library/collections.html#collections.defaultdict Автор использовал именно этот контейнер, чтобы избежать написание boilerplate-кода на проверку существования элемента или "поимку" KeyError, если элемента не существовало
@artpro91913 жыл бұрын
pep8? Не...
@nikitasatin3 жыл бұрын
зашел сюда за этим комментарием
@jeromewicks38962 жыл бұрын
зачем коду на доске pep8? это же не продакшн код, который нужно поддерживать
@MrBibiw2 жыл бұрын
@@jeromewicks3896 зачем говорить красивым и грамотным языком? мы же не на егэ
@MarkWaner2 жыл бұрын
@@MrBibiw Именно!
@dmitrymalygin33233 жыл бұрын
В работе нужны знания того как оптимизировать алгоритм? Или, как обычно, дворников заставляют сдавать кандидатский минимум?
@okke002 жыл бұрын
Чуваки просто копируют FAANG) Когда у тебя огромный поток кандидатов, то на собеседовании ты можешь, что угодно спрашивать. В реальной же работе ты с этим не столкнешься в 90% случаев
@jeromewicks38962 жыл бұрын
@@okke00 если формочки клепаешь, наверное не столкнёшься. Но если пишешь код, производительность которого более менее что-то значит, то хорошо как минимум понимать какая сложность используемого кода, чтобы не написать код с сложность n!
@okke002 жыл бұрын
@@jeromewicks3896 Производительность в реальных продакшн приложениях почти никогда не упирается в сложность алгоритмов, скорее в I\O операции, где оптимизируют совершенно другими методами. Плюс узкие места ищут не умозрительной оценкой сложности алгоритмов, а профилированием. Ну и да, любая нормальная quality gate тулза тебе подсветить откровенную дичь с экспоненциальной сложностью
@tarasg71222 жыл бұрын
@@okke00 1) Я при код ревью много раз встречал места где алгоритм можно оптимизировать. Как по скорости, так и по памяти. 2) Да, узкие места ищут профилированием. Но высокий скил в том и заключается чтобы такие узкие места создавать как можно реже. 3) Проблема в том что "quality gate тулза" работает уже с готовым кодом. Зачем в команде человек, который пишет говно и потом его переделывает (и то если сможет)? Поэтому вполне логично слабеньких отсекать еще на входе.
@okke002 жыл бұрын
@@tarasg7122 1) Далеко не всегда такие места надо оптимизировать. Одно дело когда правка тривиальна и по сути ничего не стоит, тут да, можно и оптимизнуть. Но если надо убить часа два времени, а то и больше, на оптимизацию алгоритма, который просто выглядит так, что его можно написать оптимальнее, то это явно не то чем стоит заниматься. 2.) Без профилирования практически невозможно находить реальные узкие места и от скилла тут мало что зависит(разве что скилл поможет совсем уж тривиальные ошибки не допускать) 3) А как тут поможет алгоритмическая секция? Любой олимпиадник ее пройдет с легкостью, при этом именно они чаще других пишут то, что в энтерпрайзе принято считать говнокодом.
@MikhailMatrosov3 жыл бұрын
5:29 Хм, а почему бы не написать просто return ca == cb?
@stttrannnik3 жыл бұрын
Время 4:50. return ca==cb исправляет ситуацию.
@kernelbug22942 жыл бұрын
Да, но тогда пришлось бы разбираться с более хитровывернутым примером, чтобы донести мысль о том, что иногда явная кодяра лучше неявной.
@LenaFelica_songwriter Жыл бұрын
почему Python, не понятно? на собесе тоже этот язык надо использовать, он что, самый основной вдруг?
@andreip93784 жыл бұрын
Можно было просто написать counter1 == counter2
@peso4ek Жыл бұрын
Нерекурсивно, тут ещё можно с помощью кодов Грея очень красивое решение выдать (скобочные последовательности).
@gerhardshreder2391 Жыл бұрын
я бы подумал, брать ли кандидата с таким кодом. Вот написал функцию, какие-то входные аргументы. А аннотации типов не написал. Что за cur, что за open, close??? С первого взгляда ничего не ясно.
@PrefixKrema Жыл бұрын
В начале рассуждения для языка python очень некоректные. Вы и так и так будете делать для строк копии данных, так как это неизменяемый тип файла. Так что собеседование например на позициюю питон разработчика превращается в какой то сюр. Вообще большая ошибка брать задачи из строготепизированных языков со стеком памяти, и натягивать их на языки где только управляемая куча. Понятно что питон тут чисто для наглядности как псевдоязык, но сам язык позволяет решать такие задачи проще и лаконичнее.
@total_anihilation2 жыл бұрын
Я не знаю питон, но я бы решил первую задачу так: Проходим в цикле по всем буквам первой строки, внутри цикла проходим по буквам второй строки. Если находим совпадение - удаляем обе буквы. В конце должны остаться две пустых строки.
@w1cked112 жыл бұрын
Что значит удаляем? Допустим, строки у вам из миллионов байт, тогда каждое такое удаление - это реаллокация и копирование памяти и это дорого. К тому же у вас выходит квадратичная сложность алгоритма, а тут - линейная, за счёт доп памяти на словари.
@total_anihilation2 жыл бұрын
@@w1cked11 ну не удаляем, а заменяем на пробел
@w1cked112 жыл бұрын
@@total_anihilation без разницы, строки иммутабельны в питоне и это будет уже новая скопированная строка. Плюс квадратичная сложность. В общем, потренируйтесь ещё, собес вы бы пока не прошли :)
@MarkWaner2 жыл бұрын
Можно еще вызывать рекурсивную функцию с параметрами ("(", 1, 0, n). Выигрыш очень маленький, но он есть
@tirsky4 жыл бұрын
ln - это натуральный, с основанием e, а log - это уже другое основание (например, 2)
@mapron14 жыл бұрын
С точки зрения О большого основание алгоритма не важно.
@vasya.k1n64 жыл бұрын
@@mapron1 в том то и дело, что обычно пишется log без указания основания. А ln - это уже с основанием, которое в данном случае, скорее всего, не подойдет
@user-zr6vw3kj1u4 жыл бұрын
@@vasya.k1n6 при оценке O-большое сложность берется с точностью до константы. log2(x)=ln(x)/ln(2) - формула перехода к новому основанию, где ln(2) - константа. Т.е. если пишется оценка O большое основание можно указывать вообще любое.
@MrAlexPhilippov3 жыл бұрын
Для O большое с асимптотическим приближением не важно.
@AntonioLopez8888 Жыл бұрын
Вроде задача была про все возможные последовательности.. Тут только одна ((())) . ???
@sermotАй бұрын
Требуется вывести все правильные скобочные последовательности длины 2 ⋅ n, упорядоченные лексикографически
@segreyfurt3 жыл бұрын
в первой задаче есть ошибка. Смотрим определение анаграммы "Слово или словосочетание, образованное путём перестановки букв, составляющих другое слово (или словосочетание)." Важно обратить внимание на слово "другое". Т.е. абв не является анаграммой абв
@segreyfurt3 жыл бұрын
во втором решении, я бы не стал перезатирать стандартную функцию open - это не ошибка в алгоритме, но так делать не надо
@manOfPlanetEarth2 жыл бұрын
@@segreyfurt что за функция open? у него есть только параметр open метода generate
@user-zg2bx5cb3d10 ай бұрын
@@manOfPlanetEarth нельзя использовать имена встроенных сущностей для переменных. `open` -- открытие файла
@user-zg2bx5cb3d10 ай бұрын
"другое" не значит "не равное". см разницу is/==
@valekprometey Жыл бұрын
Но ведь во второй задаче генерируется только 1 из возможных последовательностей - "((( )))" а требуются все.
@ezphantom Жыл бұрын
не так :)
@Scvairy5 жыл бұрын
Но ведь разность Counter-ов возвращает Counter, и никогда не будет равна 0 :(
Главным критерием было сохранение времени и отсутствие модификаций, так что не пойдет
@user-pw9sn6ih9e4 жыл бұрын
@@nazarbayev_university и где же мы модифицировали строки?
@KoScosss4 жыл бұрын
На сортировку O(nlogn) вместо O(n) уйдет
@dmitrijkarmatskij21244 жыл бұрын
Для анограм можно посчитать hash по алгоритму hash += *str++
@dmitrijkarmatskij21244 жыл бұрын
Очень сложный юмор
@gologames3 жыл бұрын
Нельзя. Пример "abc" и "aad"
@dmitrijkarmatskij21243 жыл бұрын
@@gologames Я же сказал очень сложный юмор
@gologames3 жыл бұрын
@@dmitrijkarmatskij2124 Я подозревал. Хорошо тогда
@ZeksaitАй бұрын
вроде так нельзя переменные называть. aSet
@OStrekalovsky5 жыл бұрын
Алгоритм №4: O(n) по скорости и O(1) по памяти - заводим массив размера всех возможных букв алфавита, где в i-ом элементе будет храниться количество таких букв. Проходя по первой строке увеличиваем счетчик букв в этом массиве, проходя по второй строке - уменьшаем счётчик числа повторений этих букв. Если массив стал из нулей, то строки - анаграммы.
@nevmem6715 жыл бұрын
Не верная оценка памяти, так как в описанном Вами решении количество используемой памяти О(С), где С - размер алфавита, чем нельзя пренебрегать
@FakePlv5 жыл бұрын
Хм. А время, которое уйдет на формирование массива с алфавитом, обеспечение уникальности символов в нем, а проверка массива на нули? Это же вроде всё время займет.
@user-gk1ih1dz8d5 жыл бұрын
Время растет линейно, а расход памяти не растет, поэтому асимптотическая сложность записана верно
@nevmem6715 жыл бұрын
@@user-gk1ih1dz8d Очень поверхностно оценивать время работы программы описанным Вами образом, потому что размер алфавита может быть не ограничен только одним языком или например только таблицей ASCII, а быть например размером во весь лонг т. е. порядка 2 в 64 степени значений, тогда выделение такого объёма памяти нельзя оценивать как константу
@nevmem6715 жыл бұрын
@@FakePlv Да, займёт причём ровно О(С) так как проверку на нули можно осуществлять с помощью поддерживая одного числа, которое будет значить количество нулей в массиве на данной итерации, такую величину пересчитывать очень просто, так как на каждой итерации изменяется ровно один элемент такого массива
@RusShbreak1 Жыл бұрын
4:42 - Зачем вычитать словари, если их можно сравнить и как они могут вычитаться, если питон это не поддерживает? Напутано с множествами. И соответственно не понятно, как там неправильно работает Counter - мега сложный питон функционал, который автор следом изобретает и сам.
@aleksandr30944 жыл бұрын
Как я решил на пхп (реализацию автора не видел) function anag() { $str1 = str_split('asdasdasdasdasd'); $str2 = str_split('dsadasdasdasdas'); if (count($str1) === count($str2)) { sort($str1); sort($str2); return $str1 == $str2; } return false; }
@aleksandr30944 жыл бұрын
Между реализацией в комменте и этой: function ang2() { if (splitt('asdasdasdasdasd') == splitt('dsadasdasdasdas')) return true; return false; } function splitt(string $str) { $res = []; for ($i = 0; $i
@niklkelbon36623 жыл бұрын
Мне кажется мой алгоритм получше для последней задачи, не идеально конечно, но ни одного вызова зря, меньше передаваемых параметров, можно ещё строку сразу делать 2 N размера, чтобы не прибавлять, но по сути вот: С++ void wow(int N, std::string currentString = std::string(), int openCount = 0) { if ((N == 0) && (openCount == 0)) { std::cout
@BuffyKek Жыл бұрын
Я вот в 11 классе сейчас и смотрю строчки кода он пишет знакомые и понятные, а говорит что-то максимально страшное
@TONHEAD72 жыл бұрын
Внимание, в решении второй задачи ашипка ) Если n == 0 то выводится на печать пустая строка, а это неправильно, пустая строка не является корректной комбинацией скобок. Возьмите меня на работу, лол
@Kamapec4 жыл бұрын
Разве так не будет быстрее и без доп.средств(sort, counter): str1 = "hhelloo" str2 = "oollehh" str2 = str2[::-1] print(str2 == str1) ?
@zhalgasnurakhmetov96464 жыл бұрын
Вам нужно почитать что такое анаграммы. Ваш код проверяет является ли одна строка другой , но заданной в обратном порядке.
@Kamapec4 жыл бұрын
@@zhalgasnurakhmetov9646 Да, спасибо, разобрался, действительно, не понял задание сначала )
@aikolkoikelov75143 жыл бұрын
Это код для определения палиндрома
@zugzug90 Жыл бұрын
Да кто такая эта ваша симметрия?
@ELLA-fq6lo3 жыл бұрын
14:20, мне вот просто интересно, неужели я такой тупой, и в яндексе сидят гениальные люди, потому что, когда я встретил эту задачу, мне понадобилось где-то около 5-6 часов и лишняя пара нервов, чтобы найти решение. Но дело в том, что если гуглить, то решение найти можно за пару минут. И у меня возникает вопрос, на кой фиг просить на собеседовании писать подобное карандашом, если в реале, ты просто пойдешь гуглить. Я уверен, что встреться эта задача этому челу через год, он бы взял и пошел гуглить, так почему отбор кандидатов делается по тому, сколько ты тупо вызубришь и насколько тебе повезет, а не по твоим реальным умственным способностям или знаниям тех или иных инструментов разработки???
@ELLA-fq6lo3 жыл бұрын
А еще кстати, этот код не проходит проверку на их же тестах(язык котлин, ни одной лишней строчки), выбрасывает, что лимит памяти исчерпан)))
@jeromewicks38962 жыл бұрын
@@ELLA-fq6lo Если лимит памяти исчерпан - это не проблема алгоритма, а проблема Котлина и JVM. Напиши на чём-нибудь, что не тратит так много памяти
@ELLA-fq6lo2 жыл бұрын
@@jeromewicks3896 Вот, сука, как я сразу не додумался до этого, пойду на ассемблере напишу
@MrSsergb2 жыл бұрын
Он и так читает по бумажке с запинками
@total_anihilation2 жыл бұрын
Смысл не в том, чтобы ты загуглил решение. Смысл в том, чтобы проверить, способен ли ты решить сам, то есть, насколько хорошо у тебя работают мозги. Зубрить не надо - это сразу будет видно, когда ты выдаешь заученные решения. Собеседующему важно увидеть, как ты сам думаешь.
@nihttoter32408 ай бұрын
Первая задача (str1, str2) => { const getHash = (str) => str.split('').sort().join() return getHash(str1) === getHash(str2) }
@mm_mistermaks2 жыл бұрын
питон выглядит так будто на нем алгоритмы писать проще в 10 раз чем на java
@user-nq4fx4jg8o2 жыл бұрын
почему в анаграммах нельзя сравнивать первый символ а с последним символом b в цикле, сдвигая соответственно итератор по а вперед, по b назад, если символы равны, и предварительно проверив на равенство длины строк (на плюсах бы я так и сделал, питон не знаю)
@jeromewicks38962 жыл бұрын
Потому что если слова W1 и W2 являются анаграммами, то не всегда W1 == reversed(W2) (и наоборот). Например, слова eat и tea - анаграммы, но eat != reversed(tea) = aet
@user-nq4fx4jg8o2 жыл бұрын
@@jeromewicks3896 а, точно, спасибо за ответ )
@RusShbreak1 Жыл бұрын
@@jeromewicks3896 Да eat != reversed(tea), т.к. reversed(tea) == "aet". Но в задаче на врят ли имелись ввиду анаграммы в литературном смысле, т.е. не важно сходится конкретная строка в реальное слово языка или нет.
@andreyokoch5 жыл бұрын
For the first function to work one should first do: from collections import defaultdict
@apogo782 жыл бұрын
Не будем использовать сложное встроенное встроенное в язык средство. Будем использовать другое сложное встроенное в язык средство (>_
Блин, а я решил эту задачу построив граматику, сделал правила прождения цепочек и на шаге n отсекал нетерминальные цепочки... а тут на тебе.. открыл закрыл... 🤣🤣🤣
@maksimkovtun95172 жыл бұрын
Я бы первую задачу решил так: class YandexTest(): def is_anagramma(self, a: str, b: str) -> bool: bb = list(b) for x in a: try: bb.remove(x) except: return False return not bool(bb)
@MrAlexPhilippov3 жыл бұрын
char ['kær] (от англ. character) - символ
@a_pifagor2 жыл бұрын
Господи, какая скука.
@askarsaitov29134 жыл бұрын
шлак
@user-xz8dd1xn4o3 жыл бұрын
8:02 в последней строчке произойдёт сравнение ссылок на словари, а не сравнение словарей. Всегда будет False
@ilyapikulin28843 жыл бұрын
сравнение ссылок происходит по оператору `is`. оператор `==` вызывает метод `__eq__()`.
@mixwheels5 жыл бұрын
Скучная и неинтересная задача. Я ожидал какого-то иного решения, чем банальная рекурсия, да еще и с передачей строк в стеке! Думаю, есть решение, когда в стек строку не кладут, последовательно меняя в единой базовой строке парные скобки. Вы его даже не удосужились придумать. Накатал на пхп за 15 минут, включая отладку. На бумаге (на собеседовании) проверить алгоритм вряд ли возможно в адекватное кол-во времени. На просчет рекурсии на бумаге уйдет много времени.
@nevmem6715 жыл бұрын
Описанным в видео способом решить задачу, на мой взгляд, не сложно, так как именно это решение обычно первым приходит в голову, к тому же строки в Python иммутабельный тип и, возможно, поэтому была выбрана такая реализация. Написание кода на бумаге это нормальная практика, поскольку, как было сказано в видео, не обязательно помнить все сигнатуры функций, важно правильно придумать, изложить и доказать адгоритм, который на Ваш взгляд является оптимальным для решения данной задачи. Менять скобки местами также может иметь худшую ассимптотику, чем предложенное решение, так как чтобы найти правильную пару скобок, возможно придётся обойти всю строку
@mixwheels5 жыл бұрын
@@nevmem671 Я о другом. Повторю свою мысль. На бумаге накатать рекурсию - элементарная задача. Но практически невозможно отладить на бумаге. Т.к. наличие нескольких if делают поведение не предсказуемым. При наличии компа и возможности быстро запустить, увидеть ошибку, внести коррективы - 15 минут. Без компа - проверки рекурсии придется считать на бумаге, что чревато ошибками и огромным временем. Даже при правильном написании всех if в рекурсии нет шансов на бумаге что-либо проверить. Вывод: это не лучшая задача на алгоритмы для собеседования. Да, кстати, у меня есть решение без рекурсии линейным циклом - см отдельный коммент.
@tirsky4 жыл бұрын
В том же ролике про собеседование в Google, на сортировку массива, гораздо интереснее рассказывается про то, как надо вести себя на интервью и поэтапно рассматривается решение задачи.
@TheZloymedved4 жыл бұрын
15 минут? да уж, программист ты так себе
@user-zi7ge2uf6q Жыл бұрын
Мда) а вас не смущает, что counter вероятнее всего считая количества вхождений символа для каждой буквы будет пробегаться по всей строке? И так каждый раз? А это n в квадрате сложность. Что же касается кода, если он считает количество уникальных символов, а затем вы сравниваете общую длину, то что вы скажете о таких строках? abb aab В общем я думал к вам регнуться на контест, но неприятно удивлен.
@rednil82422 ай бұрын
как же яндекс переживет потерю такого ценного кандидата