Салем друзья! 👋

Новая неделя, новые идеи. 🙂

Появилась мысль подготовить довольно подробный план на 3-4 месяца по подготовке к Google и Amazon. И не просто решать задачи, читать посты/книги, а больше увязать получение знаний с текущий местом работы. Что это значит? сейчас объясню

Алгоритмы и структуры данных - это просто навык, который нарабатывается решением задач на том же литкод и умением их объяснять, тот же pramp. Никакой магии, только практика.

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

Ситуационные вопросы (behavioral questions) - для меня самая сложная часть собеседований. В отличии от двух предыдущих, тут не обойдись просто знаниями как правильно/неправильно, нужно рассказывать про свой реальный опыт из жизни. Поэтому легко попасть в ситуацию, когда начинаешь просто придумывать/подстраивать нерелевантный опыт под вопрос собеседующего. Мой главный инсайт после собеседований - ты уже на текущием месте работы должен следовать принципам Гугла/Амазона/Меты и просто нужно продемонстировать использование этих принципов на реальном интервью. Значит берем потенциальные ситуации и пробуем их спровоцировать на текущем проекте, нарабатываем необходимый опыт.

Подготовка резюме (CV screening) - тоже не люблю придумывать достижения на ровном месте, высасывать из пальца. Лучше наоборот, ввязываться в задачи, которые могут показать прирост пользователей/ускорение работы сервиса/больше денег бизнесу/управление командой. И отказываться от простых задач, которые несут ноль пользы твоему портфолио, рефакторинг кода, фикс багов, написание тестов и так далее.

Если кратко, то идея перевернуть игру. Стать тем, кто следует принципам лидерства Amazon уже сейчас. Стать гуглером, который временно работает в другой компании. Быть, делать, иметь.

Поделюсь, как накидаю шаблон. Stay tuned. 💻

Давайте на этой неделе порешаем задачи, связанные с хэшами 📦

🧩 Задача 16/200 ✅

https://leetcode.com/problems/contains-duplicate/
Сложность: Легкая, Процент успешных попыток 61.3%

#problemoftheday

Are Right A Lot

👀 Когда я готовился к собеседованиям от Амазона, всегда затормаживал на одном принципе лидерства «Are Right A Lot». Дословно переводится «Лидеры правы, очень часто». Если я допускаю баги в коде, значит я не лидер? Или если я ложил продакшн, значит я не лидер?

🧐 Но этот принцип больше про спорные моменты, умеет ли человек находить и доносить правильные решения до других.

🗣 В споре не всегда побеждает самый умный, а зачастую тот, кто своими знаниями, харизмой или своим авторитетом может убедить других. Так вот «Are Right A Lot» - это принцип про предвидение и убеждение. Это может звучать контринтуитивно, но если ты убедил, значит ты прав, потому что история не терпит сослагательных наклонений. Современный бизнес живет слишком быстро чтобы помнить плохое и слишком жаден, чтобы разбрасываться ресурсами, которые могут брать на себя ответственность.

💪 Как тренировать этот принцип или как получить опыт, которым можно продемонстрировать этот принцип?

Учиться отстаивать свою точку зрения, желательно спокойно и с разумными доводами. Даже маленькая победа в копилку, убедил коллегу или подчиненного, это круто. Смог доказать целесообразность своей идей перед командой или руководителем, это еще лучше. Высший пилотаж, если смог убедить бизнес и при этом принести профит компании.

😬 Ошибки тоже хорошо. Неправильные решения учат нас лучше выбирать правильные в будущем. Это именно тот принцип когда количество рано или поздно приведет к качеству. Но если не начинать, опыт сам по себе не появится.

🏆 Чтобы завтра быть в Амазоне, нужно становиться лидером уже сегодня.

💭 Делитесь, как вы понимаете этот принцип

🧩 Задача 17/200 ✅

Сегодня еще одна классическая задача, которая довольно часто попадается на собеседованиях. Сам встречал ее, когда приходил в Яндекс 🥲

https://leetcode.com/problems/group-anagrams/
Сложность: Средняя, Процент успешных попыток 65.9%

#problemoftheday

Про коллизии в хэш таблицах 🚚💥🚗

Мы привыкли, что хэштаблицы это магическое место, куда можно складывать элементы и брать оттуда за единицу времени. Есть некая хэш функция, которая вычисляет номер ячейки, но бывает так, что для нескольких разных объектов хэш функция вернет одно и тоже число. Если у вас 100 попугаев и 80 клеток, значит в какой-то клетке будет несколько попугаев. Это и называется коллизия.

Попробуем рассмотреть какие виды устранения коллизии существует и как они реализованы в языках программирования.

Separate chaining ⛓

В данном подходе используется вместо одной ячейки используется двухсвязанный список. Соотвественно когда добавляется элемент, высчитывается номер ячейки, находится соответствующий список и добавляется в конец объект. Такой подход используется во многих языках программирования, в том числе в Java, Go, C++.

Основным минусом данного подхода является то, что если все элементы попадают в один список, то получится длинный связанный список, соотвественно результирующая сложность будет соответствующая.

Давайте посчитает ассимптотику по времени.
⁃ Поиск элемента: в среднем O(1), в худшем случае O(N)
⁃ Добавление элемента: в среднем O(1), в худшем случае O(N)
⁃ Удаление элемента: в среднем O(1), в худшем случае O(N)

В Java есть оптимизация, если список разрастается и становится больше определенного количество элементов, то список превращается в сбалансированное двоичное дерево. Соотвественно сложность уменьшается до O(log N)

https://www.geeksforgeeks.org/hashing-set-2-separate-chaining/

Open addressing 🛤

Второй подход называется открытая адресация. Подход предполагает, что количество элементов для вставки не больше, чем количество ячеек в таблице. Если при вставке элемента оказывается, что ячейка уже занята, то смотрим на ячейку +1, если свободна то вставляем туда, иначе проверяем +2, +3 и так далее. Есть мини оптимизации, позволяющие не линейно прыгать по ячейкам в поисках свободного слота, а квадратично.

Стоит отметить, что удаление здесь это просто флажок (tombstone), означающий что ячейка свободна. Такой хак позволяет продолжать прыгать по ячейкам при поиске элемента, чтобы не остановиться раньше времени.

Сложность по времени.
⁃ Поиск элемента: в среднем O(1), в худшем случае O(N)
⁃ Добавление элемента: в среднем O(1), в худшем случае O(N)
⁃ Удаление элемента: в среднем O(1), в худшем случае O(N)

Такой подход тоже находит свою реализация в языках программирования, таких как Python, Ruby, Rust.

https://www.geeksforgeeks.org/hashing-set-3-open-addressing

🧩 Задача 18/200 ✅

https://leetcode.com/problems/top-k-frequent-elements/
Сложность: Средняя, Процент успешных попыток 64.8%

Требование внутри задачи, сложность должна быть меньше O(N log N), где N это длина входного массива.

#problemoftheday

Cracking the MAANGM technical
interviews
Tips and Preparation resources

Осторожно, конкурс!

🤖 Задачи решать интереснее, когда есть материальные плюшки, поэтому запускаю конкурс с призом «Месячный премиум в LeetCode». Давно хотел попробовать такой формат. Если эксперимент пройдет успешно, конкурсы будут чаще, разнообразнее, а призы более ценными 🎁.

🎯 Что нужно сделать:
⁃ Зарегистрироваться по форме ниже
⁃ Решать ежедневные задачки, публикуемые в этом канале с тэгом #problemoftheday
⁃ Чтобы задача засчиталась, нужно ее решить в течении 24 часов с момента ее публикации
⁃ Срок с 1 ноября до 30 ноября включтельно, итоги подведем 1 декабря
⁃ Для чистоты эксперимента, я буду модерировать, но не участвовать

📊 Правила подсчета баллов:
⁃ Сложные задачи оцениваются в 1.5 балла, средние в 1, легкие в 0.5
⁃ При равных суммах баллов, будет оцениваться количество задач, при всех равных закину доп задачи или же просто раздам несколько премиумов (но это не точно 😈)
⁃ В конце каждой недели буду публиковать промежуточные итоги

🤞 Верю в честность и сугубо спортивный интерес ребят, надеюсь, что не придется решать спорные моменты с читингом.

Ссылка для регистрации:
https://forms.gle/FgiFDYFYZi1sRu1J7

Удачи 🦾

🧩 Задача 19/200 ✅

Первая задача месячного контеста 💣

https://leetcode.com/problems/valid-palindrome/
Сложность: Легкая, Процент успешных попыток 43.6%

#problemoftheday

🧩 Задача 20/200 ✅

https://leetcode.com/problems/merge-two-sorted-lists/
Сложность: Легкая, Процент успешных попыток 61.8%

#problemoftheday

Всем привет! 👋

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

❗️еще один момент❗️

Вполне вероятно, что какие то задачи вы уже решали. Просто переотравьте вновь, чтобы было в последних принятых, тогда смогу скриптом подхватить.

Как не пропустить в челюсть

👷 Замечали ли вы, как утопичны собеседования по проектированию систем, они же архитектурные секции. Например тебе дают задачу, задизайнить аналог Инстаграмма. Начинаешь считать трафик, объемы хранимой информации, рисовать кучу микросервисов, подбирать множество баз данных, разные уровни балансировки, асинхронные очереди и так далее. По итогу получаешь большую и детальную схему, которая хороша в теории, но сразу же ломается на практике. Как говорил Майк Тайсон «У всех есть план... до первого удара в челюсть…».

🏗 Парадокс заключается в том, что Твиттер, Инстаграмм не начинали сразу со архитектуры, которая выдержит сотни тысяч запросов в секунду. Все стартовали с маленьких монолитов, с простенькой базой и росли пропорционально нагрузке. На каждом этапе развития они выявляли узкие горлышки и устраняли их за несколько месяцев до предполагаемого коллапса.

🧱 Реальность работает по другому. Нынешний мир живет категориями MVP. Бизнес хочет уметь дешево проверить идею и только при наличии доказанного спроса, вкладывать свои миллионы на разработку. Поэтому когда компания решит делать местный аналог инстаграмма, никто не выделит столько ресурсов, сколько нарисовано на идеальной схеме.

🪚 Чтобы убедиться в этом, можно поспрашивать чем занимаются или чем занимались разработчики востребованных сервисов. Вангую, что довольно часто можно будет услышать ответ «Распиливаем монолит на микросервисы».

😍 Ожидания - пишем все на микросервисах, реализуем оркестрирование систем и используем зоопарк баз данных.
😐 Реальность - пишем монолит, используем простую инфраструктуру и 1-2 базы данных. И если все норм, спрос есть, то усложняем схему.

💰 Как техническому специалисту мне не хочется это признавать, но прибыль компании намного важнее популярных технологий и идеальной инфраструктуры. Поэтому периодически ловлю когнитивный диссонанс на собесах по дизайну систем.

🧩 Задача 21/200 ✅

https://leetcode.com/problems/container-with-most-water/
Сложность: Средняя, Процент успешных попыток 54.3%

#problemoftheday