Как решать алгоритмические секции: помощь разработчикам, собеседующимся в Яндекс. Часть 2

  Рет қаралды 138,364

Yandex for Developers

Yandex for Developers

Күн бұрын

Пікірлер: 186
@АндрейИльин-д6ж
@АндрейИльин-д6ж 4 жыл бұрын
меня пугает когда он подходит
@suka11226
@suka11226 2 жыл бұрын
Беги
@qaLex455
@qaLex455 Жыл бұрын
))
@juliaastra4345
@juliaastra4345 7 ай бұрын
😂
@alexmiller6844
@alexmiller6844 Жыл бұрын
return Counter(a) == Counter(b)
@hlystomv
@hlystomv 5 жыл бұрын
1. Научить по видео писать алгоритмы невозможно. 2. Показать, как писать на доске алгоритм - бессмысленно. Таких видео очень много (лекции). Все они постановочные, а не документальные, в том смысле, что актер знает роль и пишет на доске заранее срежиссированный текст, делает постановочные ошибки и т.п. В реальности на собеседовании гормональный фон собеседуемого не такой, ведет он себя не так как демонстрирует видео, стремится не к тому, чтобы заученный текст с бумажки переписать, а к тому, чтобы сосредоточится и выдавить из себя хоть что-то. 3. Доска как инструмент нужна для обмена идеями. Для этого подходят рисунки, а не код.
@-MaCkRage-
@-MaCkRage- 28 күн бұрын
Яндекс🤪
@MajinSaha
@MajinSaha Жыл бұрын
Так, а где тесты перед решением первой задачи? В первом видео на тесты же напирали.
@protasovse
@protasovse 2 жыл бұрын
Зачем в анаграммах находить разницу Counter-ов, если можно их сравнить (Conter1==Counter2)?
@RusShbreak1
@RusShbreak1 Жыл бұрын
Да! И более того, как можно ее найти, если оператор вычитания не поддерживается диктом...
@vladtokarev146
@vladtokarev146 7 ай бұрын
Там память не О(n) в третьем случае, а O(2a), где а размер алфавита. Для строчных английских букв это 26
@FakePlv
@FakePlv 5 жыл бұрын
Мм, один момент не ясен: был написан тест: parents(3)== { "((( )))", "()()()", "(())()", "()(())", "(()())" }. Но код на доске генерирует только "((( )))", так ведь? Более того в статье Яндекса на хабре про эту задачу также сказано "Вывести последовательности в лексикографическом порядке(правильный алгоритм по-умолчанию выводит их в нужном порядке)" и указана ссылка на это видео как разбор задачи. Получается то, что на доске попроще будет, чем то что на собеседовании по словам из статьи.
@nevmem671
@nevmem671 5 жыл бұрын
Нет не так код на доске генерирует ровно то, что нужно то есть НЕ одну последовательность, там же рекурсивные запуски, которые например уже на второй итерации могут на префикс построить строки "((" и "()", так как эти последовательности никак не противоречат написанному коду
@FakePlv
@FakePlv 5 жыл бұрын
@@nevmem671 Да, вы абсолютно правы, я был невнимателен(забыл вернуться к первому вызову в стеке). Вы писали ниже, что это решение первым приходит в голову. Мне же первым в голову пришло создание класса или же дерево. Расскажите, как вы понимаете, что начать рассуждения надо с рекурсии?
@slavanikulin8069
@slavanikulin8069 4 жыл бұрын
​@@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 })
@FakePlv
@FakePlv 4 жыл бұрын
@@slavanikulin8069 Уже не помню, честно говоря, о чем шла речь, но да рекурсия обычно напрашивается первой, избавиться от неё обычно проблемнее, чем её применить. Как раз год назад пытался пройти контест, где было 4 олимпиадные задачи из 6(вроде шесть задач было:) ).. короче до собеседования дело даже не дошло)) У меня много вопросов возникало про адекватность формулировок, но, отвечали мне на них - никак(сам дурак). Была там задачка и про поиск множителей, где нужно было найти нужную комбинацию для заданного произведения. Алгоритм дерева был весьма кстати, правда, обходить пришлось без рекурсии, т.к. не проходил по времени. Разница в скорости алгоритма значительна, например 2ms/636Kb против рекурсивных 56ms/896Kb(метрика контеста). Так что да, в здравом уме и адекватной обстановке, рекурсия не должна приходить в голову, однако на собеседовании(до которого дело дойдет только у олимпиадников), проще сделать ей и решить задачу, чем допускать мелкие ошибки и ожидать подсказок от интервьюера. По поводу крика души. У меня тоже есть, что сказать. Жаль, конечно, что не удалось устроиться в Яндекс, хотя может оно и к лучшему. Скажу одно, у каждого свои способности и лучшие стороны, если Яндекс планирует использовать лишь скорость применение шаблона и их объем в голове разработчика, то когда-нибудь это аукнется. В универе была группа по спортивному программированию, которая занимала призовые места на мировых олимпиадах, только вот экзамен по программированию сдавал за них я, ибо по какой-то причине им не удалось осилить задачки препода. Я это к тому, что не все задачи требуют хитромудрую формулу для поиска части окружности из миллиарда окружностей, и шаблоны не помогают найти решение проблемы, они лишь пытаются её решить стандартным способом. Чтобы решать проблему надо думать. Чтобы использовать шаблон, надо его помнить. Сейчас я системный программист, занимаюсь разработкой ОС в коммерческой фирме, есть тонна задач, которые не требуют математики, но требуют очень развитой интуиции, смекалки и аналитического склада ума, что бы быстро уметь анализировать тонны опенсурсных систем и чужого кода на всевозможных языках. Наверное, таким не место в Яндексе, раз у таких дело даже до собеседования не доходит(да, разрабочик интерфейсов каких-нибудь тоже должен решить олимпиадные задачи). ps: пытался решать задачи честно - самостоятельно, не заглядывая в готовые алгоритмы.
@slavanikulin8069
@slavanikulin8069 4 жыл бұрын
Kernel Plevitsky Справедливости ради стоит сказать, что весь этот алгоритмически-олимпиадный ад стоит того, тк в Яндексе очень благоприятная среда, способствующая быстрому росту. Но если не получится пройти, то ничего страшного) Здорово, рад за вас, что нашли своё призвание и место!
@AlexosYou
@AlexosYou 5 жыл бұрын
Вы говорите об оптимальном решении и пишете код на пайтоне со встроенными функциями, чей код закрыт. По крайней мере вы не говорите как реализованы counter или defaultdict и какова их производительность (асимптотика и память). Из очевидных вариантов defaultdict это либо массив, либо map. В обоих случаях для оценки памяти и производительности необходимо брать в расчёт не только длину входной последовательности N, но и размер алфавита M. Если defaultdict реализован через вектор, то получим время O(N) и память O(M), не считая, конечно, памяти для входных строк. Если defaultdict реализован через map, то получим время O(N*log(M)) и память O(M). Причём, если быть дотошным, тут память примерно в 2 раза будет больше, чем в случае с вектором. Однако автор прокритиковал решение через массивы, так что, наверное, defaultdict не реализован через них. Но и решение через map не даёт искомой асимптотики. Так что, объясните пожалуйста что такое это этот ваш defaultdict, иначе не говорите, что это эффективное решение.
@misana77
@misana77 4 жыл бұрын
Во-первых: > 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, если элемента не существовало
@alloyoshi
@alloyoshi 3 жыл бұрын
Проблема в том, что задаются на собеседованиях задачи В РАЗЫ сложнее, чем упомянутые.
@sevenb1t
@sevenb1t 2 жыл бұрын
Решай leetcode - там есть задачи сопостовимой сложности. Вопрос тренировки - без подготовки, конечно, пройти сложно алгоритмический уровень.
@whitehaker
@whitehaker 2 жыл бұрын
Было бы странно, если бы на собесах давали задачи такого уровня, на видео показан пример процесса и типичные ошибки. Задачу со скобками мне дали в седьмом классе, при отборе на школьную олимпиаду по программированию, как-раз на листке писал)
@dmitrypetrov8491
@dmitrypetrov8491 Жыл бұрын
В основном задачи на собеседованиях задаются уровня easy-medium с leetcode. Но некоторые кандидаты и это решить не могут.
@user-chf7z61vnd6h8v
@user-chf7z61vnd6h8v Жыл бұрын
@@dmitrypetrov8491 зачем это человеку, который пишет фронт, и может ещё бэк на уровне обработать входящие запросы и сделать запрос в БД? Более 5 лет работу фулстеком с јѕ ни разу эта олимпиалная бредятина не пригодилась. Если ты пишешь игры или что-то требующее математики, то может оно и нужно, но большинству это нахер не всралось для веба, только мозги на собесе иметь собеседуемому
@Prof-Shor
@Prof-Shor Жыл бұрын
​@@user-chf7z61vnd6h8v Воистину!
@sananyuzb
@sananyuzb 5 жыл бұрын
По первой задаче маленькая ошибка : Для 3 варианта решения задачи (про анаграммы) - использование памяти констатное - O(1) - т.к набор букв всегда постоянный - т.е если у нас строка состоит из сторчных латиских букв - то длина массива будет 26. Т.е. вне зависимости от того насколько длинная у нас строка - размер массива всегда будет одинаковый, т.е размер массива не зависит от входного параметра, соответственно сложность по памяти O(1).
@ignostik2328
@ignostik2328 5 жыл бұрын
Вы были бы абсолютно правы, если бы не еще одно маленькое обстоятельство: кол-во памяти для хранение счетчиков количества символов все-таки зависит от длины входных данных, а именно для хранения числа n нужно log_2(n) с округлением бит информации. Поэтому с увеличением n, затраты по памяти также растут (хотя на данный момент те порядки, при которых рост памяти будет существенным, просто недостижимы). Поэтому, строго говоря, сложность по памяти (log_2(n)).
@sananyuzb
@sananyuzb 5 жыл бұрын
@@ignostik2328 Да. Но ассимптотика не считает количество памяти которую и чпользует программа, а показывает как используемые ресурсы изменяются в зависисости от входных данных. Мы можем создать массив из 16000 элементов, который поместит в себе все возможные символы. Соответственно ассимптотика использования памяти будет постоянная. Да, реальное использование памяти будет разное, но ассимптотика будет постоянная.
@alleycat123123123
@alleycat123123123 4 жыл бұрын
@@sananyuzb Не понял поинт про 16000 элементов. Насколько я понял Анатолий имеет в виду что будет просходить для строк: 1) 2^8 символов "a" 2) 2^16 символов "a" 3) 2^24 символов "a" 4) 2^32 символов "a" В этом случае между каждым из этих вариантов будет разница 1 байт, и память растет как O(log(n))
@user-mr-m12312
@user-mr-m12312 4 жыл бұрын
@@alleycat123123123 речь шла о случае, когда строки состоят из строчных латинских букв, в таком случае мы можем использовать массив из 26 элементов, где индекс массива соответствует букве алфавита, а значение - количеству вхождений буквы в строке. В этом случае затраты по памяти будут 26*4байта, то есть О(1), так как не зависят от размера строки.
@ВладимирТерещенко-и7ц
@ВладимирТерещенко-и7ц 3 жыл бұрын
У второй задачи пропущена секция с определением сложности алгоритма
@okke00
@okke00 3 жыл бұрын
Никогда не понимал зачем писать код на доске? Почему не на бересте например или долотом на камне высекать? Все одно с реальной работой не пересекается
@uvencosuper3471
@uvencosuper3471 6 ай бұрын
Если экстраполировать дальше, то почему бы не разрешить подгугливать синтаксис особо редковстречающихся конструкций, типа предполагается, что стековерфлоу в яндексе отключил злой одмин что ли?
@kerzhemanov
@kerzhemanov 2 ай бұрын
​@@uvencosuper3471 за синтаксис обычно не минусуют. Главное чтобы решение было верным, и соискатель мог объяснить как оно работает.
@__dot3506
@__dot3506 3 ай бұрын
Основные ошибки / корнеры: - Неправильное представление данных. Данные могут быть представлены некорректно определенной структурой. Пример: превращение строки во множество убирает повторяющиеся символы. - Асимметрия данных: следует из предыдущего. - Непонимание работы утилит, структур и методов языка - будь внимателен. Иногда стоит написать что-то своим кодом, чтобы показать понимание работы. - Всегда начинайте задачу с тесткейсов для понимания условий и работы программы - При задаче на создание строк: начинай думать о том, что можно приписать / удалить из строки для достижения ответа. - Быстрые исправления не всегда хороши. - Пытайся написать / исправить сложную функцию так, чтобы в ней не было лишних вызовов - Не мутируй состояние аргументов внутри рекурсивной функции, если точно не уверен, что это не повредит алгоритму
@РоманГалушка-ж2е
@РоманГалушка-ж2е Жыл бұрын
Задача со скобочками на джаве в таком виде не принимается в вашем же контесте. не проходит по ограничению памяти (наверное слишком много занимает рекурсивный стек вызова). Убил всю голову, пока не нашел уже решенный вариант на гитхабе. и там алгоритм очень потный вышел. я его так и не понял
@rusfungame
@rusfungame 3 жыл бұрын
А если я устроюсь в яндекс, футболки выдадут?
@tarasg7122
@tarasg7122 3 жыл бұрын
да, ты и будешь тем кто их будет выдавать)
@dmitrymalygin3323
@dmitrymalygin3323 3 жыл бұрын
В работе нужны знания того как оптимизировать алгоритм? Или, как обычно, дворников заставляют сдавать кандидатский минимум?
@okke00
@okke00 3 жыл бұрын
Чуваки просто копируют FAANG) Когда у тебя огромный поток кандидатов, то на собеседовании ты можешь, что угодно спрашивать. В реальной же работе ты с этим не столкнешься в 90% случаев
@jeromewicks3896
@jeromewicks3896 3 жыл бұрын
@@okke00 если формочки клепаешь, наверное не столкнёшься. Но если пишешь код, производительность которого более менее что-то значит, то хорошо как минимум понимать какая сложность используемого кода, чтобы не написать код с сложность n!
@okke00
@okke00 3 жыл бұрын
@@jeromewicks3896 Производительность в реальных продакшн приложениях почти никогда не упирается в сложность алгоритмов, скорее в I\O операции, где оптимизируют совершенно другими методами. Плюс узкие места ищут не умозрительной оценкой сложности алгоритмов, а профилированием. Ну и да, любая нормальная quality gate тулза тебе подсветить откровенную дичь с экспоненциальной сложностью
@tarasg7122
@tarasg7122 3 жыл бұрын
@@okke00 1) Я при код ревью много раз встречал места где алгоритм можно оптимизировать. Как по скорости, так и по памяти. 2) Да, узкие места ищут профилированием. Но высокий скил в том и заключается чтобы такие узкие места создавать как можно реже. 3) Проблема в том что "quality gate тулза" работает уже с готовым кодом. Зачем в команде человек, который пишет говно и потом его переделывает (и то если сможет)? Поэтому вполне логично слабеньких отсекать еще на входе.
@okke00
@okke00 3 жыл бұрын
@@tarasg7122 1) Далеко не всегда такие места надо оптимизировать. Одно дело когда правка тривиальна и по сути ничего не стоит, тут да, можно и оптимизнуть. Но если надо убить часа два времени, а то и больше, на оптимизацию алгоритма, который просто выглядит так, что его можно написать оптимальнее, то это явно не то чем стоит заниматься. 2.) Без профилирования практически невозможно находить реальные узкие места и от скилла тут мало что зависит(разве что скилл поможет совсем уж тривиальные ошибки не допускать) 3) А как тут поможет алгоритмическая секция? Любой олимпиадник ее пройдет с легкостью, при этом именно они чаще других пишут то, что в энтерпрайзе принято считать говнокодом.
@SiarheiAkhramenia
@SiarheiAkhramenia 3 ай бұрын
PEP8 попросил передать вам привет! ;)
@ZzooD
@ZzooD 3 жыл бұрын
Какие типы данных могут быть в строке кроме char? 7:48
@gologames
@gologames 3 жыл бұрын
Мб wchar в C++
@ffelicius
@ffelicius 3 жыл бұрын
Тут скорее оговорка, не в строке, а во входной последовательности данных. Задача ведь искусственная. Обычно подобные задачи требуют не строки проверить на "анаграмность", а коллекции каких угодно объектов. Словари из объектов можно создать, а вот массивы объектами индексировать - не очень удобно)
@Sevenvad
@Sevenvad 5 жыл бұрын
То чувство, когда задача посложнее оказалась легче, чем задача полегче.
@rustyhex9899
@rustyhex9899 2 жыл бұрын
на литкоде такое постоянно... медиум иногда легче чем изи
@tirsky
@tirsky 5 жыл бұрын
ln - это натуральный, с основанием e, а log - это уже другое основание (например, 2)
@mapron1
@mapron1 5 жыл бұрын
С точки зрения О большого основание алгоритма не важно.
@vasya.k1n6
@vasya.k1n6 4 жыл бұрын
@@mapron1 в том то и дело, что обычно пишется log без указания основания. А ln - это уже с основанием, которое в данном случае, скорее всего, не подойдет
@ИванПавлов-г4т6э
@ИванПавлов-г4т6э 4 жыл бұрын
@@vasya.k1n6 при оценке O-большое сложность берется с точностью до константы. log2(x)=ln(x)/ln(2) - формула перехода к новому основанию, где ln(2) - константа. Т.е. если пишется оценка O большое основание можно указывать вообще любое.
@MrAlexPhilippov
@MrAlexPhilippov 4 жыл бұрын
Для O большое с асимптотическим приближением не важно.
@stttrannnik
@stttrannnik 3 жыл бұрын
Время 4:50. return ca==cb исправляет ситуацию.
@kernelbug2294
@kernelbug2294 2 жыл бұрын
Да, но тогда пришлось бы разбираться с более хитровывернутым примером, чтобы донести мысль о том, что иногда явная кодяра лучше неявной.
@MikhailMatrosov
@MikhailMatrosov 4 жыл бұрын
5:29 Хм, а почему бы не написать просто return ca == cb?
@artpro9191
@artpro9191 4 жыл бұрын
pep8? Не...
@nikitasatin
@nikitasatin 3 жыл бұрын
зашел сюда за этим комментарием
@jeromewicks3896
@jeromewicks3896 3 жыл бұрын
зачем коду на доске pep8? это же не продакшн код, который нужно поддерживать
@MrBibiw
@MrBibiw 3 жыл бұрын
@@jeromewicks3896 зачем говорить красивым и грамотным языком? мы же не на егэ
@MarkWaner
@MarkWaner 3 жыл бұрын
@@MrBibiw Именно!
@МаксимЗозуля-м2р
@МаксимЗозуля-м2р 3 жыл бұрын
А есть такая же футботка, только немного поярче?)
@gerhardshreder2391
@gerhardshreder2391 2 жыл бұрын
я бы подумал, брать ли кандидата с таким кодом. Вот написал функцию, какие-то входные аргументы. А аннотации типов не написал. Что за cur, что за open, close??? С первого взгляда ничего не ясно.
@segreyfurt
@segreyfurt 3 жыл бұрын
в первой задаче есть ошибка. Смотрим определение анаграммы "Слово или словосочетание, образованное путём перестановки букв, составляющих другое слово (или словосочетание)." Важно обратить внимание на слово "другое". Т.е. абв не является анаграммой абв
@segreyfurt
@segreyfurt 3 жыл бұрын
во втором решении, я бы не стал перезатирать стандартную функцию open - это не ошибка в алгоритме, но так делать не надо
@manOfPlanetEarth
@manOfPlanetEarth 2 жыл бұрын
@@segreyfurt что за функция open? у него есть только параметр open метода generate
@КириллКириллович
@КириллКириллович Жыл бұрын
@@manOfPlanetEarth нельзя использовать имена встроенных сущностей для переменных. `open` -- открытие файла
@КириллКириллович
@КириллКириллович Жыл бұрын
"другое" не значит "не равное". см разницу is/==
@Xeem_Pad
@Xeem_Pad Ай бұрын
@@КириллКириллович можно, просто не стоит. В таких случаях пишут 'open_'
@LenaFelica_songwriter
@LenaFelica_songwriter Жыл бұрын
почему Python, не понятно? на собесе тоже этот язык надо использовать, он что, самый основной вдруг?
@MajesticNut
@MajesticNut 3 жыл бұрын
Как правильно вычислить временную сложность для последней задачи со скобками?
@aslanator
@aslanator 3 жыл бұрын
поидеи линейная
@MarkWaner
@MarkWaner 3 жыл бұрын
@@aslanator точно не линейная. Экспоненциальная с базой экспоненты < 4 и > 2 Ну или суб-экспоненциальная. Там непросто вычислить из-за условий
@valekprometey
@valekprometey 2 жыл бұрын
Но ведь во второй задаче генерируется только 1 из возможных последовательностей - "((( )))" а требуются все.
@ezphantom
@ezphantom 2 жыл бұрын
не так :)
@uncle-xxi
@uncle-xxi 4 жыл бұрын
так там скрытых вычислений хватает :) даром что коротко и красиво :)
@Andrei-t5w
@Andrei-t5w 3 жыл бұрын
Тут же O нотация только интересна
@Scvairy
@Scvairy 5 жыл бұрын
Но ведь разность Counter-ов возвращает Counter, и никогда не будет равна 0 :(
@gologames
@gologames 3 жыл бұрын
Там len() от Counter
@peso4ek
@peso4ek Жыл бұрын
Нерекурсивно, тут ещё можно с помощью кодов Грея очень красивое решение выдать (скобочные последовательности).
@ЖеняПетров-ч2м
@ЖеняПетров-ч2м 2 жыл бұрын
Спасибо, видео помогло разобраться с рекурсией при помощи визуализатора, добавил return после 3го if-a так нагляднее.
@PrefixKrema
@PrefixKrema 2 жыл бұрын
В начале рассуждения для языка python очень некоректные. Вы и так и так будете делать для строк копии данных, так как это неизменяемый тип файла. Так что собеседование например на позициюю питон разработчика превращается в какой то сюр. Вообще большая ошибка брать задачи из строготепизированных языков со стеком памяти, и натягивать их на языки где только управляемая куча. Понятно что питон тут чисто для наглядности как псевдоязык, но сам язык позволяет решать такие задачи проще и лаконичнее.
@OStrekalovsky
@OStrekalovsky 5 жыл бұрын
Алгоритм №4: O(n) по скорости и O(1) по памяти - заводим массив размера всех возможных букв алфавита, где в i-ом элементе будет храниться количество таких букв. Проходя по первой строке увеличиваем счетчик букв в этом массиве, проходя по второй строке - уменьшаем счётчик числа повторений этих букв. Если массив стал из нулей, то строки - анаграммы.
@nevmem671
@nevmem671 5 жыл бұрын
Не верная оценка памяти, так как в описанном Вами решении количество используемой памяти О(С), где С - размер алфавита, чем нельзя пренебрегать
@FakePlv
@FakePlv 5 жыл бұрын
Хм. А время, которое уйдет на формирование массива с алфавитом, обеспечение уникальности символов в нем, а проверка массива на нули? Это же вроде всё время займет.
@РомаБерендеев-ш3з
@РомаБерендеев-ш3з 5 жыл бұрын
Время растет линейно, а расход памяти не растет, поэтому асимптотическая сложность записана верно
@nevmem671
@nevmem671 5 жыл бұрын
@@РомаБерендеев-ш3з Очень поверхностно оценивать время работы программы описанным Вами образом, потому что размер алфавита может быть не ограничен только одним языком или например только таблицей ASCII, а быть например размером во весь лонг т. е. порядка 2 в 64 степени значений, тогда выделение такого объёма памяти нельзя оценивать как константу
@nevmem671
@nevmem671 5 жыл бұрын
@@FakePlv Да, займёт причём ровно О(С) так как проверку на нули можно осуществлять с помощью поддерживая одного числа, которое будет значить количество нулей в массиве на данной итерации, такую величину пересчитывать очень просто, так как на каждой итерации изменяется ровно один элемент такого массива
@AntonioLopez8888
@AntonioLopez8888 2 жыл бұрын
Вроде задача была про все возможные последовательности.. Тут только одна ((())) . ???
@sermot
@sermot 7 ай бұрын
Требуется вывести все правильные скобочные последовательности длины 2 ⋅ n, упорядоченные лексикографически
@andreyokoch
@andreyokoch 5 жыл бұрын
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.
@MsCoolJohnny
@MsCoolJohnny 5 жыл бұрын
You should always start counting from zero ;)
@gregorykadonsky660
@gregorykadonsky660 5 жыл бұрын
def anagram(srt1, str2): return sorted(str1) == sorted(str2)
@nazarbayev_university
@nazarbayev_university 5 жыл бұрын
Главным критерием было сохранение времени и отсутствие модификаций, так что не пойдет
@АндрейАлексеев-х3д
@АндрейАлексеев-х3д 4 жыл бұрын
@@nazarbayev_university и где же мы модифицировали строки?
@KoScosss
@KoScosss 4 жыл бұрын
На сортировку O(nlogn) вместо O(n) уйдет
@vdrmkr
@vdrmkr Жыл бұрын
А почему N log N если после сортировки нужно будет ещё сравнить строки? Это уже O(N)
@vadipp
@vadipp 4 ай бұрын
O(n log(n)) + O(n) это та же оценка что и O(n log(n))
@bipolar-fox
@bipolar-fox 3 жыл бұрын
Я не знаю питон, но я бы решил первую задачу так: Проходим в цикле по всем буквам первой строки, внутри цикла проходим по буквам второй строки. Если находим совпадение - удаляем обе буквы. В конце должны остаться две пустых строки.
@w1cked11
@w1cked11 3 жыл бұрын
Что значит удаляем? Допустим, строки у вам из миллионов байт, тогда каждое такое удаление - это реаллокация и копирование памяти и это дорого. К тому же у вас выходит квадратичная сложность алгоритма, а тут - линейная, за счёт доп памяти на словари.
@bipolar-fox
@bipolar-fox 3 жыл бұрын
@@w1cked11 ну не удаляем, а заменяем на пробел
@w1cked11
@w1cked11 3 жыл бұрын
@@bipolar-fox без разницы, строки иммутабельны в питоне и это будет уже новая скопированная строка. Плюс квадратичная сложность. В общем, потренируйтесь ещё, собес вы бы пока не прошли :)
@ДаниилГолов-к5й
@ДаниилГолов-к5й 3 жыл бұрын
В третьем подходе к первой задаче тратится ведь константное количество памяти
@levp1801
@levp1801 3 жыл бұрын
мы создаём 4*n дополнительной памяти для хранения пар символ - количество,; а когда поправил зависит от того, сколько там памяти этот хипстерский метод берёт
@RusShbreak1
@RusShbreak1 Жыл бұрын
4:42 - Зачем вычитать словари, если их можно сравнить и как они могут вычитаться, если питон это не поддерживает? Напутано с множествами. И соответственно не понятно, как там неправильно работает Counter - мега сложный питон функционал, который автор следом изобретает и сам.
@serhiisakhno84
@serhiisakhno84 5 жыл бұрын
А если использовать ord? Коды символов одной строки прибавляем к переменной, коды второй соответственно вычитаем?
@mixwheels
@mixwheels 5 жыл бұрын
что за глупость? причем тут ord? замени скобки на 1/0 и ищи решение
@minmanr
@minmanr 5 жыл бұрын
Не будет работать, суммы кодов символов строк "bb" и "ac" равны, но они не являются анаграммами
@serhiisakhno84
@serhiisakhno84 5 жыл бұрын
@@mixwheels я имел ввиду задачу про анаграммы. Но да, моя ошибка. что не уточнил о какой задаче речь.
@serhiisakhno84
@serhiisakhno84 5 жыл бұрын
@@minmanr , утром я это уж тоже понял)
@hlystomv
@hlystomv 5 жыл бұрын
может сложение на xor заменить?
@nihttoter3240
@nihttoter3240 Жыл бұрын
Первая задача (str1, str2) => { const getHash = (str) => str.split('').sort().join() return getHash(str1) === getHash(str2) }
@MarkWaner
@MarkWaner 3 жыл бұрын
Можно еще вызывать рекурсивную функцию с параметрами ("(", 1, 0, n). Выигрыш очень маленький, но он есть
@alexk3929
@alexk3929 2 жыл бұрын
Эх, а потом перекладывать жсоны….
@dmitrijkarmatskij2124
@dmitrijkarmatskij2124 4 жыл бұрын
Для анограм можно посчитать hash по алгоритму hash += *str++
@dmitrijkarmatskij2124
@dmitrijkarmatskij2124 4 жыл бұрын
Очень сложный юмор
@gologames
@gologames 3 жыл бұрын
Нельзя. Пример "abc" и "aad"
@dmitrijkarmatskij2124
@dmitrijkarmatskij2124 3 жыл бұрын
@@gologames Я же сказал очень сложный юмор
@gologames
@gologames 3 жыл бұрын
@@dmitrijkarmatskij2124 Я подозревал. Хорошо тогда
@ELLA-fq6lo
@ELLA-fq6lo 3 жыл бұрын
14:20, мне вот просто интересно, неужели я такой тупой, и в яндексе сидят гениальные люди, потому что, когда я встретил эту задачу, мне понадобилось где-то около 5-6 часов и лишняя пара нервов, чтобы найти решение. Но дело в том, что если гуглить, то решение найти можно за пару минут. И у меня возникает вопрос, на кой фиг просить на собеседовании писать подобное карандашом, если в реале, ты просто пойдешь гуглить. Я уверен, что встреться эта задача этому челу через год, он бы взял и пошел гуглить, так почему отбор кандидатов делается по тому, сколько ты тупо вызубришь и насколько тебе повезет, а не по твоим реальным умственным способностям или знаниям тех или иных инструментов разработки???
@ELLA-fq6lo
@ELLA-fq6lo 3 жыл бұрын
А еще кстати, этот код не проходит проверку на их же тестах(язык котлин, ни одной лишней строчки), выбрасывает, что лимит памяти исчерпан)))
@jeromewicks3896
@jeromewicks3896 3 жыл бұрын
@@ELLA-fq6lo Если лимит памяти исчерпан - это не проблема алгоритма, а проблема Котлина и JVM. Напиши на чём-нибудь, что не тратит так много памяти
@ELLA-fq6lo
@ELLA-fq6lo 3 жыл бұрын
@@jeromewicks3896 Вот, сука, как я сразу не додумался до этого, пойду на ассемблере напишу
@bipolar-fox
@bipolar-fox 3 жыл бұрын
Смысл не в том, чтобы ты загуглил решение. Смысл в том, чтобы проверить, способен ли ты решить сам, то есть, насколько хорошо у тебя работают мозги. Зубрить не надо - это сразу будет видно, когда ты выдаешь заученные решения. Собеседующему важно увидеть, как ты сам думаешь.
@Kotofosonline
@Kotofosonline 8 ай бұрын
@@bipolar-fox Почему бы тогда не дать приближенную к реальности задачу?
@andreyokoch
@andreyokoch 5 жыл бұрын
For the first function to work one should first do: from collections import defaultdict
@ЭрикОвсепян-б9з
@ЭрикОвсепян-б9з 3 ай бұрын
бред, конечное решение первой задачи решается одним if(ом) len(a) == len(b) в теле первого или второго решения, где мы созвываем в сет одну строку и потом смотрим вхождения из первой
@andreip9378
@andreip9378 5 жыл бұрын
Можно было просто написать counter1 == counter2
@BuffyKek
@BuffyKek Жыл бұрын
Я вот в 11 классе сейчас и смотрю строчки кода он пишет знакомые и понятные, а говорит что-то максимально страшное
@niklkelbon3662
@niklkelbon3662 4 жыл бұрын
Мне кажется мой алгоритм получше для последней задачи, не идеально конечно, но ни одного вызова зря, меньше передаваемых параметров, можно ещё строку сразу делать 2 N размера, чтобы не прибавлять, но по сути вот: С++ void wow(int N, std::string currentString = std::string(), int openCount = 0) { if ((N == 0) && (openCount == 0)) { std::cout
@Zeksait
@Zeksait 8 ай бұрын
вроде так нельзя переменные называть. aSet
@Chel1k7
@Chel1k7 4 ай бұрын
Можно как угодно, хоть _. Другое дело, рекомендуется это или нет
@АлешаКарасиков
@АлешаКарасиков 3 жыл бұрын
почему в анаграммах нельзя сравнивать первый символ а с последним символом b в цикле, сдвигая соответственно итератор по а вперед, по b назад, если символы равны, и предварительно проверив на равенство длины строк (на плюсах бы я так и сделал, питон не знаю)
@jeromewicks3896
@jeromewicks3896 3 жыл бұрын
Потому что если слова W1 и W2 являются анаграммами, то не всегда W1 == reversed(W2) (и наоборот). Например, слова eat и tea - анаграммы, но eat != reversed(tea) = aet
@АлешаКарасиков
@АлешаКарасиков 3 жыл бұрын
@@jeromewicks3896 а, точно, спасибо за ответ )
@RusShbreak1
@RusShbreak1 Жыл бұрын
@@jeromewicks3896 Да eat != reversed(tea), т.к. reversed(tea) == "aet". Но в задаче на врят ли имелись ввиду анаграммы в литературном смысле, т.е. не важно сходится конкретная строка в реальное слово языка или нет.
@zugzug90
@zugzug90 2 жыл бұрын
Да кто такая эта ваша симметрия?
@TONHEAD7
@TONHEAD7 2 жыл бұрын
Внимание, в решении второй задачи ашипка ) Если n == 0 то выводится на печать пустая строка, а это неправильно, пустая строка не является корректной комбинацией скобок. Возьмите меня на работу, лол
@Kamapec
@Kamapec 5 жыл бұрын
Разве так не будет быстрее и без доп.средств(sort, counter): str1 = "hhelloo" str2 = "oollehh" str2 = str2[::-1] print(str2 == str1) ?
@zhalgasnurakhmetov9646
@zhalgasnurakhmetov9646 5 жыл бұрын
Вам нужно почитать что такое анаграммы. Ваш код проверяет является ли одна строка другой , но заданной в обратном порядке.
@Kamapec
@Kamapec 5 жыл бұрын
@@zhalgasnurakhmetov9646 Да, спасибо, разобрался, действительно, не понял задание сначала )
@aikolkoikelov7514
@aikolkoikelov7514 4 жыл бұрын
Это код для определения палиндрома
@mm_mistermaks
@mm_mistermaks 2 жыл бұрын
питон выглядит так будто на нем алгоритмы писать проще в 10 раз чем на java
@aleksandr3094
@aleksandr3094 4 жыл бұрын
Как я решил на пхп (реализацию автора не видел) function anag() { $str1 = str_split('asdasdasdasdasd'); $str2 = str_split('dsadasdasdasdas'); if (count($str1) === count($str2)) { sort($str1); sort($str2); return $str1 == $str2; } return false; }
@aleksandr3094
@aleksandr3094 4 жыл бұрын
Между реализацией в комменте и этой: function ang2() { if (splitt('asdasdasdasdasd') == splitt('dsadasdasdasdas')) return true; return false; } function splitt(string $str) { $res = []; for ($i = 0; $i
@maksimkovtun9517
@maksimkovtun9517 3 жыл бұрын
Я бы первую задачу решил так: 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)
@HI-fi2wy
@HI-fi2wy 8 ай бұрын
пример правильной скобочной последовательности: ( . ) ( . ) пример неправильной скобочной последовательности: ( . ) ( . ) ( . ) Извините)
@ИванКутиков-з8и
@ИванКутиков-з8и 4 жыл бұрын
8:02 в последней строчке произойдёт сравнение ссылок на словари, а не сравнение словарей. Всегда будет False
@ilyapikulin2884
@ilyapikulin2884 4 жыл бұрын
сравнение ссылок происходит по оператору `is`. оператор `==` вызывает метод `__eq__()`.
@apogo78
@apogo78 2 жыл бұрын
Не будем использовать сложное встроенное встроенное в язык средство. Будем использовать другое сложное встроенное в язык средство (>_
@darkduke83
@darkduke83 3 жыл бұрын
Блин, а я решил эту задачу построив граматику, сделал правила прождения цепочек и на шаге n отсекал нетерминальные цепочки... а тут на тебе.. открыл закрыл... 🤣🤣🤣
@MrAlexPhilippov
@MrAlexPhilippov 4 жыл бұрын
char ['kær] (от англ. character) - символ
@a_pifagor
@a_pifagor 2 жыл бұрын
Господи, какая скука.
@askarsaitov2913
@askarsaitov2913 5 жыл бұрын
шлак
@ЕвгенийИльин-ф4м
@ЕвгенийИльин-ф4м 2 жыл бұрын
Мда) а вас не смущает, что counter вероятнее всего считая количества вхождений символа для каждой буквы будет пробегаться по всей строке? И так каждый раз? А это n в квадрате сложность. Что же касается кода, если он считает количество уникальных символов, а затем вы сравниваете общую длину, то что вы скажете о таких строках? abb aab В общем я думал к вам регнуться на контест, но неприятно удивлен.
@rednil8242
@rednil8242 8 ай бұрын
как же яндекс переживет потерю такого ценного кандидата
@mixwheels
@mixwheels 5 жыл бұрын
Скучная и неинтересная задача. Я ожидал какого-то иного решения, чем банальная рекурсия, да еще и с передачей строк в стеке! Думаю, есть решение, когда в стек строку не кладут, последовательно меняя в единой базовой строке парные скобки. Вы его даже не удосужились придумать. Накатал на пхп за 15 минут, включая отладку. На бумаге (на собеседовании) проверить алгоритм вряд ли возможно в адекватное кол-во времени. На просчет рекурсии на бумаге уйдет много времени.
@nevmem671
@nevmem671 5 жыл бұрын
Описанным в видео способом решить задачу, на мой взгляд, не сложно, так как именно это решение обычно первым приходит в голову, к тому же строки в Python иммутабельный тип и, возможно, поэтому была выбрана такая реализация. Написание кода на бумаге это нормальная практика, поскольку, как было сказано в видео, не обязательно помнить все сигнатуры функций, важно правильно придумать, изложить и доказать адгоритм, который на Ваш взгляд является оптимальным для решения данной задачи. Менять скобки местами также может иметь худшую ассимптотику, чем предложенное решение, так как чтобы найти правильную пару скобок, возможно придётся обойти всю строку
@mixwheels
@mixwheels 5 жыл бұрын
​@@nevmem671 Я о другом. Повторю свою мысль. На бумаге накатать рекурсию - элементарная задача. Но практически невозможно отладить на бумаге. Т.к. наличие нескольких if делают поведение не предсказуемым. При наличии компа и возможности быстро запустить, увидеть ошибку, внести коррективы - 15 минут. Без компа - проверки рекурсии придется считать на бумаге, что чревато ошибками и огромным временем. Даже при правильном написании всех if в рекурсии нет шансов на бумаге что-либо проверить. Вывод: это не лучшая задача на алгоритмы для собеседования. Да, кстати, у меня есть решение без рекурсии линейным циклом - см отдельный коммент.
@tirsky
@tirsky 5 жыл бұрын
В том же ролике про собеседование в Google, на сортировку массива, гораздо интереснее рассказывается про то, как надо вести себя на интервью и поэтапно рассматривается решение задачи.
@TheZloymedved
@TheZloymedved 5 жыл бұрын
15 минут? да уж, программист ты так себе
@uvencosuper3471
@uvencosuper3471 6 ай бұрын
invert_string = string[::-1] return True if string == invert_string else False подглядывал только синтаксис среза, что бы инвертнуть строку, сам алгоритм сходу придумал. Вытирал бы доску сто раз, могу я приходить на собес в яндекс или мал еще?
The IMPOSSIBLE Puzzle..
00:55
Stokes Twins
Рет қаралды 187 МЛН
Do you love Blackpink?🖤🩷
00:23
Karina
Рет қаралды 22 МЛН
Симбу закрыли дома?! 🔒 #симба #симбочка #арти
00:41
Симбочка Пимпочка
Рет қаралды 5 МЛН
Максим про поход на собеседование в Яндекс
17:33
Андрей += Пронин
Рет қаралды 8 М.
Задача из Собеседования на 160,000 Евро в Год
13:27
Саша Лукин
Рет қаралды 1,1 МЛН
Разбираемся с АЛГОРИТМИЧЕСКИМ собесом
16:14
Максим Фатин
Рет қаралды 13 М.
SENIOR on JUNIOR Javascript Developer interview
26:35
BELOV
Рет қаралды 358 М.
The IMPOSSIBLE Puzzle..
00:55
Stokes Twins
Рет қаралды 187 МЛН