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

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

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

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

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

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