Задача с собеседования: удалить n-й элемент с конца в односвязном списке
#алгоритмы #linkedlist #twopointers

Классическая задача. Встречал на реальном собеседовании в Яндекс.

Задача. Дан односвязный список. Нужно удалить n-й элемент с конца и вернуть голову списка в качестве результата. Можно считать, что n <= размер списка.
Например:
Список: [1,2,3,4,5], n = 2 -> [1,2,3,5]
Список: [1], n = 1 -> []
Список: [1, 2], n = 2 -> [1]
Решение. Решение опубликовал на платформе dev.to:
Удалить n-й элемент с конца в односвязном списке

Напишите в комментариях, подходит ли вам эта платформа. Если да, то буду публиковать там.

Код самого решения:
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode fast = head;
ListNode slow = head;
//Перемещаем fast указатель на расстояние n от slow
for (int i = 0; i < n; i++) {
fast = fast.next;
}
ListNode prev = null;
//Итерируемся по списку до тех пор, пока fast не достигнет
//конца списка, а slow при этом будет указывать на n-й
//элемент с конца списка
while (fast != null) {
prev = slow;
slow = slow.next;
fast = fast.next;
}
//Edge-case, нужно удалить голову списка
if (slow == head) {
head = head.next;
slow.next = null;
return head;
}
// Удаляем n-й элемент списка с конца
prev.next = slow.next;
slow.next = null;
return head;
}
}

Используют ли FAANG компании Scrum или Kanban?
Я работал только в двух FAANG компаниях: Amazon и Facebook. В этих компаниях каждая команда сама определяет использовать ли ей какую-то методологию или нет. В Amazon есть понятие Two-Pizza team, т.е. команды делаются достаточно маленькими, чтобы их можно было накормить двумя пиццами. Обычно это 5-10 человек. Команда сама решает хочет ли она использовать какую-то из методологий или нет. Наша команда использовала Scrum, но не в чистом виде, т.к. он оказался не совсем применим к реалиям компании. В Facebook эти методологии используются еще реже. Почему так и как устроен проджект менеджмент в таких компаниях? Что обьединяет обе компании - процесс планирования и процесс оценки перфоманса сотрудников. В начале года или полугодия все команды составляют список целей, которые должна достигнуть команда, организация, целый отдел и т.д. Под эти цели составляются проекты, которые позволят достичь этих целей и метрики, как измерить, что мы достигли этих целей. Далее эти проекты попадают в roadmap команды, приоритезируются и расспределяютя между разработчиками в команде. В конце года или полугодия, происходит оценка производительности сотрудников на основе выполненных проектов и достигнутых целей. Scrum в чистом виде не очень подходит под такой стиль работы. Если каждый разработчик будет просто брать задачу из бэклога из разных проектов, то не будут очевидны заслуги конкретного разработчика в конце полугодия или года по достижению определенной цели. Особенно, если это senior разработчик и у него скоуп задач и достижений должен быть достаточно большим, иначе он получит плохую оценку производительности и может быть уволен. Поэтому обычно один разработчик делает проект от начала и до конца. Если проект очень большой, то за основной скоуп отвечает более senior разработчик, который дробит на подпроекты, которые могут делать более junior разработчики. Если все будут просто брать задачи из разных проектов, то оценить перфоманс разработчика будет очень сложно. Особенно, это более заметно в Facebook. Это результат-ориентированная компания. На оценке производительности разработчика самое главное показать какой impact ты заделиверил. Например, сделал X и это улучшило производительность на Y. Или сделал фичу Z, которая принесла столько-то денег/пользователей и т.д. Я внедрял Scrum в обоих компаниях, но сильно в измененном виде. В Facebook это оказалось вообще бессмысленно. Там люди могут спокойно самостоятельно работать и достигать больших результатов без какой либо методологии. Это добавляет немного хауса в процесс, но тем не менее работает и не отнимает время на доп. митинги.

Процесс постановки целей OKR это элемент Agile at Scale, что точно используется в FAANG компаниях. А Scrum на уровне команд или не используется вообще или в измененном виде.

System Design: Data Partitioning/Sharding
#systemdesign
Написал краткую справку по партиционированию: Data Partitioning/Sharding

Задача с собеседования: задизайнить Uber/Яндекс Такси
#systemdesign
Задача. Нужно сделать дизайн сервиса по типу Uber или Яндекс Такси.
Решение описал тут: Дизайн Uber/Яндекс Такси

Подборка статей, которые я уже написал и опубликовал в этом канале по system design
#systemdesign
1) Load Balancers 1
2) Load Balancers 2
3) Load Balancers 3
4) Consistent Hashing
5) Data Partitioning/Sharding
6) Design Web Crawler
7) Дизайн Uber/Яндекс Такси

Задача с собеседования на 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.
Решение описал тут: Задача на динамическое программирование. Разделение на слова.