Вопросы на собеседовании в FAANG

Всем привет!
После многочисленных попыток пройти собеседование в FAAANG с 0 фидбеком у меня накопилось несколько вопросов.
Два из них не дают мне покоя, прошу всех неравнодушных пролить свет ибо спать не могу ночами — размышляю.
Фидбека ни разу не получил, обычно кивают головами, говорят ’авесом!’, а потом приходит отказ :(


1) Наверняка вы знаете о задачах с деревьями и графами требующих применения DFS алгоритма для решения, например:
Обычно я решаю такие задачи с применением рекурсии, понимаю что задача учебная и если стек в какой-то момент переполнится и приведет к краху программы — ничего страшного. Я так думаю, что данных подход для продакшена не годится т.к. невозможно определить на сколько итераций осталось доступной стековой памяти. Поэтому правильнее было бы заменить рекурсию на очередь (контейнер стек).


Вопрос: Правильны ли мои рассуждения и насколько правильно решать задачи рекурсией на собеседованиях?


2) Задача на нахождение наименьшего общего предка (Lowest common ancestor — LCA) в несбалансированном и небинарном дереве (абсолютно рандомном)


Самый простой, наивный алгоритм для нахождения наименьшего общего предка — вычислить глубину вершин u и v и постепенно подниматься из каждой вершины вверх по дереву, пока не будет найдена общая вершина. Время работы этого алгоритма составляет O(h), где h — высота дерева.


Различные модификации данного алгоритма — с применением HashSet и прочее — не ускоряют эту задачу, она остается O(h).


Есть ли кто-то, кто может прояснить для меня алгоритм двоичного подъема, требующий O(n log n) или любой другой алгоритм с таким же временем?
👍НравитсяПонравилось1
В избранноеВ избранном1
LinkedIn
Допустимые теги: blockquote, a, pre, code, ul, ol, li, b, i, del.
Ctrl + Enter
Допустимые теги: blockquote, a, pre, code, ul, ol, li, b, i, del.
Ctrl + Enter

оставлю здесь, может кому-то пригодится.
в телеге группа неравнодушных создала и активно модерирует несколько каналов, связанных с прохождением интервью в фаанги (общее интервью, сисдиз, мобайл, фронтенд) и последующими шагами (обсуждение проблем, возникажщих в первые недели в сша в частности). среди каналов есть также такой, где люди договариваются о проведении мок интервью с участниками канала.

tinyurl.com/554acs8u

прямой линк на основной канал: t.me/FaangInterviewChannel

Небольшой апдейт по поводу моего вопроса о применении рекурсии: на соседнем проекте лямбда на AWS была написана с использованием рекурсии, что приводило к ее краху при определенных входных данных. Переписали без рекурсии.

1) неправильно
при рекурсии мы загружаем стек памяти, при итерациях мы нагружаем стек который сами создали, то есть в любом случае dfs это О(h) по памяти
2) если есть ссылка за parent node то задача сводится к вот этой leetcode.com/...​tion-of-two-linked-lists
это решается за O(h)/O(1)

1) неправильно

При рекурсиях мы загружаем стек + динамическая память. Если переписать рекурсию через контейнеры (Stack, Queue например) — будет использоваться только динамическая память

2) если есть ссылка за parent node то задача сводится к вот этой leetcode.com/...​tion-of-two-linked-lists

решение за O(h) я знал и предоставил, но это не оптимальное решение

Это оптимальное решение. Если я Вам дам какое-то дерево и зафиксирую две вершины, Вам понадобится в худшем случае Θ(n) времени, чтоб только «изучить» топологию Вашего дерева. Это неизбежный шаг в любом алгоритме. То есть любой алгоритм будет работать на самых худших входных данных не быстрее, чем Ω(n).
А Ваш алгоритм работает за время O(h) = O(n). То есть этот алгоритм в самом худшем случае работает по нижней границе всех возможных алгоритмов. Это оптимум.

А то, что Вас не устраивает алгоритм за время O(h) (который на самом деле O(n)), и вместо этого Вы пытаетесь искать какой-то «оптимальный» алгоритм, который работает за время O(nlog(n)) (то есть медленней) — это вызывает удивление и подозрение, что Вы не очень понимаете, как читать символы Ландау.

1) Рекурсія — без проблем. Мене один раз попросили переписати алгоритм саме з використанням рекурсії (задача спочатку була вирішена методами динамічного програмування). А потім ми ще трохи поговорили про недоліки і переваги кожного з рішень.

Там є багато варіацій задачі LCA. Сама класична це коли дерево статичне, у тебе є час на препроцесінг і потім тобі треба швидко відповідати на запити в стилі LCA(u, v). Власне в такому формулюванні є супер красиве рішення, яке з препроцесінгом за O(NlogN) дасть можливість відповідати на запити LCA(u, v) за O(1) — да-да, саме за константу.

Більш продвинута LCA це коли у тебе можуть бути запити не тільки LCA(u,v) а ще й такі, які модифікують саме дерево. І вимога стоїть така, що треба вміти швидко відповідати на обидва типи запитів. Це «гроб».

Але якщо у тебе сама класична задача, то від тебе очікували чогось тіпа такого. Спочатку порахуємо глибину кожної вершини v: d[v]. Далі коли прийшов запит LCA(u, v) ми можемо знати яка з вершин «глибше»: скажем d[u]=10, d[v]=6. Це значить, що u на глибині 10 ребер від кореня, а v — на глибині 6. LCA, очевидно, хоча б на глибині 6. Власне тепер можна було непогано швидко піднятись від u хоча б до глибини v, тобто на 10-6=4 вверх: u=go_up(u, d[u]-d[v]);. Якщо після підйому u == v, то v була предком u, і можна робити return u. Інакше можна двійковим пошуком йти «вверх» і перевіряти чи співпало. Тобто зараз у тебе обидві вершини на глибині depth=6, давай з обидвох підемо вверх на половину цієї глибини: u1 = go_up(u, depth/2), v1 = go_up(v, depth/2); якщо u1==v1, то це вже точно їх спільний предок, але не обов’язково найнижчий — далі можна йти половинним поділом не до глибини 0, а до цієї depth/2. Якщо u1 != v1, то далі можна шукати спільного предка u1 і v1, їм до корня в 2 рази менше відстані треба йти. В любому випадку ти довжину шляху зменшуєш вдвоє (LCA буде або десь між depth і depth/2 або між depth/2 і 0), тобто двійковий поділ. Залишилось придумати як швидко реалізувати go_up(vertex, num_levels). Тут один досить простий трюк: а давай для кожної вершини предпорахуємо таке:
up[v,0] — вершина на 1 рівень вище v; тобто предок v
up[v,1] — вершина на 2 рівня вище v; тобто дід предок-предка v.
up[v,2] — вершина на 4 рівня вище v
up[v,k] — вершина на 2^k рівнів вище v.
Тобто ти отримуєш можливість з любої вершини за один скачок перейти на 1, 2, 4, 8, 16, ... рівнів вверх. Ну і далі з таких скачків ти зможеш скласти шлях за O(log(depth)) на любу кількість рівнів вверх.
А ... ну і up[v, k] = up[up[v, k-1], k-1] — тобто предпорахувати up[v,k] теж досить просто.

Власне навіть якщо це все «в лоб» реалізувати, то получиш алгоритм, якому для LCA треба буде O(log(depth)) раз викликати go_up, тобто O(log^2(depth)). Але тут можна досить легко оптимізувати до O(log(depth)) так:

Нехай є u, v на глибині depth, u != v. Шукаємо найнижчого спільного предка, але вже на даний момент знаємо, що на глибині ca_depth точно вже є спільні предки. Спочатку ca_depth=0, тобто ми дійсно знаємо, що root (вершина на глибині 0) дійсно, 100%, спільний предок u, v; І далі шукатимемо якогось предка поглибше. Тобто нам треба йти вверх не відомо скільки кроків, але відомо, що це число від 1 до depth-ca_depth, включно. Тобто якщо з самого початку depth=6, ca_depth=0 то спільний предок може бути на 1, 2, ..., 6 рівнів вище. На 6 рівнів вище (на рівні 0) є вершина, яка точно спільний предок — цікаво чи є щось понижче :).

Давай візьмемо максимальну степінь двійки, яка менша за depth-ca_depth. Наприклад в попередньому прикладі ми пробуємо перевірити чи якийсь із предків 1, ..., 6 теж є спільним. Макс степінь двійки строго менша за 6 це 4. Йдемо з обидвох вершин на jump=4 рівні вверх за 1 скачок і маємо u1=up[u, 2], v1=up[v, 2]; якщо u1==v1, то ми вже знаємо, що на глибині depth-4 == 2 теж спільний предок, тому якщо u1==v1, то ca_depth := depth-jump; А якщо u1 != v1, то далі будемо шукати спільного предка u1 і v1, які знаходяться на глибині depth-jump.

Тобто замість того, щоб йти «в лоб» двійковим пошуком, де кожен крок O(log(depth)) ми йдемо по степенях двійки за O(1) кожен крок. Ітого LCA за O(log(depth)) запит.

---------------------

Але є дуже красивий і ефективний спосіб за O(1).

Спочатку трохи інша задача. Нехай у тебе є масив arr, тобі його треба якось предобробити, щоб потім за O(1) вміти відповідати на запитання який мінімум на відрізку arr[L:R]. Це так звана задача RMQ — Range Minimum Query, вона є багато де описана. Але ідея така: давай для кожної позиції i порахуємо такі значення: m[i,0] = min(arr[i:i+1]), m[i,1] = min(arr[i:i+2]), m[i,2] = min(arr[i:i+4]), ..., m[i,k] = min(arr[i:i+2**k]). Це зробити досить просто, бо m[i,0] = arr, а всі наступні це просто min з 2х попередніх.

Тепер коли у тебе є запит RMQ(L, R), то ти шукаєш k — макс степінь двійки ≤ за R-L і тоді мінімальне значення на arr[L:R] буде min(m[L,k], m[R-2**k,k]). Наприклад треба RMQ(5, 11), тобто min(arr[5:11]) = min(arr[5], arr[6], arr[7], arr[8], arr[9], arr[10]) — мінімум з 11-5=6 елементів. Тут легко знайти k=2, бо 2**2 == 4 ≤ 6, а при k=3 вже буде більше ніж треба (як швидко знайти k? див функцію __builtin_clz()). Ок, маємо k=2. Тепер подивимось що у нас є:
m[5,k=2] = min(arr[5], arr[6], arr[7], arr[8])
m[R-2**k, k=2] == m[11-2**2, k=2] = m[7,k=2] = m[7,k=2] = min(arr[7], arr[8], arr[9], arr[10])
min з цих 2х значень і є min(arr[5:11]).

Ok, назад до LCA. Нехай у тебе є дерево. Давай зробимо його DFS обхід і: 1) перенумеруємо всі вершини в порядку обходу 2) випишемо цей обхід.
Ось рандомні дерева з інету: media.geeksforgeeks.org/...​uploads/minHeightTree.png
Перше дерево згенерує такий обхід: [1, 3, 2, 3, 4, 5, 4, 3, 1].
Друге дерево згенерує такий обхід: [2, 3, 1, 3, 4, 5, 4, 3, 2].
Третє дерево згенерує такий обхід: [3, 1, 3, 2, 3, 4, 5, 4, 3].
Четверте дерево згенерує такий обхід: [4, 3, 1, 3, 2, 3, 4, 5, 4].
П’яте дерево згенерує такий обхід: [5, 4, 3, 1, 3, 2, 3, 4, 5].
Але нас цікавлять не оригінальні назви вершин, а нові індекси в порядку обходу. Тобто якщо глянути 5-те дерево, то ми спочатку відкрили для себе вершину 5, потім 4, потім 3, потім 1, потім 2 (другий раз коли ми зайшли в 3 це вже не «відкрили для себе»).
Псевдокодом пояснити буде простіше і буде якось так:

global_index = 0
path = []
def dfs(v):
  new_name = global_index
  global_index++
  path.append(new_name)
  for u in children[v]:
    dfs(u)
    path.append(new_name)
dfs(root)
(тут ще треба додати створення двох map/dict’ів з оригінальних назв вершин в нові назви і навпаки). Перенумерація потрібна для дуже простої штуки: всі пердки мають менші номери за любих нащадків. Тепер дуже цікава штука: якщо у тебе є path, то ти можеш точно сказати коли ти вперше побував у вершині: first_pos[original_name]. Цікаво те, що мінімальне значення на path[first_pos[u] .. first_pos[v]] це і є твій LCA. А мінімум на відрізку ти вже вмієш шукати за O(1).

якщо є можливіть для вершини знайти parent (нехай для кореня він буде None), то я би ще згадав такий доволі дерев’яний підхід

u1, v1 = u, v
while u1 != v1:
    u1 = parent(u1) if u1 else v
    v1 = parent(v1) if v1 else u
return u1

такой подход в самом плохом случае требует O(h) времени и это не O(NlogN)

такой подход в самом плохом случае требует O(h) времени

це повинно мені про щось сказати? в залежності від точної постановки задачі така складність може бути як оптимальною так і неприйнятною.

O(h) времени и это не O(NlogN)

а 7 не дорівнює 48, далі що?

У меня есть пару замечаний по поводу LCA:
— Вы должны определиться, какую именно задачу Вы решаете. Ваш алгоритм — это решение для произвольного дерева и произвольных вершин u и v, и Ваш алгоритм является оптимальным в том плане, что нет алгоритма, который решал бы эту задачу быстрей (правда, не очень понятно, зачем искать глубины вершин u и v). Те замечания про более оптимальные алгоритмы в вики — они касаются версии с запросами, когда граф как бы задан и фиксирован, а нас в первую очередь интересует именно время выполнения запроса.

— Хотя на вики и написано, что сложность можно измерять в глубине дерева, но лично я, если б очень хотел придраться, то обратил бы внимание, что в таком виде получается, что Ваш алгоритм псевдополиномиальный, так как зависит не от размера входных данных, а от численных значений этих самых данных, что как бы не очень хорошо для столь простой задачи. Обычно временная (да и пространственная) сложность считается как функция от размера входных данных. Есть исключения, но не думаю, что эта задача одна из них.

По первому вопросу, рекурсивный алгоритм можно реализовать и без рекурсии. Рекурсия работает на стеке вызовов, можно организовать тот же алгоритм применив структуру данных + стек т.е. FILO очередь. Как я понимаю собеседующему важно понимать вашу осведомленность в этом вопросе, вывести вас на беседу спросить вправо, влево и т.п. В курсе вы как работает стек вызовов, какие есть соглашение о вызовах, как работает раннее и позднее связывание и т.д. Аналогично с задачами на: динамический массив и связный список, дополнение до двойки, стратегии кеширования и т.д. Задача состоит в том чтобы определить базовый уровень алгоритмической подготовки собеседуемого. У синиоров он как правило выше, так как приходилось сталкиваться по работе и дополнять вузовское образование практикой и т.д, в общем сображалка заточена правильно мыслить. Соответственно и в реальной боевой работе будешь думать рекурсию тебе применять или стек на хипе, если потоков много то увеличить размер стека может быть неприемлемо т.к. много памяти будет утеряно, зато стек на хипе может потребовать N дополнительных выделения памяти что будет сильно медленнее. 2. Алгоритмы на графах описаны в куче источников, например e-maxx.ru/algo/lca

А реально ли вообще в стандартном дереве сделать это со сложностью меньшей, чем O(h), без хранения дополнительных пре-процесснутых данных в каждой ноде, кроме стандартных ссылок на left/right/parent?
Если нет, то тогда мы получается утяжеляем операции вставки/удаления, плюс увеличиваем требования к памяти.

Тут как раз и спрашивают за все возможные опции, включая parent. Если посмотреть реализации красно-черных деревьев из стандартных библиотек то там как раз этот parent по началу и удивляет, непонятно зачем тратить столько памяти. Однако кода начинаешь реализовывать итератор у себя в коде ядра сразу все становится понятным.

Знали б вы, ребята, сколько гемора потом у garbage collector в распутывании ваших деревьев. Особенно если они нестандартные. Это только в теории всё классно, а на практике — совсем не лишним будет написать деструктор.

Вопрос: Правильны ли мои рассуждения и насколько правильно решать задачи рекурсией на собеседованиях?

Все рассуждения нужно озвучивать и обговаривать с интервьюером.
Скорее всего интервьюер согласится на любое предложенное решение, если все риски описаны, а временная сложность алгоритма такая как он хочет.
Принцип простой: don’t make assumptions.

Это не совсем так, конечно надо все озвучивать
Но в случаях когда я справлялся на отлично (по моему мнению), или лажал, или откровенно тупил — я получал примерно одинаковый ответ — «Don’t worry, this solution is very good»
Что привело меня к мысли, что конфликты и критика намеренно избегаются, кандидат должен сам критически оценить свой код и улучшить что можно

кандидат должен сам критически оценить свой код и улучшить что можно

Як ви можете щось покращити, якщо вам невідомі параметри по яким треба оптимізувати?

имхо: если кандидату неизвестно что спрашивать и как улучшить решение — это уже показывает определенный уровень. Учитывая что многие компании переходят на удаленную работу мне кажется, что кандидаты требующие какого-то одобрения или рецензии своих решений — не так востребованы. Идет отбор на кандидатов типа — вот есть такое решение, оно оптимальное потому-что ...
Пару раз ко мне приходило отличное решение через 5 мин после конца интервью, я пытался проявить активность — находил и писал этим людям в LinkedIn — но это было напрасно :/

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

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

Лучший способ получить ответ на ваши вопросы это таки получить фидбек, для этого можно пройти мок интервью (например здесь www.pramp.com). Если вы уверенно решаете LC задачи средней сложности, пусть даже не самым опртимальным алгоритмом, то проблема не в ваших кодинг скилах.

упомянуть о проблеме с переполнением стека

 — это мой фейл. Беда в том что не получил толкового фидбека ни разу. Даже не смог получить ответ какое из 4 интервью провалилось. Попробую пойти по вашей ссылке.

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

Рекурсия, это всегда О(n) по памяти (ну кроме хвостовой которую иногда среда оптимизирует но это зависит от самоц среды исполенения) и по времени, что далеко не всегда оптимально.

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

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

второй раз мс чет молчали как рыбы

а чем закончилось?

До сих пор молчат :-) Пинговал, сказали что форварднули мой риквест на фидбэк дальше и пока ничего :-)

В Люксембург или в штаты звали? Шкурный интерес — меня звали в Люксембург но я забил болт на рекрутера. Французского не знаю и так себе идея для релокации мне показалась. Да и методы заманивания после долгих лет в торговле меня испугали, больно рассчитаны на болвана который ведётся на все акции.

Алго вопросы можно спросить в этом чате по подготовке

Есть ли кто-то, кто может прояснить для меня алгоритм двоичного подъема, требующий O(n log n) или любой другой алгоритм с таким же временем?

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

хочу попасть на работу в FAANG и проверить что вся эта фигня там используется ))

питання: нащо вам в фаанг?
якщо що, гроші іншими способами можна заробити, де не треба літкод

Да че вы прицепились к человеку? Ну хочет, его право, топик же не про то что «устроиться или нет». Как набегут ото со своими советами когда их не просят.

Такая мечта у меня дурная. Кто-то хочет БМВ, а кто-то Ауди.
Одна из причин состоит в том, что походив по этим собеседованиям я понял насколько заржавел.
Начал тренироваться на литкоде и подучил алгоритмы решения разных задач, прокачал скилл онлайн кодирования на время (что сильно помогло мне при прохождении в ЕПАМ).
Собеседования по дизайну заставили меня читать новые доки в этом направлении — тоже интересная тема.
Все собеседования проходили на английской с инженерами из разных стран — опыт понимания других акцентов кроме индийского)))
Это больше как путь саморазвития, такой себе квест).

на английской с инженерами из разных стран — опыт понимания других акцентов кроме индийского)))

из свежего по работе

youtu.be/irfQczdVjRA

я так отвык уже )) думал такое только в кино

youtu.be/lj96YnI9El8

Была шутка в фаанг чатике.
У человека, работающего в Амазоне спрашивают — используешь ли ты все эти алгоритмы на работе?
он отвечает — да, спрашиваю на собеседованиях ))

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

А то в теории могут решать огромные деревья, а на практике — забывают про 6.5 рукопожатий.

Подписаться на комментарии