1. Научить по видео писать алгоритмы невозможно. 2. Показать, как писать на доске алгоритм - бессмысленно. Таких видео очень много (лекции). Все они постановочные, а не документальные, в том смысле, что актер знает роль и пишет на доске заранее срежиссированный текст, делает постановочные ошибки и т.п. В реальности на собеседовании гормональный фон собеседуемого не такой, ведет он себя не так как демонстрирует видео, стремится не к тому, чтобы заученный текст с бумажки переписать, а к тому, чтобы сосредоточится и выдавить из себя хоть что-то. 3. Доска как инструмент нужна для обмена идеями. Для этого подходят рисунки, а не код.
Было бы странно, если бы на собесах давали задачи такого уровня, на видео показан пример процесса и типичные ошибки. Задачу со скобками мне дали в седьмом классе, при отборе на школьную олимпиаду по программированию, как-раз на листке писал)
@@dmitrypetrov8491 зачем это человеку, который пишет фронт, и может ещё бэк на уровне обработать входящие запросы и сделать запрос в БД? Более 5 лет работу фулстеком с јѕ ни разу эта олимпиалная бредятина не пригодилась. Если ты пишешь игры или что-то требующее математики, то может оно и нужно, но большинству это нахер не всралось для веба, только мозги на собесе иметь собеседуемому
Мм, один момент не ясен: был написан тест: parents(3)== { "((( )))", "()()()", "(())()", "()(())", "(()())" }. Но код на доске генерирует только "((( )))", так ведь? Более того в статье Яндекса на хабре про эту задачу также сказано "Вывести последовательности в лексикографическом порядке(правильный алгоритм по-умолчанию выводит их в нужном порядке)" и указана ссылка на это видео как разбор задачи. Получается то, что на доске попроще будет, чем то что на собеседовании по словам из статьи.
Нет не так код на доске генерирует ровно то, что нужно то есть НЕ одну последовательность, там же рекурсивные запуски, которые например уже на второй итерации могут на префикс построить строки "((" и "()", так как эти последовательности никак не противоречат написанному коду
@@nevmem671 Да, вы абсолютно правы, я был невнимателен(забыл вернуться к первому вызову в стеке). Вы писали ниже, что это решение первым приходит в голову. Мне же первым в голову пришло создание класса или же дерево. Расскажите, как вы понимаете, что начать рассуждения надо с рекурсии?
@@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 })
@@slavanikulin8069 Уже не помню, честно говоря, о чем шла речь, но да рекурсия обычно напрашивается первой, избавиться от неё обычно проблемнее, чем её применить. Как раз год назад пытался пройти контест, где было 4 олимпиадные задачи из 6(вроде шесть задач было:) ).. короче до собеседования дело даже не дошло)) У меня много вопросов возникало про адекватность формулировок, но, отвечали мне на них - никак(сам дурак). Была там задачка и про поиск множителей, где нужно было найти нужную комбинацию для заданного произведения. Алгоритм дерева был весьма кстати, правда, обходить пришлось без рекурсии, т.к. не проходил по времени. Разница в скорости алгоритма значительна, например 2ms/636Kb против рекурсивных 56ms/896Kb(метрика контеста). Так что да, в здравом уме и адекватной обстановке, рекурсия не должна приходить в голову, однако на собеседовании(до которого дело дойдет только у олимпиадников), проще сделать ей и решить задачу, чем допускать мелкие ошибки и ожидать подсказок от интервьюера. По поводу крика души. У меня тоже есть, что сказать. Жаль, конечно, что не удалось устроиться в Яндекс, хотя может оно и к лучшему. Скажу одно, у каждого свои способности и лучшие стороны, если Яндекс планирует использовать лишь скорость применение шаблона и их объем в голове разработчика, то когда-нибудь это аукнется. В универе была группа по спортивному программированию, которая занимала призовые места на мировых олимпиадах, только вот экзамен по программированию сдавал за них я, ибо по какой-то причине им не удалось осилить задачки препода. Я это к тому, что не все задачи требуют хитромудрую формулу для поиска части окружности из миллиарда окружностей, и шаблоны не помогают найти решение проблемы, они лишь пытаются её решить стандартным способом. Чтобы решать проблему надо думать. Чтобы использовать шаблон, надо его помнить. Сейчас я системный программист, занимаюсь разработкой ОС в коммерческой фирме, есть тонна задач, которые не требуют математики, но требуют очень развитой интуиции, смекалки и аналитического склада ума, что бы быстро уметь анализировать тонны опенсурсных систем и чужого кода на всевозможных языках. Наверное, таким не место в Яндексе, раз у таких дело даже до собеседования не доходит(да, разрабочик интерфейсов каких-нибудь тоже должен решить олимпиадные задачи). ps: пытался решать задачи честно - самостоятельно, не заглядывая в готовые алгоритмы.
Kernel Plevitsky Справедливости ради стоит сказать, что весь этот алгоритмически-олимпиадный ад стоит того, тк в Яндексе очень благоприятная среда, способствующая быстрому росту. Но если не получится пройти, то ничего страшного) Здорово, рад за вас, что нашли своё призвание и место!
Если экстраполировать дальше, то почему бы не разрешить подгугливать синтаксис особо редковстречающихся конструкций, типа предполагается, что стековерфлоу в яндексе отключил злой одмин что ли?
Вы говорите об оптимальном решении и пишете код на пайтоне со встроенными функциями, чей код закрыт. По крайней мере вы не говорите как реализованы counter или defaultdict и какова их производительность (асимптотика и память). Из очевидных вариантов defaultdict это либо массив, либо map. В обоих случаях для оценки памяти и производительности необходимо брать в расчёт не только длину входной последовательности N, но и размер алфавита M. Если defaultdict реализован через вектор, то получим время O(N) и память O(M), не считая, конечно, памяти для входных строк. Если defaultdict реализован через map, то получим время O(N*log(M)) и память O(M). Причём, если быть дотошным, тут память примерно в 2 раза будет больше, чем в случае с вектором. Однако автор прокритиковал решение через массивы, так что, наверное, defaultdict не реализован через них. Но и решение через map не даёт искомой асимптотики. Так что, объясните пожалуйста что такое это этот ваш defaultdict, иначе не говорите, что это эффективное решение.
Во-первых: > 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, если элемента не существовало
По первой задаче маленькая ошибка : Для 3 варианта решения задачи (про анаграммы) - использование памяти констатное - O(1) - т.к набор букв всегда постоянный - т.е если у нас строка состоит из сторчных латиских букв - то длина массива будет 26. Т.е. вне зависимости от того насколько длинная у нас строка - размер массива всегда будет одинаковый, т.е размер массива не зависит от входного параметра, соответственно сложность по памяти O(1).
Вы были бы абсолютно правы, если бы не еще одно маленькое обстоятельство: кол-во памяти для хранение счетчиков количества символов все-таки зависит от длины входных данных, а именно для хранения числа n нужно log_2(n) с округлением бит информации. Поэтому с увеличением n, затраты по памяти также растут (хотя на данный момент те порядки, при которых рост памяти будет существенным, просто недостижимы). Поэтому, строго говоря, сложность по памяти (log_2(n)).
@@ignostik2328 Да. Но ассимптотика не считает количество памяти которую и чпользует программа, а показывает как используемые ресурсы изменяются в зависисости от входных данных. Мы можем создать массив из 16000 элементов, который поместит в себе все возможные символы. Соответственно ассимптотика использования памяти будет постоянная. Да, реальное использование памяти будет разное, но ассимптотика будет постоянная.
@@sananyuzb Не понял поинт про 16000 элементов. Насколько я понял Анатолий имеет в виду что будет просходить для строк: 1) 2^8 символов "a" 2) 2^16 символов "a" 3) 2^24 символов "a" 4) 2^32 символов "a" В этом случае между каждым из этих вариантов будет разница 1 байт, и память растет как O(log(n))
@@alleycat123123123 речь шла о случае, когда строки состоят из строчных латинских букв, в таком случае мы можем использовать массив из 26 элементов, где индекс массива соответствует букве алфавита, а значение - количеству вхождений буквы в строке. В этом случае затраты по памяти будут 26*4байта, то есть О(1), так как не зависят от размера строки.
Чуваки просто копируют FAANG) Когда у тебя огромный поток кандидатов, то на собеседовании ты можешь, что угодно спрашивать. В реальной же работе ты с этим не столкнешься в 90% случаев
@@okke00 если формочки клепаешь, наверное не столкнёшься. Но если пишешь код, производительность которого более менее что-то значит, то хорошо как минимум понимать какая сложность используемого кода, чтобы не написать код с сложность n!
@@jeromewicks3896 Производительность в реальных продакшн приложениях почти никогда не упирается в сложность алгоритмов, скорее в I\O операции, где оптимизируют совершенно другими методами. Плюс узкие места ищут не умозрительной оценкой сложности алгоритмов, а профилированием. Ну и да, любая нормальная quality gate тулза тебе подсветить откровенную дичь с экспоненциальной сложностью
@@okke00 1) Я при код ревью много раз встречал места где алгоритм можно оптимизировать. Как по скорости, так и по памяти. 2) Да, узкие места ищут профилированием. Но высокий скил в том и заключается чтобы такие узкие места создавать как можно реже. 3) Проблема в том что "quality gate тулза" работает уже с готовым кодом. Зачем в команде человек, который пишет говно и потом его переделывает (и то если сможет)? Поэтому вполне логично слабеньких отсекать еще на входе.
@@tarasg7122 1) Далеко не всегда такие места надо оптимизировать. Одно дело когда правка тривиальна и по сути ничего не стоит, тут да, можно и оптимизнуть. Но если надо убить часа два времени, а то и больше, на оптимизацию алгоритма, который просто выглядит так, что его можно написать оптимальнее, то это явно не то чем стоит заниматься. 2.) Без профилирования практически невозможно находить реальные узкие места и от скилла тут мало что зависит(разве что скилл поможет совсем уж тривиальные ошибки не допускать) 3) А как тут поможет алгоритмическая секция? Любой олимпиадник ее пройдет с легкостью, при этом именно они чаще других пишут то, что в энтерпрайзе принято считать говнокодом.
В начале рассуждения для языка python очень некоректные. Вы и так и так будете делать для строк копии данных, так как это неизменяемый тип файла. Так что собеседование например на позициюю питон разработчика превращается в какой то сюр. Вообще большая ошибка брать задачи из строготепизированных языков со стеком памяти, и натягивать их на языки где только управляемая куча. Понятно что питон тут чисто для наглядности как псевдоязык, но сам язык позволяет решать такие задачи проще и лаконичнее.
я бы подумал, брать ли кандидата с таким кодом. Вот написал функцию, какие-то входные аргументы. А аннотации типов не написал. Что за cur, что за open, close??? С первого взгляда ничего не ясно.
Я не знаю питон, но я бы решил первую задачу так: Проходим в цикле по всем буквам первой строки, внутри цикла проходим по буквам второй строки. Если находим совпадение - удаляем обе буквы. В конце должны остаться две пустых строки.
Что значит удаляем? Допустим, строки у вам из миллионов байт, тогда каждое такое удаление - это реаллокация и копирование памяти и это дорого. К тому же у вас выходит квадратичная сложность алгоритма, а тут - линейная, за счёт доп памяти на словари.
@@cat35467 без разницы, строки иммутабельны в питоне и это будет уже новая скопированная строка. Плюс квадратичная сложность. В общем, потренируйтесь ещё, собес вы бы пока не прошли :)
Задача со скобочками на джаве в таком виде не принимается в вашем же контесте. не проходит по ограничению памяти (наверное слишком много занимает рекурсивный стек вызова). Убил всю голову, пока не нашел уже решенный вариант на гитхабе. и там алгоритм очень потный вышел. я его так и не понял
Основные ошибки / корнеры: - Неправильное представление данных. Данные могут быть представлены некорректно определенной структурой. Пример: превращение строки во множество убирает повторяющиеся символы. - Асимметрия данных: следует из предыдущего. - Непонимание работы утилит, структур и методов языка - будь внимателен. Иногда стоит написать что-то своим кодом, чтобы показать понимание работы. - Всегда начинайте задачу с тесткейсов для понимания условий и работы программы - При задаче на создание строк: начинай думать о том, что можно приписать / удалить из строки для достижения ответа. - Быстрые исправления не всегда хороши. - Пытайся написать / исправить сложную функцию так, чтобы в ней не было лишних вызовов - Не мутируй состояние аргументов внутри рекурсивной функции, если точно не уверен, что это не повредит алгоритму
в первой задаче есть ошибка. Смотрим определение анаграммы "Слово или словосочетание, образованное путём перестановки букв, составляющих другое слово (или словосочетание)." Важно обратить внимание на слово "другое". Т.е. абв не является анаграммой абв
@@mapron1 в том то и дело, что обычно пишется log без указания основания. А ln - это уже с основанием, которое в данном случае, скорее всего, не подойдет
@@vasya.k1n6 при оценке O-большое сложность берется с точностью до константы. log2(x)=ln(x)/ln(2) - формула перехода к новому основанию, где ln(2) - константа. Т.е. если пишется оценка O большое основание можно указывать вообще любое.
бред, конечное решение первой задачи решается одним if(ом) len(a) == len(b) в теле первого или второго решения, где мы созвываем в сет одну строку и потом смотрим вхождения из первой
14:20, мне вот просто интересно, неужели я такой тупой, и в яндексе сидят гениальные люди, потому что, когда я встретил эту задачу, мне понадобилось где-то около 5-6 часов и лишняя пара нервов, чтобы найти решение. Но дело в том, что если гуглить, то решение найти можно за пару минут. И у меня возникает вопрос, на кой фиг просить на собеседовании писать подобное карандашом, если в реале, ты просто пойдешь гуглить. Я уверен, что встреться эта задача этому челу через год, он бы взял и пошел гуглить, так почему отбор кандидатов делается по тому, сколько ты тупо вызубришь и насколько тебе повезет, а не по твоим реальным умственным способностям или знаниям тех или иных инструментов разработки???
Смысл не в том, чтобы ты загуглил решение. Смысл в том, чтобы проверить, способен ли ты решить сам, то есть, насколько хорошо у тебя работают мозги. Зубрить не надо - это сразу будет видно, когда ты выдаешь заученные решения. Собеседующему важно увидеть, как ты сам думаешь.
Тут скорее оговорка, не в строке, а во входной последовательности данных. Задача ведь искусственная. Обычно подобные задачи требуют не строки проверить на "анаграмность", а коллекции каких угодно объектов. Словари из объектов можно создать, а вот массивы объектами индексировать - не очень удобно)
4:42 - Зачем вычитать словари, если их можно сравнить и как они могут вычитаться, если питон это не поддерживает? Напутано с множествами. И соответственно не понятно, как там неправильно работает Counter - мега сложный питон функционал, который автор следом изобретает и сам.
Мне кажется мой алгоритм получше для последней задачи, не идеально конечно, но ни одного вызова зря, меньше передаваемых параметров, можно ещё строку сразу делать 2 N размера, чтобы не прибавлять, но по сути вот: С++ void wow(int N, std::string currentString = std::string(), int openCount = 0) { if ((N == 0) && (openCount == 0)) { std::cout
мы создаём 4*n дополнительной памяти для хранения пар символ - количество,; а когда поправил зависит от того, сколько там памяти этот хипстерский метод берёт
Алгоритм №4: O(n) по скорости и O(1) по памяти - заводим массив размера всех возможных букв алфавита, где в i-ом элементе будет храниться количество таких букв. Проходя по первой строке увеличиваем счетчик букв в этом массиве, проходя по второй строке - уменьшаем счётчик числа повторений этих букв. Если массив стал из нулей, то строки - анаграммы.
Хм. А время, которое уйдет на формирование массива с алфавитом, обеспечение уникальности символов в нем, а проверка массива на нули? Это же вроде всё время займет.
@@РомаБерендеев-ш3з Очень поверхностно оценивать время работы программы описанным Вами образом, потому что размер алфавита может быть не ограничен только одним языком или например только таблицей ASCII, а быть например размером во весь лонг т. е. порядка 2 в 64 степени значений, тогда выделение такого объёма памяти нельзя оценивать как константу
@@FakePlv Да, займёт причём ровно О(С) так как проверку на нули можно осуществлять с помощью поддерживая одного числа, которое будет значить количество нулей в массиве на данной итерации, такую величину пересчитывать очень просто, так как на каждой итерации изменяется ровно один элемент такого массива
Внимание, в решении второй задачи ашипка ) Если n == 0 то выводится на печать пустая строка, а это неправильно, пустая строка не является корректной комбинацией скобок. Возьмите меня на работу, лол
Блин, а я решил эту задачу построив граматику, сделал правила прождения цепочек и на шаге n отсекал нетерминальные цепочки... а тут на тебе.. открыл закрыл... 🤣🤣🤣
почему в анаграммах нельзя сравнивать первый символ а с последним символом b в цикле, сдвигая соответственно итератор по а вперед, по b назад, если символы равны, и предварительно проверив на равенство длины строк (на плюсах бы я так и сделал, питон не знаю)
Потому что если слова W1 и W2 являются анаграммами, то не всегда W1 == reversed(W2) (и наоборот). Например, слова eat и tea - анаграммы, но eat != reversed(tea) = aet
@@jeromewicks3896 Да eat != reversed(tea), т.к. reversed(tea) == "aet". Но в задаче на врят ли имелись ввиду анаграммы в литературном смысле, т.е. не важно сходится конкретная строка в реальное слово языка или нет.
Как я решил на пхп (реализацию автора не видел) function anag() { $str1 = str_split('asdasdasdasdasd'); $str2 = str_split('dsadasdasdasdas'); if (count($str1) === count($str2)) { sort($str1); sort($str2); return $str1 == $str2; } return false; }
Между реализацией в комменте и этой: function ang2() { if (splitt('asdasdasdasdasd') == splitt('dsadasdasdasdas')) return true; return false; } function splitt(string $str) { $res = []; for ($i = 0; $i
Я бы первую задачу решил так: 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)
Скучная и неинтересная задача. Я ожидал какого-то иного решения, чем банальная рекурсия, да еще и с передачей строк в стеке! Думаю, есть решение, когда в стек строку не кладут, последовательно меняя в единой базовой строке парные скобки. Вы его даже не удосужились придумать. Накатал на пхп за 15 минут, включая отладку. На бумаге (на собеседовании) проверить алгоритм вряд ли возможно в адекватное кол-во времени. На просчет рекурсии на бумаге уйдет много времени.
Описанным в видео способом решить задачу, на мой взгляд, не сложно, так как именно это решение обычно первым приходит в голову, к тому же строки в Python иммутабельный тип и, возможно, поэтому была выбрана такая реализация. Написание кода на бумаге это нормальная практика, поскольку, как было сказано в видео, не обязательно помнить все сигнатуры функций, важно правильно придумать, изложить и доказать адгоритм, который на Ваш взгляд является оптимальным для решения данной задачи. Менять скобки местами также может иметь худшую ассимптотику, чем предложенное решение, так как чтобы найти правильную пару скобок, возможно придётся обойти всю строку
@@nevmem671 Я о другом. Повторю свою мысль. На бумаге накатать рекурсию - элементарная задача. Но практически невозможно отладить на бумаге. Т.к. наличие нескольких if делают поведение не предсказуемым. При наличии компа и возможности быстро запустить, увидеть ошибку, внести коррективы - 15 минут. Без компа - проверки рекурсии придется считать на бумаге, что чревато ошибками и огромным временем. Даже при правильном написании всех if в рекурсии нет шансов на бумаге что-либо проверить. Вывод: это не лучшая задача на алгоритмы для собеседования. Да, кстати, у меня есть решение без рекурсии линейным циклом - см отдельный коммент.
В том же ролике про собеседование в Google, на сортировку массива, гораздо интереснее рассказывается про то, как надо вести себя на интервью и поэтапно рассматривается решение задачи.
Мда) а вас не смущает, что counter вероятнее всего считая количества вхождений символа для каждой буквы будет пробегаться по всей строке? И так каждый раз? А это n в квадрате сложность. Что же касается кода, если он считает количество уникальных символов, а затем вы сравниваете общую длину, то что вы скажете о таких строках? abb aab В общем я думал к вам регнуться на контест, но неприятно удивлен.
invert_string = string[::-1] return True if string == invert_string else False подглядывал только синтаксис среза, что бы инвертнуть строку, сам алгоритм сходу придумал. Вытирал бы доску сто раз, могу я приходить на собес в яндекс или мал еще?
меня пугает когда он подходит
Беги
))
😂
1. Научить по видео писать алгоритмы невозможно.
2. Показать, как писать на доске алгоритм - бессмысленно. Таких видео очень много (лекции). Все они постановочные, а не документальные, в том смысле, что актер знает роль и пишет на доске заранее срежиссированный текст, делает постановочные ошибки и т.п. В реальности на собеседовании гормональный фон собеседуемого не такой, ведет он себя не так как демонстрирует видео, стремится не к тому, чтобы заученный текст с бумажки переписать, а к тому, чтобы сосредоточится и выдавить из себя хоть что-то.
3. Доска как инструмент нужна для обмена идеями. Для этого подходят рисунки, а не код.
Так, а где тесты перед решением первой задачи? В первом видео на тесты же напирали.
return Counter(a) == Counter(b)
Зачем в анаграммах находить разницу Counter-ов, если можно их сравнить (Conter1==Counter2)?
Да! И более того, как можно ее найти, если оператор вычитания не поддерживается диктом...
Проблема в том, что задаются на собеседованиях задачи В РАЗЫ сложнее, чем упомянутые.
Решай leetcode - там есть задачи сопостовимой сложности. Вопрос тренировки - без подготовки, конечно, пройти сложно алгоритмический уровень.
Было бы странно, если бы на собесах давали задачи такого уровня, на видео показан пример процесса и типичные ошибки.
Задачу со скобками мне дали в седьмом классе, при отборе на школьную олимпиаду по программированию, как-раз на листке писал)
В основном задачи на собеседованиях задаются уровня easy-medium с leetcode. Но некоторые кандидаты и это решить не могут.
@@dmitrypetrov8491 зачем это человеку, который пишет фронт, и может ещё бэк на уровне обработать входящие запросы и сделать запрос в БД? Более 5 лет работу фулстеком с јѕ ни разу эта олимпиалная бредятина не пригодилась. Если ты пишешь игры или что-то требующее математики, то может оно и нужно, но большинству это нахер не всралось для веба, только мозги на собесе иметь собеседуемому
@@user-chf7z61vnd6h8v
Воистину!
Мм, один момент не ясен: был написан тест: parents(3)== { "((( )))", "()()()", "(())()", "()(())", "(()())" }. Но код на доске генерирует только "((( )))", так ведь? Более того в статье Яндекса на хабре про эту задачу также сказано "Вывести последовательности в лексикографическом порядке(правильный алгоритм по-умолчанию выводит их в нужном порядке)" и указана ссылка на это видео как разбор задачи. Получается то, что на доске попроще будет, чем то что на собеседовании по словам из статьи.
Нет не так код на доске генерирует ровно то, что нужно то есть НЕ одну последовательность, там же рекурсивные запуски, которые например уже на второй итерации могут на префикс построить строки "((" и "()", так как эти последовательности никак не противоречат написанному коду
@@nevmem671 Да, вы абсолютно правы, я был невнимателен(забыл вернуться к первому вызову в стеке). Вы писали ниже, что это решение первым приходит в голову. Мне же первым в голову пришло создание класса или же дерево. Расскажите, как вы понимаете, что начать рассуждения надо с рекурсии?
@@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 })
@@slavanikulin8069 Уже не помню, честно говоря, о чем шла речь, но да рекурсия обычно напрашивается первой, избавиться от неё обычно проблемнее, чем её применить. Как раз год назад пытался пройти контест, где было 4 олимпиадные задачи из 6(вроде шесть задач было:) ).. короче до собеседования дело даже не дошло)) У меня много вопросов возникало про адекватность формулировок, но, отвечали мне на них - никак(сам дурак). Была там задачка и про поиск множителей, где нужно было найти нужную комбинацию для заданного произведения. Алгоритм дерева был весьма кстати, правда, обходить пришлось без рекурсии, т.к. не проходил по времени. Разница в скорости алгоритма значительна, например 2ms/636Kb против рекурсивных 56ms/896Kb(метрика контеста). Так что да, в здравом уме и адекватной обстановке, рекурсия не должна приходить в голову, однако на собеседовании(до которого дело дойдет только у олимпиадников), проще сделать ей и решить задачу, чем допускать мелкие ошибки и ожидать подсказок от интервьюера.
По поводу крика души. У меня тоже есть, что сказать. Жаль, конечно, что не удалось устроиться в Яндекс, хотя может оно и к лучшему. Скажу одно, у каждого свои способности и лучшие стороны, если Яндекс планирует использовать лишь скорость применение шаблона и их объем в голове разработчика, то когда-нибудь это аукнется. В универе была группа по спортивному программированию, которая занимала призовые места на мировых олимпиадах, только вот экзамен по программированию сдавал за них я, ибо по какой-то причине им не удалось осилить задачки препода. Я это к тому, что не все задачи требуют хитромудрую формулу для поиска части окружности из миллиарда окружностей, и шаблоны не помогают найти решение проблемы, они лишь пытаются её решить стандартным способом. Чтобы решать проблему надо думать. Чтобы использовать шаблон, надо его помнить.
Сейчас я системный программист, занимаюсь разработкой ОС в коммерческой фирме, есть тонна задач, которые не требуют математики, но требуют очень развитой интуиции, смекалки и аналитического склада ума, что бы быстро уметь анализировать тонны опенсурсных систем и чужого кода на всевозможных языках. Наверное, таким не место в Яндексе, раз у таких дело даже до собеседования не доходит(да, разрабочик интерфейсов каких-нибудь тоже должен решить олимпиадные задачи).
ps: пытался решать задачи честно - самостоятельно, не заглядывая в готовые алгоритмы.
Kernel Plevitsky Справедливости ради стоит сказать, что весь этот алгоритмически-олимпиадный ад стоит того, тк в Яндексе очень благоприятная среда, способствующая быстрому росту. Но если не получится пройти, то ничего страшного)
Здорово, рад за вас, что нашли своё призвание и место!
Там память не О(n) в третьем случае, а O(2a), где а размер алфавита. Для строчных английских букв это 26
Никогда не понимал зачем писать код на доске? Почему не на бересте например или долотом на камне высекать? Все одно с реальной работой не пересекается
Если экстраполировать дальше, то почему бы не разрешить подгугливать синтаксис особо редковстречающихся конструкций, типа предполагается, что стековерфлоу в яндексе отключил злой одмин что ли?
Вы говорите об оптимальном решении и пишете код на пайтоне со встроенными функциями, чей код закрыт. По крайней мере вы не говорите как реализованы counter или defaultdict и какова их производительность (асимптотика и память).
Из очевидных вариантов defaultdict это либо массив, либо map. В обоих случаях для оценки памяти и производительности необходимо брать в расчёт не только длину входной последовательности N, но и размер алфавита M.
Если defaultdict реализован через вектор, то получим время O(N) и память O(M), не считая, конечно, памяти для входных строк.
Если defaultdict реализован через map, то получим время O(N*log(M)) и память O(M). Причём, если быть дотошным, тут память примерно в 2 раза будет больше, чем в случае с вектором.
Однако автор прокритиковал решение через массивы, так что, наверное, defaultdict не реализован через них. Но и решение через map не даёт искомой асимптотики.
Так что, объясните пожалуйста что такое это этот ваш defaultdict, иначе не говорите, что это эффективное решение.
Во-первых:
> 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, если элемента не существовало
PEP8 попросил передать вам привет! ;)
У второй задачи пропущена секция с определением сложности алгоритма
По первой задаче маленькая ошибка : Для 3 варианта решения задачи (про анаграммы) - использование памяти констатное - O(1) - т.к набор букв всегда постоянный - т.е если у нас строка состоит из сторчных латиских букв - то длина массива будет 26. Т.е. вне зависимости от того насколько длинная у нас строка - размер массива всегда будет одинаковый, т.е размер массива не зависит от входного параметра, соответственно сложность по памяти O(1).
Вы были бы абсолютно правы, если бы не еще одно маленькое обстоятельство: кол-во памяти для хранение счетчиков количества символов все-таки зависит от длины входных данных, а именно для хранения числа n нужно log_2(n) с округлением бит информации. Поэтому с увеличением n, затраты по памяти также растут (хотя на данный момент те порядки, при которых рост памяти будет существенным, просто недостижимы).
Поэтому, строго говоря, сложность по памяти (log_2(n)).
@@ignostik2328 Да. Но ассимптотика не считает количество памяти которую и чпользует программа, а показывает как используемые ресурсы изменяются в зависисости от входных данных. Мы можем создать массив из 16000 элементов, который поместит в себе все возможные символы. Соответственно ассимптотика использования памяти будет постоянная. Да, реальное использование памяти будет разное, но ассимптотика будет постоянная.
@@sananyuzb Не понял поинт про 16000 элементов. Насколько я понял Анатолий имеет в виду что будет просходить для строк:
1) 2^8 символов "a"
2) 2^16 символов "a"
3) 2^24 символов "a"
4) 2^32 символов "a"
В этом случае между каждым из этих вариантов будет разница 1 байт, и память растет как O(log(n))
@@alleycat123123123 речь шла о случае, когда строки состоят из строчных латинских букв, в таком случае мы можем использовать массив из 26 элементов, где индекс массива соответствует букве алфавита, а значение - количеству вхождений буквы в строке. В этом случае затраты по памяти будут 26*4байта, то есть О(1), так как не зависят от размера строки.
То чувство, когда задача посложнее оказалась легче, чем задача полегче.
на литкоде такое постоянно... медиум иногда легче чем изи
В работе нужны знания того как оптимизировать алгоритм? Или, как обычно, дворников заставляют сдавать кандидатский минимум?
Чуваки просто копируют FAANG) Когда у тебя огромный поток кандидатов, то на собеседовании ты можешь, что угодно спрашивать. В реальной же работе ты с этим не столкнешься в 90% случаев
@@okke00 если формочки клепаешь, наверное не столкнёшься. Но если пишешь код, производительность которого более менее что-то значит, то хорошо как минимум понимать какая сложность используемого кода, чтобы не написать код с сложность n!
@@jeromewicks3896 Производительность в реальных продакшн приложениях почти никогда не упирается в сложность алгоритмов, скорее в I\O операции, где оптимизируют совершенно другими методами. Плюс узкие места ищут не умозрительной оценкой сложности алгоритмов, а профилированием. Ну и да, любая нормальная quality gate тулза тебе подсветить откровенную дичь с экспоненциальной сложностью
@@okke00
1) Я при код ревью много раз встречал места где алгоритм можно оптимизировать. Как по скорости, так и по памяти.
2) Да, узкие места ищут профилированием. Но высокий скил в том и заключается чтобы такие узкие места создавать как можно реже.
3) Проблема в том что "quality gate тулза" работает уже с готовым кодом. Зачем в команде человек, который пишет говно и потом его переделывает (и то если сможет)?
Поэтому вполне логично слабеньких отсекать еще на входе.
@@tarasg7122 1) Далеко не всегда такие места надо оптимизировать. Одно дело когда правка тривиальна и по сути ничего не стоит, тут да, можно и оптимизнуть. Но если надо убить часа два времени, а то и больше, на оптимизацию алгоритма, который просто выглядит так, что его можно написать оптимальнее, то это явно не то чем стоит заниматься.
2.) Без профилирования практически невозможно находить реальные узкие места и от скилла тут мало что зависит(разве что скилл поможет совсем уж тривиальные ошибки не допускать)
3) А как тут поможет алгоритмическая секция? Любой олимпиадник ее пройдет с легкостью, при этом именно они чаще других пишут то, что в энтерпрайзе принято считать говнокодом.
Спасибо, видео помогло разобраться с рекурсией при помощи визуализатора, добавил return после 3го if-a так нагляднее.
Эх, а потом перекладывать жсоны….
А если я устроюсь в яндекс, футболки выдадут?
да, ты и будешь тем кто их будет выдавать)
В начале рассуждения для языка python очень некоректные. Вы и так и так будете делать для строк копии данных, так как это неизменяемый тип файла. Так что собеседование например на позициюю питон разработчика превращается в какой то сюр.
Вообще большая ошибка брать задачи из строготепизированных языков со стеком памяти, и натягивать их на языки где только управляемая куча. Понятно что питон тут чисто для наглядности как псевдоязык, но сам язык позволяет решать такие задачи проще и лаконичнее.
я бы подумал, брать ли кандидата с таким кодом. Вот написал функцию, какие-то входные аргументы. А аннотации типов не написал. Что за cur, что за open, close??? С первого взгляда ничего не ясно.
Я не знаю питон, но я бы решил первую задачу так: Проходим в цикле по всем буквам первой строки, внутри цикла проходим по буквам второй строки. Если находим совпадение - удаляем обе буквы. В конце должны остаться две пустых строки.
Что значит удаляем? Допустим, строки у вам из миллионов байт, тогда каждое такое удаление - это реаллокация и копирование памяти и это дорого.
К тому же у вас выходит квадратичная сложность алгоритма, а тут - линейная, за счёт доп памяти на словари.
@@w1cked11 ну не удаляем, а заменяем на пробел
@@cat35467 без разницы, строки иммутабельны в питоне и это будет уже новая скопированная строка.
Плюс квадратичная сложность.
В общем, потренируйтесь ещё, собес вы бы пока не прошли :)
так там скрытых вычислений хватает :) даром что коротко и красиво :)
Тут же O нотация только интересна
Задача со скобочками на джаве в таком виде не принимается в вашем же контесте. не проходит по ограничению памяти (наверное слишком много занимает рекурсивный стек вызова). Убил всю голову, пока не нашел уже решенный вариант на гитхабе. и там алгоритм очень потный вышел. я его так и не понял
Время 4:50. return ca==cb исправляет ситуацию.
Да, но тогда пришлось бы разбираться с более хитровывернутым примером, чтобы донести мысль о том, что иногда явная кодяра лучше неявной.
Основные ошибки / корнеры:
- Неправильное представление данных. Данные могут быть представлены некорректно определенной структурой. Пример: превращение строки во множество убирает повторяющиеся символы.
- Асимметрия данных: следует из предыдущего.
- Непонимание работы утилит, структур и методов языка - будь внимателен. Иногда стоит написать что-то своим кодом, чтобы показать понимание работы.
- Всегда начинайте задачу с тесткейсов для понимания условий и работы программы
- При задаче на создание строк: начинай думать о том, что можно приписать / удалить из строки для достижения ответа.
- Быстрые исправления не всегда хороши.
- Пытайся написать / исправить сложную функцию так, чтобы в ней не было лишних вызовов
- Не мутируй состояние аргументов внутри рекурсивной функции, если точно не уверен, что это не повредит алгоритму
в первой задаче есть ошибка. Смотрим определение анаграммы "Слово или словосочетание, образованное путём перестановки букв, составляющих другое слово (или словосочетание)." Важно обратить внимание на слово "другое". Т.е. абв не является анаграммой абв
во втором решении, я бы не стал перезатирать стандартную функцию open - это не ошибка в алгоритме, но так делать не надо
@@segreyfurt
что за функция open? у него есть только параметр open метода generate
@@manOfPlanetEarth нельзя использовать имена встроенных сущностей для переменных. `open` -- открытие файла
"другое" не значит "не равное". см разницу is/==
Но ведь во второй задаче генерируется только 1 из возможных последовательностей - "((( )))" а требуются все.
не так :)
pep8? Не...
зашел сюда за этим комментарием
зачем коду на доске pep8? это же не продакшн код, который нужно поддерживать
@@jeromewicks3896 зачем говорить красивым и грамотным языком? мы же не на егэ
@@MrBibiw Именно!
ln - это натуральный, с основанием e, а log - это уже другое основание (например, 2)
С точки зрения О большого основание алгоритма не важно.
@@mapron1 в том то и дело, что обычно пишется log без указания основания. А ln - это уже с основанием, которое в данном случае, скорее всего, не подойдет
@@vasya.k1n6 при оценке O-большое сложность берется с точностью до константы.
log2(x)=ln(x)/ln(2) - формула перехода к новому основанию, где ln(2) - константа. Т.е. если пишется оценка O большое основание можно указывать вообще любое.
Для O большое с асимптотическим приближением не важно.
5:29 Хм, а почему бы не написать просто return ca == cb?
Вроде задача была про все возможные последовательности.. Тут только одна ((())) . ???
Требуется вывести все правильные скобочные последовательности длины 2 ⋅ n, упорядоченные лексикографически
бред, конечное решение первой задачи решается одним if(ом) len(a) == len(b) в теле первого или второго решения, где мы созвываем в сет одну строку и потом смотрим вхождения из первой
Нерекурсивно, тут ещё можно с помощью кодов Грея очень красивое решение выдать (скобочные последовательности).
14:20, мне вот просто интересно, неужели я такой тупой, и в яндексе сидят гениальные люди, потому что, когда я встретил эту задачу, мне понадобилось где-то около 5-6 часов и лишняя пара нервов, чтобы найти решение. Но дело в том, что если гуглить, то решение найти можно за пару минут. И у меня возникает вопрос, на кой фиг просить на собеседовании писать подобное карандашом, если в реале, ты просто пойдешь гуглить. Я уверен, что встреться эта задача этому челу через год, он бы взял и пошел гуглить, так почему отбор кандидатов делается по тому, сколько ты тупо вызубришь и насколько тебе повезет, а не по твоим реальным умственным способностям или знаниям тех или иных инструментов разработки???
А еще кстати, этот код не проходит проверку на их же тестах(язык котлин, ни одной лишней строчки), выбрасывает, что лимит памяти исчерпан)))
@@ELLA-fq6lo Если лимит памяти исчерпан - это не проблема алгоритма, а проблема Котлина и JVM. Напиши на чём-нибудь, что не тратит так много памяти
@@jeromewicks3896 Вот, сука, как я сразу не додумался до этого, пойду на ассемблере напишу
Смысл не в том, чтобы ты загуглил решение. Смысл в том, чтобы проверить, способен ли ты решить сам, то есть, насколько хорошо у тебя работают мозги. Зубрить не надо - это сразу будет видно, когда ты выдаешь заученные решения. Собеседующему важно увидеть, как ты сам думаешь.
@@cat35467 Почему бы тогда не дать приближенную к реальности задачу?
почему Python, не понятно? на собесе тоже этот язык надо использовать, он что, самый основной вдруг?
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.
You should always start counting from zero ;)
Но ведь разность Counter-ов возвращает Counter, и никогда не будет равна 0 :(
Там len() от Counter
Как правильно вычислить временную сложность для последней задачи со скобками?
поидеи линейная
@@aslanator точно не линейная. Экспоненциальная с базой экспоненты < 4 и > 2
Ну или суб-экспоненциальная. Там непросто вычислить из-за условий
Какие типы данных могут быть в строке кроме char? 7:48
Мб wchar в C++
Тут скорее оговорка, не в строке, а во входной последовательности данных. Задача ведь искусственная. Обычно подобные задачи требуют не строки проверить на "анаграмность", а коллекции каких угодно объектов. Словари из объектов можно создать, а вот массивы объектами индексировать - не очень удобно)
def anagram(srt1, str2):
return sorted(str1) == sorted(str2)
Главным критерием было сохранение времени и отсутствие модификаций, так что не пойдет
@@nazarbayev_university и где же мы модифицировали строки?
На сортировку O(nlogn) вместо O(n) уйдет
А есть такая же футботка, только немного поярче?)
Первая задача
(str1, str2) => {
const getHash = (str) => str.split('').sort().join()
return getHash(str1) === getHash(str2)
}
4:42 - Зачем вычитать словари, если их можно сравнить и как они могут вычитаться, если питон это не поддерживает? Напутано с множествами. И соответственно не понятно, как там неправильно работает Counter - мега сложный питон функционал, который автор следом изобретает и сам.
Можно еще вызывать рекурсивную функцию с параметрами ("(", 1, 0, n). Выигрыш очень маленький, но он есть
Мне кажется мой алгоритм получше для последней задачи, не идеально конечно, но ни одного вызова зря, меньше передаваемых параметров, можно ещё строку сразу делать 2 N размера, чтобы не прибавлять, но по сути вот:
С++
void wow(int N, std::string currentString = std::string(), int openCount = 0)
{
if ((N == 0) && (openCount == 0))
{
std::cout
А почему N log N если после сортировки нужно будет ещё сравнить строки? Это уже O(N)
O(n log(n)) + O(n) это та же оценка что и O(n log(n))
В третьем подходе к первой задаче тратится ведь константное количество памяти
мы создаём 4*n дополнительной памяти для хранения пар символ - количество,;
а когда поправил зависит от того, сколько там памяти этот хипстерский метод берёт
Можно было просто написать counter1 == counter2
Алгоритм №4: O(n) по скорости и O(1) по памяти - заводим массив размера всех возможных букв алфавита, где в i-ом элементе будет храниться количество таких букв.
Проходя по первой строке увеличиваем счетчик букв в этом массиве, проходя по второй строке - уменьшаем счётчик числа повторений этих букв. Если массив стал из нулей, то строки - анаграммы.
Не верная оценка памяти, так как в описанном Вами решении количество используемой памяти О(С), где С - размер алфавита, чем нельзя пренебрегать
Хм. А время, которое уйдет на формирование массива с алфавитом, обеспечение уникальности символов в нем, а проверка массива на нули? Это же вроде всё время займет.
Время растет линейно, а расход памяти не растет, поэтому асимптотическая сложность записана верно
@@РомаБерендеев-ш3з Очень поверхностно оценивать время работы программы описанным Вами образом, потому что размер алфавита может быть не ограничен только одним языком или например только таблицей ASCII, а быть например размером во весь лонг т. е. порядка 2 в 64 степени значений, тогда выделение такого объёма памяти нельзя оценивать как константу
@@FakePlv Да, займёт причём ровно О(С) так как проверку на нули можно осуществлять с помощью поддерживая одного числа, которое будет значить количество нулей в массиве на данной итерации, такую величину пересчитывать очень просто, так как на каждой итерации изменяется ровно один элемент такого массива
Я вот в 11 классе сейчас и смотрю строчки кода он пишет знакомые и понятные, а говорит что-то максимально страшное
Внимание, в решении второй задачи ашипка ) Если n == 0 то выводится на печать пустая строка, а это неправильно, пустая строка не является корректной комбинацией скобок. Возьмите меня на работу, лол
А если использовать ord? Коды символов одной строки прибавляем к переменной, коды второй соответственно вычитаем?
что за глупость? причем тут ord? замени скобки на 1/0 и ищи решение
Не будет работать, суммы кодов символов строк "bb" и "ac" равны, но они не являются анаграммами
@@mixwheels я имел ввиду задачу про анаграммы. Но да, моя ошибка. что не уточнил о какой задаче речь.
@@minmanr , утром я это уж тоже понял)
может сложение на xor заменить?
Для анограм можно посчитать hash по алгоритму hash += *str++
Очень сложный юмор
Нельзя. Пример "abc" и "aad"
@@gologames
Я же сказал очень сложный юмор
@@dmitrijkarmatskij2124 Я подозревал. Хорошо тогда
питон выглядит так будто на нем алгоритмы писать проще в 10 раз чем на java
Да кто такая эта ваша симметрия?
For the first function to work one should first do: from collections import defaultdict
вроде так нельзя переменные называть. aSet
Можно как угодно, хоть _. Другое дело, рекомендуется это или нет
Блин, а я решил эту задачу построив граматику, сделал правила прождения цепочек и на шаге n отсекал нетерминальные цепочки... а тут на тебе.. открыл закрыл... 🤣🤣🤣
пример правильной скобочной последовательности: ( . ) ( . )
пример неправильной скобочной последовательности: ( . ) ( . ) ( . )
Извините)
Не будем использовать сложное встроенное встроенное в язык средство. Будем использовать другое сложное встроенное в язык средство (>_
почему в анаграммах нельзя сравнивать первый символ а с последним символом b в цикле, сдвигая соответственно итератор по а вперед, по b назад, если символы равны, и предварительно проверив на равенство длины строк (на плюсах бы я так и сделал, питон не знаю)
Потому что если слова W1 и W2 являются анаграммами, то не всегда W1 == reversed(W2) (и наоборот). Например, слова eat и tea - анаграммы, но eat != reversed(tea) = aet
@@jeromewicks3896 а, точно, спасибо за ответ )
@@jeromewicks3896 Да eat != reversed(tea), т.к. reversed(tea) == "aet". Но в задаче на врят ли имелись ввиду анаграммы в литературном смысле, т.е. не важно сходится конкретная строка в реальное слово языка или нет.
Как я решил на пхп (реализацию автора не видел)
function anag() {
$str1 = str_split('asdasdasdasdasd');
$str2 = str_split('dsadasdasdasdas');
if (count($str1) === count($str2)) {
sort($str1);
sort($str2);
return $str1 == $str2;
}
return false;
}
Между реализацией в комменте и этой:
function ang2() {
if (splitt('asdasdasdasdasd') == splitt('dsadasdasdasdas'))
return true;
return false;
}
function splitt(string $str) {
$res = [];
for ($i = 0; $i
Я бы первую задачу решил так:
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)
Разве так не будет быстрее и без доп.средств(sort, counter):
str1 = "hhelloo"
str2 = "oollehh"
str2 = str2[::-1]
print(str2 == str1)
?
Вам нужно почитать что такое анаграммы.
Ваш код проверяет является ли одна строка другой , но заданной в обратном порядке.
@@zhalgasnurakhmetov9646 Да, спасибо, разобрался, действительно, не понял задание сначала )
Это код для определения палиндрома
Господи, какая скука.
8:02 в последней строчке произойдёт сравнение ссылок на словари, а не сравнение словарей. Всегда будет False
сравнение ссылок происходит по оператору `is`.
оператор `==` вызывает метод `__eq__()`.
char ['kær] (от англ. character) - символ
шлак
Скучная и неинтересная задача. Я ожидал какого-то иного решения, чем банальная рекурсия, да еще и с передачей строк в стеке! Думаю, есть решение, когда в стек строку не кладут, последовательно меняя в единой базовой строке парные скобки. Вы его даже не удосужились придумать. Накатал на пхп за 15 минут, включая отладку. На бумаге (на собеседовании) проверить алгоритм вряд ли возможно в адекватное кол-во времени. На просчет рекурсии на бумаге уйдет много времени.
Описанным в видео способом решить задачу, на мой взгляд, не сложно, так как именно это решение обычно первым приходит в голову, к тому же строки в Python иммутабельный тип и, возможно, поэтому была выбрана такая реализация. Написание кода на бумаге это нормальная практика, поскольку, как было сказано в видео, не обязательно помнить все сигнатуры функций, важно правильно придумать, изложить и доказать адгоритм, который на Ваш взгляд является оптимальным для решения данной задачи. Менять скобки местами также может иметь худшую ассимптотику, чем предложенное решение, так как чтобы найти правильную пару скобок, возможно придётся обойти всю строку
@@nevmem671 Я о другом. Повторю свою мысль. На бумаге накатать рекурсию - элементарная задача. Но практически невозможно отладить на бумаге. Т.к. наличие нескольких if делают поведение не предсказуемым. При наличии компа и возможности быстро запустить, увидеть ошибку, внести коррективы - 15 минут. Без компа - проверки рекурсии придется считать на бумаге, что чревато ошибками и огромным временем. Даже при правильном написании всех if в рекурсии нет шансов на бумаге что-либо проверить. Вывод: это не лучшая задача на алгоритмы для собеседования. Да, кстати, у меня есть решение без рекурсии линейным циклом - см отдельный коммент.
В том же ролике про собеседование в Google, на сортировку массива, гораздо интереснее рассказывается про то, как надо вести себя на интервью и поэтапно рассматривается решение задачи.
15 минут? да уж, программист ты так себе
Мда) а вас не смущает, что counter вероятнее всего считая количества вхождений символа для каждой буквы будет пробегаться по всей строке? И так каждый раз? А это n в квадрате сложность.
Что же касается кода, если он считает количество уникальных символов, а затем вы сравниваете общую длину, то что вы скажете о таких строках?
abb aab
В общем я думал к вам регнуться на контест, но неприятно удивлен.
как же яндекс переживет потерю такого ценного кандидата
invert_string = string[::-1]
return True if string == invert_string else False
подглядывал только синтаксис среза, что бы инвертнуть строку, сам алгоритм сходу придумал. Вытирал бы доску сто раз, могу я приходить на собес в яндекс или мал еще?