Как я готовился к собеседованию и попал 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 компании с должностями и зарплатами. Зеленым отметил инженерные позиции.

Подборка алгоритмических задач с решениями и описание алгоритмов уже опубликованных в этом канале
#interview #собеседование #алгоритмы #подборка

Обновление подборки.

Общие статьи:
1) Как выбрать язык программирования для алгоритмического собеседования?
2) Как решать алгоритмические задачи на подготовке, чтобы это было эффективно
3) Как не забыть решения задач и алгоритмы
4) Шпаргалка по основным алгоритмам для алгоритмического собеседования
5) Шпаргалка по Java для алгоритмического собеседования
6) Подборка из easy задач для начала подготовки к алгоритмическому собеседованию.
7) Сбалансированная подборка из 100 задач для подготовки к алгоритмическому собеседованию.

Two Pointers:
1) Проверка на палиндром.
2) Усложненная версия проверки на палиндром.
3) Merge Two Sorted Arrays
4) Самая длинная палиндромная подстрока
5) Удалить дубликаты в отсортированном массиве
6) Видео: Merge Intervals
HashTable:
7) Two Sum
8) Видео: Сгруппировать анаграммы
9) Задача с собеседования в Google. 939. Minimum Area Rectangle
Stack:
10) Проверить скобочное выражение.
11) Удалить минимальное число скобок, чтобы сделать скобочное выражение правильным
Sorting:
12) Первый пропущенный положительный элемент массива
LinkedList:
13) Удалить n-й элемент с конца в односвязном списке
14) Deep Copy списка со ссылкой на случайный элемент.
BinarySearch:
Описание алгоритма BinarySearch.
15) Пропущенный элемент в отсортированном массиве.
16) Пиковый элемент.
17) Число итераций в бинарном поиске.
18) Первая плохая версия
DFS:
Описание алгоритма DFS.
19) Flood Fill.
20) Видео: Число Островов
BFS:
Описание алгоритма BFS.
21) Проверить полноту дерева.
22) Обход дерева по уровням.
23) Remove Invalid Parentheses
Топологическая сортировка:
Топологическая сортировка
24) Видео: Top k elements
Binary Tree:
Алгоритмы обхода двоичного дерева
25) Invert Binary Tree
26) BranchSums
27) Максимальная высота дерева
28) Максимальная сумма пути в бинарном дереве
29) Сумма элементов бинарного дерева поиска в диапазоне значение
30) Удалить вершины в дереве и вернуть оставшийся лес/forest
Dynamic Programming:
Основные этапы решения задач на динамическое программирование Top-Down методом
31) Top Down подход на примере задачи про ступеньки
32) Задача на динамическое программирование. Разделение на слова.
33) Количество дождевой воды
34) Bottom-up подход: разменять деньги
35) Видео: Longest Increasing Subsequence
36) Лучшее время для покупки и продажи акции

Подборка статей, которые я уже написал и опубликовал в этом канале по system design
#systemdesign

Обновление подборки

1) Load Balancers 1
2) Load Balancers 2
3) Load Balancers 3
4) Consistent Hashing
5) Data Partitioning/Sharding
6) Design Web Crawler
7) Дизайн Uber/Яндекс Такси
8) Дизайн новостной ленты соцсети типа Twitter или Facebook
9) Availability
10) Consistency
11) Дизайн мессенджера Telegram
12) Обработка ошибок при вызове другой компоненты
13) Распределенный кэш. Часть 1.
14) Распределенный кэш. Часть 2.
15) Распределенный кэш. Часть 3.
16) Характерные числовые характеристики, которые нужно знать для System Design собеседования
17) Дизайн Google Maps

Подборка вопросов и ответов для подготовки к собеседованию на Java программиста
#java #interview #собеседование

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

Общие вопросы:
1) Методы класса Object
2) Иерархия и типы исключений
3) GC
4) Сравнение строк в Java

Коллекции:
5) HashMap
6) ArrayList vs LinkedList
7) Иерархия коллекций в Java
8) Иерархия Map
9) Maximum ArraySize

Многопоточность:
10) Перевод между банковскими аккаунтами (dead-lock).
11) Ping-Pong (wait-notify).
12) Приостанавливаемый поток.
13) Подборка вопросов по многопоточности
14) Напечатать последовательность чисел при помощи нескольких потоков на Java.
15) ConcurrentModificationException
16) Thread Safe Singleton
17) Обедающие философы
18) Реализовать потокобезопасную блокирующую очередь на Java ограниченного размера
19) Реализовать потокобезопасный неблокирующий стек на Java
20) Daemon потоки
21) Является ли immutable class в Java Thread safe?
22) Implicit Lock Reentrancy
23) Java Memory Model и happens-before
24) ConcurrentHashMap vs Collections.synchronizedMap vs Hashtable vs HashMap
25) Реализовать потокобезопасную неблокирующую очередь на Java

SQL:
26) Типы SQL joins
27) Плюсы и минусы индексов

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

Zuck про недавний релиз meta.ai и llama3
https://youtu.be/bc6uFV9CJGg

И директор по продукту рассказывает как тренировали llama3:
https://youtu.be/r3DC_gjFCSA

Вопрос с собеседования на Java программиста: Как выполнить код в отдельном потоке в Java?

Ответ на этот вопрос описал тут: Как выполнить код в отдельном потоке в Java?

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

С будущих статьях также расскажу про CompletableFuture и виртуальные потоки.

Нужна ли сертификация Java программисту?

Краткий ответ - нет.
Раньше были официальные сертификаты от Sun. После поглащения Sun Oracle'ом эти сертификаты теперь есть от Oracle. Их несколько разных наименований, вроде Oracle Certified Associate Java Programmer и тому подобное.
На начальных этапах карьеры, я думал, что их нужно обязательно сдать. И даже купил литературу. Но выяснилось, что их нигде не требуют, и за 17 лет работы у меня их никто не спросил. Более того, я не знаю никого, кто бы их получил. Вопросы там не совпадают с теми, что спрашивают на реальных собеседованиях. Они, в основном, на редкие и тонкие места в синтаксисе. Стать хорошим программистом или научиться проходить собеседования они вам не помогут, а при найме их никто не спрашивает. Поэтому это достаточно бесполезная трата времени и денег.
Но если у вас куча времени и вы хотите заботать тонкие детали и аспекты синтаксиса, то можете заняться получением подобных сертификатов.
Из сертификатов, более полезным, я бы назвал сертификаты по AWS. Но их тоже не спрашивают при найме в Amazon или FAANG. Но они могут пригодиться при найме на позиции не в FAANG, где активно используют AWS, особенно, если ваша позиция Architect или хотя бы Senior.