Какой максимальный размер массива int[] в Java?
Ответ на этот вопрос не такой простой как кажется. Теоретический предел это максимальное значение int в Java: Integer.MAX_VALUE, что равно 2^31-1. Но практический предел немного ниже и зависит от конкретной JVM, на которой вы запускаете программу. Например, посмотрите эту реализацию функции max_array_length в HotSpot JVM. align_down(max_jint - header_size(type), MinObjAlignment); Это дает меньший максимальный размер массива на header. В большинстве классов JDK утилиты используют такую нижнюю планку для безопасности: private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; ArraysSupport например.

Top-down подход в динамическом программировании
#dynamicprogramming #memoization #topdown #algo
Рассмотрел Top-down подход в динамическом программировании на примере задачи:
Задача. Человек идет по лестнице, в которой n ступенек. На каждом шаге, человек может перейти на следующую ступеньку, или перешагнуть одну или две ступеньки. Нужно найти число способов, которыми человек может преодолеть лестницу.
Например, для 3 ступенек есть 4 способа:

1+1+1 (по одной ступеньке за шаг),

1+2 (первый шаг — одна ступенька, второй перешагнуть через одну ступеньку),

2+1 (первый шаг через одну ступеньку, второй на следующую ступеньку),

3 (сразу на последнюю ступеньку).

Решение: Top-down dynamic programming

Код решения:

int countWays(int n) {
Map<Integer, Integer> cache = new HashMap<>();
return countWays(n, cache);
}

int countWays(int n, Map<Integer, Integer> cache) {
if (n < 0) {
return 0;
}
if (n == 0) {
return 1;
}
//есть ли такое значение к кэше, если есть,
//то возвращаем закэшированное значение
if (cache.containsKey(n)) {
return cache.get(n);
}

int result = countWays(n - 1, cache)
+ countWays(n - 2, cache)
+ countWays(n - 3, cache);

//сохраняем вычисленный результат в кэше
cache.put(n, result);

return result;
}

Основные этапы решения задачи на динамическое программирование при помощи Top-Down подхода

Если в формулировке задачи присутствуют фразы типа "найти число способов...", "максимальное/минимальное число ...", "используя самую выгодную стратегию.." и т.д. Или вы видите какие-то ветвления в задаче. Это хорошие индикаторы, что это задача на динамическое программирование.

В целом динамическое программирование это "умный перебор".

В Top-down подходе есть четыре ключевых шага в решении:

1) Составить рекурсивное выражение. Чтобы это сделать, посмотрите, какие есть ветвления в задаче. В задаче про лестницу: шаги на 1, 2, 3 ступеньки. В задаче про размен монет: будем ли использовать на текущем шагу монету определенного номинала или нет. Далее нужно что-то сделать с результатами рекурсивных вызовов, чтобы получить финальный результат. В задачах про "число способов" это обычно сумма. В задачах на минимальное, оптимальное и т.д. Обычно это какие-то минимумы или максимумы. В задаче про лестницу это сумма: f(n) = f(n-1) + f(n-2) + f(n-3).
2) Найти base-cases. Чтобы у вас рекурсия была не бесконечной, ее нужно где-то прервать. Для чисел Фибоначчи это f(0) = 1, f(1) = 1. Для лестницы это n<0 -> 0, n==0 -> 1. Обычно, это значения для нулевых или отрицательных значений. Обычно, они равны 1 или 0. Не всегда, конечно, все зависит от задачи. Но чаще всего так. Иногда это может быть плюс или минус бесконечность, особенно в задачах, где нужно работать с минимумами или максимумами.
3) Написать код решения.
4) Добавить кэш (мемоизацию). Это позволяет резко сократить количество вычислений. Кэш позволяет хранить уже вычисленные ранее значения.

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

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

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

Общие вопросы:
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

Задача с собеседования на java программиста: Обедающие философы
#java #concurrency
Задача. Несколько философов сидят за круглым столом. Между каждым из них есть одна палочка для еды. Для того чтобы поесть, философу нужно получить две палочки для еды. Философы всегда сначала берут левую от себя палочку, а потом правую. Dead-lock может возникнуть если все философы одновременно возьмут левую от себя палочку и будут ждать пока освободится правая.
Решение описал тут: Обедающие философы

Задача на обход бинарного дерева: сумма элементов путей начинающихся с корня бинарного дерева
#алгоритмы #binarytree #dfs #treetraversal #inordertraversal
Задача. Дано бинарное дерево. Нужно вычислить суммы значений элементов для каждого из путей в бинарном дереве, начинающихся с корня дерева. Результат вернуть в порядке от самого левого пути до самого правого.
Решение описал тут: Сумма элементов путей начинающихся с корня бинарного дерева
Код самого решения:
public static List<Integer> branchSums(BinaryTree root) {
List<Integer> result = new ArrayList<>();
if (root == null) {
return result;
}
dfs(root, 0, result);
return result;
}

private static void dfs(BinaryTree node, int sum, List<Integer> result) {
//Вычисляем сумму текущего пути
sum += node.value;
//Если это листовая вершина дерева (нет дочерних вершин),
//то мы вычислили сумму для текущей ветки
if (node.left == null && node.right == null) {
result.add(sum);
return;
}
//рекурсивно вызываем для левого и правого ребенка
if (node.left != null) {
dfs(node.left, sum, result);
}
if (node.right != null) {
dfs(node.right, sum, result);
}
}

Для подписчиков из России. В июне 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/Яндекс Такси