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

[hlystomv]

1. Научить по видео писать алгоритмы невозможно.
2. Показать, как писать на доске алгоритм - бессмысленно. Таких видео очень много (лекции). Все они постановочные, а не документальные, в том смысле, что актер знает роль и пишет на доске заранее срежиссированный текст, делает постановочные ошибки и т.п. В реальности на собеседовании гормональный фон собеседуемого не такой, ведет он себя не так как демонстрирует видео, стремится не к тому, чтобы заученный текст с бумажки переписать, а к тому, чтобы сосредоточится и выдавить из себя хоть что-то.
3. Доска как инструмент нужна для обмена идеями. Для этого подходят рисунки, а не код.

[alloyoshi]

Проблема в том, что задаются на собеседованиях задачи В РАЗЫ сложнее, чем упомянутые.

[vladtokarev]

Там память не О(n) в третьем случае, а O(2a), где а размер алфавита. Для строчных английских букв это 26

[protasovse]

Зачем в анаграммах находить разницу Counter-ов, если можно их сравнить (Conter1==Counter2)?

[MajinSaha]

Так, а где тесты перед решением первой задачи? В первом видео на тесты же напирали.

[FakePlv]

Мм, один момент не ясен: был написан тест: parents(3)== { "((( )))", "()()()", "(())()", "()(())", "(()())" }. Но код на доске генерирует только "((( )))", так ведь? Более того в статье Яндекса на хабре про эту задачу также сказано "Вывести последовательности в лексикографическом порядке(правильный алгоритм по-умолчанию выводит их в нужном порядке)" и указана ссылка на это видео как разбор задачи. Получается то, что на доске попроще будет, чем то что на собеседовании по словам из статьи.

[sananyuzb]

По первой задаче маленькая ошибка : Для 3 варианта решения задачи (про анаграммы) - использование памяти констатное - O(1) - т.к набор букв всегда постоянный - т.е если у нас строка состоит из сторчных латиских букв - то длина массива будет 26. Т.е. вне зависимости от того насколько длинная у нас строка - размер массива всегда будет одинаковый, т.е размер массива не зависит от входного параметра, соответственно сложность по памяти O(1).

[okke]

Никогда не понимал зачем писать код на доске? Почему не на бересте например или долотом на камне высекать? Все одно с реальной работой не пересекается

[AlexosYou]

Вы говорите об оптимальном решении и пишете код на пайтоне со встроенными функциями, чей код закрыт. По крайней мере вы не говорите как реализованы counter или defaultdict и какова их производительность (асимптотика и память).
Из очевидных вариантов defaultdict это либо массив, либо map. В обоих случаях для оценки памяти и производительности необходимо брать в расчёт не только длину входной последовательности N, но и размер алфавита M.
Если defaultdict реализован через вектор, то получим время O(N) и память O(M), не считая, конечно, памяти для входных строк.
Если defaultdict реализован через map, то получим время O(N*log(M)) и память O(M). Причём, если быть дотошным, тут память примерно в 2 раза будет больше, чем в случае с вектором.
Однако автор прокритиковал решение через массивы, так что, наверное, defaultdict не реализован через них. Но и решение через map не даёт искомой асимптотики.
Так что, объясните пожалуйста что такое это этот ваш defaultdict, иначе не говорите, что это эффективное решение.

[ВладимирТерещенко-иц]

У второй задачи пропущена секция с определением сложности алгоритма

[__dot]

Основные ошибки / корнеры:
- Неправильное представление данных. Данные могут быть представлены некорректно определенной структурой. Пример: превращение строки во множество убирает повторяющиеся символы.
- Асимметрия данных: следует из предыдущего.
- Непонимание работы утилит, структур и методов языка - будь внимателен. Иногда стоит написать что-то своим кодом, чтобы показать понимание работы.
- Всегда начинайте задачу с тесткейсов для понимания условий и работы программы
- При задаче на создание строк: начинай думать о том, что можно приписать / удалить из строки для достижения ответа.
- Быстрые исправления не всегда хороши.
- Пытайся написать / исправить сложную функцию так, чтобы в ней не было лишних вызовов
- Не мутируй состояние аргументов внутри рекурсивной функции, если точно не уверен, что это не повредит алгоритму

[dmitrymalygin]

В работе нужны знания того как оптимизировать алгоритм? Или, как обычно, дворников заставляют сдавать кандидатский минимум?

[Sevenvad]

То чувство, когда задача посложнее оказалась легче, чем задача полегче.

[gerhardshreder]

я бы подумал, брать ли кандидата с таким кодом. Вот написал функцию, какие-то входные аргументы. А аннотации типов не написал. Что за cur, что за open, close??? С первого взгляда ничего не ясно.

[rusfungame]

А если я устроюсь в яндекс, футболки выдадут?

[РоманГалушка-же]

Задача со скобочками на джаве в таком виде не принимается в вашем же контесте. не проходит по ограничению памяти (наверное слишком много занимает рекурсивный стек вызова). Убил всю голову, пока не нашел уже решенный вариант на гитхабе. и там алгоритм очень потный вышел. я его так и не понял

[cat]

Я не знаю питон, но я бы решил первую задачу так: Проходим в цикле по всем буквам первой строки, внутри цикла проходим по буквам второй строки. Если находим совпадение - удаляем обе буквы. В конце должны остаться две пустых строки.

[ZzooD]

Какие типы данных могут быть в строке кроме char? 7:48

[tirsky]

ln - это натуральный, с основанием e, а log - это уже другое основание (например, 2)

[MikhailMatrosov]

5:29 Хм, а почему бы не написать просто return ca == cb?