Разбираем систем дизайн и алгоритмы для подготовки к FAANG: Facebook, Apple, Amazon, Netflix, Google - решаем популярные задачи с интервью - обсуждаем систем дизайн интервью - пишем подкаст с инженерами из BigTech компаний
Спасибо большое за разбор. Делайте больше!. Хочется добавить несколько уточнений - Про репликацию и СH примерно 25:00. Вот эти ноды на круге A,B,C это не физические ноды, это виртуальные ноды. А за этими виртуальными нодами стоит какое-то количество физических, так же одна физическая нода может быть ответственна за N виртуальных нод. - Это сделано именно для распределения нагрузки(мы не знаем заранее какое распределение хешей будет на кольце). Можно добавлять/убавлять физические ноды на виртуальные - Сама же репликация - да, на N-1 следующих по часовой стрелке виртуальных нод. Как они называют "preference list" - 38:50 - немного путаницы с coordinator - coordinator - нода из "preference list" которая хендлит get/set. Еще ответственность координатора - обновлять отставшие ноды(если нода вернула однозначно определяемое как отставшее значение через векторные часы) - при случайном обращении к одной из нод в кольце - если это нода из preference list - она отвечает на запрос без перенаправления, если это другая нода - то она перенаправляет запрос на первую из preference list - Таким образом у нас есть резервирование и на уровне виртуальных и на уровне физических нод. - Но! Тут же могут проявляться интересные эффекты из-за виртуальных нод т.к. за N виртуальных нод может стоять <N реальных нод. - 36:30 - Sx, Sy, Sz - это серверы/ноды которые меняют объект. Поскольку у нас данные среплицированы на несколько нод и обновление происходит по gossip протоколу - в момент когда мы читаем D5 - и читаем с трех разных нод - мы можем получить 3 разные версии. Ну а там дальше да, как ты и рассказывал: Sx видели все - поэтому он точно не последний, и coordinator вернет остальные casual unrelated и там уже что выбрать между Sy и Sz - хз. - 52:55 - важная добавка - Hinted Handoff это для кратковременных выходов из строя
"Как данные будут храниться и как шардироваться"? - это точно не первый вопрос выбора sql osql))) Первый вопрос - как данные будут использоваться? Сколько запросов будет на чтение и запись и т.п.? Какие будут накладные раскоды на запросах(сложные ли запросы, много ли джойнов и т.п.)? Нужны ли транзакции? При этом ваша система вообще может не быть распределенной. Жуть, а не видео.
Спасибо за комментарий! 1. В видео речь идет о выборе бд для текущих транзакций, не для аналитики данных. Потому о джойнах данных не может быть и речи из-за накладных расходов. 2. Выбор бд должен определять исходя из паттерна доступа к данным (как мы пишем и как читаем) - с этим никто не спорит 3. Транзакции предоставляются многими типами баз данных (в том числе ACID) включая реляционные и не реляционные 4. Речь идет только о распределенных системах.
имхо в большинстве случаев так называемые back-of-the-envelope estimates никак не помогают в дизайне системы, а просто съедают твое время на интервью и практически всегда ничего кроме "оо ну да это много" ты сказать не можешь, ну еще и что твой интервьюер видит, что ты в первые пять классов школы посещал поэтому если твой интервьюер ОК чтобы скипнуть это часть (опять же имхо) -- стоит об этом попросить время на интервью улетает моментально
Спасибо! Очень дельный комментарий! В идеале из этих вычислений сделать какие-то более интересные выводы чем "много" :). Но на практике, получается очень механическая часть интервью: посчитали, покивали ну и дальше пошли :))
Вы про текстовый документ имеете ввиду? Кажется для текстовых файлов совершенно другой алгоритм используется, в отличие от бинарных файлов (видео, аудио, фото) Или не так?
1:00:00 По поводу отдельных таблиц под каждую колонку для эмуляции колоночных бд. Наверняка на каждую строку хранится куча метаинформации, еще и выравнивание по блокам. Хранится такое будет хуже, чем в целевой бд.
Да, зато с базой работаем унифицированно, можем переезжать с одной базы на другую. Опять же как сканировать уникальные индексы если бд шардирована? А вот с таблицами-индексами это делается без проблем
какое-то отвращение вызывают разборы интервью... есть в этом какое-то лицемерие. делать из этого товар. типа давайте рандомного типа научим как устроиться на работу, пусть он потом творит дичь, зато мы ему помогли, это так здорово!
@monnoroch привет, я честно говоря так и не понял идею с деревом, чем она лучше сортировки массива? (случай когда на входе у нас сразу вся конечная последовательность)
Потому что хороший кодер != хороший инженер, ФААНГ нанимает инженеров, если мы не говорим про практикантов. Студент может быть отличным кодером, но вообще не понимать как ведется промышленная разработка софта. Первый человек смог проявить слабые навыки даже для какой-нибудь рандомной мелкой софтверной компании. Впрочем, навыки самостоятельности и лидерства именно в мелких а-ля стартапах и нужны больше всего. И самое смешное что нарешивание алгоритмов на LeetCode никак не помогает обрести эти навыки.
Интересно, что почти все интервью, интервьер говорит что не надо говорить фигню не подумав, а потом на 3:35:00 говорит что 10^10 температуру можно получить при ядерной реакции (что не правда) и температура сильно ограничена в размеа, особенно с той, с которой мы взаимодействуем. То есть, все проблемы что интервьюер говорил, они в принципе свойственны всем и стоит работать над собой, чтобы уменьшить их.
Интересен вопрос попадания на интервью в Apple. Вопрос по сути такой, если в Амазон/Мету/Гугл более менее зовут на собеседование то в Apple ни разу, более того, все попытки самому туда как-то попасть, не увенчались успехом. Слышал такую "легенду" что для попадания на собес в Apple необходим реферал от человека, который там уже работает, но при этом очень важно что бы ты с этим человеком тоже лично работал (те он как бы за вас ручается), а не просто вы нашли какого-то реферала на условном Reddit. Вопрос такой, правда ли это?
Оставлю еще один комментарий. Известно, что задачи на алгосекциях в ФААНГах немного разные (я собесился только в Мету и Амазон). В Мете мне давали 2е задачки на 45 минут примерно изи-медиум уровня и по сути, как мне кажется, для Меты валиднее отточить подход второго кандидата, те очень круто и структурированно описывать свое решение, при этом что лично мне не понравилось, это нелюбовь кандидатов прописывать тест кейсы именно в редакторе. Я пытался в уме что-то прогонять, но обычно получается полная ерунда, а вот когда напишешь, то и интервьюеру понятно, чем я сейчас занимаюсь и мне проще не вылетать из контекста. В Амазоне же задачка была несложной, но очень много было бихейв вопросов и для этого интеревью, на мой взгляд, нужно хорошо пересмотреть свой опыт, что бы не рыться в памяти и вспоминать наиболее подходящую ситуацию под данный вопрос, а практически сразу начать отвечать, так как эта часть отъедает ваше время от алго секции и тогда у вас просто не будет времени на решение, хоть какое-то даже.
Возник такой вопрос. Задача в данном моке была действительно очень обширной и в ней было очень много мест, которые можно и нужно было уточнять, однако, часто бывает задача более "простая", например вам дан список и в нем что-то нужно найти, например 5е максимальное число. Кажется что в этом случае, довольно сложно и на мой взгляд странно задавать вопрос на тему того, а какое бизнес приложение у этой задачи, что бы самому сформировать различные варианты ТЗ. Верно ли я понимаю, что не во всех задачах получится проявить leadership?
Собеседования проводятся под конкретный уровень. Я проводил собеседование под L5 для всех кандидатов, для демонстрационных целей. Под L4/L3 задачи могут быть проще. Тем не менее, это не относится к вашему примеру. Задача найти пятое максимальное число имеет достаточно свободы, чтобы senior (L5) инженер смог показать все те же скиллы, которые были разобраны на стриме. Увидеть эти возможности (и воспользоваться ими) и есть основной признак L5 инженера. Заметьте, что ни один из кандидатов не увидел их в задаче вычисления среднего (хотя третий подошел максимально близко). Это не значит, что этих возможностей не было.
Именно с этого видео нужно начинать подготовку к собеседованиям. Насколько классного разбора собесов я никогда и ни у кого не видел!!! (Конечно все 4е часа сложновато просмотреть, но оно того стоит и лучше потрать свое время на него, а не на какие-то другие видео).