Ресурсы для подготовки к system design интервью

👩‍🎓 Курсы:
https://www.udemy.com/course/system-design-interview-prep/
https://www.educative.io/courses/grokking-the-system-design-interview
https://www.coursera.org/specializations/software-design-architecture
https://www.udemy.com/course/system-design-a-comprehensive-guide/
https://www.educative.io/courses/web-application-software-architecture-101

🙂 Бесплатные материалы:
https://github.com/donnemartin/system-design-primer
https://github.com/karanpratapsingh/system-design

❓ Вопросы:
https://medium.com/double-pointer/top-25-system-design-interview-questions-c468e025b370

☑️ Выделю отдельно educative, тут есть каталог вопросов и ответов на них:
https://www.educative.io/courses/grokking-the-system-design-interview

👨‍🏫 По процессу прохождения system design интервью:
https://habr.com/ru/company/piter/blog/650785/
https://habr.com/ru/company/getmatch/blog/516718/
https://hackernoon.com/anatomy-of-a-system-design-interview-4cb57d75a53f

Список будет дополняться.

🧩 Задача 13/200 ✅

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

#problemoftheday

🧩 Задача 14/200 ✅

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

#problemoftheday

Как научиться думать вслух 🗣

😷 На собесах нельзя молчать. Из уст всегда должны излагаться вопросы, идеи (даже тупые), решения.
Интервьюер хочет понять, как ты думаешь, насколько креативно подходишь к решению задач, умеешь ли объяснять свой код, не уходишь ли в лес. В идеале интервью от начала до конца должно проходить без пауз, все время нужно что-то говорить.
Большие молчаливые паузы это минус в финальный отчет кандидата.

🤕 Самое сложное, это научиться писать и одновременно комментировать свой код, особенно на английском 🙂
И комментировать не строчку за строчкой, а для чего ты пишешь эту часть кода, какой кейс она должна покрыть.

👥 Поэтому я при подготовке к собесам использую https://www.pramp.com/. Бесплатный сервис, который матчит двух кандидатов и вы поочереди собеседуете друг друга. Ценен не фидбек второго кандидата, а то насколько ты можешь комментировать свое решение. Навык довольно быстро осваивается.
Вторая ценность pramp, это то, что твоим собеседующим может стать любой инженер с любым уровнем английского. Страх перед интервьюерами из Индии уходит буквально через пару звонков 🇮🇳.

🧩 Задача 15/200 ✅

Пятница это повод для сложных задач 🍻🙂

https://leetcode.com/problems/string-compression-ii/
Сложность: Сложная, Процент успешных попыток 50.1%

#problemoftheday

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

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

Появилась мысль подготовить довольно подробный план на 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

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

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