На этой неделе будем объединять два отсортированных массива. Задача по форме похожа на объединение двух отсортированных списков, которую мы разбирали ранее.

Посмотрим на брутфорсное решение, а после модифицируем его до решения без дополнительной памяти, что ожидается на собеседовании за «дополнительный плюс в карму».

Про мой опыт собеседования с Амазоном: сколько заняло времени, как общался с рекрутером, примерно что спрашивали и что отвечал — https://leetcode.com/discuss/interview-experience/498867/Amazon-or-SDE2-(Front-End)-or-Edinburgh-UK-or-Jan-2020-Offer

Задача этой недели про «доминантный» элемент, звучит-то как! Это мой вольный перевод слова majority, а найти нужно число, которое повторяется больше половины длины массива раз.

В этой задаче я привожу небольшой экскурс в «О-большое», два разных решения для оценки трейд-офов, а так же алгоритм Бойера-Мура, который со всех сторон оптимальный, но есть и обратная сторона медали — относительно сложный для понимания.

Обычно, на собеседовании это не ожидается, но будет жирным плюсом в карму, конечно. Главное помнить, что время ограничено и нужно успеть написать код и протестировать, что с «хитрыми алгоритмами» может занять больше отведённого под секцию времени.

О чём этот канал?

Всем привет! Меня зовут Виктор. Я увлекаюсь алгоритмами, всякими олимпиадными задачками (решил ~250 задач на LeetCode, если вам это о чём-то говорит). Собеседовался в крупные западные компании: Amazon, Google, Facebook, Microsoft. В итоге, устроился в Amazon, в Эдинбурге 🇬🇧

Еженедельно публикую статьи рассчитанные на 5-10 минут чтения и разбора кода и, возможно, ещё немного времени для чтения «дополнительной литературы», ссылки на которую я буду стараться давать где это имеет смысл. Код написан на JavaScript в императивном стиле, и, в основном, без использования специальных конструкций языка, так что выглядит почти как С 😉

Пока задач 27, из списка на LeetCode, который был подготовлен кем-то из комьюнити на форуме и многими одобрен как «отлично подходящий для начинающих». К сожалению, оригинальная тема на форуме пропала, но список я успел сохранить себе.

Кроме общих задач, таких как конвертер римских чисел, есть задачи на определённые темы: списки, деревья, хеш-таблицы, sliding window, и даже одна задача про дизайн хэш-таблицы с нуля.

Кроме самих решений я буду стараться сопровождать все небольшим экскурсом в используемые структуры данных, как например в задачах про списки.

Можно смело писать в личку в Телеграме, буду рад обсудить задачи, ответить на вопросы и просто пообщаться 😊