Поиск в ширину (Breadth-first Search)
#algo #algorithms #собеседование #interview #bfs #graphs
Описал второй алгоритм обхода графа - поиск в ширину: BFS.
Если тема интересна, то накидаю задач с решениями с собеседований в FAANG компании.

Вопрос с собеседования на Java программиста: как работает Garbage Collector в Java?
#java #собеседование #interview
Тут может быть много различных вопросов:
1) Как устроен Java Heap?
2) Чем отличаются Minor от Major сборки мусора?
3) Что такое Generational GC?
4) Какие бывают Garbage Collectors?
5) Что такое MetaSpace/PermGen?

Могут быть и другие, более продвинутые вопросы. Я рассмотрел лишь самые базовые моменты, знание которых для большинства случаев будет хватать.
Описал ответы тут: https://telegra.ph/Kak-rabotaet-Garbage-Collector-v-Java-06-02

Относительно свежее видео от Veritasium, в котором упоминаются DFS и BFS
Напрямую эти алгоритмы не рассматриваются. Лишь упоминаются как варианты решения нахождения пути в лабиринте. Упоминания алгоритмов с 6 минуты.
https://youtu.be/ZMQbHMgK2rw

Большая подборка вопросов и ответов по многопоточности в Java
#interview #собеседование #java #concurrency
Тут хорошая подборка вопросов по многопоточности: https://github.com/arteam/100-Java-Concurrency-questions
Часть про "Железо" можно пропустить, т.к. встречается крайне редко.

Какие языки программирования используются в крупнейших IT компаниях?
Я работал в Amazon и Facebook, в одном из крупнейших инвест банков мира и других компаниях. Все они используют множество разных языков для разных целей. Вот их неполный список: Java Script, C++, C, C#, Java, Python, Rust, Kotlin, Swift, Objective C, Hack, Go, Php, Erlang, Ocaml, Haskell. FAANG компании обычно не собеседуют на знания каких-то конкретных языков программирования. Они спрашивают задачи на алгоритмы и System Design. Но код на собеседовании вам нужно писать на реальном языке программирования на ваш выбор. Псевдокод использовать нельзя. При этом писать без IDE и кодкомплишена. Код должен быть приближен к реально компилируемому коду.
Для каких целей используют разные языки?
Например инста написана на python и django фреймворке. Но использует куча других сервисов, написанных на других языках. Очень много платформенных вещей написано на C++, Rust. Мобильные клиенты, очевидно, написаны на Objective C, Swift, Kotlin, Java. Бэкенд вотсапа написан на языке Erlang. Веб версии Амазона и фейсбука написаны на JS, с использование реакта. В Амазоне очень много бэкенда на Java. Платформенные вещи C++. Бэкенд фейсбука это язык Hack, которые дергает другие платформенные вещи, которые в основном на C++. В твиттере бэкенд, в основном, на Java. В однокласниках тоже на Java. Machine Learning и Data Science это, в основном, python. В Microsoft очень много C# и C++. В Google много Go. Работая в FAANG очень часто приходится писать на разных языках. Поэтому нужно знать скорее не язык, а базовые подходы в разработке, алгоритмы и структуры данных и быть инженером, а не кодером на одном языке.

Подборка вопросов и ответов для подготовки к собеседованию на Java программиста
#java #interview #собеседование
Подборку составил из постов, которые я уже публиковал ранее в этом канале.
1) Методы класса Object: https://telegra.ph/Kakie-metody-klassa-Object-vy-znaete-05-28
2) HashMap: https://telegra.ph/HashMap-05-18
3) ArrayList vs LinkedList: https://telegra.ph/ArrayList-vs-LinkedList-05-03
4) Иерархия коллекций в Java: https://telegra.ph/Ierarhiya-kollekcij-v-Java-05-08
5) Иерархия Map: https://telegra.ph/Ierarhiya-kollekcij-v-Java-chast-2-05-08
6) Иерархия и типы исключений: https://telegra.ph/Ierarhiya-isklyuchenij-v-Java-05-30
7) GC: https://telegra.ph/Kak-rabotaet-Garbage-Collector-v-Java-06-02
8) Перевод между банковскими аккаунтами (dead-lock): Решение.
9) Ping-Pong (wait-notify): Решение.
10) Приостанавливаемый поток: Решение.
11) Подборка вопросов по многопоточности: https://github.com/arteam/100-Java-Concurrency-questions

Сколько нужно решить задач на leetcode, чтобы пройти собеседование в FAANG компанию?
Я сразу оговорюсь, что умение решать алгоритмические задачи это необходимое, но недостаточное условие для успешного прохождения собеседования в компании типа: Facebook, Apple, Amazon, Netflix, Google, Uber, Microsoft, Lyft, Booking, Two Sigma, Jane Street, Citadel и другие. Там еще есть System Design и поведенческая часть.
В этом посте я сосредоточусь только на алгоритмической части.
В моем случае у меня 317 решенных задач на leetcode на данный момент. Кроме этого я решил ~100 задач из Cracking the Coding Interview, ~100 задач на платформе algoexpert.io, и еще ~100 задач на других платформах и из других книг. В сумме получается ~600 задач.
Мой процент успешного прохождения собеседований в FAANG компании 50%. Из 4 попыток, я получил 2 офера.
В среднем, этот процент ~1-5%. А по откликам на вакансии это еще меньше: 0.1-1%.
В основном, процент такой низкий, потому что люди приходят неподготовленными на собеседование.
Сколько алгоритмических задач я бы рекомендовал решить перед первой попыткой?

Все зависит от вашей текущей подготовки:

1) Если вы опытный олимпиадник по программированию, победитель или призер крупных соревнований, имеете высокий рейтинг на платформах типа topcoder, codeforces. То вам или не надо вообще готовиться к этой части собеседования или посмотреть на leetcode ~10-30 задач отфильтрованные по компании, в которую вы собеседуетесь, чтобы понять примерные типы задач.

2) Вы изучали алгоритмы раньше (в универе, самостоятельно и решали какие-то задачи). Но звезд с неба не хватали, в олимпиадах не участвовали или ничего не занимали. Я бы рекомендовал решить хотя бы 100-200 задач. Из которых, половина easy, чтобы постепенно развить скил решения таких задач. И половина medium.

3) Вы новичок в алгоритмах. Я бы рекомендовал хотя бы 300 задач, из которых больше половина это easy задачи. И хотя бы 100 medium задач. Вообще, новичкам я бы рекомендовал или начать с книги Cracking the Coding Interview (главы, которые относятся к алгоритмическим задачам) и/или algoexpert.io потому что там очень детальное пошаговое решение.

Я начинал с уровня между 2 и 3. Для успешного прохождения в Amazon мне понадобилось решить ~200-300 задач (из Cracking the Coding Interview, leetcode, hackerrank, и других книг). Еще 300-400 я решил for fun и для подготовки в Facebook.

Моя текущая статистика на leetcode

Хотите научиться проектировать современные высоконагруженные системы, вырасти в Senior+ (Senior, Lead, Architect, Staff, Principal) программиста или же готовитесь к System Design собеседованию?
#systemdesign #собеседование #interview

Набросал подборку для изучения:

1) Курс на educative.io: Grokking Modern System Design Interview for Engineers & Managers (https://www.educative.io/courses/grokking-modern-system-design-interview-for-engineers-managers). Этот курс мне порекомендовали, когда я готовился к собеседованию в Facebook. Мне его хватило, чтобы успешно пройти System Design собеседование в Facebook. Если у вас ограниченное время и вам надо за ~1 месяц подготовиться к System Design собеседованию - то этого курса достаточно.

2) Курс на algoexpert.io: https://www.algoexpert.io/systems/product. Стоит его пройти, если уже на той же платформе проходите курс по алгоритмам.

3) Книги “System Design Interview – An insider's guide” Volume 1, Volume 2. By Alex Xu. Очень похоже на курс от educative, но в виде двух книг.

4) Книга "Designing Data-Intensive Applications by Martin Kleppmann". Очень крутая книга, если вы не торопитесь с подготовкой, то очень советую прочитать. Там вы узнаете про replication, sharding, transaction isolation levels, two phase commits, про стримы типа Kafka, про SQL и No-SQL базы, про основные характеристики и подходы в распределенных системах и многом другом.

5) Книга “Building Microservices by Sam Newman”. Тут вы узнаете про все аспекты создания микросервисов. Книга небольшая, читается легко. Несмотря на то, что микросервисы это достаточно спорный подход, многие моменты применимы и для других подходов.

6) Если у вас очень много времени и вам интересно, что и как делают топ компании, то можете читать их тех блоги:
Engineering at Meta, Meta Research, AWS Architecture Blog, Amazon Science Blog, Netflix TechBlog, Google Research, Engineering at Quora, Uber Engineering Blog, Databricks Blog, Pinterest Engineering, BlackRock Engineering, Lyft Engineering, and Salesforce Engineering.

7) Пару youtube каналов по теме:
https://www.youtube.com/@gkcs
https://www.youtube.com/@TechDummiesNarendraL

Почему FAANG компании используют алгоритмические задачи на собеседовании?
#мысли

Представьте, что вы человек, который должен организовать процесс собеседований в Google, Amazon или Facebook.
Какие у вас вводные данные?

1) Вы хотите нанять самых лучших специалистов на рынке труда. Причем не только на рынке труда конкретной страны, но найти лучших специалистов со всего мира.
2) Вы хотите сделать этот процесс справедливым, чтобы в нем могли участвовать люди со всего мира, любого пола, расы, национальности, культуры и вероисповедания.
3) Вы предлагаете работу над самыми крупными и известными IT-продуктами мира.
4) Вы предлагаете самые высокие зарплаты по сравнению с другими IT-компаниями.
5) Вы позволяете сотрудникам менять команды и подразделения раз в год. Т.е. задачи и технологии, над которыми человек будет работать через пару лет не известно.
6) Вам нужно нанять много специалистов. Скажем 10 000 человек за год.
7) Вы получили ~100-500 откликов и резюме на каждую вакансию. В сумме 1-5 миллионов резюме.
8) У вас используются кастомные тулы и технологии, которые нигде больше не используются.

Описал свои мысли тут: Почему FAANG компании используют алгоритмические задачи на собеседовании?

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

Задача на BFS: Проверить полноту двоичного дерева
#bfs #algorithms #algo #собеседование #interview

Встречалось на собеседованиях в Apple, Amazon и Facebook.

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

Задача на BFS: Обход бинарного дерева по слоям/уровням
#bfs #algorithms #algo #собеседование #interview

Встречалось на собеседованиях в Amazon, LinkedIn, Bloomberg, Uber, Apple.

Дано двоичное дерево. Нужно обойти его по слоям/уровням. Каждый уровень обходить слева направо. Результат вернуть в виде списка списков. Каждый вложенный список это элементы одного уровня.
Решение: Обход бинарного дерева по слоям/уровням.

Задача на многопоточность в Java: Напечатать последовательность чисел при помощи нескольких потоков
#java #concurrency #interview #собеседование

Необходимо написать программу на Java, которая напечатает последовательно числа от 0 до N — 1 (или от 1 до N) при помощи нескольких потоков.
Решение: Напечатать последовательность чисел при помощи нескольких потоков на Java

Какие version control практики используют топ компании?

Одним из моих удивлений, когда я начал работать в топ компаниях, стало то, что они, в основном, используют так называемый Trunk-based development. В то время как в других, маленьких и средних компаниях, использовался, в основном, Gitflow Workflow.
Я начал работать в FAANG компаниях 6 лет назад. В то время, в более маленьких компаниях, стандартом был Git Workflow. Это когда есть множество долгоживущих feature бранчей, есть develop branch, есть release branch, который периодически мержится в trunk. На тот момент я думал, что такой подход более безопасный. Когда я пришел в Amazon, а потом в Facebook, я с удивлением узнал, что они используют Trunk-based development. В таком подходе, есть только trunk/master и все разработчики делают очень маленькие инкрементальные изменения, которые тут же попадают в trunk и через несколько часов попадают в продакшен. Это позволяет организовать настоящий CI/CD (Continuous Integration/Continuous delivery).

Как выглядит типичный процесс разработки и деплоя кода при таком подходе?

Разработчик получает или создает таску, над которой он работает. В рамках одной таски разработчик может сделать одно или множество изменений кода. Каждое такое изменение кода проходит code review и не должно ломать trunk. При этом одно такое изменение не обязательно должно полностью реализовать функциональность, которую описывает таска. Например, в первом code change вы можете объявить некие интерфейсы, без реализации, во втором, реализовать методы этих интерфейсов, в третьем добавить вызовы этих методов. Каждое такое изменение кода должно сопровождаться добавлением соответствующих автоматических тестов (unit tests, integration-tests, performance tests, end-to-end tests, UI tests и т.д.). Т.к. выделенных QA обычно в таких компаниях не бывает. Все тестирование делается самими разработчиками. Как только code review пройден, все комментарии и замечания к коду учтены, то разработчик делает push в trunk. Это изменение последовательно проходит через множество шагов в рамках deployment pipeline. Вначале это все компилируется и собирается. Далее прогоняются автоматические unit тесты. Далее эта сборка деплоится на выделенный тестовый сервер, на котором прогоняются интеграционные тесты, перфоманс тесты и т.д. Далее деплоится на canary сервер (на один продакшен сервер, например). Где собираются разные метрики, на основе которых делается автоматическое решение деплоить ли эту сборку далее или сделать rollback. Если все хорошо, то далее эта сборка волнами попадает на все остальные сервера. Все эти деплоймент шаги выполняются автоматически.

Чем отличаются эти два подхода можно посмотреть, например, тут https://www.toptal.com/software/trunk-based-development-git-flow

Пишите в комментариях, какие практики используются в вашей компании.

Какие бывают собеседования программистов и когда они имеют смысл?

Типы собеседований описал тут: Типы собеседований.

Пишите в комментариях, какие еще бывают собеседования, которые я не описал и какие вы считаете самыми лучшими.

Что будет результатом выполнения такой программы?
#interview #собеседование #java #concurrency
public class Main {
public static void main(String[] args) {
List<String> list = new ArrayList<>();
list.add("a");
list.add("b");
list.add("c");
list.add("d");
for (String el : list) {
if (el.equals("b")) {
list.remove(el);
}
}
System.out.println(list);
}
}
Ответ описал тут: Модификация коллекции Java в однопоточной и многопоточной среде

Что я думаю про курсы по программированию, которые рекламируют на каждом углу?
#мысли

Если смотришь youtube, то несколько раз за день увидишь рекламу такого рода курсов. Основной питч - закончите курсы, будете зарабатывать сотни тысяч рублей.

Я даже принял участие в создании одного такого курса по Java на одной из образовательных платформ (бесплатно).

Содержания курсов самих по себе неплохое, но отсутствует фундаментальное образование. Т.е. список тем полезный для будущего программиста, но для текущего состояния технологий. Я бы даже сказал, что неплохо бы такие курсы иметь в вузах. Но на этих курсах обычно отсутствует фундаментальное образование по программированию. В вузах же наоборот. В основном дают фундаментальное образование: алгоритмы, структуры данных, разные парадигмы программирования, операционные системы, разные типы программирования и т.д. Но не останавливаются на конкретных технологиях, потому что они устаревают за ~5 лет.

Нет жесткого отсева и контроля знаний студентов. В образовании два ключевых компонента: знания, которые дает преподаватель или любой другой источник(книга, видеокурс и т.д.) и контроль знаний студента. Если нет серьезного контроля знаний, то максимум что можно сказать, что человек прослушал курс лекций. Условно, если взять кассиршу пятерочки (ничего не имею против кассирш), и посадить ее слушать курс лекций по квантовой механики в Гарвардском университете, то это не значит, что она его усвоит. В хорошие вузы сложно поступить и сложно учиться. Это как минимум показатель, что студент может учиться и усваивать новые знания. На такого рода курсах, нет большого отсева на зачислении и при обучениии относятся мягко в плане контроля знаний.

Такого рода курсы создают избыточное предложение Junior программистов на рынке труда. Если посмотреть на спрос программистов (например на hh.ru), то требуются в основном мидлы и senior разработчики. Junior вакансий не очень много. Такие курсы же создают огромное число Junior разработчиков, которые будут конкуррировать между собой и теми, кто и так планировал стать программистом (выпускники вузов, в том числе выпускники топовых вузов по типу МФТИ, МГУ, ИТМО). Поэтому такие курсы еще больше повышают входную планку для того, чтобы стать программистом. Конкуренция сильно возросла.

P.S. Я тоже окончил курсы по программированию(17 лет назад), перед тем как стал программистом. Но я закончил вуз, в котором я получил фундаментальное образование и курсы были по конкретному языку программирования и конкретным технологиям (которые были релевантны тогда, сейчас они уже давно устарели). Более того, это были курсы от компании, которая готовила программистов для себя и после курсов мы сразу проходили упрощенное собеседование в эту компанию.

Пишите, что вы думаете про такие курсы и каков ваш опыт, если вы учились или окончили такие курсы.

Задача с собеседования в Amazon и Яндекс: Trapping Rain Water
#algo #algorithms #dymanicprogramming
Условие. Дан массив целых чисел. Каждое число отображает высоту рельефа в данной точке. Теперь представим, что сверху льют воду/идет дождь. Нужно вычислить, сколько накопится воды. Нужно предполагать, что слева и справа стенок нет и вода может свободно утекать влево и вправо.
Решение описал тут: Количество дождевой воды

Проверить, является ли строка палиндромом
#algo #twopointers #алгоритмы #собеседование #interview

Задача: Проверить, является ли строка палиндромом. Палиндром — это строка, которая читается одинаково слева направо и справа налево.
Эту задачу можно решить при помощи так называемого метода Two Pointers. Я дал краткую справку по этому методу в описании к решению.
Решение: Проверка на палиндром
Усложнение задачи: Также проверить, что это палиндром, но можно игнорировать пробелы, регистр букв и все символы, которые не являются английскими буквами и цифрами. Например: "A b a" -> палиндром, "A!23 * 32a"-> палиндром. Решение на усложненную версию опубликую завтра. Попробуйте решить ее сами сначала.

Усложнение задачи на палиндром
#algo #twopointers #алгоритмы #собеседование #interview

Публикую решение вчерашней задачи.
Встречается на реальном собеседовании в Facebook как разминочная.

Условие. Проверить, является ли строка палиндромом. Палиндром — это строка, которая читается одинаково слева направо и справа налево. Нужно игнорировать пробелы, регистр букв и все символы, которые не являются английскими буквами и цифрами. Например: “A b a” -> палиндром, “A!23 * 32a”-> палиндром.
Решение: Проверка на палиндром, усложненная версия