1. Научить по видео писать алгоритмы невозможно. 2. Показать, как писать на доске алгоритм - бессмысленно. Таких видео очень много (лекции). Все они постановочные, а не документальные, в том смысле, что актер знает роль и пишет на доске заранее срежиссированный текст, делает постановочные ошибки и т.п. В реальности на собеседовании гормональный фон собеседуемого не такой, ведет он себя не так как демонстрирует видео, стремится не к тому, чтобы заученный текст с бумажки переписать, а к тому, чтобы сосредоточится и выдавить из себя хоть что-то. 3. Доска как инструмент нужна для обмена идеями. Для этого подходят рисунки, а не код.
@-MaCkRage-28 күн бұрын
Яндекс🤪
@MajinSaha Жыл бұрын
Так, а где тесты перед решением первой задачи? В первом видео на тесты же напирали.
@protasovse2 жыл бұрын
Зачем в анаграммах находить разницу Counter-ов, если можно их сравнить (Conter1==Counter2)?
@RusShbreak1 Жыл бұрын
Да! И более того, как можно ее найти, если оператор вычитания не поддерживается диктом...
@vladtokarev1467 ай бұрын
Там память не О(n) в третьем случае, а O(2a), где а размер алфавита. Для строчных английских букв это 26
@FakePlv5 жыл бұрын
Мм, один момент не ясен: был написан тест: parents(3)== { "((( )))", "()()()", "(())()", "()(())", "(()())" }. Но код на доске генерирует только "((( )))", так ведь? Более того в статье Яндекса на хабре про эту задачу также сказано "Вывести последовательности в лексикографическом порядке(правильный алгоритм по-умолчанию выводит их в нужном порядке)" и указана ссылка на это видео как разбор задачи. Получается то, что на доске попроще будет, чем то что на собеседовании по словам из статьи.
@nevmem6715 жыл бұрын
Нет не так код на доске генерирует ровно то, что нужно то есть НЕ одну последовательность, там же рекурсивные запуски, которые например уже на второй итерации могут на префикс построить строки "((" и "()", так как эти последовательности никак не противоречат написанному коду
@FakePlv5 жыл бұрын
@@nevmem671 Да, вы абсолютно правы, я был невнимателен(забыл вернуться к первому вызову в стеке). Вы писали ниже, что это решение первым приходит в голову. Мне же первым в голову пришло создание класса или же дерево. Расскажите, как вы понимаете, что начать рассуждения надо с рекурсии?
@slavanikulin80694 жыл бұрын
@@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 })
@FakePlv4 жыл бұрын
@@slavanikulin8069 Уже не помню, честно говоря, о чем шла речь, но да рекурсия обычно напрашивается первой, избавиться от неё обычно проблемнее, чем её применить. Как раз год назад пытался пройти контест, где было 4 олимпиадные задачи из 6(вроде шесть задач было:) ).. короче до собеседования дело даже не дошло)) У меня много вопросов возникало про адекватность формулировок, но, отвечали мне на них - никак(сам дурак). Была там задачка и про поиск множителей, где нужно было найти нужную комбинацию для заданного произведения. Алгоритм дерева был весьма кстати, правда, обходить пришлось без рекурсии, т.к. не проходил по времени. Разница в скорости алгоритма значительна, например 2ms/636Kb против рекурсивных 56ms/896Kb(метрика контеста). Так что да, в здравом уме и адекватной обстановке, рекурсия не должна приходить в голову, однако на собеседовании(до которого дело дойдет только у олимпиадников), проще сделать ей и решить задачу, чем допускать мелкие ошибки и ожидать подсказок от интервьюера. По поводу крика души. У меня тоже есть, что сказать. Жаль, конечно, что не удалось устроиться в Яндекс, хотя может оно и к лучшему. Скажу одно, у каждого свои способности и лучшие стороны, если Яндекс планирует использовать лишь скорость применение шаблона и их объем в голове разработчика, то когда-нибудь это аукнется. В универе была группа по спортивному программированию, которая занимала призовые места на мировых олимпиадах, только вот экзамен по программированию сдавал за них я, ибо по какой-то причине им не удалось осилить задачки препода. Я это к тому, что не все задачи требуют хитромудрую формулу для поиска части окружности из миллиарда окружностей, и шаблоны не помогают найти решение проблемы, они лишь пытаются её решить стандартным способом. Чтобы решать проблему надо думать. Чтобы использовать шаблон, надо его помнить. Сейчас я системный программист, занимаюсь разработкой ОС в коммерческой фирме, есть тонна задач, которые не требуют математики, но требуют очень развитой интуиции, смекалки и аналитического склада ума, что бы быстро уметь анализировать тонны опенсурсных систем и чужого кода на всевозможных языках. Наверное, таким не место в Яндексе, раз у таких дело даже до собеседования не доходит(да, разрабочик интерфейсов каких-нибудь тоже должен решить олимпиадные задачи). ps: пытался решать задачи честно - самостоятельно, не заглядывая в готовые алгоритмы.
@slavanikulin80694 жыл бұрын
Kernel Plevitsky Справедливости ради стоит сказать, что весь этот алгоритмически-олимпиадный ад стоит того, тк в Яндексе очень благоприятная среда, способствующая быстрому росту. Но если не получится пройти, то ничего страшного) Здорово, рад за вас, что нашли своё призвание и место!
@AlexosYou5 жыл бұрын
Вы говорите об оптимальном решении и пишете код на пайтоне со встроенными функциями, чей код закрыт. По крайней мере вы не говорите как реализованы 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, если элемента не существовало
@alloyoshi3 жыл бұрын
Проблема в том, что задаются на собеседованиях задачи В РАЗЫ сложнее, чем упомянутые.
@sevenb1t2 жыл бұрын
Решай leetcode - там есть задачи сопостовимой сложности. Вопрос тренировки - без подготовки, конечно, пройти сложно алгоритмический уровень.
@whitehaker2 жыл бұрын
Было бы странно, если бы на собесах давали задачи такого уровня, на видео показан пример процесса и типичные ошибки. Задачу со скобками мне дали в седьмом классе, при отборе на школьную олимпиаду по программированию, как-раз на листке писал)
@dmitrypetrov8491 Жыл бұрын
В основном задачи на собеседованиях задаются уровня easy-medium с leetcode. Но некоторые кандидаты и это решить не могут.
@user-chf7z61vnd6h8v Жыл бұрын
@@dmitrypetrov8491 зачем это человеку, который пишет фронт, и может ещё бэк на уровне обработать входящие запросы и сделать запрос в БД? Более 5 лет работу фулстеком с јѕ ни разу эта олимпиалная бредятина не пригодилась. Если ты пишешь игры или что-то требующее математики, то может оно и нужно, но большинству это нахер не всралось для веба, только мозги на собесе иметь собеседуемому
@Prof-Shor Жыл бұрын
@@user-chf7z61vnd6h8v Воистину!
@sananyuzb5 жыл бұрын
По первой задаче маленькая ошибка : Для 3 варианта решения задачи (про анаграммы) - использование памяти констатное - O(1) - т.к набор букв всегда постоянный - т.е если у нас строка состоит из сторчных латиских букв - то длина массива будет 26. Т.е. вне зависимости от того насколько длинная у нас строка - размер массива всегда будет одинаковый, т.е размер массива не зависит от входного параметра, соответственно сложность по памяти O(1).
@ignostik23285 жыл бұрын
Вы были бы абсолютно правы, если бы не еще одно маленькое обстоятельство: кол-во памяти для хранение счетчиков количества символов все-таки зависит от длины входных данных, а именно для хранения числа n нужно log_2(n) с округлением бит информации. Поэтому с увеличением n, затраты по памяти также растут (хотя на данный момент те порядки, при которых рост памяти будет существенным, просто недостижимы). Поэтому, строго говоря, сложность по памяти (log_2(n)).
@sananyuzb5 жыл бұрын
@@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), так как не зависят от размера строки.
@ВладимирТерещенко-и7ц3 жыл бұрын
У второй задачи пропущена секция с определением сложности алгоритма
@okke003 жыл бұрын
Никогда не понимал зачем писать код на доске? Почему не на бересте например или долотом на камне высекать? Все одно с реальной работой не пересекается
@uvencosuper34716 ай бұрын
Если экстраполировать дальше, то почему бы не разрешить подгугливать синтаксис особо редковстречающихся конструкций, типа предполагается, что стековерфлоу в яндексе отключил злой одмин что ли?
@kerzhemanov2 ай бұрын
@@uvencosuper3471 за синтаксис обычно не минусуют. Главное чтобы решение было верным, и соискатель мог объяснить как оно работает.
@__dot35063 ай бұрын
Основные ошибки / корнеры: - Неправильное представление данных. Данные могут быть представлены некорректно определенной структурой. Пример: превращение строки во множество убирает повторяющиеся символы. - Асимметрия данных: следует из предыдущего. - Непонимание работы утилит, структур и методов языка - будь внимателен. Иногда стоит написать что-то своим кодом, чтобы показать понимание работы. - Всегда начинайте задачу с тесткейсов для понимания условий и работы программы - При задаче на создание строк: начинай думать о том, что можно приписать / удалить из строки для достижения ответа. - Быстрые исправления не всегда хороши. - Пытайся написать / исправить сложную функцию так, чтобы в ней не было лишних вызовов - Не мутируй состояние аргументов внутри рекурсивной функции, если точно не уверен, что это не повредит алгоритму
@РоманГалушка-ж2е Жыл бұрын
Задача со скобочками на джаве в таком виде не принимается в вашем же контесте. не проходит по ограничению памяти (наверное слишком много занимает рекурсивный стек вызова). Убил всю голову, пока не нашел уже решенный вариант на гитхабе. и там алгоритм очень потный вышел. я его так и не понял
@rusfungame3 жыл бұрын
А если я устроюсь в яндекс, футболки выдадут?
@tarasg71223 жыл бұрын
да, ты и будешь тем кто их будет выдавать)
@dmitrymalygin33233 жыл бұрын
В работе нужны знания того как оптимизировать алгоритм? Или, как обычно, дворников заставляют сдавать кандидатский минимум?
@okke003 жыл бұрын
Чуваки просто копируют FAANG) Когда у тебя огромный поток кандидатов, то на собеседовании ты можешь, что угодно спрашивать. В реальной же работе ты с этим не столкнешься в 90% случаев
@jeromewicks38963 жыл бұрын
@@okke00 если формочки клепаешь, наверное не столкнёшься. Но если пишешь код, производительность которого более менее что-то значит, то хорошо как минимум понимать какая сложность используемого кода, чтобы не написать код с сложность n!
@okke003 жыл бұрын
@@jeromewicks3896 Производительность в реальных продакшн приложениях почти никогда не упирается в сложность алгоритмов, скорее в I\O операции, где оптимизируют совершенно другими методами. Плюс узкие места ищут не умозрительной оценкой сложности алгоритмов, а профилированием. Ну и да, любая нормальная quality gate тулза тебе подсветить откровенную дичь с экспоненциальной сложностью
@tarasg71223 жыл бұрын
@@okke00 1) Я при код ревью много раз встречал места где алгоритм можно оптимизировать. Как по скорости, так и по памяти. 2) Да, узкие места ищут профилированием. Но высокий скил в том и заключается чтобы такие узкие места создавать как можно реже. 3) Проблема в том что "quality gate тулза" работает уже с готовым кодом. Зачем в команде человек, который пишет говно и потом его переделывает (и то если сможет)? Поэтому вполне логично слабеньких отсекать еще на входе.
@okke003 жыл бұрын
@@tarasg7122 1) Далеко не всегда такие места надо оптимизировать. Одно дело когда правка тривиальна и по сути ничего не стоит, тут да, можно и оптимизнуть. Но если надо убить часа два времени, а то и больше, на оптимизацию алгоритма, который просто выглядит так, что его можно написать оптимальнее, то это явно не то чем стоит заниматься. 2.) Без профилирования практически невозможно находить реальные узкие места и от скилла тут мало что зависит(разве что скилл поможет совсем уж тривиальные ошибки не допускать) 3) А как тут поможет алгоритмическая секция? Любой олимпиадник ее пройдет с легкостью, при этом именно они чаще других пишут то, что в энтерпрайзе принято считать говнокодом.
@SiarheiAkhramenia3 ай бұрын
PEP8 попросил передать вам привет! ;)
@ZzooD3 жыл бұрын
Какие типы данных могут быть в строке кроме char? 7:48
@gologames3 жыл бұрын
Мб wchar в C++
@ffelicius3 жыл бұрын
Тут скорее оговорка, не в строке, а во входной последовательности данных. Задача ведь искусственная. Обычно подобные задачи требуют не строки проверить на "анаграмность", а коллекции каких угодно объектов. Словари из объектов можно создать, а вот массивы объектами индексировать - не очень удобно)
@Sevenvad5 жыл бұрын
То чувство, когда задача посложнее оказалась легче, чем задача полегче.
@rustyhex98992 жыл бұрын
на литкоде такое постоянно... медиум иногда легче чем изи
@tirsky5 жыл бұрын
ln - это натуральный, с основанием e, а log - это уже другое основание (например, 2)
@mapron15 жыл бұрын
С точки зрения О большого основание алгоритма не важно.
@vasya.k1n64 жыл бұрын
@@mapron1 в том то и дело, что обычно пишется log без указания основания. А ln - это уже с основанием, которое в данном случае, скорее всего, не подойдет
@ИванПавлов-г4т6э4 жыл бұрын
@@vasya.k1n6 при оценке O-большое сложность берется с точностью до константы. log2(x)=ln(x)/ln(2) - формула перехода к новому основанию, где ln(2) - константа. Т.е. если пишется оценка O большое основание можно указывать вообще любое.
@MrAlexPhilippov4 жыл бұрын
Для O большое с асимптотическим приближением не важно.
@stttrannnik3 жыл бұрын
Время 4:50. return ca==cb исправляет ситуацию.
@kernelbug22942 жыл бұрын
Да, но тогда пришлось бы разбираться с более хитровывернутым примером, чтобы донести мысль о том, что иногда явная кодяра лучше неявной.
@MikhailMatrosov4 жыл бұрын
5:29 Хм, а почему бы не написать просто return ca == cb?
@artpro91914 жыл бұрын
pep8? Не...
@nikitasatin3 жыл бұрын
зашел сюда за этим комментарием
@jeromewicks38963 жыл бұрын
зачем коду на доске pep8? это же не продакшн код, который нужно поддерживать
@MrBibiw3 жыл бұрын
@@jeromewicks3896 зачем говорить красивым и грамотным языком? мы же не на егэ
@MarkWaner3 жыл бұрын
@@MrBibiw Именно!
@МаксимЗозуля-м2р3 жыл бұрын
А есть такая же футботка, только немного поярче?)
@gerhardshreder23912 жыл бұрын
я бы подумал, брать ли кандидата с таким кодом. Вот написал функцию, какие-то входные аргументы. А аннотации типов не написал. Что за cur, что за open, close??? С первого взгляда ничего не ясно.
@segreyfurt3 жыл бұрын
в первой задаче есть ошибка. Смотрим определение анаграммы "Слово или словосочетание, образованное путём перестановки букв, составляющих другое слово (или словосочетание)." Важно обратить внимание на слово "другое". Т.е. абв не является анаграммой абв
@segreyfurt3 жыл бұрын
во втором решении, я бы не стал перезатирать стандартную функцию open - это не ошибка в алгоритме, но так делать не надо
@manOfPlanetEarth2 жыл бұрын
@@segreyfurt что за функция open? у него есть только параметр open метода generate
@КириллКириллович Жыл бұрын
@@manOfPlanetEarth нельзя использовать имена встроенных сущностей для переменных. `open` -- открытие файла
@КириллКириллович Жыл бұрын
"другое" не значит "не равное". см разницу is/==
@Xeem_PadАй бұрын
@@КириллКириллович можно, просто не стоит. В таких случаях пишут 'open_'
@LenaFelica_songwriter Жыл бұрын
почему Python, не понятно? на собесе тоже этот язык надо использовать, он что, самый основной вдруг?
@MajesticNut3 жыл бұрын
Как правильно вычислить временную сложность для последней задачи со скобками?
@aslanator3 жыл бұрын
поидеи линейная
@MarkWaner3 жыл бұрын
@@aslanator точно не линейная. Экспоненциальная с базой экспоненты < 4 и > 2 Ну или суб-экспоненциальная. Там непросто вычислить из-за условий
@valekprometey2 жыл бұрын
Но ведь во второй задаче генерируется только 1 из возможных последовательностей - "((( )))" а требуются все.
@ezphantom2 жыл бұрын
не так :)
@uncle-xxi4 жыл бұрын
так там скрытых вычислений хватает :) даром что коротко и красиво :)
@Andrei-t5w3 жыл бұрын
Тут же O нотация только интересна
@Scvairy5 жыл бұрын
Но ведь разность Counter-ов возвращает Counter, и никогда не будет равна 0 :(
@gologames3 жыл бұрын
Там len() от Counter
@peso4ek Жыл бұрын
Нерекурсивно, тут ещё можно с помощью кодов Грея очень красивое решение выдать (скобочные последовательности).
@ЖеняПетров-ч2м2 жыл бұрын
Спасибо, видео помогло разобраться с рекурсией при помощи визуализатора, добавил return после 3го if-a так нагляднее.
@PrefixKrema2 жыл бұрын
В начале рассуждения для языка python очень некоректные. Вы и так и так будете делать для строк копии данных, так как это неизменяемый тип файла. Так что собеседование например на позициюю питон разработчика превращается в какой то сюр. Вообще большая ошибка брать задачи из строготепизированных языков со стеком памяти, и натягивать их на языки где только управляемая куча. Понятно что питон тут чисто для наглядности как псевдоязык, но сам язык позволяет решать такие задачи проще и лаконичнее.
@OStrekalovsky5 жыл бұрын
Алгоритм №4: O(n) по скорости и O(1) по памяти - заводим массив размера всех возможных букв алфавита, где в i-ом элементе будет храниться количество таких букв. Проходя по первой строке увеличиваем счетчик букв в этом массиве, проходя по второй строке - уменьшаем счётчик числа повторений этих букв. Если массив стал из нулей, то строки - анаграммы.
@nevmem6715 жыл бұрын
Не верная оценка памяти, так как в описанном Вами решении количество используемой памяти О(С), где С - размер алфавита, чем нельзя пренебрегать
@FakePlv5 жыл бұрын
Хм. А время, которое уйдет на формирование массива с алфавитом, обеспечение уникальности символов в нем, а проверка массива на нули? Это же вроде всё время займет.
@РомаБерендеев-ш3з5 жыл бұрын
Время растет линейно, а расход памяти не растет, поэтому асимптотическая сложность записана верно
@nevmem6715 жыл бұрын
@@РомаБерендеев-ш3з Очень поверхностно оценивать время работы программы описанным Вами образом, потому что размер алфавита может быть не ограничен только одним языком или например только таблицей ASCII, а быть например размером во весь лонг т. е. порядка 2 в 64 степени значений, тогда выделение такого объёма памяти нельзя оценивать как константу
@nevmem6715 жыл бұрын
@@FakePlv Да, займёт причём ровно О(С) так как проверку на нули можно осуществлять с помощью поддерживая одного числа, которое будет значить количество нулей в массиве на данной итерации, такую величину пересчитывать очень просто, так как на каждой итерации изменяется ровно один элемент такого массива
@AntonioLopez88882 жыл бұрын
Вроде задача была про все возможные последовательности.. Тут только одна ((())) . ???
@sermot7 ай бұрын
Требуется вывести все правильные скобочные последовательности длины 2 ⋅ n, упорядоченные лексикографически
@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.
Главным критерием было сохранение времени и отсутствие модификаций, так что не пойдет
@АндрейАлексеев-х3д4 жыл бұрын
@@nazarbayev_university и где же мы модифицировали строки?
@KoScosss4 жыл бұрын
На сортировку O(nlogn) вместо O(n) уйдет
@vdrmkr Жыл бұрын
А почему N log N если после сортировки нужно будет ещё сравнить строки? Это уже O(N)
@vadipp4 ай бұрын
O(n log(n)) + O(n) это та же оценка что и O(n log(n))
@bipolar-fox3 жыл бұрын
Я не знаю питон, но я бы решил первую задачу так: Проходим в цикле по всем буквам первой строки, внутри цикла проходим по буквам второй строки. Если находим совпадение - удаляем обе буквы. В конце должны остаться две пустых строки.
@w1cked113 жыл бұрын
Что значит удаляем? Допустим, строки у вам из миллионов байт, тогда каждое такое удаление - это реаллокация и копирование памяти и это дорого. К тому же у вас выходит квадратичная сложность алгоритма, а тут - линейная, за счёт доп памяти на словари.
@bipolar-fox3 жыл бұрын
@@w1cked11 ну не удаляем, а заменяем на пробел
@w1cked113 жыл бұрын
@@bipolar-fox без разницы, строки иммутабельны в питоне и это будет уже новая скопированная строка. Плюс квадратичная сложность. В общем, потренируйтесь ещё, собес вы бы пока не прошли :)
@ДаниилГолов-к5й3 жыл бұрын
В третьем подходе к первой задаче тратится ведь константное количество памяти
@levp18013 жыл бұрын
мы создаём 4*n дополнительной памяти для хранения пар символ - количество,; а когда поправил зависит от того, сколько там памяти этот хипстерский метод берёт
@RusShbreak1 Жыл бұрын
4:42 - Зачем вычитать словари, если их можно сравнить и как они могут вычитаться, если питон это не поддерживает? Напутано с множествами. И соответственно не понятно, как там неправильно работает Counter - мега сложный питон функционал, который автор следом изобретает и сам.
@serhiisakhno845 жыл бұрын
А если использовать ord? Коды символов одной строки прибавляем к переменной, коды второй соответственно вычитаем?
@mixwheels5 жыл бұрын
что за глупость? причем тут ord? замени скобки на 1/0 и ищи решение
@minmanr5 жыл бұрын
Не будет работать, суммы кодов символов строк "bb" и "ac" равны, но они не являются анаграммами
@serhiisakhno845 жыл бұрын
@@mixwheels я имел ввиду задачу про анаграммы. Но да, моя ошибка. что не уточнил о какой задаче речь.
@serhiisakhno845 жыл бұрын
@@minmanr , утром я это уж тоже понял)
@hlystomv5 жыл бұрын
может сложение на xor заменить?
@nihttoter3240 Жыл бұрын
Первая задача (str1, str2) => { const getHash = (str) => str.split('').sort().join() return getHash(str1) === getHash(str2) }
@MarkWaner3 жыл бұрын
Можно еще вызывать рекурсивную функцию с параметрами ("(", 1, 0, n). Выигрыш очень маленький, но он есть
@alexk39292 жыл бұрын
Эх, а потом перекладывать жсоны….
@dmitrijkarmatskij21244 жыл бұрын
Для анограм можно посчитать hash по алгоритму hash += *str++
@dmitrijkarmatskij21244 жыл бұрын
Очень сложный юмор
@gologames3 жыл бұрын
Нельзя. Пример "abc" и "aad"
@dmitrijkarmatskij21243 жыл бұрын
@@gologames Я же сказал очень сложный юмор
@gologames3 жыл бұрын
@@dmitrijkarmatskij2124 Я подозревал. Хорошо тогда
@ELLA-fq6lo3 жыл бұрын
14:20, мне вот просто интересно, неужели я такой тупой, и в яндексе сидят гениальные люди, потому что, когда я встретил эту задачу, мне понадобилось где-то около 5-6 часов и лишняя пара нервов, чтобы найти решение. Но дело в том, что если гуглить, то решение найти можно за пару минут. И у меня возникает вопрос, на кой фиг просить на собеседовании писать подобное карандашом, если в реале, ты просто пойдешь гуглить. Я уверен, что встреться эта задача этому челу через год, он бы взял и пошел гуглить, так почему отбор кандидатов делается по тому, сколько ты тупо вызубришь и насколько тебе повезет, а не по твоим реальным умственным способностям или знаниям тех или иных инструментов разработки???
@ELLA-fq6lo3 жыл бұрын
А еще кстати, этот код не проходит проверку на их же тестах(язык котлин, ни одной лишней строчки), выбрасывает, что лимит памяти исчерпан)))
@jeromewicks38963 жыл бұрын
@@ELLA-fq6lo Если лимит памяти исчерпан - это не проблема алгоритма, а проблема Котлина и JVM. Напиши на чём-нибудь, что не тратит так много памяти
@ELLA-fq6lo3 жыл бұрын
@@jeromewicks3896 Вот, сука, как я сразу не додумался до этого, пойду на ассемблере напишу
@bipolar-fox3 жыл бұрын
Смысл не в том, чтобы ты загуглил решение. Смысл в том, чтобы проверить, способен ли ты решить сам, то есть, насколько хорошо у тебя работают мозги. Зубрить не надо - это сразу будет видно, когда ты выдаешь заученные решения. Собеседующему важно увидеть, как ты сам думаешь.
@Kotofosonline8 ай бұрын
@@bipolar-fox Почему бы тогда не дать приближенную к реальности задачу?
@andreyokoch5 жыл бұрын
For the first function to work one should first do: from collections import defaultdict
@ЭрикОвсепян-б9з3 ай бұрын
бред, конечное решение первой задачи решается одним if(ом) len(a) == len(b) в теле первого или второго решения, где мы созвываем в сет одну строку и потом смотрим вхождения из первой
@andreip93785 жыл бұрын
Можно было просто написать counter1 == counter2
@BuffyKek Жыл бұрын
Я вот в 11 классе сейчас и смотрю строчки кода он пишет знакомые и понятные, а говорит что-то максимально страшное
@niklkelbon36624 жыл бұрын
Мне кажется мой алгоритм получше для последней задачи, не идеально конечно, но ни одного вызова зря, меньше передаваемых параметров, можно ещё строку сразу делать 2 N размера, чтобы не прибавлять, но по сути вот: С++ void wow(int N, std::string currentString = std::string(), int openCount = 0) { if ((N == 0) && (openCount == 0)) { std::cout
@Zeksait8 ай бұрын
вроде так нельзя переменные называть. aSet
@Chel1k74 ай бұрын
Можно как угодно, хоть _. Другое дело, рекомендуется это или нет
@АлешаКарасиков3 жыл бұрын
почему в анаграммах нельзя сравнивать первый символ а с последним символом b в цикле, сдвигая соответственно итератор по а вперед, по b назад, если символы равны, и предварительно проверив на равенство длины строк (на плюсах бы я так и сделал, питон не знаю)
@jeromewicks38963 жыл бұрын
Потому что если слова W1 и W2 являются анаграммами, то не всегда W1 == reversed(W2) (и наоборот). Например, слова eat и tea - анаграммы, но eat != reversed(tea) = aet
@АлешаКарасиков3 жыл бұрын
@@jeromewicks3896 а, точно, спасибо за ответ )
@RusShbreak1 Жыл бұрын
@@jeromewicks3896 Да eat != reversed(tea), т.к. reversed(tea) == "aet". Но в задаче на врят ли имелись ввиду анаграммы в литературном смысле, т.е. не важно сходится конкретная строка в реальное слово языка или нет.
@zugzug902 жыл бұрын
Да кто такая эта ваша симметрия?
@TONHEAD72 жыл бұрын
Внимание, в решении второй задачи ашипка ) Если n == 0 то выводится на печать пустая строка, а это неправильно, пустая строка не является корректной комбинацией скобок. Возьмите меня на работу, лол
@Kamapec5 жыл бұрын
Разве так не будет быстрее и без доп.средств(sort, counter): str1 = "hhelloo" str2 = "oollehh" str2 = str2[::-1] print(str2 == str1) ?
@zhalgasnurakhmetov96465 жыл бұрын
Вам нужно почитать что такое анаграммы. Ваш код проверяет является ли одна строка другой , но заданной в обратном порядке.
@Kamapec5 жыл бұрын
@@zhalgasnurakhmetov9646 Да, спасибо, разобрался, действительно, не понял задание сначала )
@aikolkoikelov75144 жыл бұрын
Это код для определения палиндрома
@mm_mistermaks2 жыл бұрын
питон выглядит так будто на нем алгоритмы писать проще в 10 раз чем на java
@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
@maksimkovtun95173 жыл бұрын
Я бы первую задачу решил так: 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)
8:02 в последней строчке произойдёт сравнение ссылок на словари, а не сравнение словарей. Всегда будет False
@ilyapikulin28844 жыл бұрын
сравнение ссылок происходит по оператору `is`. оператор `==` вызывает метод `__eq__()`.
@apogo782 жыл бұрын
Не будем использовать сложное встроенное встроенное в язык средство. Будем использовать другое сложное встроенное в язык средство (>_
@darkduke833 жыл бұрын
Блин, а я решил эту задачу построив граматику, сделал правила прождения цепочек и на шаге n отсекал нетерминальные цепочки... а тут на тебе.. открыл закрыл... 🤣🤣🤣
@MrAlexPhilippov4 жыл бұрын
char ['kær] (от англ. character) - символ
@a_pifagor2 жыл бұрын
Господи, какая скука.
@askarsaitov29135 жыл бұрын
шлак
@ЕвгенийИльин-ф4м2 жыл бұрын
Мда) а вас не смущает, что counter вероятнее всего считая количества вхождений символа для каждой буквы будет пробегаться по всей строке? И так каждый раз? А это n в квадрате сложность. Что же касается кода, если он считает количество уникальных символов, а затем вы сравниваете общую длину, то что вы скажете о таких строках? abb aab В общем я думал к вам регнуться на контест, но неприятно удивлен.
@rednil82428 ай бұрын
как же яндекс переживет потерю такого ценного кандидата
@mixwheels5 жыл бұрын
Скучная и неинтересная задача. Я ожидал какого-то иного решения, чем банальная рекурсия, да еще и с передачей строк в стеке! Думаю, есть решение, когда в стек строку не кладут, последовательно меняя в единой базовой строке парные скобки. Вы его даже не удосужились придумать. Накатал на пхп за 15 минут, включая отладку. На бумаге (на собеседовании) проверить алгоритм вряд ли возможно в адекватное кол-во времени. На просчет рекурсии на бумаге уйдет много времени.
@nevmem6715 жыл бұрын
Описанным в видео способом решить задачу, на мой взгляд, не сложно, так как именно это решение обычно первым приходит в голову, к тому же строки в Python иммутабельный тип и, возможно, поэтому была выбрана такая реализация. Написание кода на бумаге это нормальная практика, поскольку, как было сказано в видео, не обязательно помнить все сигнатуры функций, важно правильно придумать, изложить и доказать адгоритм, который на Ваш взгляд является оптимальным для решения данной задачи. Менять скобки местами также может иметь худшую ассимптотику, чем предложенное решение, так как чтобы найти правильную пару скобок, возможно придётся обойти всю строку
@mixwheels5 жыл бұрын
@@nevmem671 Я о другом. Повторю свою мысль. На бумаге накатать рекурсию - элементарная задача. Но практически невозможно отладить на бумаге. Т.к. наличие нескольких if делают поведение не предсказуемым. При наличии компа и возможности быстро запустить, увидеть ошибку, внести коррективы - 15 минут. Без компа - проверки рекурсии придется считать на бумаге, что чревато ошибками и огромным временем. Даже при правильном написании всех if в рекурсии нет шансов на бумаге что-либо проверить. Вывод: это не лучшая задача на алгоритмы для собеседования. Да, кстати, у меня есть решение без рекурсии линейным циклом - см отдельный коммент.
@tirsky5 жыл бұрын
В том же ролике про собеседование в Google, на сортировку массива, гораздо интереснее рассказывается про то, как надо вести себя на интервью и поэтапно рассматривается решение задачи.
@TheZloymedved5 жыл бұрын
15 минут? да уж, программист ты так себе
@uvencosuper34716 ай бұрын
invert_string = string[::-1] return True if string == invert_string else False подглядывал только синтаксис среза, что бы инвертнуть строку, сам алгоритм сходу придумал. Вытирал бы доску сто раз, могу я приходить на собес в яндекс или мал еще?