Задача c собеседования: число способов разменять деньги
#алгоритмы #dynamicprogramming
Задача. Надо разменять n рублей. У вас есть монеты номиналами [d1, d2, ..., dm] в неограниченном количестве. Нужно найти число способов, которыми можно разменять изначальные n рублей.
Например:
Надо разменять 6 рублей.
И даны номиналы: [1, 5]. Это значит у вас есть в неограниченном количестве монеты номиналами 1 и 5 рублей.
Вы можете разменять 6 рублей двумя способами: шесть раз по рублю или 1 рубль + 5 рублей.
Решение опубликую завтра. Встречал на реальном собеседовании в Дойче Банк.

Стоит ли учить алгоритмы и структуры данных и готовиться к собеседованиям вообще?
#мысли
Все зависит от ваших целей. На первых этапах карьеры я имел достаточно размытое представление об алгоритмах и структурах данных. Я долго работал на одном месте и приобрел знания, чтобы делать нормально работу для данного конкретного работодателя. Зарабатывал неплохие деньги, но ничего серьезного (пару - тройку тысяч долларов в месяц).
Когда я решил сменить место работы в первый раз, я с удивлением узнал, что я не могу пройти собеседование практически ни в одну компанию.
Мой процент успешного прохождения собеседований был несколько процентов.
Тогда я решил уделять существенное время подготовки к собеседованиям. Через некоторое время я начал учить алгоритмы и развил скил в решении алгоритмических задач. Благодаря этому я стал работать над более интересными и сложными проектами, стал работать в топ компаниях. Я повысил свой процент успешных прохождений собеседований практически до 90-100% и повысил зп в несколько раз. Сейчас я зарабатываю ~400 000 долларов в год.
С учетом развития ИИ (ChatGPT и LLM как один из этапов), позиции начинающих или низкоквалицированных программистов постепенно будут исчезать или будут очень низкооплачиваемыми специальностями. Если хотите быть конкурными на этом рынке, то я считаю, этому нужно уделять время своему развитию. Что думаете вы?

Задача c собеседования: число способов разменять деньги
#алгоритмы #dynamicprogramming

Публикую решение вчерашней задачи.

Задача. Надо разменять n рублей. У вас есть монеты номиналами [d1, d2, ..., dm] в неограниченном количестве. Нужно найти число способов, которыми можно разменять изначальные n рублей.
Например:
Надо разменять 6 рублей.
И даны номиналы: [1, 5]. Это значит у вас есть в неограниченном количестве монеты номиналами 1 и 5 рублей.
Вы можете разменять 6 рублей двумя способами: шесть раз по рублю или 1 рубль + 5 рублей.
Решение: Число способов разменять деньги.

Задача с собеседования в Яндекс: Merge Two Sorted Arrays
#mergesort #twopointers
Задача. Дано два отсортированных по возрастанию массива целых чисел. Надо их смержить в один, который также будет отсортирован по возрастанию.
Решение. Эта задача повторяет существенную часть сортировки Merge Sort. Для решения нам нужно одновременно итерироваться по двум массивам. Т.е. иметь два индекса (Two Pointers). Один по первому массиву, второй по второму. Если текущий элемент из первого массива меньше, чем текущий элемент из второго, то в результирующий массив копируем элемент из первого массива и увеличиваем индекс для первого массива. В противном случае копируем элемент из второго массива и увеличиваем второй индекс. После того, как мы достигли конца одного из массивов, нам надо скопировать оставшиеся элементы из второго.
Код решения:
public static int[] merge(int[] arr1, int[] arr2) {
int i = 0;
int j = 0;
int k = 0;
int result[] = new int[arr1.length + arr2.length];
while (i < arr1.length && j < arr2.length) {
if (arr1[i] < arr2[j]) {
result[k++] = arr1[i++];
} else {
result[k++] = arr2[j++];
}
}
while (i < arr1.length) {
result[k++] = arr1[i++];
}
while (j < arr2.length) {
result[k++] = arr2[j++];
}
return result;
}
Time complexity O(n+m), Space Complexity: O(n+m). n, m - размеры массивов.

Мое ревью книги: Структуры данных и алгоритмы в Java | Лафоре Роберт
#книги
Если вы Java программист и хотите изучить алгоритмы и структуры данных, но у вас очень туманное или практически нулевое представление о них, то можно изучить эту книгу. Эта книга не научит вас решать алгоритмические задачи. Тем более в короткие сроки. Т.е. если вы спешите и хотите подготовиться к алгоритмическому собеседованию за несколько месяцев, то с этой книгой вы просто потеряете время. Но эта книга содержит описание и реализацию всех основных алгоритмов и структур данных. Они тут даны в избытке. Для собеседования нужно знать только небольшую часть из этого. Тем более на собеседовании вас не попросят реализовать стандартные структуры данных типа стека или очереди. Вы должны уметь пользоваться готовыми. Но эта книга даст вам понимание как устроены внутри те или иные структуры данных. А это в свою очередь даст вам чувство, что вы понимаете как они устроены и работают. Качество кода и реализаций не очень. Но суть отражена верно. Поэтому если вы новичек в этом и не планируете в ускоренном режиме подготовиться к собеседованию, то можете использовать эту книгу для начального понимания темы и потом переходить к другой литературе или платформам, которые уже более практические и содержат только необходимый для собеседования материал.

Алгоритмы обхода двоичных деревьев
#algo #binarytree
Написал краткую справку по обходу двоичных деревьев: Binary Tree Traversal.
В будущем набросаю примеров задач с решениями. Ранее я уже публиковал одну такую задачу: Invert Binary Tree

Нужно ли вам учить алгоритмы и структуры данных?
#мысли
На базовом уровне знать основные структуры данных, понимать что такое алгоритмическая сложность, нужно практически всем программистам.
Знать что такое и уметь использовать массив, список, мапу/словарь, очередь, стек нужно всем программистам. А также знать, что такое алгоритмическая сложность и какая она для основных методов для перечисленных выше структур данных (добавления, удаления и поиска элементов).
Знать что-то сложнее этого всем не обязательно. Все дело в том, что программирование это всего лишь инструмент для достижения тех или иных целей (например каких-то бизнес целей). Для одних бизнесов достаточно простых инструментов, для других нужны сложные инструменты. Если какую-то аналогию провести: для одних задач достаточно иметь молоток и гвозди, а для других нужен ускоритель элементарных частиц. Так вот, для большинства бизнесов не нужны какие-то сложные программные, алгоритмические или архитектурные решения. Достаточно условного молотка. Поэтому вы сможете прогрессировать в карьере без глубокого знания алгоритмов. А когда вы достигнете условного Senior уровня, то дальше для прогресса в карьере в рамках одной компании нужно будет развивать скорее soft скилы (тот же эффективный communication).
Но если вы хотите прогрессировать именно в техническом смысле и переходить работать в компании, где уже умение делать и использовать условные молотки не достаточно, то знание алгоритмов и структур данных уже must have. Что вы думаете об этом?

Какой максимальный размер массива 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);
}
}