Комментарии 152
Литкод - это не замена теории и не мерило красивого кода. Учить теорию больших О по литкоду - это как учить язык по дуолингво, примеров много, но правильных ответов не найдёшь.
Алгоритмическая сложность "производительного" алгоритма O(N), потому что сортировка 26 значений в O-нотации это всё ещё O(1).
Потребление памяти обоими алгоритмами O(N), хотя константа у левого и меньше. Наивно полагать, что на больших N слово влезет в память константного размера.
Попробуйте прогнать эти решения со строкой в миллионы символов.
Согласен. Учить что-то на литкоде - довольно сомнительное удовольствие с невнятным результатом. По-хорошему это инструмент чисто для практики, но так вышло, что через "игру" и "соревнования" это интереснее делать, поэтому способ в какой-то степени рабочий.
По сложности тоже согласен. Не самый удачный пример выбрал все-таки. Постараюсь поправить этот момент
Потребление памяти обоими алгоритмами O(N),
O() потребление памяти подразумевает сколько дополнителной памяти будет выделено в худшем случае при выполнении алгоритма, то есть исключая память на входные данные. Если это несколько переменных и исходный входные данные меняются на месте или происходит выделение памяти некоторого фиксированного размера, не имеющего зависимости от размера входных данных, то это всё ещё константа. У производительного примера именно так и происходит, а у лаконичного происходит кучка почти N константных небольших аллокации (listOf(-2)) в лямбде, которая почти сразу же освобождаются. И вероятно есть скрытые аллокации в zipWithNext, из-за чего и страдает производительность, но эти аллокации делают как раз C*N дополнительных аллокаций, что приводит к амортизированному O(N) по памяти для второго алгоритму и O(1) для производительного.
Когда решал задачи на Rust, старался сделать так, чтобы код был лаконичным и производительным. 99.9% задач решались как раз вот такими вот map/filter цепочками с ленивым вычислением. Отслеживание лишних аллокаций - как раз путь к производительному коду. Есть алгоритмы, которые нельзя записать лаконично и производительно, но большинство алгоритмов вполне. По крайней мере в рамках задач на литкоде, где обработка ошибок/исключений обычно не требуется.
Я бы ещё добавил что первое решение игнорирует полезные практики, например, continue если ветка условия не нужна в цикле. Когда отступов много фокус теряется и легко допустить ошибку. Ну и I там не нужно. Понятно что компилятор оптимизирует обращение к массиву по индексу, но там вполне можно обойтись двумя указателями.
Выглядит как литкод ради литкода)
Есть конкретный пример из жизни ? Например раньше я делал задачи так, а теперь когда преисполнился делаю в 10 раз быстрее и работают они в 50 раз лучше
Просто хочется какого то осязаемого сравнения, что это дает на практике, а не вот эту воду про собесы в бигтех и разминку для мозга
Человеческий мозг это как уникальный процессор, который способен творить, но почему то из него пытаются сделать hdd, заучить функции языка, заучить алгоритмы которые с вероятностью 99% никогда не пригодятся и тд
Выглядит как литкод ради литкода)
Именно так это и ощущалось!)
На самом деле, примеров не так уж и много
Для себя отметил такие вещи:
Стал обращать внимание на последовательность вызовов - если можно изменить их очередность и кол-во обрабатываемых данных сократиться.
Аналогично с алг. сложностью - чаще использовать set, map и иногда деревья (их редко). Т.е. мозг начал обращать внимание на вещи, которые большинство пропустит мимо.
Заметно подрос уровень владением языка - для чего раньше придумывался велосипед, сейчас я знаю как сделать функциями из коробки (группировки, окна и т.п.). Это может и просто с опытом прийти, но многим проще писать по старинке как привыкли, а тут будет небольшой толчок.
Как и писал в статье, очень это специфический инструмент обучения, но мне почему-то зашло (не во всех аспектах)
Литкод просто инструмент. Площадка, которая способна что-то тебе дать, но не обязательно она тебе это даст) Все же зависит от человека. Для кого-то это литкод ради литкода, а кто-то увидев новое решение пойдет как минимум почитает о нем. Я первое время с интересом шерстил гугл когда встречал новые для себя вещи.
Я спустя 700 задач могу сказать, что по сравнению с 1,5-2 годами назад натыкаясь иногда на свои старые решения смотрю на них с улыбкой и понимаю сколько же в них лишнего, буквально натягивание совы на глобус по сравнению с тем как решаю сейчас. Стал использовать более подходящие структуры данных, стал почти моментально видеть хотя бы верхнюю границу big О того или иного кода, не говоря о том, что узнал кучу алгоритмов, которые на порядок бустят мои старые решения. Да и банально, это учит тебя постепенно смотреть на задачу под разным углом. На литкоде не мало задач, которые разумно решаются фактически только одним способом, но есть и те, где можно раскрутить и реализовать по-разному и все варианты хороши.
Ну и конечно начинаешь быстрее решать задачи, так как уже есть какой-то багаж в голове и более широкий кругозор, быстрее приходят некоторые варианты решения и сразу понимаешь их ±, где это будет быстро, а можно ли быстрее и как, и т.п.
Искренне восхищен дисциплиной. Сам пытался в такой марафон, но сошел с дистанции уже на второй день. Понимаю какая сила воли нужна для такой системной работы. Думаю, что именно способность системно и дисциплинировано двигаться вперед и приводит к самым крутым результатам.
В реальной работе алгоритмы не так часто применяются, но тем не менее, как результат многократных упражнений в спортзале — прокачанная мышца, которая затем помогает развиваться профессионально.
Код выглядит абсолютно по-разному, хотя алгоритм практически идентичен.
А потом такое, для запуска нашего notepad вам необходимо 100500 гб винта, 100500 гб мозгов и камень в 32 ядра о 5 ггц.
На самом деле, меня иногда сильно удивляет производительность работы "коробочных" функций
Даже использование базовых функций map, sumOf, reduce и т.п. накладывает какой-то отпечаток на производительность. Несмотря на то, что алгоритм идентичен, "модное" решение практически всегда будет заметно проигрывать в скорости и памяти.
Аналогично и со стримами java, насколько я знаю
По-хорошему надо покопаться в кишках реализации и выяснить в чем все-таки дело, но это уже совсем другая история)
О да, тоже решаю литкодж и пытаюсь как-то эксперементировать. Решение просто манипулировать массивом в джаве это 6 мс, но вместо массива взять стримы иииии 26 мс. В 4 раза дольше. Но самый прикол. Решение на джаве - 5 мс: https://leetcode.com/problems/maximum-number-of-distinct-elements-after-operations/submissions/1805361112/ Решение абсолютно такое же, но с векторами на С++ - 95 мс: https://leetcode.com/problems/maximum-number-of-distinct-elements-after-operations/submissions/1805360930/
Тоже замечал такое
Иногда кажется, что литкод просто рандомное число выдает в этот результат
может с деревом будет по-лучше
Вы отключаете синхронизацию ввода/вывода для C++ в своем решении?
Вот не знаю чего не открывается. Я только сам код решения адаптировал. Там по сути 2 решения. Одно за O(max val) и с соответствующим расходом памяти для диапазонов до 500 000. Другое - с сортировкой за O(N log N). Я думал, что в решении ща O(max val) самое сложное это выделение такого объёма памяти, но C++ по идее с этим должен был справиться не хуже джавы. Я так подозреваю, что дело таки в использовании вектора, но для C++ литкод всегда и предлагает использовать векторы.
Java
class Solution {
public int maxDistinctElements(int[] nums, int k) {
if (nums.length <= (k << 1) + 1) {
return nums.length;
}
int result = 0;
int minVal = Integer.MIN_VALUE;
int max = 0;
for (int num : nums) {
max = Math.max(max, num);
}
if (max < 500_000) {
return digSortSolution(nums, k, max);
}
return sortingSolution(nums, k);
}
private int digSortSolution(int[] nums, int k, int max) {
int minVal = Integer.MIN_VALUE;
int[] freqs = new int[max + 1];
int result = 0;
for (int num : nums) {
freqs[num] ++;
}
for (int i = 0; i < freqs.length; i ++) {
int count = freqs[i];
if (count > 0) {
int currentMinVal = Math.max(minVal, i - k);
for (int j = 0; j < count && currentMinVal <= i + k; j ++, currentMinVal ++) {
result ++;
minVal = currentMinVal + 1;
}
}
}
return result;
}
private int sortingSolution(int[] nums, int k) {
int result = 0;
int minVal = Integer.MIN_VALUE;
Arrays.sort(nums);
for (int num : nums) {
int currentMinVal = Math.max(minVal, num - k);
if (currentMinVal <= num + k) {
result ++;
minVal = currentMinVal + 1;
}
}
return result;
}
}C++
class Solution {
public:
int maxDistinctElements(vector<int>& nums, int k) {
if (nums.size() <= static_cast<size_t>((k << 1) + 1)) {
return nums.size();
}
int max_val = 0;
for (int num : nums) {
max_val = max(max_val, num);
}
if (max_val < 500000) {
return digSortSolution(nums, k, max_val);
}
return sortingSolution(nums, k);
}
private:
int digSortSolution(vector<int>& nums, int k, int max_val) {
vector<int> freqs(max_val + 1, 0);
int minVal = INT_MIN;
int result = 0;
for (int num : nums) {
freqs[num]++;
}
for (int i = 0; i < static_cast<int>(freqs.size()); i++) {
int count = freqs[i];
if (count > 0) {
int currentMinVal = max(minVal, i - k);
for (int j = 0; j < count && currentMinVal <= i + k; j++, currentMinVal++) {
result++;
minVal = currentMinVal + 1;
}
}
}
return result;
}
int sortingSolution(vector<int>& nums, int k) {
int minVal = INT_MIN;
int result = 0;
sort(nums.begin(), nums.end());
for (int num : nums) {
int currentMinVal = max(minVal, num - k);
if (currentMinVal <= num + k) {
result++;
minVal = currentMinVal + 1;
}
}
return result;
}
};
Я не был залогинен, потому и не открывалось.
У меня больше подозрения на то, что нужно отключать синхронизацию ввода вывода:
https://stackoverflow.com/questions/48367983/why-does-sync-with-stdiofalse-speed-up-the-code
Алсо есть в голове идея, что можно решить и без выделения доп вектора, но обязательно с сортировкой. Но руки не дошли попробовать написать решение.
Решение абсолютно такое-же. Но, полагаю, значимое отличие это сортировка. Которая под капотом реализована силно по-разному в Java и С++. Алгоритмы разные и возможно тестовые данные для джавовского удобнее.
А литкод убрал убрал дисперсию в замерах? Если нет, то на время работы особого смысла нет смотреть. Раньше точно было такое, что посылка одного и того же решения могла дать "beats 100%", а могла и "beats 30%"
Там для разных языков есть заметный разброс на накладные расходы - на время исполнения, на потребление памяти. Непонятно с чем связана, но два идентичных сабмишна на Rust будут выполняться с практически милисекундной точностью и относительно стабильно съедать примерно 2мб+сколько сами навыделяете сверху. В С++ сабмит даёт разброс по времени едва ли не в полсекунды иногда и разброс по памяти 5-10мб + выделенная вами память, хотя если запускать тот же код локально с некоторой минимальной обвязкаой, то память едва-едва будет больше килобайта помимо того, что выделил непосредственно ваш алгоритм. Отдельно встречал приколы, когда отправлял очень старые решения повторно и те показывали втрое худшие цифры как по скорости, так и по памяти. Видимо там есть какие-то накладные расходы на песочницы, поэтому замеры скорости у программ на leetcode полезны только ранжирования решений на leetcode. Аналогичные истории с другими языками.
А вообще подозрительно, что код на С++ при прочих равных сожрал на 30 метров памяти больше.
Стримы имеют большие накладные расходы в константах, но сильно выигрывают когда надо взять большой объем на входе, его очень сильно фильтровать и трансформировать. Использовать стримы на простых операциях смысла нет.
Как правило, в большинстве задачек литкода бывают достаточно объемные тест кейсы
Частенько по лимиту памяти или времени падает. Приходится придумывать что-то
Да нет, там накладные расходы - расплата за удобство. Вместо проверки условия внутри цикла, там просиходит вызов функции, плюс сохраниение какого-то состояния, чтобы можно было эти операции комбинировать произвольно.
Не будет стрим выигрывать перед простым continue в цикле, как часто бы оно не срабатывало.
Вы правы, что стримы стоит использовать на сложных операциях, но только из-за простоты восприятия кода. Даже там они будут в то же самое количество раз медленнее.
Я имел ввиду не ручную работу с тем же массивом, а операции типа map, filter и т.п. В сравнении их применения на коллекциях и на стримах )))
Я тоже. Там нет никакой магии. Как бы вы не фильтровали, фильтр точно так же как ручной цикл пройдется по всем элементам, проверит там условие, ненужные пропусит, а нужные передаст дальше. Только там этот цикл разбит по куче вызовов функции для получения следующего элемента.
Такой же эффект, как если бы вы в ручном цикле вставили в начало continue. Так что оно не будет внезапно быстрее для очень больших данных и сильной фильтрации. Если оно медленнее для мелкого примера, оно также будет медленнее для большого примерно в такое же количество раз.
Вы правильно сказали, что там константа больше, но эта константа у точно такого же O(n).
Там ничего удивительного нет, достаточно понимать принцип работы этих функций и будет сильно проще их использовать.
И notepad этот обязательно от самых пресамых, у кого уже hard задачи на собеседованиях
Ну а как, в блокноте же теперь копайлот есть. Жизненно необходимая фича.
fun minimumPushes(word: String) = word
.groupingBy { it }
.eachCount()
.values
.sortedDescending()
.chunked(8)
.foldIndexed(0) { i, acc, counts -> acc + counts.sum() * (i + 1) }Скажите, а вот это вот,что сейчас стало признаком крутизны, как его дебажить и ускорять.
Раньше били по рукам за гото и чрезмерное увлечение сырыми указателями, а тепреь вот новая напасть.
как его дебажить
ну, кажется очевидным поставить бряк в нужный этап. Ну, а с ускорением тут не сказать чтобы много вариантов - либо смотреть на производительность алгоритмов (например, поменять сортировку на нестабильную), либо на выделения памяти в куче (как у автора listOf), либо на размер передаваемого контекста, но последнее это уже этап микробенчмаркинга.
Код читается довольно легко с таким подходом. Не зная язык программирования, я просто прочел и просто понял почти всё, что там делается
как его дебажить
Извините за пассивно агрессивный тон, но дебажить это надо деббагером.
Мне лень прикреплять картинку, но IDE спокойно ставит брики внутри лямбд и спокойно проваливается внутрь функций
ускорять
1) По ситуации. Заменять библиотечные функции, своими если вас не устраивает их скорость, использовать sequence там где просто mapReduce обработка, добавить подсказки компилятору
Да и дебажить именно этот метод нет вообще никакой необходимости. Он "чистый", идеально покрывается тестами и очень понятен.
Ну ошибиться там тоже можно. И если результат не совпадает с ожиданиями, то дебажить вполне себе вариант.
Другое дело что не особо понимаю в чём должна быть проблема. Любая более-менее адекватная IDE имеет что-нибудь вроде "watches" или "live console". Поставил брейкпоинт в начале выражения и можно "вручную" выполнить любой из этапов с просмотром результата...
вот именно что использовать watches, вместо того, чтобы по-человечески поставить бряк в нужное место. А с "нужным местом" в таких многоэтажных лямбдах проблемы, особенно если нужно быстро посмотреть значение локальных переменных на какой-то итерации
вот именно что использовать watches, вместо того, чтобы по-человечески поставить бряк в нужное место.
А что вам даёт ваш "бряк"? Как вы значение видите?
А с "нужным местом" в таких многоэтажных лямбдах проблемы
Нет там никаких проблем. Ставишь на первую строчку и всё.
особенно если нужно быстро посмотреть значение локальных переменных на какой-то итерации
Где вы там итерации увидели?
Этот язык я не знаю, но в Rust IDE после каждой строчки напишет, что именно за типы получаются на выходе. А в Python можно бряк с условием поставить, типа "останови на восьмой итерации или когда х % 2 == 0"
Так что применяйте современные инструментарии и всё будет.
Я вот ни бельмеса в Kotlin, но это буквально почти как dotnet linq, и читается не хуже
в idea , например, есть отладка стримов, вероятно, тут тоже она есть
тут же на хабре узнал о проекте highload.fun (можете считать за рекламу). а вот leetcode мне сильно не понравился, неудобен, постоянная борьба с интерфейсом.
спросите у автора, там недавно zig добавили по просьбе трудящихся. я пишу в основном на C#, мне нра.
То есть Go, Rust и Zig вас не смутили?
А как "highload" связан с языком программирования, простите?
Тут видимо имеется ввиду. что С# - это управляемый код, так что у нас есть дополнительная прослойка в виде IL/JIT, соответственно получить производительность, сравнимую с тем же Си или Растом бывает чуть сложнее. Писать высокопроизводительный код на нативном Питоне (ну то есть без библиотек) - примерно тоже самое, только ещё хуже. Вообще если упираться в максимально эффективный машинный код, то тут ещё и компилятор влияет, ингода перекомпиляция Си кода интеловским компилятором может дать хороший буст. Ну и при анализе узких мест желательно заглядывать именно в машинный код, на уровне ассемблера, и С# тут не сильно помогает. Бывает проще расчехлить Си, аккуратно выписать и отпрофилировать самую нагруженную часть там, а затем уже подключать к С# или Питону в виде библиотеки.
Так "highload" же не связан с оптимальным машинным кодом. Есть много примеров хайлоада, написанных вообще на пхп, нагрузка никак не зависит от того, насколько быстро оно будет шевелиться.
Может я тогда сакральный смысл "highload" не очень понимаю. Просто захожу вот сюда - highload.fun/tasks, вижу список заданий. Соревнование идёт именно за время выполнения кода, там везде "...for the shortest time". Практически везде С++ с хорошим отрывом от С#, и мне понятно почему. В первом же примере С++ 2,911, а С# 14,506 - это пятикратная разница. Вот медиана ещё показательнее - тут вообще в 60 раз, медиану на чистом шарпе оптимально найти непросто. Кстати, Раст почти вровень с С++, это то что я и на практике наблюдаю. Я это к тому, что можно соревноваться в классе С++ или С#, но сравнивать их нельзя. Это примерно как есть Формула 1, а есть ралли "Дакар" - просто разные вещи, разные "весовые категории", что ли. Но писать оптимальный код именно на используемом языке надо уметь, конечно, и такие упражнения помогают, да.
Ну это же просто наблюдение Гудхарта (все "законы" Мёрфи - это наблюдения за функционированием бюрократических \ социальных систем в реальности) в действии.
Раньше "умение решать алгоритмы" хорошо коррелировало с сообразительностью и способностью разобраться в других сферах.
Сейчас "умение решать алгоритмы" (ну за исключением hard - но там уже даже при наличии олимпиадного бэкграунда не 2 вечера вспоминать) - коррелирует с потраченным на leetcode временем.
Как правило, по отношению к LeetCode люди делятся на два лагеря:
ценители и любители LeetCode и алгоритмов;
ненавистники LeetCode, которые считают его бесполезной тратой времени.
Приглашаю в свой третий лагерь:
LeetCode - это слишком легко, решайте серьезные задачи на https://eolymp.com/ru/problems или https://codeforces.com/problemset?locale=ru
Зашёл на codeforces, и как будто попал в школьные времена, когда к ЕГЭ и олимпиадам готовился, странно что я тогда про него не слышал. Возьму на заметку, спасибо. Жаль что для eolymp айпишником не вышел :(
Тогда уж вот эти: https://ru.wikipedia.org/wiki/Категория:Нерешённые_проблемы
PS: и я не шучу.
В заголовке написано "что из этого вышло".
В тексте нет ни слова о том, что же из этого вышло.
Как решал задачи, так и решает.
День за днем. Месяц за месяцем.
"потратил колоссальное количество усилий и времени."
У вас жизнь бесконечная, усилия ничего не стоят. Решайте Литкод.
Само по себе решение задач по фану - вполне достойное времяпрепровождение, но вряд ли большое количество решений уровня Easy поднимет ваш уровень программирования. В любом деле для прогресса обучения надо повышать сложность. Программирование тут не является исключением, реальные задачи обычно требуют продолжительной работы. Они могут быть и не сложными алгоритмически, но требующими многодневной концентрации внимания.
А как хобби - почему бы и нет.
Адепты литкода подскажите пожалуйста, когда вы решаете - вы сначала перечитываете всю теорию и уже потом приступаете или сначала сталкиваетесь с проблемой и уже потом заполняете пробелы?
По-разному. По большей части вопросы по математике ставят в тупик и нужно что-то повторять. Но при этом задачи как будто похожи друг на друга. То есть всё вертится вокруг формулы сочетаний и способов посчитать их. Например, все сочетания до 50 50 можно считать треугольником Паскаля, но иногда есть приколы, что нужна малая теорема Ферма, когда нужно посчитать сочетания для очень больших значений по модулю. Но недавно в дэйли задачах была задача, где модуль - составное число и тут даже малая теорема Ферма не поможет) Не люблю математику в общем)
Больше зависит от человека, который решает
Если говорить про "правильный" способ, то конечно надо знать основные моменты всех базовых алгоритмов, чтобы при решении понимать в какую сторону копать
Но на практике, конечно, знать все невозможно, поэтому часто приходится разбирать алгоритм в процессе решения конкретной задачи
Помню начал решать, понял, что у меня пробелы в базовых знаниях, и от этого процесс решения неэффективен. Отставил литкод и пошёл проходить курсы, благо материалов в интернете - вагон и маленькая тележка.
После прокачки теории вернулся к задачам, стало гораздо лучше.
Большинство задач просто брутфорсом пробовал, потом оптимизировал по необходимости алгоритм, какие-то задачи разбирают на ютубе. Например, neetcode имеет много разборов дейликов на питоне. Какие-то задачи поясняют в обсуждениях но там как повезёт - иногда есть годные разборы, иногда фигня типа "ставь лайк, подписка, вот тебе скриншот решения вензельным шрифтом". Для большинства задач имеется достаточно явная чуйка о необходимых подходах, что позволяет брутфорсить оптимальные решения сходу.
Человеку для хорошего настроения нужны регулярные победы. Пусть они будут маленькими, но победы. Обычно их и так хватает в жизни и работе, но иногда может быть недостаток. Решение легких задачек может быть неплохим источников таких маленьких доступных и регулярных побед.
Я учился по книжке "Задачи по программированию". За давностью лет не помню автора. 80-е годы, перевод. Задачи были типа "Вот упрощенный вариант Монополии (для N игроков) - правила. Напишите код. Слишком легко? Предложите и напишите оптимальную стратегию игры со стороны компьютера". А на первом курсе нам показали пошаговую игру "Посадка на Луну" (на текстовом терминале) - предложили свой вариант написать. Мне это показалось легким и я стал решать задачу оптимальной посадки в общем виде. Быстро пришел к выводу необходимости тренировок и расставлением полученной телеметрии в многомерном пространстве высота-скорость-масса-топливо-тяга. С интерполяцией между исследованными точками. А вот до обученной нейросетки не додумался, это да :)
Решать 600 легких задач никакого смысла нет. Чтобы рос навык - надо постепенно усложнять уровень задач. Это все равно что ходить в качалку и каждый день жать один и тот же вес одинаковое число повторов.
Абсолютно согласен
Последнее время стараюсь больше внимания уделять medium задачам
Но вообще, как и написал в статье, т.к. цели решать любой алгоритм у меня нет, то и стремления повышать уровень тоже не хватает
Вероятно, после нового года перестану заниматься этим, т.к., как отметили комментаторы выше, смысла в этом мало.
На Easy и Medium чувствую себя +- комфортно, но на Hard уже нужно реально тратить время, а не под чаек посидеть
Вы всё равно упрётесь в максимальный вес и одинаковое число повторов, просто оно будет больше.
Это все равно что ходить в качалку и каждый день жать один и тот же вес одинаковое число повторов
А что плохого? Если устраивает объем мышц и сила
>Это все равно что ходить в качалку и каждый день жать один и тот же вес одинаковое число повторов.
так это норм же, не? Я несколько лет уже делаю "одинаковое число повторов с одинаковыми весами" и бегаю "одинаковые дистанции в одинаковом темпе с одинаковым пульсом"
Это же гигиена, чищу зубы я тоже одинаково.
Если у тебя цель "чтобы навык не падал" (aka "бегаю, чтобы не жиреть"), то подход автора вполне ок, разве нет?
Если бы литкод был просто сайтом для добровольной тренировки навыков, это одно. Но когда из него сделали мерило "берем на работу или нет", это лис полярный. И вызывает только злость, потому что не хочется тратить кусок жизни на это.
То что в полицию не берут людей не сдающих нормативы - это ок, а то что разработчиков не знающих алгоритмы - не ок?
Представляю нытьё полицейских:
- "В реальной работе я не занимаюсь отжиманиями и подтягиваниями!"
- "Я и с пузом нормально арестовываю!"
- "Мы давно на машинах за преступниками бегаем - кому этот бег нужен!"
- "А мы просто за жизнь спрашиваем - если человек может рассказать кого как арестовывал над какими делами работал - берем!"
Для крупных кампаний такой фильтр относительно оправдан. Ошибки полицейского не влияют на большое количество людей, в отличии от ошибок серийного программиста Джона.
Нормативы физподготовки может без труда сдать примерно каждый второй здоровый человек. Конкретную сложную алгоритмическую задачу с литкода - едва ли один на 10к - если вот недавно именно её читал и ещё не успел забыть за ненадобностью.
Если бы на работу в полицию стояла такая же очередь как и на работу в условный google - нормативы были бы куда выше. Тут скорее по требованиям надо сравнивать с отрядом элитного спецназа. (хотя сейчас и там скорее недобор желающих нежели какой-то конкурс)
PS. Когда ты обычный разраб и решил пройти собес в гугл
Как-то на каком-то похожем сайте решал задачки давно.
И там была задачка - дано сколько-то «рук» в покере - надо посчитать когда левая бьет правую комбинацию.
И мне она так понравилась, что я её давал как тестовую потом.
Прикол в том, что это не сложная какая-то муть про o(n), это максимально близко к тому, что приходится писать в бизнес-приложениях: куча странных условий друг на друге. И написать это красиво и понятно - надо прям уметь.
Такие задачки на leetcode попадаются?
А опишите пожалуйста коротко задачу, с примером. Может быть, тоже возьму на вооружение такое тестовое.
Вот она: https://projecteuler.net/problem=54
На hard и medium иногда встречаются задачи подобной сложности. Иногда читаешь задачу - звучит просто. А потом добавляется какой-нибудь дополнительный финт к базовой струтуре и начинается веселье.
Прочитал вашу задачку - вроде интересная, но думаю, можно подобрать задачку получше. Позвольте пояснить (вдруг кому опыт пригодится)...
Дело в том, что "работать при зрителях" - это одна из самых стрессовых ситуаций в профессии. Даже если человек способен выдать решение или знает то, что мне нужно, далеко не факт, что я эту информацию смогу из него достать. Примерно у половины разработчиков тип личности такой, что при зрителях они буквально входят в ступор. Уж не знаю, как правильно этот эффект называют психологи - "социальная ингибиция" или просто "паническая атака", но факт в том, что нужен буквально "высший пилотаж", чтобы подобного человека раскрепостить. В рамках собеседования, скорее всего, просто не успеешь.
Поэтому со временем я ввел некоторые правила, которые помогают искать подходящие задачи. Одно из них звучит так:
Запрещено использовать текст задачи, в котором встречаются такие выражения, которые человек не мог вчера услышать "в IT-быту". То есть, запрещены: анаграмма, палиндром, сходящийся ряд, фулл-хаус, ход конем, интеграл, римские цифры, дискретность, инвариант, простые числа и так далее. Вы поняли идею...
Это не значит, что нужно запрещать все техническое. В активном словаре айтишника достаточно материала, чтобы работать. Например, следующие слова совершенно не вызывают проблем в тексте и нейтральны для состояния "пациента": стек, односвязный список, сортировка, массив, пара, вектор, равенство и т. д.
Я не имею в виду, что человек, скорее всего, "сложного" не знает - наоборот, скорее всего, все он знает. Но когда мы только знакомимся и занимаемся такой хрупкой работой, как оценка его аналитических способностей, способности к структурному мышлению, каждое лишнее слово может быть фатально. И мы просто не узнаем за отведенное время, кем же он был на самом деле.
PS: Кстати, если на какую-то позицию допустимо проводить собеседование без задач - лучше так и сделать. Вряд ли кто-то из нас заканчивал "пед". Мы с трудом понимаем, как именно это нужно делать, чтобы не навредить ни себе, ни испытуемому.
Конкретно эту я давал офлайн решать, ребятам из учебки - там это было уместно.
Для онлайн "при зрителях" - она прям слишком сложная. У меня для собесов задачи прям супер-простые, в т.ч. чтобы не парализовало. Уровня дописать полу-готовый ToDo List на React, или вынуть суммы из трех связанных таблиц на .NET.
Но задачи все - с кучей точек где что-то дописать, спросить, обсудить.
На самом Эйлере ещё несколько похожих было, правда сходу не найду. Они может и ближе к практике, но решать такое в свободное время - очень на любителя имхо. Больше про гриндинг, чем про нахождение красивого и эффективного решения.
Не знаком с leetcode, подскажите, в чем отличия от codewars?
Суть одинаковая, но codewars имеет больше уровней сложности, из-за чего можно более точно под себя подобрать.
Плюс слышал, что тесты там сложнее пройти и они мене щадящие
Сам давно туда не заходил, Литкод просто показался больше юзер френдли, поэтому остановился на нем
leetcode и hackerrank просто считаются "более профессиональным" т.к. позволяют получить некоторую сертификацию за отдельную плату. А так площадок подобного рода уже немало. Та же code kata, например.
Если 600 дней тратить по 2 часа, можно неплохой дом построить. Или на квартиру накопить.
Если 600 дней тратить по 2 часа, можно неплохой дом построить. Или на квартиру накопить.
1200 часов — это семь с половиной месяцев. При средней зарплате, показываемый сейчас Хабром для мидл-разработчика квартирку придётся брать где-нибудь в Воркуте.
Кажется, когда зарабатываешь по МРОТ в час про литкоды думать уже и не надо.
ну или выбить несколько ачивок в EuropaUniversalis4
За последние 14 месяцев решил более 1300 задач, из них чуть больше 200 сложных. При этом замечаю, что я достиг некого потолка - многие сложные задачи всё равно не даются, ибо предполагают знания какого-то специфического неочевидного подхода, который фиг найдёшь, опыт решения других задач в этом не помогает.
Ещё есть некоторые задачи, которые так уродски составлены, что могут быть решены в требуемых временных рамках только одним конкретным подходом. При этом могут быть и альтернативные подходы, на тесты составлены так, чтобы эти альтернативные подходы не укладывались в данное время. И я тут имею в виду не очевидные случаи с линейными/квадратичными алгоритмами, а нечто более хитрое, вроде оптимизаций, которые в некоторых случаях не срабатывают или просто алгоритмы с другой константой перед показателем временной сложности.
Сложность задач (easy/medium/hard) весьма тролльская. Некоторые easy задачи всё-же требуют написание немалой портянки кода для решения. Половина medium задач вполне себе тяжёлые и или не поддаются вовсе, или требуют от часа времени мозговых усилий.
Ежедневные задачи - вдвойне троллинг. Там или что-то очень лёгкое, или же наоборот - практически нерешаемые задачи. Зачем редакторы ставят такие задачи ежедневными - неясно, разве что чтобы аудиторию разозлить.
А тамошних монеток-то хоть нафармил сколько-нибудь? Ачивки все закрыл?
Тоже иногда решаю литкод.
Мне нравится ощущение когда ты решил задачу, накатывают позитивные эмоции :)
Есть ли польза? Я думаю что есть, иногда на работе нужно написать алгоритм сортировки с несколькими условиями или обойти дерево. Их решение уже не вызывает трудностей как раньше.
Сейчас есть ИИ, много бесплатных, которые напишут тебе нужный алгоритм, и тесты к нему, это будет быстрее чем делать самому. Надо ли самому что то делать или уже нет, каждый сам решит. Я продолжу решать сам для себя, не так часто как раньше конечно, но думаю что это полезно, и когда мне будет лень, то передам это ИИ.
Дофаминовая зависимость или как правильно называется то о чем пишет автор статьи? Напишите кто разбирается.
funcanPlaceFlowers(flowerbed:IntArray, n:Int):Boolean{if(n == 0)returntruevarremaining = nvari = 0while(i < flowerbed.size) {if(flowerbed[i] == 0) {valprev =if(i == 0) 0elseflowerbed[i - 1]valnext =if(i == flowerbed.size - 1) 0elseflowerbed[i + 1]if(prev == 0 && next == 0) { flowerbed[i] = 0 remaining--if(remaining == 0)returntrue i++ } } i++ }returnremaining == 0}
Вы только что показали. Почему ваш восход ни к чему не приводит. В вашем, так называемом «высокоскоростном» решении, нет ничего высокоскоростного и оптимизированного. Так нормальные люди писали код пока не набежали фанаты цепных вызовов и не стали говорить что это круче.
У вас идёт проверка условий и доступ к массиву для prev и next, которые не нужны и могут быть оптимизированны
Код без цепочки вызовов - не мой
Взят самый популярный пример в разделе Kotlin. Это просто пример и не претендует на максимальную производительность. Это решение такого же обычного человека
Цепные вызовы и правда стабильно хуже в производительности, но позволяет меня задумываться о деталях, а отдаваться реализации конкретной функции
Плюс такие функции являются чистыми, что дает больше уверенности и претендует на тестируемость
Все зависит от вашей цели. Если нужна производительность - придется писать обычный код
Претензия не е коду, а к вам. Вы привели его как пример высокоскоростного решения. Как пример «нормально решения» он подойдёт, но говорить о том что это оптимизированный код нельзя. Это просто «тупой» код для решения задачи как он должен быть. Тупо, понятно, легко транслируется на любой язык.
Цепные вызовы и правда стабильно хуже в производительности
А в Kotlin разве нет lazy-evaluation? Обычно это позволяет писать код обработки массивов в виде цепочки вызовов, а в итоге выполнять все эти действия за 1 проход.
Проходил курс Grokking на educative.io. Принцип построения материалов неплохой - сначала демонстрируется примерное решение на основе псевдокода, затем ты пытаешься его выполнить, далее сверяешься с ответом. На практике, большую часть заданий приходится решать через воспроизведение кода из ответов по памяти. Это страшно демотивирует. Как научиться решать задачи самому без зубрёжки?
Не уважаю казуалов, уважаю только hard, только жесть. Грудью на танк! С ноги в толпу!
Были времена, когда я был моложе и готов был биться за идею о том, что задачки бесполезны и все кто ими увлекаются, в итоге теряют чужое время, задавая их на собеседованиях и что-то по ним измеряя.
С тех пор я поменялся, вырос над собой, стал сильнее
Биться за идею стало проще
Дополнил:
А надо ли оно? Для точного ответа на этот вопрос важно ответить на уточняющие:
Вы работаете с высоконагруженной системой?
Хотите ли вы попасть в бигтех?
Вас привлекают алгоритмы и приносят вам радость?
У вас нет профильного высшего образования?
Вы не участвовали в олимпиадах по информатике?
ez katka
Ориентироваться на количество имхо непродуктивно, т.к. мотивирует щёлкать множество лёгких однотипных задач. Сложные задачи могут стоить десятков если не сотен "пятиминуток", и по пользе и по затраченному времени.
В плане прокачки скиллов, может лучше было бы ставить целью, например по 10 лёгких задач из каждого подраздела, затем по 10 средних и сложных.
Не будете вы ни в каком бигтехе решать хоть что-то отдалённо похожее на задачи с литкода. А то что там на собеседованиях такое спрашивают - это другой вопрос, но в любом случае это их проблемы
Решая задания на Литкод и ему подобных сайтах, вы научитесь решать задания на Литкод и ему подобных сайтах.
Тебя взяли в Google?
Все бомбически, вот только откуда столько свободного времени? Имея основную работу + подработку, выходит по 10-12 часов занятости. Какой литкод, ррработать.
На easy/medium задачи уходит не так много времени, как может показаться (до часа максимум, а иной раз можно и за минуту решить, если совсем легкая)
Это как раз мой основной поинт, почему не трогаю hard - экономия времени
Особенно мне интересно как люди решают контесты. Там вроде как 4 задачи. И есть довольно сложные. И вот топовые китайцы решают всё минут за 10-20. Вот это кажется вообще нереальным.
Для меня это даже сейчас звучит как что-то нереальное
Кажется, люди этим всю жизнь занимаются, либо реально гении
Ну, так китайские студенты гриндят как Anfet работает - по 10-12 часов в сутки без продыху. Только наверняка реальный рабочие часы у человека всё же близятся к половине этого времени, а остальное на покушать, пообщаться, поволанить в сторонке - чтобы не выгорать. Китаец же тратит 90% этого времени на код, а остальное на покушать. Вот и получаются такие "суперлюди", впихивающие четырёхчасовые таски в полчаса.
Китайцы после обеда спят, потом работают. Может, в этом секрет?)
Их просто много и у них хардкорная конкуренция за хорошие места во всех сферах. Именно поэтому большинство победителей мат.олимпиад по миру тоже имеют узкий разрез глаз. Интереса ради можете посмотреть как выглядит какой-нибудь Gaokao и сравнить с экзаменами МГУ/МФТИ/МИФИ.
Есть люди, которые решают интегралы и выкладывают многочасовые видео...
Я узнал, что такое лидкод :)
Нас учили на кафедре, все эти штучки дрючки конечно прикольно, но в российской реальности кормить вас будут 1С и эскуэль :) Так реально и выходит.
Субьективное мнение. Проще под каждую задачу спрашивать у нейросети оптимальные алгоритмы для такой то задачи с условием. Пробелы в знаниях спрашивать там же. для большинства решений этого достаточно. Скорость решения + какое то понимание запоминание. Часто приходишь к такой необходимости быстрее запомнишь решение+понимание структуры решения.
Нейросетки знают решения и из них очень трудно выудить что-то, что не заложено в стандартные решения. К примеру, была задача, где надо было раобтать с элементами в изменяющемся массиве и авторское решение было с деревом Фэнвика. И нейросетка только про это решение долбила. А я хотел проконсультироваться про другое, но нейросетка долбила, мол только дерево Фенвика, хотя есть и другая реализация у дерева отрезков. Просто нейросетка знает авторское решение и ни в какую не отклоняется от него. Хотя другое решение таки было засабмитано, то есть оно есть.
У меня примерно такой же подход - если могу быстро решить дейли - решаю. Нет - любую попавшуюся, которую могу быстро решить. Не хочется тратить более 30 минут, т.к. семья, работа, ремонт и т.д. За 350 дней - 650 задач.
Однако чувствую, что не хватает системности. Т.е. если подходить к решению более осознанно, решать по каким-то темам, постепенно повышая сложность задач, то, наверное, можно добиться лучших результатов
Согласен с вами
Тоже считаю, что решение первой попавшейся задачи дает крайне мало профита в последнее время
Кажется, что просто не хватает какой-то глобальной цели и плана
Иначе так можно и застрять на каком-то уровне
Основная проблема в том, что на такой дистанции обучение без плана, я бы сказал, что даже невозможно.
И тут либо самому жестко запариваться и создавать этот план или искать какие-то левые курсы по алгоритмам. У Яндекса что-то такое есть, но даже не думал пробовать пока
Я попробовал зарегистрироваться на тренировки по алгоритмам от Яндекса в этом году. Отвалился в первый же день =)) И вот почему:
Задачи не самые простые, я бы сказал medium+. Т.е. времени на само решение нужно потратить немало
Во многом тесты придумывать самому, что тоже время
Решение нужно оформлять практически как полноценный проект с импортами (не так как на LeetCode, где просто решаешь). В общем, это тоже время
В целом, задачи крутые, заставляют думать над решением, продумывать и контролировать свое решение. Есть чатик для обсуждений, еженедельные разборы. Но времени на это нужно прилично.
HR увидит один ваш "стрик" и обнулит ваши 600 плюсов на LeetCode
Я решаю codeforces(подготовка к олимпиадам). Как я понял, Leetcode сильно проще и по своему опыту начинать переходить к более сложным задачам труднее на cf
Не очень понимаю полезность этой статьи, единственное хотел заметить, что нет смысла показывать код Джуниор vs сеньор, разница которых в том, что сеньорский код использует готовые функции библиотеки языка, потому что "джуниорский" вариант это чистый алгоритм, а в готовых функциях могут использоваться дополнительные оптимизации или алгоритмы, потому джуниорский вариант и отработал быстрее и именно он и требуется, чтобы показать понимание предмета
Код был вставлен только для примера в "познаниях" языка и не более, не принимайте близко к сердцу. Каждая задача требует своего подхода
Статья является скорее ретроспективой и рефлексией - это просто мои мысли по поводу проделанного пути.
А вы, в свою очередь, можете прокомментировать его со взглядом извне
Я решал LeetCode 600 дней подряд и что из этого вышло