Задача с собеседования на Java программиста: Реализовать Thread Safe блокирующую очередь
#java #concurrency
Задача. Нужно реализовать Thread Safe (потокобезопасную) блокирующую очередь на Java ограниченного размера. В Java уже есть стандартные блокирующие очереди, которые наследуют интерфейс BlockingQueue, такие как ArrayBlockingQueue, DelayQueue, LinkedBlockingDeque, LinkedBlockingQueue, LinkedTransferQueue, PriorityBlockingQueue, SynchronousQueue.
Но в текущей задаче их нельзя использовать. Нужно хранить элементы очереди, скажем в LinkedList и реализовать два метода: put и take.
put - добавляет новый элемент в конец очереди, если размер очереди достиг максимального размера - то поток, который вызвал put ждет на этом методе (блокируется), пока размер очереди не станет меньше.
take - удаляет элемент из головы очереди и возвращает его в качестве результата. Если очередь пустая, то поток, который вызвал take ждет на этом методе (блокируется), пока не появится новый элемент в очереди.

Решение. Решение описал тут: Реализовать потокобезопасную блокирующую очередь на Java ограниченного размера

Код решения:
public class MyBlockingQueue<T> {
private final LinkedList<T> list;
private final int maxSize;

public MyBlockingQueue(int maxSize) {
this.maxSize = maxSize;
this.list = new LinkedList<>();
}

public synchronized void put(T t) throws InterruptedException {
while (list.size() >= maxSize) {
wait();
}
list.add(t);
notifyAll();
}

public synchronized T take() throws InterruptedException {
while (list.isEmpty()) {
wait();
}
T head = list.removeFirst();
notifyAll();
return head;
}
}

Классическая задача с собеседования на алгоритмы
#алгоритмы #interview #hashtable

Задача баянистая. В Google вы ее уже не встретите. Но в другие, не FAANG компании, запросто. Встречал ее на собесах в Skyscanner и Booking в качестве отборочного online теста. Задача также подходит для новичков, которые только начинают учиться решать задачи на алгоритмы.

Задача. Дан массив целых чисел. Надо найти пару чисел в массиве, сумма которых равна заданному числу. В качестве результата вернуть индексы этих элементов. Можно считать, что такая пара есть всегда и только одна.
Например:
Для массива nums = [2, 11, 15, 7], target = 9
Ответ: [0,3]
Т.к. nums[0] + nums[3] = 2 + 7 = 9

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

Код решения:

public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int comp = target - nums[i];
if (map.containsKey(comp)) {
return new int[] {i, map.get(comp)};
}
map.put(nums[i], i);
}
return new int[]{-1, -1};
}

Подборка книг для Java программиста
#книги

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

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

Книги для начинающих (не обязательно читать все, можно пару книг):

1) Head First Java by Kathy Sierra & Bert Bates (Сьерра К., Бэйтс Б. "Изучаем Java")
2) Java: A Beginner’s Guide by Herbert Schildt (Шилдт Герберт "Java. Руководство для начинающих")
3) Java: Programming Basics for Absolute Beginners by Nathan Clark
4) Core Java Volume I — Fundamentals by Cay Horstmann (Кей С. Хорстманн "Java. Библиотека профессионала. 11-е изд. Т. 1. Основы")

Средний уровень:
5) Effective Java by Joshua Bloch (Джошуа Блох "Java. Эффективное программирование") и
6) Thinking in Java by Bruce Eckel (Перевод: Эккель Б. "Философия Java")
7) Clean Code by Robert C. Martin (Чистый код: создание, анализ и рефакторинг. Мартин Роберт) - содержит много спорных или устаревших практик. Но большинство все еще актуальны. Можете прочитать эту книгу и обсудить в своей команде, какие практики будете использовать в своей команде при написании кода и на код ревью, а какие нет.
8) Data Structures and Algorithms in Java by Lafore, R. (Структуры данных и алгоритмы в Java. Лафоре Роберт). Если вы в структурах данных и алгоритмах не в зуб ногой и вы не спешите готовиться к собеседованию на алгоритмические задачки - можно прочитать. Это позволит плавно и медленно погрузиться в устройство тех или иных стуктур данных и алгоримов. Собеседования она вам не поможет пройти. Качество кода и реализаций оставляет желать лучшего, но идеи и подходы верные.
9) Head First Design Patterns (A Brain Friendly Guide) by Kathy Sierra (Head First. Паттерны проектирования) - Легкая для чтения книга про паттерны проектирования в ООП.
10) Spring in Action (Spring в действии. Уоллс К.) - для тех, кто использует Spring.

Продвинутый уровень:
11) Java Concurrency in Practice by Brian Goetz. Я бы сказал библия по многопоточности в Java от одного из ее создателей. Рекомендую читать только в оригинале. Если вы бэкендер, то она поможет вам пройти собеседования в топ компании вашей страны как минимум. В FAANG, конечно, нужны алгоритмы и system design.
12) Cracking the Coding Interview, 6th Edition: 189 Programming Questions and Solutions (Cracking the Interview & Career) by Gayle Laakmann McDowell. Если у вас есть хоть какой-то базис по структурам данных и у вас не возникает паническая атака от слов очередь или граф, то готовиться к собеседованиям на алгоритмические задачи я рекомендую начать с этой книги.
Я уже не раз ее рекомендовал и она позволила мне начать готовиться к собесам в FAANG и около FAANG компании. Книга содержит подробные решения к каждой задаче и последовательность шагов, как к нему прийти.
13) Книга "Designing Data-Intensive Applications by Martin Kleppmann". Очень крутая книга, если вы не торопитесь с подготовкой, то очень советую прочитать. Там вы узнаете про replication, sharding, transaction isolation levels, two phase commits, про стримы типа Kafka, про SQL и No-SQL базы, про основные характеристики и подходы в распределенных системах и многом другом.
14) Книга “Building Microservices by Sam Newman”. Тут вы узнаете про все аспекты создания микросервисов. Книга небольшая, читается легко. Несмотря на то, что микросервисы это достаточно спорный подход, многие моменты применимы и для других подходов.

Задача с собеседования на алгоритмы: Самая длинная палиндромная подстрока
#алгоритмы #interview
Задача. Дана строка. Нужно найти самую длинную подстроку, которая является палиндромом.
Например,
Для "babad", ответ "bab" или "aba"
Для "cbbd", ответ "bb"
Для "abaxyzzyxb", ответ "xyzzyx".
Решение описал тут: Самая длинная палиндромная подстрока

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

Если вы задумываетесь над тем, чтобы пройти собеседование в FAANG компанию (Facebook, Apple, Amazon, Netflix, Google), около FAANG компании (Microsoft, Uber, Lyft, Twitter, Booking) или топ хэдж фонд (Two Sigma, Jane Street, Citadel), чтобы работать над большими и известными продуктами и получать за это большие деньги, то вас может интересовать вопрос, сколько времени займет подготовка.

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

Сначала немного расскажу про свой опыт. Меня эта тема заинтересовала в 2015 году. Я как-то писал про то, как я провалил свое первое собеседование в Google в 2015 (https://t.me/faangmaster/6). С тех пор я решил попробовать поработать в Европе как минимум, а как максимум попасть в FAANG компанию. Через год я переехал в Германию, а еще через год я начал работать в Amazon. Т.е. у меня подготовка заняла два года. Это все было параллельно с работой программистом в других компаниях. Т.е. я не занимался этим full time. А скорее это было как хобби. На момент начала подготовки я имел некоторые представления о том, что такое структуры данных, но довольно поверхностное. Тем более я не умел решать алгоритмические задачи. За эти два года я прочитал несколько книг по алгоритмам и структурам данных, наизусть выучил основные алгоритмы, необходимые для решения задач. Выработал навык быстрого решения алгоритмических задач. В сумме я прорешал на тот момент ~300 алгоритмических задач. В итоге в Amazon я прошел с первой попытки.
Далее я примерно на год забил на подготовку, потом начал снова совершенствоваться в решении задач и в течении еще пару лет прорешал еще 300-400 задач (https://t.me/faangmaster/74). И прошел собеседование в Facebook, со второго раза. Первый раз был в тот же год, когда я собеседовался в Amazon. Тогда я провалил это собеседование.

Я бы сказал, что для выработки навыка решения задач для успешного прохождения в FAANG с нуля нужно ~2 лет, если это просто хобби. Если вы этим занимаетесь full time, то это время можно сократить думаю до 6 месяцев спокойно.

Если вы начинаете не с нуля, а уже неплохо знаете алгоритмы и структуры данных, но навыка решения задач еще нет, то это время можно сократить раза в два: до года если параллельно с работой или месяца 3 если full time.

Тут надо также не забывать, про system design и получения релевантного опыта в других компаниях. А также изучение английского языка, без которого собеседования не пройти.

Если вы уже топовый олимпиадник по программированию, то вам возможно хватит месяца подготовки, в основном по system design.

Задача на System Design: Дизайн Новостной ленты соцсети типа Twitter или Facebook
#systemdesign
Задача. Задизайнить новостную ленту соцсети типа Facebook или Twitter, которая будет содержать посты с текстом, фото и видео, статус апдейтами от людей, на которых подписан пользователь.
Решение. Описал решение тут: Дизайн Новостной ленты соцсети типа Twitter или Facebook

Как готовиться к поведенческому собеседованию в Amazon?
Это может быть интересно и полезно как тем, кто хочет пройти собеседование в Amazon, так и тем, кто хочет изучить и, возможно, использовать Amazon Leadership Principles в своей работе.

В большинстве других компаний поведенческое собеседование - это отдельное собеседование. В Amazon оно размазано на все собеседования. На каждом из 4 онсайт собеседований у вас будет 15-20 минут посвященно Leadership Principles. Напомню, онсайт для разраба в Amazon состоит из 4 собеседований по 45 минут. 3 на кодинг(решение алгоритмических задач) и одно на систем дизайн. Но на каждом из них у вас будут спрашивать поведенческие вопросы на Leadership Principles. Их всего 16. Их описание можно найти тут: https://www.amazon.jobs/content/en/our-workplace/leadership-principles. Для подготовки вам нужно с ними ознакомиться и на каждый подготовить пример из своего профессионально опыта, как вы его продемонстрировали. Эти Leadership Principles очень важны для работы в Amazon. Они реально используются в работе и на них ссылаются в рабочих дискуссиях и общении. Т.е. это не просто лозунги на стене. Это добавляет некой идеологии внутри компании и это многим не нравится. Часто это становится одной из причин, почему люди уходят, т.к. им такая идеологичность компании не нравится. Поэтому если вы хотите там работать, имейте это ввиду.
Что касается моего мнения, то сначала мне все это не очень нравилось, но потом я принял их как правила игры и научился их использовать. Все они имеют практический смысл. В том числе, производительность сотрудников оценивают на основе того, какие из Leadership Principles и как проявил сотрудник.

Задача с собеседования: Максимальная сумма пути в бинарном дереве
#binarytree #algo #алгоритмы #treetraversal

Эту задачу я сам спрашивал несколько раз, когда собеседовал кандидатов в Facebook.

Задача. Дано бинарное дерево. Путь в бинарном дереве — это последовательность вершин, в которой каждая пара соседних вершин в последовательности имеет соединяющее их ребро. Вершина может появиться в последовательности не более одного раза. Путь не обязательно должен проходить через корень. Сумма пути — это сумма значений вершин в пути. Необходимо найти максимальную сумму среди всех непустых путей.
Решение. Описал тут: Максимальная сумма пути в бинарном дереве

Сколько я зарабатывал в Amazon?

В Amazon я проработал 3.5 года на позиции SDE 2. Дело было в Европе (в США зп другие).
Компенсация в Amazon состоит из 3 частей. Первая это базовая зарплата, которая выплачивается каждый месяц. Вторая часть это бонус. Третья это RSU (акции). RSU выплачиваются в соответствии с расписанием. В Amazon это расписание не в пользу сотрудника. Оно не равномерное и призвано стимулировать сотрудника оставаться в компании как можно дольше. Например, в первый год я получил 5% от 4-х летнего плана выплат. Во второй год 15%, В третий и четвертый год по 40%. В Facebook и Google выплаты акций равномерные и каждые 3 месяца.

Мой изначальный offer был таким:
1) 76 000 евро - базовая зарплата
2) Sign-on бонус: 21 000 евро в первый год и 18 000 евро во второй год.
3) 80 RSU на 4 года. Тогда 1 акция стоила ~800 евро за штуку (до сплита, в 2022 был сплит 20 к 1). Т.е. 64 000 евро на 4 года.

В среднем offer в пересчете на год был ~101 000 евро в год.

Но из-за того, что акции Amazon все время росли, часть моей компенсации росла. На момент когда я ушел из компании, акции выросли в 4 раза с момента моего прихода в компанию.

Сколько же я зарабатывал в реальности за 3 года работы? (также указал значения с учетом инфляции на сегодняшний день)

1) Первый год. Базовая зп 76 000. Бонус 21 000. Акции 6400. Итого 103400 евро. С учетом инфляции 130 000 евро.
2) Второй год. Базовая зп 80 000. Бонус 18 000. Акции 21 600. Итого 119 600 евро. С учетом инфляции 149 000 евро.
3) Третий год. Базовая зп 85 000. Бонус 0. Акции 108 800. Итого 193 000 евро. С учетом инфляции 240 000 евро.

Amazon платит хорошо в сравнении с другими компаниями. Но среди FAANG компаний Google и Facebook платят сильно больше.

Простенькая алгоритмическая задача на массивы и Two Pointers
#алгоритмы #arrays #twopointers

Задача. Дан отсортированный массив целых чисел, в котором возможны дубликаты. Нужно удалить дубликаты in-place и вернуть число уникальных элементов в массиве. Например, есть массив: [1, 1, 1, 2, 2, 3, 4, 5, 5, 7, 7, 9]. В результате должно получиться [1, 2, 3, 4, 5, 7, 9, .., .., ....] и число уникальных элементов 7. На троеточие я заменил хвост массива, и нам не важно что там будет после преобразования. Мы будем проверять только первые 7, что они отображают все уникальные числа из массива.

Решение. На ум сразу приходят несколько вариантов решения не in-place. Например, использовать второй массив, в который будем копировать элементы только когда nums[i] != nums[i + 1]. Или использовать HashSet , в который будем помещать элементы массива по мере итераций по нему и проверять видели ли мы этот элемент или нет. Но все эти варианты решения требуют O(n) памяти.
Можно решить используя Two Pointers(два указателя). Один указатель для итераций по массиву, а второй индекс то, куда мы будем копировать уникальный элемент в том же массиве. Копирование будем делать только тогда, когда текущий элемент отличается от следующего. Плюс edge-case для последнего элемента, который мы всегда копируем.

Код решения:

public int removeDuplicates(int[] nums) {
int k = 0;
for (int i = 0; i < nums.length; i++) {
if (i == nums.length - 1 || nums[i] != nums[i + 1]) {
nums[k++] = nums[i];
}
}
return k;
}
Time Complexity O(n), Space Complexity O(1)

Как решение работает по шагам описал тут: Удалить дубликаты в отсортированном массиве

Как в Amazon происходит Design Review?

Если вам необходимо сделать фичу средней или большой сложности, то вам необходимо сделать сначала ее технический дизайн и пройти ревью.

Для этого вам надо придумать несколько вариантов ее реализации, очень кратко их описать с диаграммами и сравнить, найти все основные pros/cons ее реализации данным способом и один из вариантов пометить как предпочтительный.
Все это описание должно быть на пару-тройку страничек. В идеале это 1-pager документ.

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

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

Дизайн ревью это просто способ быстро за 0.5-1 час получить конструктивную обратную связь на ваше текущее видение проблемы и ее решения.

Ключевые моменты, которые отличают Amazon от других компаний в этом аспекте:
1) очень короткие дизайн документы
2) никаких презентаций, просто чтение в тишине.
3) описание нескольких способов решения с pros/cons
4) указание предпочтительного и аргументация почему.

Пишите в коментах как проходит дизайн ревью в вашей компании

Задача на многопоточность в Java: Реализовать потокобезопасный неблокирующий стек на Java
#concurrency #java

Задача. Необходимо реализовать потокобезопасный (Thread Safe) неблокирующий стек на Java. Т.е. нельзя использовать локи или synchonized, при этом он должен корректно работать в многопоточной среде.

Решение. Решение описал тут: Реализовать потокобезопасный неблокирующий стек на Java

Задача на динамическое программирование. Разделение на слова.
#алгоритмы #dynamicprogramming #topdown
Задача. Дана строка s и набор заданных слов wordDict. Нужно проверить можно ли полностью разделить исходную строку на отдельные слова из заданного словаря.
Например,
s = "leetcode", wordDict = ["leet","code"] -> true
s = "catsandog", wordDict = ["cats","dog","sand","and","cat"] -> false.
Решение описал тут: Задача на динамическое программирование. Разделение на слова.

Daemon потоки в Java
#java #concurrency

Несколько фактов про Daemon потоки в Java:
1) В Java есть два вида потоков: User и Daemon
2) JVM будет ждать завершения всех User потоков (не Daemon)
3) Если были завершены все User потоки, то JVM не будет ждать завершения работы Daemon потоков. JVM просто завершит свою работу. Никакие finally блоки в Daemon потоках также не будут выполнены. Поэтому не рекомендуется производить никакие I/O операции в Daemon потоках.
4) Из 3) есть исключение. Если был вызов .join() на выполняющемся Daemon потоке, то это может помешать завершению работы JVM. Поэтому это не рекомендуется делать.
5) Daemon потоки обычно используется для вспомогательной логики. Потоки самой JVM (например GC) являются Daemon потоками.
6) Чтобы сделать поток Daemon, нужно вызвать .setDaemon(true);
7) Если вызвать setDaemon после start(), то это приведет к IllegalThreadStateException. Вызов нужно делать после создания потока, но перед start
8) Daemon флаг наследуется от родительского потока. Если вы в Daemon потоке создали еще один поток, то он будет Daemon по умолчанию.
8) Daemon потоки имеют более низкий приоритет по сравнению с другими потоками

Как выглядит релокация в другую страну, если вы получили offer от FAANG компании?

Я два раза переезжал из одной страны в другую для работы в FAANG компании (В Amazon и Facebook).

FAANG компании предоставляют множество услуг по переезду:

1) Помогают с оформлением визы. Предоставляют консультационные услуги и помощь в подготовке документов. И сопровождение в течении всего процесса получения визы
2) Оплачивают или покупают билеты.
3) Предоставляют жилье на первые 1-3 месяца (В зависимости от вашего уровня). Например в Люксембурге мне сняли пентхаус с двумя балконами и джакузи за 5 тысяч евро в месяц.
4) Предоставляют человека на месте, который будет помогать в поиске постоянной квартиры (риэлтор).
5) Если вам нужно, оплачивают аренду автомобиля на первые 1-3 месяца.
6) Предоставляют человека, который поможет оформить документы по прибытию (зарегистрироваться в гос. органах, податься на получение blue card, Biometrical Residence Permit и т.д.)
7) Выплачивают часть денег на карту на переезд (например 10-20 тысяч долларов)
8) Перевозят всю мебель из одной страны в другую. Приходят грузчики и за день упаковывают все вещи и мебель. Перевозят ее в страну назначения. Хранят все на складе, пока вы не найдете постоянную квартиру. Как только вы найдете постоянную квартиру, то привозят всю мебель и вещи, собирают мебель и раскладывают все вещи.

Какие есть подводные камни в такой поддержке при переезде?
Вы обязуетесь проработать в компании 1 (в Facebook) или 2 года (в Amazon). Если вы решите уйти раньше - то вы должны вернуть часть денег потраченных на переезд. Например, вы отработали 6 месяцев в Facebook и решили уйти, то вы должны вернуть половину денег. Если же решение было не ваше, вас уволили, то обычно можно договориться, чтобы эти деньги не возвращать. Но это не касается sign-on бонуса. Sign-on бонус придется возвращать пропорционально проработанному времени.

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

https://t.me/faangmasterchat

Подборка алгоритмических задач с решениями и описание алгоритмов уже опубликованных в этом канале
#interview #собеседование #алгоритмы #подборка

Обновление подборки. Часть опубликована на medium (возможно потребуется vpn).

Two Pointers:
1) Проверка на палиндром.
2) Усложненная версия проверки на палиндром.
3) Merge Two Sorted Arrays
4) Самая длинная палиндромная подстрока
5) Удалить дубликаты в отсортированном массиве
HashTable:
6) Two Sum
Stack:
7) Проверить скобочное выражение.
LinkedList:
8) Удалить n-й элемент с конца в односвязном списке
BinarySearch:
Описание алгоритма BinarySearch.
9) Пропущенный элемент в отсортированном массиве.
10) Пиковый элемент.
11) Число итераций в бинарном поиске.
DFS:
Описание алгоритма DFS.
12) Flood Fill.
BFS:
Описание алгоритма BFS.
13) Проверить полноту дерева.
14) Обход дерева по уровням.
Binary Tree:
Алгоритмы обхода двоичного дерева
15) Invert Binary Tree
16) BranchSums
17) Максимальная высота дерева
18) Максимальная сумма пути в бинарном дереве
Dynamic Programming:
Основные этапы решения задач на динамическое программирование Top-Down методом
19) Top Down подход на примере задачи про ступеньки
20) Задача на динамическое программирование. Разделение на слова.
21) Количество дождевой воды
22) Bottom-up подход: разменять деньги

Подборка вопросов и ответов для подготовки к собеседованию на Java программиста
#java #interview #собеседование

Обновление подборки.

Подборку составил из постов, которые я уже публиковал ранее в этом канале. Часть опубликована на medium (возможно потребуется vpn).

Общие вопросы:
1) Методы класса Object
2) Иерархия и типы исключений
3) GC
4) Сравнение строк в Java

Коллекции:
5) HashMap
6) ArrayList vs LinkedList
7) Иерархия коллекций в Java
8) Иерархия Map
9) Maximum ArraySize

Многопоточность:
10) Перевод между банковскими аккаунтами (dead-lock).
11) Ping-Pong (wait-notify).
12) Приостанавливаемый поток.
13) Подборка вопросов по многопоточности
14) Напечатать последовательность чисел при помощи нескольких потоков на Java.
15) ConcurrentModificationException
16) Thread Safe Singleton
17) Обедающие философы
18) Реализовать потокобезопасную блокирующую очередь на Java ограниченного размера
19) Реализовать потокобезопасный неблокирующий стек на Java
20) Daemon потоки