Задача с собеседования в Amazon: Пропущенный элемент в отсортированном массиве
#собеседование #interview #algo #amazon #binarysearch
Еще одна задача на бинарный поиск в компанию Amazon.

Дан отсортированный по возрастанию массив целых чисел, все элементы которого уникальны. В массиве есть пропущенные элементы.
Необходимо найти k-й пропущенный элемент начиная с нулевого элемента массива.

Например: [4, 7, 9, 10], k = 1 -> Ответ 5. [4, 7, 9, 10], k = 3 -> Ответ 8 (пропущены 5, 6, 8)

Решение опубликую позже. Подсказка - оптимальное решение работает за O(log(n)) с использованием бинарного поиска.

Задача с собеседования в Facebook(Meta): Найти пиковый элемент
#собеседование #interview #algo #meta #binarysearch

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

Дан массив целый чисел. Любые два соседних числа не равны друг другу. Найти любой пик в массиве. Пик это элемент в массиве, который больше своих соседей слева и справа. Т.е. arr[i-1] < arr[i] > arr[i + 1] в этом случае i-индекс пика в массиве. Можно предположить, что arr[-1] = arr[n] = минус бесконечность.

Решение:
1. Первое решение, которое приходит в голову - линейный поиск. Просто в цикле пройти по массиву и сравнить каждый элемент с соседями. Как только найдем arr[i-1] < arr[i] > arr[i + 1] вернуть i. Временная сложность такого решения: O(n).
Можно еще немного упростить:
проверять только arr[i] > arr[i + 1],
т.к. дано, что на краях значения это минус бесконечность, значит вначале массив возрастает, можно найти первый случай, когда массив убывает.
Код:

public int findPeakElement(int[] nums) {
  for (int i = 0; i < nums.length -1; i++) {
    if (nums[i] > nums[i + 1]) return i;
  }
  return nums.length - 1;
}

2. Можно ли еще улучшить решение? Т.к. дано, что соседние элементы не равны друг другу - в массиве присутствуют отрезки, где массив только возрастает или только убывает. Можно это использовать для применения бинарного поиска.
Т.к. нам нужно найти любой пик, то вполне можно начать поиск с середины массива, как в бинарном поиске.
Давайте попробуем применить бинарный поиск для поиска такого пика.
Пусть мы смотрим на середину массива. К каким выводам мы можем прийти смотря на серединный и соседний элемент?
Равными они не могут быть по условию.
Если следующий элемент больше середины, то массив возрастает. Значит пик точно есть справа. Иначе - слева. На следующей итерации мы снова будет смотреть на новую середину, мы не обязательно найдем вершину, возрастание к которой мы обнаружили на предыдущем шаге. Но мы точно знаем, что в новой уменьшенной области он точно есть. Рано или поздно наша область поиска будет уменьшена до одного элемента, который гарантировано будет пиком. Он будет работать за O(log(n)), что быстрее линейного поиска.
Код:

public int findPeakElement(int[] nums) {
  int left = 0;
  int right = nums.length - 1;
  while (left < right) {
    int mid = (left + right) / 2;
    if (nums[mid] < nums[mid + 1]) {
      left = mid + 1;
    } else {
      right = mid;
    }
  }
  return left;
}

Введение в Load Balancers. Часть 1 из 3
#собеседование #interview #systemdesign

Начал писать цикл статей посвященных system design собеседованиям.
Публикую первую часть посвященную Load Balancers.
Знать, что такое LB и уметь их применять критически необходимо на system design собеседовании.
https://telegra.ph/Load-Balancers-Vvedenie-CHast-1-iz-3-05-15

Введение в Load Balancers. Часть 2 из 3
#собеседование #interview #systemdesign

Публикую вторую часть посвященную Load Balancers.
https://telegra.ph/Load-Balancers-Vvedenie-CHast-2-iz-3-05-16

Минусы работы в IT/программистом
#мысли
Сейчас из каждого утюга рекламируют курсы по программированию и работы в IT.
Рассказывают про огромные зарплаты и удаленку из любой точки мира.
Но мало кто говорит про минусы и недостатки работы программистом или в IT в целом.

Конечно, работа в IT имеет большое число плюсов, иначе я бы этим не занимался. Но в этом есть и множество недостатков.
Я попытался выделить наиболее значимые, по-моему субъективному мнению:

1) Это сидячая работа перед компом/ноутом. Вам нужно проводить практически всю жизнь сидя (лежа, если вы на удаленке😄) возле компа. На первый взгляд, это может показаться плюсом. Это не в шахте работать. Но через много лет такой сидячей работы, почти гарантированно, у вас будут проблемы с осанкой, спиной, кистями рук, шеей, лишним весом.  Кроме того, сейчас большинство людей предпочитает проводить свой отдых также за компом/ноутом/телефоном. Поэтому почти все время, не занятое сном, вы скорее всего будете проводить перед компьютером.
2) Постоянное обучение. Вы не можете просто закончить универ, курсы и использовать эти знания всю жизнь. В IT все очень быстро меняется. Каждый день появляются новые технологии, библиотеки, подходы, тулы и т.д.  Вам нужно постоянно что-то изучать, чтобы не остаться за бортом. Т.е. кроме работы 40 часов в неделю вам нужно постоянно выделять время на самообразование и отнимать это время из своего личного (отдыха, времени с семьей и друзьями).
3) Конкуренция и стресс. Несмотря на большую потребность в программистах, получить работу и пройти собеседование очень сложно. Типичной, является ситуация, когда человек откликается на сотни вакансий, проходит десятки собеседований и получает одно предложение о работе после 6 месяцев поисков работы. Кроме конкуренции внешней, есть конкуренция внутри компаний. Есть перфоманс ревью вашей работы, конкуренция за повышение, за премию, за то, чтобы не быть уволенным. Это постоянный стресс.
4) Написание кода это лишь маленькая часть работы программистом. Допустим, вам нравится писать код или проектировать системы. Вы могли бы заниматься этим хоть целый день. Но в реальности, это будет лишь малая часть того, что вы будете делать. Вам нужно будет взаимодействовать с другими людьми, командами и о чем-то договариваться, писать формальные документы. И провожу 40-50% времени на митингах (совещаниях), которые часто не дают никаких результатов. Придумывание дизайна системы занимает очень мало времени. После этого нужно это все описать и очень долго ревьюить с другими людьми. Даже если вы сядете писать код, то вначале вам нужно прочитать тонну другого кода, чтобы понять куда его нужно вставить. Потом долго и упорно бороться с непонятными проблемами и багами. Если вы начинающий программист, что скорее всего вы будете часто застревать и искать помощи у других коллег.
5) У вас будет страдать ваша социальная жизнь. Из-за того, что вы много работаете, а потом еще и много учитесь у вас будет очень мало времени на друзей и семью. Если вы социально активный человек, то ваша социальная активность скорее всего сильно снизится.
6) Прокрастинация. Как и в любой другой умственной деятельности вы будете постоянно прокрастинировать и бороться с прокрастинацией. Особенно, в той части работы, которую вы не очень любите. А как я уже сказал, работа в IT это не только проектирование систем, написание кода, анализ данных или тестирование. Это много всякой бюрократии, митингов и попыток о чем-то договориться. Будьте готовы заставлять себя постоянно что-то делать, что вам не очень нравится.

Если вы уже работаете в IT, пишите в комментариях, что вам больше всего не нравится в вашей работе.

Хотите изучить многопоточность в Java и легко проходить собеседования на Backend Java Developer?
#книги #interview #собеседование #java
Рекомендую книгу от одного из создателей многопоточности в Java: "Java Concurrency in Practice by Brian Goetz". В ней разбираются основные понятия и концепции многопоточности в Java, рассматриваются конкретные примеры и тонкие места. Вы узнаете что такое thread safe классы, immutable, как работает volatile, final и synchronized в контексте многопоточности. Узнаете про thread safe коллекции в Java, создание, синхронизацию, приостановку и остановку потоков. Что такое dead lock и как его предотвратить. Что такое Java Memory Model и happens before. Если вы хотите стать backend разработчиком или улучшить свои знания, то я рекомендую эту книгу не просто полистать, а изучить очень подробно. Эту книгу я прочитал раз 5. Она мне помогла в свое время получить 3 офера о работе. Собеседования в такие компании как Яндекс, Сбертех, Mail, Revolut(раньше еще был Дойче Банк в России) на Java бэкендера содержат существенную часть посвященную многопоточности. Иногда это треть или даже половина всех вопросов связанных с Java напрямую. Очень много вопросов просто взяты из этой книги.

Вопрос с собеседования: как работает HashMap в Java?
#собеседование #interview #java #collections #hashmap #коллекции
Это очень популярный вопрос на собеседовании. Встречается практически на любом собеседовании на Java программиста.
Описал ответ тут: https://telegra.ph/HashMap-05-18

Задача с собеседования в Яндекс на бинарный поиск
#собеседование #interview #algo #алгоритмы #яндекс #binarysearch #бинарныйпоиск
Решил сделать отдельный пост, т.к. задача оказалась несколько сложнее, чем я изначально думал.
Задача: Какое число итераций (чтений из массива) потребуется, чтобы при помощи бинарного поиска гарантированно найти индекс заданного числа или установить его отсутствие в отсортированном массиве из 1000 чисел в худшем случае?
Решение: Бинарный поиск работает за O(log(n)) т.к. сокращает область поиска в два раза на каждой итерации. Я описывал бинарный поиск тут: Бинарный поиск. Худший случай это, например, поиск элемента на краях массива. Скажем у нас есть массив: [1, 2, 3, 4] и нам требуется найти 4. Нам потребуется 3 итерации.
Давайте попробует установить общую закономерность для любого размера массива.
Для размера 1: 1 итерация.
Для размера 2: 2 итерации.
Для размера 3: 2 итерации.
Для размера 4: 3 итерации.
Для размера 5, 6, 7: 3 итерации.
Для размера 8: 4 итерации.
Для размера 9, 10, 11, 12, 13, 14, 15: 4 итерации.
Для размера 16: 5 итераций.

Общая закономерность: Если размер массива это степень двойки (2, 4, 8, ...), То число итераций равно log2(n) + 1. Если размер не является степенью двойки, то нужно округлить log2(n) вверх до ближайшего целого: roundup(log2(n)).
Или За k-итераций бинарный поиск может обработать от 2^(k-1) до 2^k - 1 элементов массива: В виде отрезка это: [2^(k-1), 2^k) 2^k - не включительно

Теперь вернемся к задаче.
2^10 = 1024. Это больше, чем 1000. За 10 итераций бинарный поиск сможет обработать [2^(10-1), 2^10) = [512, 1024) элементов. Или от 512 до 1023 элементов. Т.е. ответ 10
Или 1000 не является степенью двойки, поэтому ответ: roundup(log2(n)) = 10
Давайте посмотрим как будет уменьшаться область поиска по итерациям для 1000:
1: 1000->500
2: 500->250
3: 250->125
4: 125->62
5: 62->31
6: 31->15
7: 15->7
8: 7->3
9: 3->1
10: Находим элемент или устанавливаем его отсутствие.
Ответ: 10

Спасибо всем, кто писал свои соображения в комментариях и чате.

Задача на алгоритмы и структуры данных: проверить правильность скобочного выражения
#собеседование #interview #algo #string #строка #stack #стек #алгоритмы
Эта задача широко известна, часто применяется как разминочная или для первичного отсева кандидатов на phone screen.
Встречал ее в реальности на собеседованию в компанию skyscanner. В модифицированном и усложненном виде встречал на собеседовании в facebook.
Кратко условие: дана строка, которая может содержать 3 типа скобок и другие символы. Проверить правильность скобочного выражение.
Эта задача поможет вам лучше понимать как работать со строками и стеком.

Решение описал тут: Решение.

System Design: Consistent Hashing
#systemdesign
Написал статью про Consistent Hashing, который используется во многих современных распределенных системах типа AWS Dynamo DB, Apache Casandra, Couchbase и т.д.: https://telegra.ph/Consistent-Hashing-05-22

Задача с собеседования на многопоточность: Пинг-Понг или Шагающий Робот
#собеседование #interview #java #concurrency
Встречал эту задачу в несколько компаний, в том числе в Яндекс.
Задача следующая. Нужно написать многопоточную программу на Java, в которой будет два потока, первый поток будет печатать “Ping”, второй поток “Pong”. Причем они должны делать это последовательно. Вначале первый поток печатает Ping, а потом второй Pong, потом первый Ping, потом второй Pong и т.д. Есть вариация для этой задачи про шагающий робот. Там также нужно два потока, каждый отвечает за одну из ног робота. Один поток “ходит” левой ногой, второй правой ногой. Они должны делать это последовательно. Начать можно например с левой ноги.

Решение через wait-notify описал тут: Решение.

Можно придумать много других решений, например, при помощи Condition и ReentrantLock.

System design: Load Balancers. Часть 3.
#systemdesign
Публикую 3 часть про Load Balancers: https://telegra.ph/Load-Balancers-CHast-3-05-22

Готовитесь к собеседованию по алгоритмам или по решению алгоритмических задач? Или просто хотите научиться решать алгоритмические задачи?
Я успешно прошел собеседования в Amazon и Facebook, существенная часть которых это алгоритмические задачи.
Например, в Amazon, у меня было 5 алгоритмических задач (2 на phone screen/online test, 3 на onsite собеседовании). В Facebook, было 6 алгоритмических задач (2 на phone screen и 4 на onsite собеседовании). На каждую такую задачу, по сути, давалось 15-20 минут.
Поэтому эти задачи надо уметь решать очень быстро.
В процессе подготовки я прочитал много книг и использовать множество различных ресурсов.
Но эти 3 я считаю лучшими и стоящими своих денег:

1) Книга Cracking the Coding Interview by Gayle Laakmann McDowell. Новичкам стоит начать с нее. Читать нужно в оригинале. Она разбита по темам. В начале каждой темы приведен алгоритм, который нужно знать наизусть и потом приведены задачи и решения к ним. Стоит начать с запоминания и понимания работы алгоритмов. Попробуйте выписать эти алгоритмы на бумажке без использования подсказок. Делайте это до тех пор, пока у вас это не будет получаться на автомате за пару минут. Далее смотрите задачи. Попробуйте сначала решить задачу сами. Если не смогли решить за 1-2 часа, изучайте решение до тех пор, пока не сможете сами, без подсказок, написать решение. По факту, мне этой книги хватило для прохождения собеседования в Amazon (но только после того, как я мог решить каждую задачу минут за 15 из этой книги. На это у меня ушел примерно год).
2) algoexpert.io. Этот ресурс я также рекомендую новичкам и при среднем владением алгоритмами. У автора этого ресурса есть youtube канал: https://www.youtube.com/@clem. По промокоду clem можно получить скидку. Ресурс содержит набор типовых алгоритмических задач и решений к ним. Его большой плюс - на каждую задачу есть часовое видео с пошаговым разбором решения. Более того, там есть материалы для подготовки к другим собеседованиям: system design, поведенческое собеседование, blockchain, front-end, ML.
3) leetcode.com. Содержит огромную библиотеку задач и решений к ним (более 1000 задач). К сожалению, пояснения к решениям могут отсутствовать или быть очень непонятно написанными. Поэтому рекомендую его только начиная со среднего и продвинутого уровня владения алгоритмами. Leetcode позволяет отфильтровать задачи по названию компании и по частоте встречаемости в этой компании. Благодаря leetcode я смог легко решить все алгоритмические задачи на собеседовании в Facebook. При подготовке я решал задачи, которые спрашивали в Facebook и взял топ 100 по частоте. Половина из задач на собеседовании просто совпали с теми, что я решал на подготовке. А другая половина была похожа на другие, которые я уже решал.

Я знаю и использовал много других ресурсов (тот же https://www.hackerrank.com/) и прочитал много других книг. Но они, по-моему мнению, мне меньше помогли и сделали процесс подготовки менее эффективным.

Вопрос с собеседования: Какие методы класса Object вы знаете?
#java #interview #собеседование
В том или ином виде встречается очень часто на собеседованиях на Java программиста. Он может быть использован как начальный вопрос, чтобы потом перейти к обсуждению HashMap и многопоточности с использованием wait-notify.
Ответ описал тут: https://telegra.ph/Kakie-metody-klassa-Object-vy-znaete-05-28

Алгоритм поиска в глубину в графе
#собеседование #interview #algo #алгоритмы
Алгоритмические задачи на графы достаточно распространены на собеседованиях. Особенно в топовые компании. По факту нужно знать три алгоритма для решения такого рода задач: поиск в глубину, поиск в ширину и топологическая сортировка.
Написал краткую справку по поиску в глубину: DFS.
Далее опубликую примеры задач на поиск в глубину в графе и другие алгоритмы и примеры задач к ним.

Задача на обход графа: реализовать заливку как в Paint
#algo #собеседование #interview
Классическая задача с собеседования на обход графа: реализовать заливку как в Paint.
Встречал ее на реальном собеседовании в Booking.com.
Решение и более детальное условие описал тут: Решение.

Публикую решение на задачу: найти k-й пропущенный элемент в отсортированном массиве
Дан отсортированный по возрастанию массив целых чисел, все элементы которого уникальны.  В массиве есть пропущенные элементы.
Необходимо найти k-й пропущенный элемент начиная с нулевого элемента массива.

Например: [4, 7, 9, 10], k = 1 -> Ответ 5. [4, 7, 9, 10], k = 3 -> Ответ 8 (пропущены 5, 6, 8)

Решение описал тут: Решение

Иерархия исключений в Java
#interview #собеседование #java
Я сразу рассмотрю несколько связанных вопросов с собеседования на Java программиста:

1) Какая иерархия исключений в Java?

2) Чем отличаются checked от unchecked исключений?

3) Что такое Error?

4) Какой пример Error вы знаете?

5) Можно и нужно ли перехватывать OutOfMemoryError?

6) Какие примеры RuntimeException вы знаете?

7) Можно и нужно ли перехватывать Throwable?
Ответ описал тут: Иерархия исключений в Java.

Хотите узнать сколько зарабатывают в топ IT компаниях мира?
Рекомендую сервис https://www.levels.fyi/
Там вы можете сравнить сколько платят в разных топ IT компаниях мира разным уровням программистов.
Например, сравним зп в Google, Amazon и Facebook: Сравнение.
Эти зп в год в США в кремниевой долине. В Европе в тех же компаниях зп меньше. Например, в Лондоне зп примерно в 1.5 раза ниже в тех же компаниях и тех же должностях.
Краткая выжимка для Facebook:
1) E3 (Junior) - $182 000
2) E4 (Mid) - $255 000
3) E5 (Senior) - $368 000
4) E6 (Staff) - $557 000
5) E7 (Principal) - $980 000
6) E8 (Senior Principal) - $1 660 000
7) E9 (Distinguished/Выдающийся инженер) - $2 534 000

Компенсация в таких компаниях состоит из трех частей: базовой зп (выплачивается каждый месяц), бонус(выплачивается раз или два раза в год), и акции компании (выдаются 1-4 раз в год). Акции таких компаний ликвидны. Как только вы получили акции Google или Amazon, вы можете их продать в тот же день или хранить с надежной, что они вырастут в цене.
На позиции Distinguished работают очень мало программистов. Это десятки или сотня программистов в одной такой компании. Я помню, когда работал в Amazon, у нас на позиции Distinguished работал создатель Java James Gosling.

Задача на многопоточность в Java: Приостанавливаемый поток
#interview #собеседование #java #concurrency
Напишите поток, который можно приостановить, продолжить/возобновить его выполнение и остановить.

Это вопрос на знание нескольких фактов:

1) Как в Java создать поток
2) Знание того факта, что Thread.stop(), Thread.suspend() и Thread.resume() не безопасны и deprecated. Их нельзя использовать.
3) Знание wait-notify механизма в Java
4) Знание volatile и/или synchronized в Java
5) Как работает interrupt()
Решение описал тут: ResumableThread