Comments 32
я бы по каждому методу по подробнее почитал бы с удовольствием
с парой-тройкой примеров в идеале...
Примеры не проблема, ссылки на задачи есть, а уже в самих задачах можно посмотреть лучшие варианты решения на любом языке. Порой, это буквально несколько строчек, по этому понять алгоритм не сложно. Мне это здорово помогло, когда только начинал решать задачки на Скала, я (по привычке) использовал идеоматичный функциональный подход. Увы, по скорости он сильно проигрывает (порой, но не всегда!) императивному. Возможность подсмотреть и понять, что требуется помогла выйти в лидеры.
Ну, а подробности, да, придется искать самому. Впрочем, неплохих книжек по алгоритмам хватает.
книжки по алгоритмам - планирую почитать в будущем
а вот изучать решения задач и пытаться понять паттерны, это как бы возможно, но не продуктивно. Я, собственно, так и делаю, а до многих и своим умом дохожу. Но речь скорее именно о том, как понять что в данной ситуации нужнен конкретный алгоритм и как его правильно применить, как к этому прийти итд.
Только решая задачи, этот навык приобретается.
Читая книжки по алгоритмам, вы научитесь в теории, а тот самый навык так и остнется ноль.
Вот, писал спецом на такие случаи: https://github.com/lma10h/ctod_bridge
Вот что должно вымереть в первую очередь в эпоху AI
Индусы решающие литкод?
Думается, что алгоритмические задачки не вымрут. Этот скилл требовали на собеседованиях 10 лет назад, и, скорее всего, будут требовать ещё долго - даже в эпоху развитого AI. А значит и тренажёры по зубрёжке будут жить. Кстати, как относитесь к тому, что на собесах дают алготимические задачки решать? Считаете полезной практикой или устаревшей традицией?
Мне это всегда казалось и продолжает казаться неплохим способом проверить замотивированность кандидата заниматься относительно длительной подготовкой к интервью. Примерно как диплом о ВО доказательство 4-6 лет "усидчивости". Поэтому с готовностью решаю алгоритмические секции, но со своей стороны при собеседованиях делаю скидку, что вообще говоря, человек не обязан знать трюк с prefix sum, будь он трижды тривиальным (когда его знаешь). Не обязан уметь вращать деревья в уме. Но если вдруг умеет и в структуры данных, и в методы работы с ними, то разговор точно пойдет и проще, и интереснее. По крайней мере, это точно интереснее, чем фреймворк А, который уже завтра будет заменён фреймворком Б.
Это как в математике - есть отличники, которые вызубрили стандартные задачи, есть люди, которые на стандартных задачах научились решать любые. В первых нет никакого особого смысла. С программированием то же самое - тот ч кто выучил и пошёл дальше, намного полезнее того, кто выучил и застрял.
Проблема при решении задач часто заключается в том, что не очень то понятно, что какой-то из этих паттернов может быть использован. Часто требуется какое-то неявное допущение, с которым ещё не понятно истинно ли оно и как его истинность доказать, чтобы можно было этот паттерн использовать.
Да, для паттернов это частая история. Взять в том числе гоф-паттерны: когда ты впервые с ними сталкиваешься, то не осознаёшь когда их нужно применять и стремишься их использовать даже там, где не надо. Вероятнее всего по мере решения задач, придёт понимание относительно того, где какой паттерн применить. Они сами всплывут в памяти и вам останется лишь взглянуть в статью, чтобы использовать её как шпаргалку
недавно ради разогрева прорешал яндекс контест по алгоритмам; литкод несколько расслабленее и не так жестко проверяет выходы за границы времени и памяти.
Иногда кажется что можно решить одним методом в лоб, но размерность 10^9 сразу требует упростить задачу а не решать перебором.
Яндекс контест показался более жестким чем литкод, особенно последняя задачка в контесте крови попила.
Вчера прислали результат - попал в топ 300 и могу соскочить с алго-интервью в Яндекс, но оно мне не надо... вообще подумываю а зачем я поперся на эти алгоритмы? Наверное потому что на рынке тишина а тренироваться нужно. На собеседовании по алгоритмам все было просто, основная проблема была не задача а непривычность решать задачу в свете софитов, я просто не мог думать. Решил на автомате, спинным мозгом, долго тупил, но в итоге прошел интервью.
Систем дизайн интервью это было что то нечто - слишком примитивное, интервьювер не в духе, я тупил "а что здесь собственно, нужно дизайнить???". Забыл какие то мелкие вещи на которые даже не смотрел. Так понимаю, ожидалось что я должен заучить типовые паттерны и отбарабанить их за полчаса (полчаса требования собирал только). Как то само по себе интервью чуть не превратилось в собачью свалку... У меня за плечами крупные реальные проекты где я находил ошибки (достаточно важные) уже после подписания дизайна. В реальности так никто не работает, времени обычно достаточно все спокойно обдумать. Рисовать схему за час полтора это базовая подготовка пехоты.
Пройду еще final интервью и наверное закруглюсь, что то работать в Яндексе расхотелось, впечатление что колесо сансары по фильтрации кандидатов крутится само по себе, как побочный бизнес и в итоге вряд ли будет толк. С точки зрения подготовки к интервью, повышения психологической устройчивости и тд, Яндекс дает хорошую возможность для кандидатов, большое спасибо за это.
О, я так после final и закруглился, даже офер не послушал (а зря, ради интереса можно было бы)
Спасибо, что поделились - крутой, жизненный рассказ. Прямо видно, как по ходу колесо сансары проверок превращается в проверку не алгоритмов, а нервной системы ))
System Design - отдельная боль. Прекрасно вас понимаем.
Кстати, если Яндекс не выберет - не расстраивайтесь. Выбирайте MaDeLa :) У нас тоже бывают интересные задачки, но больше с доверием к опыту. Мы ценим тех, кто умеет кодить, применяя здравый смысл.
Удачи на финале - даже если просто для галочки
спасибо за пожелания. Яндекс - в первую очередь тренировка, потолкался с молодежью, посмотреть что к чему потому что меня яндекс рекрутеры к себе потащили - даже не знаю, зачем я им нужен и нужен ли. В контекст залез потому что совпало по времени - решил проверить, заржавели мозги или нет - никогда специально алгоритмами не занимался чтобы пройти интервью. Заодно втянул коллегу в процесс.
Посмотрел ваш сайт - молодцы, правильным путем идете, желаю вам дальнейшего роста. У меня опыт работы в 3х стартапах - примерно представляю процесс что нужно пройти чтобы вытянуть бизнес: первый стартап в котором работал не прожил и двух лет (2000-2001 RIP); второй в котором был 2 года на ставке и 3 года на проектных контрактах, до сих пор живет, почти 30 лет уже (с 1997), но замер в размерах после того как был поглощен и стал по сути отделом; последний 3й стартап (2007-) в котором проработал 15 лет, вырос с 10 человек (когда пришел) до примерно 200 и сейчас снова сжался (подрубило СВО, аутсорсинг был в России, на индусов переключиться не получилось - да они и сами с зубами). Был у меня опыт аутстаффа, в IBM - бегал с их бейджиком на проектах. Самый веселый опыт, если честно - много полетов, хорошие проекты. С женой потом объездили пару стран на мили и бонусы в отелях. Если бы не семейные дела и моя прикованность к России сейчас, я бы снова рванул в IBM консалтинг или подобное.
Болевая точка любого стартапа это когда приходят хорошие деньги и очень важно не потерять желание работать и не зазнаться, не растерять старый "костяк" команды - пройти испытание медными трубами и поднять планку.
При управлении нужны обратные связи, положительные и отрицательные, понятная схема мотивации (конфета должна даваться сразу), вовлечение (ощущение себя частью компании), отрицательная обратная связь тоже важна (наказание). Если обратная связь разбалансирована и происходит "заболачивание" - компания впадает в фазу застоя, старения и гибнет. Будете расти - не расслабляйтесь.
У нас болевая точка началась когда компания вышла на уровень ~10 миллионов долларов официальной прибыли и пара владельцев ушли "лежать на пляжах", наняв себе CEO и прокладку из помощников - старичков при этом оставили на своих местах. Но все быстро меняется и нужно держать нос по ветру - пока СЕО писали отчеты в стиле "все хорошо прекрасная маркиза", копился технический долг, отставание и что самое главное, уходили (от скуки!) хорошие специалисты. Платили выше рынка, но люди уходили.
Примерно за 5 лет все протухло, разложилось, СЕО в итоге сбежали и когда владельцы попытались все снова собрать - не получилось. А тут еще проблемы с СВО - если вопрос как платить, решить смогли то требования клиентов о закрытии доступа и тд разорвал цепочки.
Что-то не понял я "Шаблон № 9". Может быть потому что машинный перевод корявый?
Лучше вот такие задачки решить:
Нахождение медианного элемента: Найти медианный элемент в неотсортированном массиве за время O(n).
Поменять местами две части массива (не обязательно равной длины) за время O(n) и с использованием O(1) дополнительной памяти (на месте).
Нахождение максимальной нулевой подматрицы: Дана прямоугольная матрица n:m, заполненная, преимущественно, нулями. Некоторым её элементам присвоены единичные значения. За время O(n*m) найти наибольший (по количеству элементов - площади) прямоугольник, состоящий из одних нулей.
Привет, спасибо за статью, как раз приходится снова вспоминать все эти истории и готовиться. В пункте 7 в примере по ссылке https://github.com/madela-team/Java/blob/master/leet-code-algorithms/src/main/java/org/madela/TopKElements.java как будто если поменять входной массив на {3, 2, 1, 6, 5, 4}; то выводом будет 6 как 2й самый большой элемент, а ведь он 1й по размеру. Или я что-то не так понял (сам шарпист, а не джавист, могу не знать нюансов класса)
Там используется приоритетная очередь PriorityQueue. В конструкторе по умолчанию используется natural ordering или сортировка по возрастанию, если по-нашему. Следовательно в каком бы порядке в эту очередь не делать ставки head будет равен минимальному элементу. А так как размер кучи k, то наибольший k элемент массива.
P.s если, например, создать очередь и добавить элементы 2, 3, 1 PriorityQueue<Integer> prior = new PriorityQueue<>();
prior.add(2);
prior.add(3);
prior.add(1);
то System.out.println(prior) - выведет [1, 3, 2]
а последовательный вызов poll() - 1, 2, 3while(!prior.isEmpty()){
System.out.print(prior.poll());
}
А в чем смысл первого шаблона (префиксный массив)? Сам префиксный массив делать же затратно, нет? Например, если там миллион элементов. Или миллиард.
Тоже не понял для чего, пример не совсем удачный, ведь можно просто просуммировать...
В задаче Range Sum Query - Immutable (LeetCode #303) даётся массив и нужно сконструировать класс с методом, возвращающим сумму элементов с i по j элемента включительно. Метод будет вызываться много раз.
Там же написанно - когда надо много раз искать сумму. Вы тратите O(n) времени на предподсчет и потом за O(1) считаете сумму. Навиное же решение считает одну сумму за O(n). Если надо m раз считать сумму, то наивное решение будет за O(nm), а с префиксными суммами - O(n + m). Что лучше почти всегда.
Плюс, переход к префиксным суммам упрощает задачи где вы ищете массивы с каким-то свойством суммы, ибо там сумма кучи переменных заменяется на разность всего двух. Вот там примеры даже есть в статье, вроде: найти количество подмассивов дающих заданную сумму. В терминах префиксных сумм - надо найти пары чисел с заданной разницей. Эта задача гораздо проще.
Прочитайте и потренируйтесь на книге Грокаем Алгоритмы, это будет полезнее
Это существенно лучше, чем "я решил 100500 задач на литкоде".
из минусов - смешана 2 разных сущности, не знаю намеренно или нет:
- сначала были именно подходы (не очень широко используесые трюки, до которых можно, скажем сидя на олимпиаде не всегда догадаться)
- потом перешли к алгоритмам - базовые знания в некоторой области (например BFS / DFS - базовые, начальные алгоритмы для графов).
спасибо за перевод!
Как решать LeetCode? Легко! Нужно просто…