Для подписчиков из России. В июне medium.com был заблокирован в России. Я там публикую решения, т.к. там можно удобно вставить листинг кода решения. telegra.ph в этом смысле менее удобна, редактор кода отсутствует. Можно только при помощи ботов или используя их API. Поэтому пользуйтесь VPN. Или порекомендуйте альтернативную платформу, которая будет доступна всем.

Еще пару задачек на обход бинарного дерева
1. Найти максимальную глубину/высоту бинарного дерева
2. Найти максимальный элемент в бинарном дереве.
Решения опубликую позже. Попробуйте решить сначала самостоятельно. Подход там такой же как и в задаче про сумму для веток или про инвертирование бинарного дерева. Смотрите статью про алгоритмы обхода бинарных деревьев.

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

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

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

С чего начать изучать программирование в 2023?
#мысли
Вы решили попробовать изучить программирование. С чего можно начать?
Стоит ли сразу бежать платить за курсы по программированию?
Я бы сказал, что все зависит от вашего бэкграунда. Если у вас за плечами хорошее техническое образование (математика, физика, химия, инженерия, информатика), но работали вы не в IT до этого, то шансы стать именно программистом у вас хорошие. Особенно, если вы еще достаточно молоды и у вас хорошие способности к обучению и самообучению. Если у вас нет образования или не техническое образование, то вам будет сложнее стать именно программистом. Если вы хотите работать в IT, то посмотрите на другие профессии, например QA, project management (если у вас есть опыт управления и менеджмента), бизнес аналитик. Аналитик данных, data science, ML будут для вас так же сложнее в освоении.
Но это не значит, что без технического/математического склада ума нельзя стать программистом. Можно, просто это будет сложнее.
Хорошо, вы твердо решили хотя бы попробовать программирование, не смотря ни на что. С чего стоит начать?
Я бы рекомендовал прочитать пару книг по программированию для новичков самостоятельно и написать самостоятельно несколько программ. Это поможет вам понять насколько вы способны к самообразованию в области программирования, насколько у вас получается и интересно ли вам это вообще (возможно вас просто заинтересовала зп из рекламы IT курсов, а само программирование вам не интересно). В любом образовании самообразование играет ключевую роль. Когда вы будете проходить курсы или учиться в вузе, реальные знания вы все равно получите только тогда, когда будете изучать что-то самостоятельно. Преподаватели или менторы могут вас только направить. Долгосрочные знания вы все равно получите если только будете изучать самостоятельно, то что вам преподают.
Если после этого вы поняли, что у вас получается и вам все еще интересно, можно пойти на какие-то курсы и/или поступить в вуз (например как второе высшее образование). Если вы школьник, то у вас самое лучшее положение. Вы можете сразу выбрать вуз, где вы можете получить хорошее образование. Если у вас в вашем опыте нет ни технического образования, ни работы в IT, то возможно, курсы или второе высшее поможет вам иметь хотя бы какие-то строчки в резюме, которые относятся к программированию и IT, и вы сможете хотя бы попасть на собеседование в IT компанию. Можно ли попасть на собеседование без курсов - можно. Просто если у вас никаких строчек в резюме нет связанных в IT, то это будет очень сложно. Но вы можете самостоятельно сделать какие-то проекты, в том числе для Open-source и фриланса. Т.е. курсы или образование само по себе не обязательно.

Хорошо, какие книги стоит прочитать для полного новичка, чтобы понять надо это вам или нет?

Выберите один из популярных языков программирования, например, Python (самый простой в изучении язык и самый популярный/один из самых популярных), Java, JavaScript, C (с C++ начинать бы не рекомендовал, т.к. он достаточно сложный). Найдите пару хороших книг для самых начинающих и прочитайте их.

Например,
Java:
1) Head First Java by Kathy Sierra & Bert Bates
2) Java: A Beginner’s Guide by Herbert Schildt
3) Java: Programming Basics for Absolute Beginners by Nathan Clark
4) Core Java Volume I — Fundamentals
(Effective Java и Thinking in Java must have, но скорее не как первые книги)

Python:
1) Head-First Python by Paul Barry
2) Python Crash Course by Eric Matthes

C:
1) C Programming Language by Kernighan Brian W., Ritchie Dennis

У всех этих книг должны быть переводы. Если не знаете английский, то можете читать в переводе. Но обычно их качество хромает.

Ссылки на переводы книг для начинающих
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. Основы")
(Effective Java (Перевод: Джошуа Блох "Java. Эффективное программирование") и Thinking in Java (Перевод: Эккель Б. "Философия Java") must have, но скорее не как первые книги)

Python:
1) Head-First Python by Paul Barry (Перевод: Изучаем программирование на Python)
2) Python Crash Course by Eric Matthes (Перевод: Изучаем Python: программирование игр, визуализация данных, веб-приложения)

C:
1) C Programming Language by Kernighan Brian W., Ritchie Dennis (Перевод: Ритчи Д.М. "Язык программирования C. 2-е изд., перераб. и доп.")

Когда стоит учить алгоритмы?
#мысли
Это может зависить от вашего текущего бэкграунда и желаний. Опишу для некоторых вариантов:
1) Вы школьник, который хочет стать программистом. Это идеальное время. У вас много времени для обучения и нет других обязательств. Знание алгоритмов будет для вас большим конкурентным преимуществом. Особенно, если вы сможете стать крутым олимпиадником по программированию. Это позволит вам поступить в хороший вуз и после легко сразу пройти на Junior позицию в топ компанию вашей страны или мира (в тот же Google, Facebook). Можно даже пройти там же стажировку во время обучения в универе. И вы сможете зарабатывать $100 000 - $200 000 в первый же год работы. Для начала вы можете изучить основы какого-то языка удобного для олимпиадного программирования (python, C, C++, Java). И потом сразу перейти к изучению алгоритмов и структур данных и практике решения задач.
2) Вы студент технического вуза. Если вы хотите стать программистом, то я рекомендую так же изучить алгоритмы и структуры данных. Это станет для вас большим преимуществом в будущем. Наверняка, в вашем вузе есть такие курсы и скорее всего даже бесплатные. Возможно, придется сменить факультет или кафедру, с большим уклоном в программирование и информатику. Так же вы можете учить их самостоятельно.
3) Вы уже программист. Вы уже работаете программистом, но знание алгоритмов и структур данных у вас на начальном уровне. Изучать их нужно если вы хотите сменить работу и перейти в более крутую компанию. Если же вам это не нужно и вы хотите расти по карьере в своей или похожих компаниях, то изучать их особого смысла нет. Для карьерного роста вам нужно будет скорее развивать другие скилы. В особенности софт скиллы.
4) Вы уже не студент и работаете в другой сфере (не в IT), но хотите стать программистом (или хотя бы попробовать). В таком случае изучение алгоритмов не должно являться вашим приоритетом. Вам скорее нужно изучить основы какого языка + получить базовое представление о структурах данных. И попробовать найти вашу первую работу, чтобы получить хоть какой-то опыт в IT. А дальше при желании уже можете решить как вам расти дальше или же в какой-то момент поймете, что это вам не подходит.

Решение на задачу про максимальную высоту/глубину дерева
#binarytree #treetraversal #dfs #inprdertraversal
Задача. Дано бинарное дерево. Найти его максимальную высоту.
Решение описал тут: Максимальная высота дерева

Код решения:
Вариант 1.
public int maxDepth(TreeNode root) {
if (root == null) {
return 0;
}
int leftDepth = maxDepth(root.left);
int rightDepth = maxDepth(root.right);
return Math.max(leftDepth, rightDepth) + 1;
}
Вариант 2.
class Solution {
int max = 0;
public int maxDepth(TreeNode root) {
//Высота корня дерева = 1
traverse(root, 1);
return max;
}

private void traverse(TreeNode root, int height) {
if (root == null) {
return;
}
//обновляем максимум
max = Math.max(max, height);
//рекурсивный вызов для левой и правой вершины
traverse(root.left, height + 1);
traverse(root.right, height + 1);
}
}
Вариант 3.
class Solution {
public int maxDepth(TreeNode root) {
//Высота корня дерева = 1
return dfs(root, 1);
}

private int dfs(TreeNode root, int height) {
if (root == null) {
return height - 1;
}
//рекурсивный вызов для левой и правой вершины
int leftHeight = dfs(root.left, height + 1);
int rightHeight = dfs(root.right, height + 1);

return Math.max(leftHeight, rightHeight);
}
}

Совсем новичек в Java? Используй этот туториал, чтобы установить бесплатную среду разработки и JDK и запустить свою первую программу на Java за 20 минут с нуля
Написал краткий туториал для совсем новичков: Запускаем свою первую программу на Java

P.S. Картинку генерил с помощью нейросети, поэтому что за красная фигня слева в тарелке я не знаю, все вопросы к нейросети.

Задача с собеседования: удалить 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