Как я готовился к собеседованию и попал в FAANG

Можно сказать, что начало этой истории - это неожиданное собеседование в Google в 2015 году, которое я провалил еще на Phone Screen. История об этом тут: История о том, как я провалил собеседование в Google. На тот момент я не имел никакого представления о собеседованиях в FAANG. Были только какие-то домыслы об этом. Leetcode, на тот момент, не был чем-то особо известным. Задач там тоже было очень мало. Когда я готовился к Phone Screen в Google, рекрутер мне посоветовал порешать задачи на topcoder. Он посоветовал мне открыть архив контестов и посмотреть вторые задачи из контестов (среднего уровня сложности, там в каждом контесте по 3 задачи, простая, средняя и сложная). А также посоветовал книгу Cracking The Coding Interview. Т.к. времени на подготовку я взял мало (я не имел никакого представления сколько подготовка у меня займет, чтобы я смог такое собеседование пройти), то успел только выучить основные алгоритмы из книги Cracking The Coding Interview и посмотреть небольшое число задач из книги и topcoder. Собеседование я провалил.
Тогда я загорелся идеей поработать в FAANG или, как минимум, зарубежом. Я понял, что мне не хватило знаний по алгоритмам, навыков решения задач, разговорного английского, чтобы пройти такое собеседование.
Для подтягивания английского я перешел на чтение технической литературы только на английском. А для прокачки разговорного английского - использовал italki (где можно беседовать с носителем языка на любые темы). Грамматику тоже изучал, но не особо интенсивно. Просто использовал книгу (macmillan english grammar in context).
Начал более системного изучать книгу Cracking The Coding Interview. Выучил основные алгоритмы до автоматизма. Мог и до сих пор могу написать ключевые алгоритмы на бумаге без ошибок за 5 минут. Практиковался с решением задач из книги и разбирал решения.
Купил еще несколько книг: Роберт Лафоре Структуры Данных и Алгоритмы, Алгоритмы (Седжвик). Также у меня уже была книга Алгоритмы: построение и анализ (Кормен). Первую из этих книг я изучил очень подробно. Но это было скорее избыточно. Я зачем-то выучил как реализовать по памяти основные операции с красно-черными деревьями, B-tree и много чего другого. Но это оказалось не нужно для собеседования. По факту алгоритмов из Cracking The Coding Interview было достаточно. Кормена и Сэджика я почитал немного, но это было очень сложно, долго и не нужно для собеседования вообще.
Параллельно, я прочитал несколько раз и заботал в деталях Java Concurrency In Practice. Мне это пригодилось на собеседованиях не в FAANG, в том числе в Европе. После года бота, параллельного с работой, я начал откликаться на вакансии в Европе, не в FAANG. Прособеседовался в десяток компаний и получил один офер в Германии. Пораздумав над офером, решил его принять. Офер был не в FAANG компанию, на среднюю для Германии зп для программиста.

После того, как немного адаптировался в немецкой компании, я продолжил решать задачи из Cracking The Coding Interview до состояния, что я мог решить задачи из основных глав книги за 15 минут. Меньше чем через год, я решил податься в Amazon для проверки своей текущей подготовки. Откликнулся на вакансию. Потом короткий созвон с рекрутером. Потом онлайн тест. Задачи мне показались простыми. Я их быстро и правильно решил. Потом меня сразу пригласили на full-loop. Собеседование было в офисе. 4 собеседования по 45 минут. 3 coding + leadership principles и 1 system design + leadership principles. Я на подготовке еще раз повторил задачи из Cracking The Coding Interview, подготовился к собеседованию по leadership principles и посмотрел немного system design. На full loop задачи мне показались сложнее. Но я все 3 решил на доске маркером. 1 я уже видел, благо самую сложную. Две другие я не видел, но сразу понял на какие алгоритмы и стуктуры данных они и мог их легко применить для задачи. System Design для меня был в новинку, поэтому я многое использовал из своего опыта или того что я видел или читал про это. После собеседования, я не был уверен, что я прошел. Но точно знал, что и не провалился на 100%. Еще не зная решения, я считал, что моя подготовка идет хорошо и я себя показал хорошо. Но неожиданно, я получил офер. Также неожиданно для себя я долго думал над офером. Т.к. я не планировал менять работу, а просто хотел себя проверить. А в текущей компании я был не очень долго и нужно было снова переезжать. Но в итоге офер я принял.
В следующих постах опишу как я готовился в Facebook.

Вопрос с собеседования на Java программиста по Spring: Что такое @Autowire в Spring? Как его использовать и как он работает?

Ответ написал тут: Что такое @Autowire в Spring? Как его использовать и как он работает?

Самая популярная задача с собеседования в Google в данный момент: Удалить вершины в дереве и вернуть оставшийся лес/forest

Задача. Дано бинарное дерево. Все значения в вершинах уникальны в рамках всего дерева. Также дан массив значений, которые нужно удалить. Нужно удалить вершины с данными значениями. После удаления этих вершин у нас останутся разъединенные деревья (лес или forest). Нужно вернуть корни оставшихся после удаления деревьев в любом порядке.

Ссылка на leetcode: https://leetcode.com/problems/delete-nodes-and-return-forest/

Решение. Решение описал тут: Задача с собеседования в Google: Удалить вершины в дереве и вернуть оставшийся лес/forest

P.S. Ее смогут решить только тру вертельщики деревьев.

Используют ли в FAANG\Big Tech Spring и Spring Boot?

Начну с того, что его не спрашивают на собеседованиях в FAANG. На собеседовании спрашивают алгоритмические задачи, system design и поведенческие вопросы. На system design может понадобиться знание конкретных баз данных, key-value хранилищ и распределенных кэшей. Знание фреймворков типа Spring вас не будут спрашивать. Я начал публиковать вопросы с собеседований по Spring, потому что меня попросили и их могут спрашивать на собеседовании на Java программиста не в Big Tech компании.

Теперь, что касается использование Spring в Big Tech компаниях. Во-первых, далеко не во всех компаниях сильно используется Java. Например, в Facebook, Java используется, в основном, для мобильной разработки под Android. Для Backend тоже используется, но очень редко. В Microsoft тоже предпочитают C++, C#. В Google Go. Но так или иначе на Java и в этих компаниях что-то пишут.
Среди Big Tech в использовании Java выделяются Amazon и Netflix. Там очень много backend на Java. Я работал в Amazon, поэтому расскажу про него. Мы использовали Java в качестве основного языка для backend части. Но в нашей команде Spring не использовался. Мы использовали внутренние тулы и библиотеки, а также среди сторонних библиотек использовали Google Guice для Dependency Injection и Google Guava для локальных кэшей, коллекций и т.д. Но я видел другие команды в Amazon использовали Spring. Правда, в основном, для Dependency Injection. А не, скажем, Spring Boot. Хотя некоторые вещи я видел и даже сделал с использование Spring Boot. Но это скорее исключение, чем правило.
Такие компании предпочитают иметь большую гибкость и переписать любую библиотеку под себя. Spring кастомизируем, но до определенной степени. Крупные компании чаще предпочитают более легковесные сторонние библиотеки и иметь все рычаги управления над кодом.
В Netflix же - очень много Java и в том числе они используют Spring и Spring Boot. Они также сделали много своих внутренних библиотек open source под Java.

Как я готовился к собеседованию и попал Facebook?

Ранее я описывал, как я готовился и попал в Amazon (Часть 1, Часть 2)

При подготовке я использовал, в основном, Cracking The Coding Interview. Но и читал другие книги по алгоритмам и структурам данных. Leetcode не пользовался вообще.
После того, как я начал работать в Amazon, я перестал решать задачи или читать книги по алгоритмам и систем дизайну. Я больше сосредоточился на адаптации в компании. В первые месяцы из книг я прочитал Clean Code. Что пригодилось мне в работе.
Через месяца 3 работы в компании, со мной связался рекрутер из Facebook. Предложил пройти собеседование. Я немного подумал, т.к. я только пришел в компанию и если бы я прошел сейчас собеседование в Facebook и принял оффер, то мне надо было снова переезжать, а также возвращать деньги амазону, потраченные на переезд. А там тысяч 30 долларов. Но я решил просто попробовать свои силы, и уже по результатам оценивать, принимать мне офер или нет, я ничего не терял от прохождения собеседования.
Рекрутер прислал мне материалы для подготовки. Среди прочего там была ссылка на leetcode. Тогда 7 лет назад я впервые зашел на leetcode и порешал там свои первые задачи. Готовился я не долго к собеседованию и в итоге провалил Phone Screen. Там дали 2 задачи на 15-20 минут каждую. Я их не осилил. Частично решил одну, но вторую - только общую идею. Я не сильно расстроился, но решил через какое-то время попробовать еще раз.
Примерно, через полгода, я снова стал активно решать задачи. Вначале это был leetcode, на котором за ~2 лет я решил ~300 задач. Потом, как только появился algoexpert.io, то я там решил 100 задач и получил сертификат. Прочитал несколько книг по system design, которые я уже рекомендовал в этом канале. Также попробовал поучаствовать в соревнованиях на topcoder. Но это было не долго, может раз 5 участвовал. Особо прогресса это мне не дало.
И после пару лет подготовки, параллельно с работой в Amazon, я подготовился неплохо к собеседованию.
После очередного раза, когда мне написал рекрутер из Facebook, я откликнулся. Потом отправил резюме, быстрый созвон на 15 минут с рекрутером. Потом Phone Screen с двумя задачами на 40 минут в сумме. Их я легко решил. Потом получил приглашение на full loop. Он был все равно online. Тогда уже ковид начался. Я взял месяц на подготовку к full loop. Я еще раз порешал задачи с algoexpert.io и 100 самых популярных задач с leetcode для Facebook. А также прошел курс по system design (https://www.designgurus.io/course/grokking-the-system-design-interview). Его мне прислали в качестве материалов для подготовки сами рекрутеры.
Full loop состоял из 4 собеседований:
1) 2 coding, по 2 задачи каждый
2) 1 system design
3) 1 поведенческое.
Каждое собеседование было по 45 минут. Кодинг я решил очень хорошо. Половину задач я уже просто видел, а половину я видел похожие и решить по аналогии не состовляло труда. Поведенческое тоже прошло хорошо. Я к нему частично подготовился на algoexpert.io, а также заранее продумал примеры из опыта и потренировался их рассказывать. А вот system design прошел сложно. Задача на дизайн была не тривиальной. Придумать дизайн, удовлетворяющий требованиям было очень сложно. Сначала я придумал, что-то из опыта и что-то я читал в курсе по system design. Но это не покрывало основные, ключевые требования. Но в итоге я выкрутился и что-то придумал.
После собеседования и сомневался, что я прошел. Особенно из-за system design. Но в итоге я получил офер, который я принял.

Характерные числовые характеристики, которые нужно знать для System Design собеседования

Оценка требуемых вычислительных ресурсов является неотъемлемой частью System Design собеседования. Это оценка числа требуемых серверов, дискового пространства и пропускной способности сети.
Чтобы сделать такую оценку, нужно представлять характерные параметры современного железа и технологий. Я приведу несколько основных таких характеристик.

Время отклика:
1) Кэш процессора. L1 - 0.9 наносекунд, L2 - 2.8 наносекунд, L3 - 12.9 наносекунд.
2) Обращение к ячейке памяти RAM (RAM access time): ~100 наносекунд.
3) Последовательное чтение 1 MB из RAM(топовая): 9 микросекунд.
4) Последовательное чтение 1MB из SSD (около топовые): 200 микросекунд.
5) Задержка сети в рамках одного дата центра: 0,5 миллисекунды.
6) Последовательное чтение 1MB из SSD (~1 GB/s): 1 миллисекунда.
7) Последовательное чтение 1MB из HDD: 2 миллисекунды.
8) Disk seek (disk access time): 4 миллисекунды.
9) Задержка сети при отправки через интернет с одного континента/страны в другую. ~50-150 миллисекунд.

Throughput на один сервер:
1) MySQL. ~1000 QPS (запросов в секунду)
2) Key-value storage/NoSQL. ~10k QPS
3) Cache server. ~100k -1M QPS.

Типичная спецификация современного сервера:
1) Число ядер: 64.
2) RAM 256 GB
3) Cache L3 112.5 MB
4) Storage 16TB.

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

Например, если у вас приложение запущено на одном сервере, а кэш сервер на другом, но они находятся в рамках одного дата центра, то несмотря на то, что чтение из RAM очень быстрое, вы будете ограничены задержкой сети 2 * ~0.5 = ~1 миллисекунды. А если ваш клиент делает запрос в ваше приложение и у вас нет локальных серверов, а они находятся в другой стране от клиента, то нужно учесть задержку как минимум в 50-200 миллисекунд на roundtrip по сети.

Вопрос с System Design собеседования: Задизайнить Google Maps

Ответ описал тут: Дизайн Google Maps

В ближайшее время дополню его частью про добавление, хранение и использование сегментов графа дорог.

Провел сегодня очередное coding interview, и когда заполнял feedback у нас в системе появилась галочка "подозреваете ли вы кандидата в использовании внешних ресурсов, в качестве подсказок?"
Значит не у меня одного возникают такие чувства. Смотрите также истории, когда я подозревал в использовании chatgpt:
Случай на собеседовании в FAANG

Еще один подозрительный случай на собеседовании

Задача с собеседования: Реализовать потокобезопасную неблокирующую очередь на Java
#java #concurrency

Задача. Реализовать потокобезопасную (Thread Safe) неблокирующую очередь на Java Т.е. нельзя использовать локи или synchonized, при этом она должна корректно работать в многопоточной среде.
Решение. Описал тут: Реализовать потокобезопасную неблокирующую очередь на Java

Смотрите также: Реализовать потокобезопасный неблокирующий стек на Java

К нам стало аплаится большое число сотрудников Google. Видимо узнали про гиганский рост акций. Только, как по мне, надо приходить, когда акции на дне. Чтобы при росте, получить рост полученных акций. Ситуация напоминает ситуацию с биткоином. Когда все покупают по максимальной цене, когда каждый утюг говорит про высокую цену, а потом как акции падают, продают, получая убыток.

Благодаря росту акций я сейчас зарабатываю, больше чем когда либо. Я даже не думал, что могу столько зарабатывать будучу разрабом.
При текущей цене акций это ~$680 000 в год. При этом это в Европе. В США на той же позиции это в в 1.5 раза больше.
Я собеседовал 4 кандидата из Google за последний месяц. Все они хорошо себя показали на технической части (кодинг и систем дизайн), но не все прошли поведенческое собеседование. Поведенческое собеседование в Facebook и Amazon сложнее, чем в Google. Поэтому нужно готовится ко всем видам собесов.
В Facebook проверяется с какими конфликтами вы встречались, как их разрешили, как достигли common ground, как драйвили до получения нужного результата, как взаимодействовали, какой сложности проблемы решали, как задавали direction и т.д.

Мои первые впечатления, когда я начал работать в FAANG

Я уже описывал свои впечатления от начала работы в Европе: Часть 1, Часть 2

1) Сразу же удивил процесс переезда. Когда я переезжал в Европу, то делал это сам. Компания помогала минимально, в основном, только с доками для визы. Amazon же помогал со всем. С доками на визу, с перевозкой мебели в другую страну (они все разобрали, упаковали, перевезли в другую страну, хранили на складе, пока я искал постоянную квартиру, потом все привезли, собрали и разложили вещи). Покупка билетов. На месте дали временную квартиру - это был пентхаус с двумя балконами, джакузи, в центре города, за 5 тысяч евро в месяц. На месте дали русскоговорящего человека, который помог зарегаться на месте, получить все доки. Помощь в поиске квартиры и заключении договора аренды. Плюс еще 13 тысяч дали налом на руки на прочие расходы. Все это за счет компании. Но вы подписываете бумажку, что если вы уйдете раньше, чем через 2 года, то вы обязаны вернуть пропорционально не отработанному времени часть денег. Т.е. если решите уволиться через 1 год - надо вернуть половину. Если же вас увольняют, то обычно можно договориться и ничего не платить.
2) Люксембург мне понравился больше, чем Германия. Почти все говорят на английском, нет сложностей с немецким, как в Германии. Очень красивая страна. Очень тихо и спокойно. Нет напрягов мегаполиса. Но при этом есть вся инфраструктура.
3) Очень хорошо отлажен процесс онбординга. Есть четкий онбординг план, с командой мне также повезло, очень сильно мне помогали.
4) Чувство эйфории от того, что попал в такую компанию и причастности к масштабным проектам. Когда друзья и коллеги узнали, где я работаю, то всегда это вызывало интерес. Даже просто если малознакомые люди узнавали случайно, где я работаю, то сразу начинали интерисоваться.
5) Чувство страха из-за возможного увольнения, денежных обязательств, визовой зависимости. Тут все примерно также как и в прошлой компании, когда я начал работать в Европе. Только ожидания от меня повысились.
6) Я встретил очень крутых инженеров и просто умных людей. Среди коллег были высококлассные инженеры, некоторые из них были очень круты, я у них многому научился. Такого класса программистов я не видел до этого.
7) На первых же код ревью посыпалась тонна комментариев. Мне, казалось, что люди придираются. Но позже мы установили и обсудили стандарты написания кода и я к ним адаптировался. Это заняло время, но это сделало меня лучше.
8) Amazon Leadership Principles это реально используемая вещь на ежедневной основе. Сначала я думал, что это просто какие-то лозунги, чтобы их написать на стене. Но их используют каждый день, к ним апеллируют. Сначала это казалось чем-то вроде религии или секты. Но потом адаптируешься. Но это удается не всем, многие считают это промывкой мозгов и увольняются.
9) Внутренние тулы и постоянно желание предложить использовать какие-то open source тулы и библиотеки. В FAANG почти все написано внутри компании. Поэтому приходится первые месяцы долго и упорно привыкать к новым тулам. И все время возникает желание предложить то, что ты уже использовал до этого, вместо того, что есть в компании.

Зарелизи сегодня meta.ai.
Пока доступно в ограниченном числе стран, поэтому, чтобы попробовать нужен vpn, желательно США. Если вы не в США конечно.
И по инженерной традиции в пятницу перед выходными😀

Задача с собеседования в Google: Минимальная площадь прямоугольника

Задача. Дан массив точек на плоскости. Нужно найти минимальную площадь прямоугольника образованного этими точками, у которого стороны параллельны оси x и y.
Если такого прямоугольника нет - в качестве результата вернуть 0.
Ссылка на leetcode: https://leetcode.com/problems/minimum-area-rectangle/

Решение. Решение описал тут: Задача с собеседования в Google. 939. Minimum Area Rectangle

Еще один случай на собеседовании.
Недавно проводил screen собеседование. Кандидат - 28 лет опыта, в том числе в одной известной компании(не FAANG, но известной в IT индустрии). Правда не весь опыт - разработка, очень много администрирования. На вид 50/60+ лет. Ну т.е. выглядит очень опытным.
Код писал на perl. При этом не знал даже базовый синтаксис. Пытался впечатлить меня знанием, что такое тренарный условный оператор, но неправильно его написал. А про базовые знания, как оперировать с массивом я уже молчу (обьявить массив, получить элемент по индексу). Ссылался, что у него есть книжка и он там может посмотреть, если что.
Задачи он не решил, только какие-то общие соображения, при этом неверные. Также сказал, что алгоритмическая сложность DFS - O(N*logN). На мои подсказки очень агресивно реагировал, отметая их как неверные рассуждения. А в конце добило, когда он заявил, что ну вроде он себя хорошо проявил на собеседовании. Не понимаю, если вы знаете правила игры(собеседования) и вы категорически против такого рода собеседований, то зачем на них ходить.

Текущие офферы в некоторые Big Tech/FAANG компании

Взял несколько основных компаний и первые три уровня (junior, mid, senior) из 6-7 (Staff+ не указывал). Сотрудники, которые работают какое-то время внутри компании на тех же позициях обычно получают больше из-за роста акций и своего перфоманса.
Компенсации приведены в долларах в год до налогов в офисах США. В европейский офисах в зависимости от локации числа в 1.5-2 раза ниже (исключение - Швейцария, где такие же компенсации как в США, для Лондона числа где-то в 1.5 раза ниже).

Microsoft: $168 000/$209 000/$274 000
Uber: $164 000/$272 000/$484 000
Apple: $152 000/$222 000/$344 000
Amazon: $182 000/$287 000/$413 000
Google: $185 000/$284 000/$389 000
Facebook: $193 000/$309 000/$504 000

Нарисовал типичную структуру FAANG/Big Tech компании с должностями и зарплатами. Зеленым отметил инженерные позиции.