Проверить, является ли строка палиндромом
#algo #twopointers #алгоритмы #собеседование #interview

Задача: Проверить, является ли строка палиндромом. Палиндром — это строка, которая читается одинаково слева направо и справа налево.
Эту задачу можно решить при помощи так называемого метода Two Pointers. Я дал краткую справку по этому методу в описании к решению.
Решение: Проверка на палиндром
Усложнение задачи: Также проверить, что это палиндром, но можно игнорировать пробелы, регистр букв и все символы, которые не являются английскими буквами и цифрами. Например: "A b a" -> палиндром, "A!23 * 32a"-> палиндром. Решение на усложненную версию опубликую завтра. Попробуйте решить ее сами сначала.

Усложнение задачи на палиндром
#algo #twopointers #алгоритмы #собеседование #interview

Публикую решение вчерашней задачи.
Встречается на реальном собеседовании в Facebook как разминочная.

Условие. Проверить, является ли строка палиндромом. Палиндром — это строка, которая читается одинаково слева направо и справа налево. Нужно игнорировать пробелы, регистр букв и все символы, которые не являются английскими буквами и цифрами. Например: “A b a” -> палиндром, “A!23 * 32a”-> палиндром.
Решение: Проверка на палиндром, усложненная версия

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

Two Pointers:
1) Проверка на палиндром.
2) Усложненная версия проверки на палиндром.
Stack:
3) Проверить скобочное выражение.
BinarySearch:
Описание алгоритма BinarySearch.
4) Пропущенный элемент в отсортированном массиве.
5) Пиковый элемент.
6) Число итераций в бинарном поиске.
DFS:
Описание алгоритма DFS.
7) Flood Fill.
BFS:
Описание алгоритма BFS.
8) Проверить полноту дерева.
9) Обход дерева по уровням.
Dynamic Programming:
10) Количество дождевой воды

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

Германия:
Берлин:
1) Deutsche Bank: https://www.linkedin.com/company/deutsche-bank/jobs/
2) Zalando: https://www.linkedin.com/company/zalando/jobs/
3) HelloFresh: https://www.linkedin.com/company/hellofresh/jobs/
4) Stripe: https://www.linkedin.com/company/stripe/jobs/
5) HERE Technologies: https://www.linkedin.com/company/here/jobs/
6) Amazon (сейчас не набирают активно): https://www.linkedin.com/company/amazon/jobs/
7) KAYAK (сейчас не набирают активно): https://www.linkedin.com/company/kayak/jobs/
Дюссельдорф:
8) Trivago: https://www.linkedin.com/company/trivagonv/jobs/
Мюнхен:
9) Google(сейчас не набирают активно): https://www.linkedin.com/company/google/jobs/
Люксембург:
10) Amazon (сейчас не набирают активно): https://www.linkedin.com/company/amazon/jobs/
Нидерланды:
11) Booking:https://www.linkedin.com/company/booking.com/jobs/
12) TomTom: https://www.linkedin.com/company/tomtom/jobs/
13) Flow Traders: https://www.linkedin.com/company/flow-traders/jobs/
14) Uber: https://www.linkedin.com/company/uber-com/jobs/
Франция:
15) Criteo: https://www.linkedin.com/company/criteo/jobs/
Великобритания:
16) JPMorgan: https://www.linkedin.com/company/jpmorganchase/
17) Deutsche Bank: https://www.linkedin.com/company/deutsche-bank/jobs/
18) Wise: https://www.linkedin.com/company/wiseaccount/jobs/
19) Revolut: https://www.linkedin.com/company/revolut/jobs/
20) Amazon (сейчас не набирают активно): https://www.linkedin.com/company/amazon/jobs/
21) Google(сейчас не набирают активно): https://www.linkedin.com/company/google/jobs/
22) Apple: https://www.linkedin.com/company/apple/jobs/
23) Facebook (сейчас не набирают активно): https://www.linkedin.com/company/meta/jobs/
24) Goldman Sachs: https://www.linkedin.com/company/goldman-sachs/jobs/
25) Twitter (не набирает сейчас): https://www.linkedin.com/company/twitter/jobs/
Швеция:
26) Spotify: https://www.linkedin.com/company/spotify/jobs/
Швейцария:
27) Google(сейчас не набирают активно): https://www.linkedin.com/company/google/jobs/

Мемная задача с собеседования:Инвертировать двоичное дерево
Max Howell, создатель Homebrew, не был нанят в Google, потому что не смог решить эту задачу. Попробуйте решить задачу сами. Завтра опубликую решение. Оригинальный твит

Решение задачи: инвертировать двоичное дерево
#алгоритмы #собеседование #binarytree #dfs #treetraversal

Решение: Invert Binary Tree

Код самого решения:

public static void invertBinaryTree(BinaryTree tree) {
if (tree == null) {
return;
}
//Меняем местами левого и правого ребенка
BinaryTree tmp = tree.left;
tree.left = tree.right;
tree.right = tmp;
//Рекурсивно вызываем функцию для левого и правого ребенка
invertBinaryTree(tree.left);
invertBinaryTree(tree.right);
}

Минусы жизни в Великобритании
Ранее я публиковал какие есть плюсы жизни в Великобритании: https://t.me/faangmaster/23

Сейчас я расскажу какие есть минусы, по моему мнению:

1) Преступность. Это касается в первую очередь Лондона. Наркоторговля, разборки банд, поножовщина, воровство случаются тут довольно часто. Это было для меня большим удивлением, когда я переехал сюда из Европы. Большинство стран Евросоюза намного безопасней (та же Германия, а Люксембург вообще рай в этом смысле). Поэтому нужно тщательно выбирать район для жизни. Есть районы с низкой преступностью, есть с очень высокой. Чем ниже уровень преступности, тем дороже там жилье.
2) Условный ЖКХ. Если у вас что-то поломалось в квартире или доме, протекла труба, поломался бойлер или что-то подобное, то вам придется иметь дело с местными сантехниками. Вам придется заблаговременно договариваться, чтобы он пришел. Качество ремонта оставляет желать лучшего. Мне почти всегда приходилось самому переделывать. Более того, часто они говорят на очень сложных диалектах английского, который очень сложно понять (тот же кокни).
3) Почти все работает через почту. Это характерно не только для Англии, но и для других стран Европы. Если вы жили в крупных городах постсоветского пространства, то скорее всего вы привыкли, что много всего можно сделать онлайн и получить результат в течении нескольких часов или максимум дней. Тут же все очень часто завязано на то, что вам нужно отправить что-то почтой.
4) Медицина. Чтобы попасть к врачу нужно записываться заблаговременно. Нельзя просто взять и пойти в больницу и выждать очередь, если это не что-то срочное. Иногда по записи нужно ждать неделями или месяцами какого-то обследования или сдачи анализов.
5) Виза в Великобританию, не позволяет путешествовать в шенгенскую зону. Если вы программист, который работает в Англии, то у вас виза типа Skilled Worker или Global Talent. Она не позволяет вам поехать в страны шенгена. Вам надо отдельно получать шенгенскую визу. Запись на подачу в страны шенгена в Лондоне сейчас за много месяцев или вообще нет слотов, их надо вылавливать. Работая, скажем в Германии, вы спокойно можете путешествовать по всем странам шенгена без доп. виз.

Задача на system design: Design Web Crawler
#systemdesign

Нужно задизайнить Web Crawler, который будет сканировать интернет и сохранять его в неком хранилище или индексе для последующего использования. Например, для поиска. Как делают поисковики типа google.
Решение описал тут: Design Web Crawler

Задача с собеседования в Яндекс на Java программиста
Что не так с этим кодом?
public class Singleton {
private static Singleton instance;

public static Singleton getInstance() {
if (instance == null) {
synchronized (Singleton.class) {
if (instance == null) {
instance = new Singleton();
}
}
}
return instance;
}
// private constructor and other methods ...
}
Решение опубликую завтра.

Решение на задачу про Singleton через Double-Checked Locking
#concurrency #java
Задача:
Что не так с этим кодом?
public class Singleton {
private static Singleton instance;

public static Singleton getInstance() {
if (instance == null) {
synchronized (Singleton.class) {
if (instance == null) {
instance = new Singleton();
}
}
}
return instance;
}
// private constructor and other methods ...
}
Решение: Thread Safe Java Singleton

Задача 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 например.