System Design: Consistent Hashing
#systemdesign
Написал статью про Consistent Hashing, который используется во многих современных распределенных системах типа AWS Dynamo DB, Apache Casandra, Couchbase и т.д.: https://telegra.ph/Consistent-Hashing-05-22

Задача с собеседования на многопоточность: Пинг-Понг или Шагающий Робот
#собеседование #interview #java #concurrency
Встречал эту задачу в несколько компаний, в том числе в Яндекс.
Задача следующая. Нужно написать многопоточную программу на Java, в которой будет два потока, первый поток будет печатать “Ping”, второй поток “Pong”. Причем они должны делать это последовательно. Вначале первый поток печатает Ping, а потом второй Pong, потом первый Ping, потом второй Pong и т.д. Есть вариация для этой задачи про шагающий робот. Там также нужно два потока, каждый отвечает за одну из ног робота. Один поток “ходит” левой ногой, второй правой ногой. Они должны делать это последовательно. Начать можно например с левой ноги.

Решение через wait-notify описал тут: Решение.

Можно придумать много других решений, например, при помощи Condition и ReentrantLock.

System design: Load Balancers. Часть 3.
#systemdesign
Публикую 3 часть про Load Balancers: https://telegra.ph/Load-Balancers-CHast-3-05-22

Готовитесь к собеседованию по алгоритмам или по решению алгоритмических задач? Или просто хотите научиться решать алгоритмические задачи?
Я успешно прошел собеседования в Amazon и Facebook, существенная часть которых это алгоритмические задачи.
Например, в Amazon, у меня было 5 алгоритмических задач (2 на phone screen/online test, 3 на onsite собеседовании). В Facebook, было 6 алгоритмических задач (2 на phone screen и 4 на onsite собеседовании). На каждую такую задачу, по сути, давалось 15-20 минут.
Поэтому эти задачи надо уметь решать очень быстро.
В процессе подготовки я прочитал много книг и использовать множество различных ресурсов.
Но эти 3 я считаю лучшими и стоящими своих денег:

1) Книга Cracking the Coding Interview by Gayle Laakmann McDowell. Новичкам стоит начать с нее. Читать нужно в оригинале. Она разбита по темам. В начале каждой темы приведен алгоритм, который нужно знать наизусть и потом приведены задачи и решения к ним. Стоит начать с запоминания и понимания работы алгоритмов. Попробуйте выписать эти алгоритмы на бумажке без использования подсказок. Делайте это до тех пор, пока у вас это не будет получаться на автомате за пару минут. Далее смотрите задачи. Попробуйте сначала решить задачу сами. Если не смогли решить за 1-2 часа, изучайте решение до тех пор, пока не сможете сами, без подсказок, написать решение. По факту, мне этой книги хватило для прохождения собеседования в Amazon (но только после того, как я мог решить каждую задачу минут за 15 из этой книги. На это у меня ушел примерно год).
2) algoexpert.io. Этот ресурс я также рекомендую новичкам и при среднем владением алгоритмами. У автора этого ресурса есть youtube канал: https://www.youtube.com/@clem. По промокоду clem можно получить скидку. Ресурс содержит набор типовых алгоритмических задач и решений к ним. Его большой плюс - на каждую задачу есть часовое видео с пошаговым разбором решения. Более того, там есть материалы для подготовки к другим собеседованиям: system design, поведенческое собеседование, blockchain, front-end, ML.
3) leetcode.com. Содержит огромную библиотеку задач и решений к ним (более 1000 задач). К сожалению, пояснения к решениям могут отсутствовать или быть очень непонятно написанными. Поэтому рекомендую его только начиная со среднего и продвинутого уровня владения алгоритмами. Leetcode позволяет отфильтровать задачи по названию компании и по частоте встречаемости в этой компании. Благодаря leetcode я смог легко решить все алгоритмические задачи на собеседовании в Facebook. При подготовке я решал задачи, которые спрашивали в Facebook и взял топ 100 по частоте. Половина из задач на собеседовании просто совпали с теми, что я решал на подготовке. А другая половина была похожа на другие, которые я уже решал.

Я знаю и использовал много других ресурсов (тот же https://www.hackerrank.com/) и прочитал много других книг. Но они, по-моему мнению, мне меньше помогли и сделали процесс подготовки менее эффективным.

Вопрос с собеседования: Какие методы класса Object вы знаете?
#java #interview #собеседование
В том или ином виде встречается очень часто на собеседованиях на Java программиста. Он может быть использован как начальный вопрос, чтобы потом перейти к обсуждению HashMap и многопоточности с использованием wait-notify.
Ответ описал тут: https://telegra.ph/Kakie-metody-klassa-Object-vy-znaete-05-28

Алгоритм поиска в глубину в графе
#собеседование #interview #algo #алгоритмы
Алгоритмические задачи на графы достаточно распространены на собеседованиях. Особенно в топовые компании. По факту нужно знать три алгоритма для решения такого рода задач: поиск в глубину, поиск в ширину и топологическая сортировка.
Написал краткую справку по поиску в глубину: DFS.
Далее опубликую примеры задач на поиск в глубину в графе и другие алгоритмы и примеры задач к ним.

Задача на обход графа: реализовать заливку как в Paint
#algo #собеседование #interview
Классическая задача с собеседования на обход графа: реализовать заливку как в Paint.
Встречал ее на реальном собеседовании в Booking.com.
Решение и более детальное условие описал тут: Решение.

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

Например: [4, 7, 9, 10], k = 1 -> Ответ 5. [4, 7, 9, 10], k = 3 -> Ответ 8 (пропущены 5, 6, 8)

Решение описал тут: Решение

Иерархия исключений в Java
#interview #собеседование #java
Я сразу рассмотрю несколько связанных вопросов с собеседования на Java программиста:

1) Какая иерархия исключений в Java?

2) Чем отличаются checked от unchecked исключений?

3) Что такое Error?

4) Какой пример Error вы знаете?

5) Можно и нужно ли перехватывать OutOfMemoryError?

6) Какие примеры RuntimeException вы знаете?

7) Можно и нужно ли перехватывать Throwable?
Ответ описал тут: Иерархия исключений в Java.

Хотите узнать сколько зарабатывают в топ IT компаниях мира?
Рекомендую сервис https://www.levels.fyi/
Там вы можете сравнить сколько платят в разных топ IT компаниях мира разным уровням программистов.
Например, сравним зп в Google, Amazon и Facebook: Сравнение.
Эти зп в год в США в кремниевой долине. В Европе в тех же компаниях зп меньше. Например, в Лондоне зп примерно в 1.5 раза ниже в тех же компаниях и тех же должностях.
Краткая выжимка для Facebook:
1) E3 (Junior) - $182 000
2) E4 (Mid) - $255 000
3) E5 (Senior) - $368 000
4) E6 (Staff) - $557 000
5) E7 (Principal) - $980 000
6) E8 (Senior Principal) - $1 660 000
7) E9 (Distinguished/Выдающийся инженер) - $2 534 000

Компенсация в таких компаниях состоит из трех частей: базовой зп (выплачивается каждый месяц), бонус(выплачивается раз или два раза в год), и акции компании (выдаются 1-4 раз в год). Акции таких компаний ликвидны. Как только вы получили акции Google или Amazon, вы можете их продать в тот же день или хранить с надежной, что они вырастут в цене.
На позиции Distinguished работают очень мало программистов. Это десятки или сотня программистов в одной такой компании. Я помню, когда работал в Amazon, у нас на позиции Distinguished работал создатель Java James Gosling.

Задача на многопоточность в Java: Приостанавливаемый поток
#interview #собеседование #java #concurrency
Напишите поток, который можно приостановить, продолжить/возобновить его выполнение и остановить.

Это вопрос на знание нескольких фактов:

1) Как в Java создать поток
2) Знание того факта, что Thread.stop(), Thread.suspend() и Thread.resume() не безопасны и deprecated. Их нельзя использовать.
3) Знание wait-notify механизма в Java
4) Знание volatile и/или synchronized в Java
5) Как работает interrupt()
Решение описал тут: ResumableThread

Через сколько лет можно получить гражданство разных стран Европы?
Если вы итишник и переезжаете в одну из стран Европы, то через некоторое время вы можете претендовать на получение гражданства этой страны. Во многих странах ЕС итишникам, которые нашли работодателя в их стране, выдается долгосрочная рабочая виза для высококвалифицированных специалистов. Во многих странах шенгена это blue card, в UK это Tier 2 Skilled Worker Visa или аналоги этих виз. Чтобы получить такую визу, вам нужно получить офер от компании, которая может предоставить вам спонсорство по этой визе, и вы должны соответствовать некоторым критериям. Например, есть нижняя граница зп, ниже которой такая виза не выдается. Прожив необходимое количество лет, вы можете подать документы на получения гражданства. Обычно нужно еще сдать экзамены на знание языка и базовые знания про страну. Иногда нужны еще рекомендации от других граждан этой страны.
Так сколько лет нужно прожить, чтобы получить гражданство? Я привел несколько популярных стран для миграции для итишников:
1) Германия - 8 лет
2) UK - 6 лет или 5 лет, если вы по визе глобальных талантов
3) Нидерланды - 5 лет
4) Чехия - 10 лет (5 лет до пмж + 5 лет до граждаства)
5) Швейцария - 10 лет
6) Франция - 5 лет
7) Люксембург - 5 лет
8) Испания - 10 лет
9) Италия - 10 лет
10) Португалия - 5 лет
11) Швеция - 5 лет
12) Польша - 3 года
13) Кипр - 7 лет

Задача на многопоточность в Java: перевод денег с одного счета на другой
#interview #собеседование #java #concurrency
Необходимо написать Thread Safe функцию перевода денег с одного счета на другой.
Это классическая задача на dead-lock.
Решение описал тут: Решение.

Поиск в ширину (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.