🔤🔤🔤🔤 🔤🔤
Алгоритмос-с-с-с, мой синьёрос. Я решил более 100 задач по алгоритмам и что я узнал? Хеш-мапа — это религия.
1️⃣➖Решать задачи без теории, это как пытаться собрать шкаф из ИКЕИ по памяти.
2️⃣➖Банально, но точно работает. Сначала понять суть задачи (рисовать на листочке, камушки перекладывать, да как угодно).
Правило: думай над задачей не больше 30м, иначе ищи ответ. Решение некоторых задач придумано умными людьми, но мы не такие.
И я джельтельмен: подсмотрел, значит не решил, помечаю задачу. Спустя несколько дней возвращаюсь и решаю сам. Если опять подсмотрел, повторяю цилк.
3️⃣➖Решил задачу? Отлично. А теперь реши её ещё раз, но по-другому. И это лучшее, что я делал для глубокого понимания темы. Разберем детальнее:
Пример 1. "Что такое анаграммааааа, бляяяяя..." (классика), поэтому поговорим про палиндромы.
➖Можно тупо развернуть строку и сравнить. Время O(n), доп. память O(n), так как храним перевернутую копию.
В целом уже неплохо, и на этом можно закончить. НО, сейчас важно придумать как можно больше решений. Тем самым ты уходишь от «запомнить одно решение» к «отработать паттерны» — а это то, что позволяет решать разные задачки.
Уже сливаешься?..
➖Применим идею двух указателей. Тогда мы экономим по памяти и получаем O(1), а время O(N).
➖Дальше можно накидать кучу всего: дек, стек, очередь, рекурсия... но для этой задачи рекурсия уже лишнее (если только у тебя нет цели отработать рекурсию).
➖Казалось бы, всё. Но я часто переписываю условия задачи.
Например: Можно ли выбросить один символ, чтобы строка стала палиндромом? Первое решение которое приходит в голову это выбрасывать по одному символу и каждый раз проверять оставшуюся строку на палиндром. Итого имеем O(N^2).
➖Дальше достаем козырь, два указателя. Взмах рукой, легкая магия, и вуаля: заветные O(N) у нас в кармане.
➖После снова меняем формулировку, покуда тут и думать не надо. Выбрасываем 2, 3, 4, другими словами, k символов. Но тут, сори, N-ки закончились.
Пример 2. 347. Top K Frequent Elements
Первое, что приходит в голову, если никогда не сталкивались с подобного рода задачами, это: "Да нахер этот Бигтех".
➖Считаем частоты, это буквально N операций, как дань собрать. А дальше частоты необходимо отсортировать (M log M), где M — это количество частот, которое может равняться N в худшем случае.
➖Эта задача, в отличие от прошлой, интересна тем, что тут заместо словаря можно использовать Counter, defaultdict. По приколу есть смысл написать решение с их использованием, но на собеседовании, скорее всего, дадут словарь.
➖После приходит хорошая идея использовать бакет и мы победили эту жизнь, решив за O(N). Можно сразу при создании бакета найти максимальную частоту, чтобы не брать длину исходного массива для обхода с конца.
➖Ещё эту задачу полезно решить через кучу, ну так, по приколу, прикольно же, не?
Что получаем?
1️⃣➖Не запоминаем решение задачи, а учимся применять разные паттерны для разных задач. Решив одну такую задачу, вы решили сразу подгруппу, что эффективнее.
Часто на собеседовании задачи придумываются по такому принципу.
2️⃣➖Да, тратим больше времени на решение одной задачи. Дело не в количестве, а в качестве. Хочется быстро написать оптимальное решение из солюшенов и пойти к следующей задаче, качая ЧСВ.
Вы учитесь тогда, когда страдаете.
Алгоритмос-с-с-с, мой синьёрос. Я решил более 100 задач по алгоритмам и что я узнал? Хеш-мапа — это религия.
1️⃣➖Решать задачи без теории, это как пытаться собрать шкаф из ИКЕИ по памяти.
2️⃣➖Банально, но точно работает. Сначала понять суть задачи (рисовать на листочке, камушки перекладывать, да как угодно).
Правило: думай над задачей не больше 30м, иначе ищи ответ. Решение некоторых задач придумано умными людьми, но мы не такие.
И я джельтельмен: подсмотрел, значит не решил, помечаю задачу. Спустя несколько дней возвращаюсь и решаю сам. Если опять подсмотрел, повторяю цилк.
3️⃣➖Решил задачу? Отлично. А теперь реши её ещё раз, но по-другому. И это лучшее, что я делал для глубокого понимания темы. Разберем детальнее:
Пример 1. "Что такое анаграммааааа, бляяяяя..." (классика), поэтому поговорим про палиндромы.
➖Можно тупо развернуть строку и сравнить. Время O(n), доп. память O(n), так как храним перевернутую копию.
В целом уже неплохо, и на этом можно закончить. НО, сейчас важно придумать как можно больше решений. Тем самым ты уходишь от «запомнить одно решение» к «отработать паттерны» — а это то, что позволяет решать разные задачки.
Уже сливаешься?..
➖Применим идею двух указателей. Тогда мы экономим по памяти и получаем O(1), а время O(N).
➖Дальше можно накидать кучу всего: дек, стек, очередь, рекурсия... но для этой задачи рекурсия уже лишнее (если только у тебя нет цели отработать рекурсию).
➖Казалось бы, всё. Но я часто переписываю условия задачи.
Например: Можно ли выбросить один символ, чтобы строка стала палиндромом? Первое решение которое приходит в голову это выбрасывать по одному символу и каждый раз проверять оставшуюся строку на палиндром. Итого имеем O(N^2).
➖Дальше достаем козырь, два указателя. Взмах рукой, легкая магия, и вуаля: заветные O(N) у нас в кармане.
➖После снова меняем формулировку, покуда тут и думать не надо. Выбрасываем 2, 3, 4, другими словами, k символов. Но тут, сори, N-ки закончились.
Пример 2. 347. Top K Frequent Elements
Первое, что приходит в голову, если никогда не сталкивались с подобного рода задачами, это: "Да нахер этот Бигтех".
➖Считаем частоты, это буквально N операций, как дань собрать. А дальше частоты необходимо отсортировать (M log M), где M — это количество частот, которое может равняться N в худшем случае.
➖Эта задача, в отличие от прошлой, интересна тем, что тут заместо словаря можно использовать Counter, defaultdict. По приколу есть смысл написать решение с их использованием, но на собеседовании, скорее всего, дадут словарь.
➖После приходит хорошая идея использовать бакет и мы победили эту жизнь, решив за O(N). Можно сразу при создании бакета найти максимальную частоту, чтобы не брать длину исходного массива для обхода с конца.
➖Ещё эту задачу полезно решить через кучу, ну так, по приколу, прикольно же, не?
Что получаем?
1️⃣➖Не запоминаем решение задачи, а учимся применять разные паттерны для разных задач. Решив одну такую задачу, вы решили сразу подгруппу, что эффективнее.
Часто на собеседовании задачи придумываются по такому принципу.
2️⃣➖Да, тратим больше времени на решение одной задачи. Дело не в количестве, а в качестве. Хочется быстро написать оптимальное решение из солюшенов и пойти к следующей задаче, качая ЧСВ.
Вы учитесь тогда, когда страдаете.