FAANG Master

В тему недавнего outage Cloudflare

Задача с собеседования в Google

Задача. Дан массив целых чисел. Значения могут быть только 0, 1 и 2. Нужно отсортировать на месте (без доп. памяти). Использовать библиотечные функции сортировки нельзя.

Например,

Input: nums = [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]

Input: nums = [2,0,1]
Output: [0,1,2]

Ссылка на leetcode: https://leetcode.com/problems/sort-colors

Решение.

Решение разобрал тут: Задача с собеседования в Google: Sort Colors

Код решения:

public void sortColors(int[] nums) {
    int left = 0;
    int right = nums.length - 1;
    int current = 0;
    while (current <= right) {
        if (nums[current] == 0) {
            swap(nums, left, current);
            left++;
            current++;
        } else if (nums[current] == 1) {
            current++;
        } else {
            swap(nums, current, right);
            right--;
        }
    }
}

private void swap(int nums[], int i, int j) {
    int tmp = nums[i];
    nums[i] = nums[j];
    nums[j] = tmp;
}

Простой вопрос с собеседования по Java

Что не так с кодом:

static int value = 1;
static final Object obj = new Object();

// поток 1
....
synchronized (obj) {
value++;
}
....

// поток 2
.....
int x = value;
....

Ответ.
Переменная не volatile, но ее изменение происходит в synchronized-блоке. Это гарантирует атомарность и видимость изменения только по отношению к потокам, которые читают в synchronized-блоке на том же мониторе (Смотри Вопрос с собеседования: что такое Java Memory Model и happens-before и Atomicity and Visibility). В соответствии с Java Memory Model, факт выхода из synchronized (obj) создаёт happens-before только по отношению к другим участкам кода, которые тоже синхронизируются на том же мониторе (obj). Поэтому для обеспечения видимости и атомарности нужно чтение поместить также в synchronized-блок на том же мониторе:

static int value = 1;
static final Object obj = new Object();

// поток 1
synchronized (obj) {
    value++;
}

// поток 2
int x;
synchronized (obj) {
    x = value;
}

В качестве альтернативы можно использовать AtomicInteger:

static final AtomicInteger value = new AtomicInteger(1);

// поток 1
value.incrementAndGet();

// поток 2
int x = value.get();

Добавление volatile в переменную обеспечит только видимость, но не атомарность операции. В данном случае у нас пишет только один поток и переменная 32-битная - поэтому эта проблема может быть не столь критичной, мы не прочитаем какое-то кривое значение, оно просто может быть не самым актуальным, если мы будем читать во время инкремента. Но если у нас будут писать уже несколько потоков, то это будет реальной проблемой, могут быть утеряны некоторые изменения. Поэтому фиксить эту проблему просто добавлением volatile - не лучшее решение.

Смотри также:
1) Разобрал 32 вопроса и задачи по Java и Многопоточность
2) Вопрос с собеседования: что такое Java Memory Model и happens-before
3) Atomicity and Visibility

В Мета на перфоманс ревью будут оценивать AI-driven impact

Со следующего года в PSC(перфоманс ревью в Мета) будет введена новая ось: AI-driven impact. На текущий момент, перфоманс оценивается по 4 осям: Project Impact, Engineering Excellence, Direction, People.
До этого, Мета уже запустила эксперимент, по использыванию AI на собеседовании: Начиная с 30 сентября Мета запускает пилот по использованию AI во время интервью

Уровень абсурда нарастает.

JS живет по своим правилам

Интересное интервью с Distinguished разработчиком из Facebook

С 1997 до 2010 работал в Microsoft. C 2010 до 2018 в Facebook и дорос до уровня E9 (Distinguished). Текущие компенсации для этого уровня в Meta - $3.3M в год (266 миллионов рублей в год). Таких людей в Meta ~100. После Меты работал в OpenAI, создал несколько компаний и преподает в Университете Вашингтона.

Его линкедин: Philip Su

Интервью: https://www.youtube.com/watch?v=v2JxdjTi_1I

Задача с собеседования в Google: Russian Doll Envelopes

Задача. Дан двумерный массив envelopes, где envelopes[i] = [wᵢ, hᵢ] — ширина и высота i-го конверта.
Один конверт может быть вложен в другой, если его ширина и высота строго меньше ширины и высоты другого конверта.

Требуется найти максимальное число конвертов, которые можно вложить друг в друга.

Например,
envelopes = [[5,4],[6,4],[6,7],[2,3]]

Output: 3.
Можно вложить максимум 3 конверта друг в друга: [2,3] => [5,4] => [6,7]

Input: envelopes = [[1,1],[1,1],[1,1]]
Output: 1
По условию, конверты, одинаковые хотя бы по одному измерению, нельзя вкладывать друг в друга.

Ссылка на leetcode: https://leetcode.com/problems/russian-doll-envelopes/description/

Решение.
Решение разобрал тут: Задача с собеседования в Google: Russian Doll Envelopes

Код решения:

Вариант 1. Динамическое программирование.

public int maxEnvelopes(int[][] envelopes) {
    Arrays.sort(envelopes, (a, b) -> {
        if (a[0] == b[0]) {
            return Integer.compare(a[1], b[1]);    
        }
        return Integer.compare(a[0], b[0]);
    });

    int[] dp = new int[envelopes.length];
    Arrays.fill(dp, 1);

    int result = 1;

    for (int i = 0; i < envelopes.length; i++) {
        for (int j = 0; j < i; j++) {
            if (envelopes[j][0] < envelopes[i][0] && envelopes[j][1] < envelopes[i][1]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
        result = Math.max(result, dp[i]);
    }

    return result;
}

Вариант 2. Бинарный поиск.

public int maxEnvelopes(int[][] envelopes) {
    Arrays.sort(envelopes, (a, b) -> {
        if (a[0] == b[0]) {
            return Integer.compare(b[1], a[1]);
        } else {
            return Integer.compare(a[0], b[0]);
        }
    });

    int[] tails = new int[envelopes.length];
    int size = 0;

    for (int i = 0; i < envelopes.length; i++) {
        int h = envelopes[i][1];

        int left = 0, right = size;
        while (left < right) {
            int mid = (left + right) >>> 1;
            if (tails[mid] < h) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }

        tails[left] = h;
        if (left == size) {
            size++;
        }
    }

    return size;
}

Текущие стартовые оферы для Staff программистов в FAANG/BigTech

Текущие оферы для Staff Software Engineer (~уровень тех лида, обычно 10+ лет опыта):

1) OpenAI: $1.2M/96.8 миллионов рублей в год.
2) Facebook: $804k/64.8 миллионов рублей в год.
3) Two Sigma: $800k/64.5 миллионов рублей в год.
4) Uber: $631k/50.9 миллионов рублей в год.
5) Airbnb: $593k/47.8 миллиона рублей в год.
6) Google: $569k/45.9 миллионов рублей в год.
7) Robinhood: $558k/45 миллионов рублей в год.
8) Hudson River Trading: $531k/42.8 миллиона рублей в год.
9) Apple: $481k/38.8 миллионов рублей в год.
10) Lyft: $472k/38 миллиона рублей в год.
11) Microsoft: $407k/32.8 миллиона рублей в год.
12) Amazon: $390k/31.4 миллионов рублей в год.

Оферы стартовые в США. В Швейцарии оферы примерно такие же как в США. В Европе и Великобритании в 1.5-2 раза меньше.

Смотри также:
1) Как подготовиться к собеседованию в FAANG/Big Tech
2) Текущие стартовые оферы для Junior программистов в FAANG/BigTech

Задача с System Design Interview: Design Google Docs

Разобрал задачу с System Design Interview: Design Google Docs и выложил на свой youtube-канал: https://youtu.be/Bas7i0dV_cY?si=kdtp1GhbhTQqntRa

Можно смотреть на 1.5x, говорю медленно.

Смотри также:
1) Разобрал 26 тем и 7 реальных задач с System Design собеседований в FAANG
2) Видео: Design a URL Shortening Service

В Москве прошла презентация первого российского антропоморфного робота с искусственным интеллектом Aidol.
Видимо пить он уже умеет.

Текущие стартовые оферы для Junior программистов в FAANG/BigTech

Текущие оферы для fresh graduate (выпускников без опыта):

1) Hudson River Trading: $395k/32 миллиона рублей в год.
2) Two Sigma: $249k/20.1 миллионов рублей в год.
3) OpenAI: $242k/19.5 миллионов рублей в год.
4) Robinhood: $201k/16.2 миллионов рублей в год.
5) The Trade Desk: $192k/15.5 миллионов рублей в год.
6) Uber: $188k/15.2 миллионов рублей в год.
7) Lyft: $186k/15 миллионов рублей в год.
8) Airbnb: $184k/14.8 миллионов рублей в год.
9) Google: $182k/14.7 миллионов рублей в год.
10) Amazon: $181k/14.6 миллионов рублей в год.
11) Facebook: $172k/13.9 миллионов рублей в год.
12) Apple: $171k/13.8 миллионов рублей в год.
13) Microsoft: $162k/13.1 миллионов рублей в год.

Оферы стартовые в США. В Швейцарии оферы примерно такие же как в США. В Европе и Великобритании в 1.5-2 раза меньше.

Несмотря на то, что в некоторые компании стартовые оферы меньше, но из-за рефрешеров (Facebook и Google) компенсация может очень быстро вырасти в разы.
В компаниях, вроде Hudson River Trading или Two Sigma платят кэшем. Поэтому на одном и том же уровне зп не сильно будет меняться.

Типичный возраст людей на этой позиции - 22-24 года.

Кому имеет смысл аплаится на Junior позицию в такие компании?
Выпускникам хороших/топовых вузов + прошедших стажировку в хорошей топовой компании. Это не обязательно вузы и компании из США или Европы, это могут быть топовые вузы и компании вашей страны.
Если вы еще студент, то имеет смысл подаваться на стажировку. Стажировки есть на 3 и 6 месяцев. У меня были интерны, в том числе из стран СНГ(много из Казахстана почему-то), и в Амазоне и в Facebook'е.

Если вы не заканчивали топовый вуз, то имеет смысл сначала получить опыт в других компаниях(лучше около топовых) вашей страны и подаваться уже имея опыт на более высокие позиции - Middle+ (E4+/L4+).

Смотри также:
1) Почему сотрудники Google и Meta получают на порядок больше, чем в Amazon?
2) В чем преимущество получения части компенсации в виде акций публичных компаний?
3) Сколько денег заработает средний Senior разработчик в Meta за 4 года в Лондоне?
4) Обновление рейтинга по стартовым оферам
5) Рейтинг топ компаний по отзывам сотрудников, без учета компенсаций
6) Диаграмма компаний

Yann LeCun уходит из Meta

Yann LeCun — крестный отец deep learning. Лауреат премии Тьюринга, Chief AI Scientist в Meta.
Он уходит из Meta и планирует создать свой стартап.

Думаю, это связано с последними изменениями в стратегии Meta по AI (создание MSL и TBD), покупкой Scale AI, наймом людей за сотни миллионов и миллиарды долларов с тремя годами опыта, задвиганием его на второстепенные роли и неверием в LLM в целом.


Смотри также:
1) LLM vs программисты
2) Meta понизила в должности Yann LeCun
3) Мета перенаправляет все ресурсы в AI
4) Почему sign-on бонусы в $100M это не очень большие деньги для компании
5) Meta наняла еще одного разраба за более чем $200M
6) Среди нанятых в Meta за десятки или сотни миллионов долларов, есть выпускник МГУ и бывший сотрудник Яндекса
7) Список новых сотрудников Мета в Super Intelligence Lab
8) Мета строит два новых AI дата-центра стоимостью с сотни миллиардов долларов
9) Мета наняла еще одного 24 летнего разраба за $250M
10) Hiring freeze в Meta AI Superintelligence lab и реорги
11) Почему Meta купила 49% Scale AI за $14B?
12) Несколько человек уже уволились из нового подразлеления Меты через месяц работы
13) Начиная с 30 сентября Мета запускает пилот по использованию AI во время интервью

Интервью с James Gosling

Это создатель языка Java.

Во время, когда я работал в Амазоне, он тоже работал в Амазоне на позиции Distinguished программиста. Текущие оферы на позицию Distinguished программистов в Амазон - $1.6M в год.

Его линкедин: James Gosling

Интервью: https://youtu.be/IT__Nrr3PNI

Это главы Nvidia, Samsung и Hundai встретились для обсуждения возможной коллаборации. Встречались в обычном кафе/фастфуде с пивом и крылышками.

Atomicity and Visibility

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

Visibility.
Visibility это гарантия, что изменения, сделанные одним потоком, станут наблюдаемы другим. Без специальных гарантий поток может видеть устаревшие значения из кэша/регистров или из-за переупорядочивания операций. Visibility гарантируют отношения happens-before из Java Memory Model.

Давайте посмотрим на конкретные примеры.

1) Есть статическая переменная static int val;
она записывается и читается в двух потоках.
Например,
Поток1:

...
val = 11111111;
....
System.out.println(val);

Поток2:

...
val = 99999999;
....
System.out.println(val);

Есть ли какие-то проблемы с этим кодом? Если есть, то какие? Как улучшить? Какие значения могут быть напечатаны на экран?

Ответы Запись 32-битной переменной (например int) является атомарной операцией. Поэтому потоки могут видеть только три возможных значения: 0 (начальное), 11111111 или 99999999. Но атомарность не гарантирует видимость (visibility). Поэтому если переменная пишется и читается в двух потоках, ее следует сделать видимой. Иначе потоки могут видеть устаревшие значения. Чтобы переменную сделать видимой, можно использовать ключевое слово - volatile. Т.е. можно добавить в объявление переменной: static volatile int val. Есть и другие способы добиться видимости, например, добавить synchronized блоки для записи и для чтения переменной. Они тоже будут гарантировать visibility в соответствии с happens-before отношениями из JMM.

2) Есть статическая переменная static long val;
она записывается и читается в двух потоках.
Например,
Поток1:

...
val = 1111111111111111L;
....
System.out.println(val);

Поток2:

...
val = 9999999999999999L;
....
System.out.println(val);

Есть ли какие-то проблемы с этим кодом? Если есть, то какие? Как улучшить? Какие значения могут быть напечатаны на экран?

Ответы. Этот пример отличается от первого только тем, что тут переменная 64-битная. Спецификация Java допускает, что 64-битные операции могут быть не атомарными. Т.е. запись переменной может состоять из двух операций: запись старших 8 байт и младших 8 байт. При этом промежуточные состояния могут стать видимыми для других потоков. Т.е. потоки могут видеть не только три возможных значения переменной, но и другие комбинации промежуточных состояний. Например, когда первый поток запишет младшие 8 байт, а второй поток 8 старших байт, будет какая-то смесь из двух чисел в одной переменной. На современных JVM и современных операционных системах атомарность будет соблюдаться и для 64-битных операций. Но по спецификации это не гарантированно. Поэтому тут не соблюдается ни атомарность, ни видимость. Добавление volatile в данном случае будет гарантировать не только видимость, но и атомарность: static volatile long val;

3) Есть статическая переменная static int val;

В двух потоках делают инкремент переменной val:

val++;

Есть ли какие-то проблемы с этим кодом? Если есть, то какие? Как улучшить?

Ответы. Инкремент не является атомарной операцией. Поэтому потоки будут видеть промежуточные значения и некоторые инкременты будут утеряны. Например, оба потока могут прочитать значение 0, увеличить до 1 и записать оба 1. При этом по факту было две операции инкремента, просто в разных потоках, а значение стало 1, а не 2. Добавление volatile не сделает операцию атомарной. В общем случае volatile будет гарантировать только видимость, но не атомарность. Для исправления можно использовать AtomicInteger val или synchronized блоки.

AtomicInteger val = new AtomicInteger();
....
val.incrementAndGet();
....
val.get();

Какие технологии использует Facebook?

Я уже писал тут, что в FAANG-компаниях очень много внутренних тулов и технологий, разработанных внутри компании. Часть из них становятся открытыми, часть нет.

Пройдусь по основному стеку, который используется в Facebook:

1) Frontend: ReactJS. Разработан внутри компании, был изначально внутренней технологией, после стал open-source. Очень популярный.
2) Frontend <-> Backend Communication: GraphQL. Изначально был внутренней технологией, потом стал open-source. Достаточно популярный.
3) Backend: hacklang. Разработан внутри компании для замены php. Имеет собственную виртуальную машину hhvm. Похож на Java и другие языки.
4) ORM: Ent Framework. Для работы с базой через кэш, разработали свой ORM-framework. Чисто внутренний, не открытый.
5) Кэш: TAO. Внутренний, закрытый. Обрабатывает миллиарды запросов к базе данных в секунду. Сделан поверх Memcached.
6) Реляционная база: MySQL + своя кастомизация для партиционирования/шардирования, работы в распределенной среде. Внутренняя, закрытая.
7) Логирование аналитических данных: Свой фреймворк для логирования, который пишет в собственный аналог Kafka, который называется - Scribe. Данные из Scribe после попадают в Scuba и/или Hive для хранения, анализа и могут скармливаться другим компонентам, в том числе Machine Learning моделям.
8) Streams: Scribe. Упомянул в предыдущем пункте, так как часто используется для логирования BigData для анализа и ML. Это внутренний аналог Kafka.
9) Data Warehouse: Hive. Изначально был разработан внутри компании, сейчас open-source. Туда стекаются гигантские объемы данных для анализа, ML, использование другими компонентами и т.д.
10) Key-value DB: RocksDB. Изначально разработанная внутри компании, сейчас open-source. Типичный use-case - данные из Hive проиндексировать и хранить в RocksDB для быстрого доступа. Т.к. запросы по Hive работают очень долго.
12) SQL Engine: Presto. Изначально разработан внутри компании, сейчас open-source. Часто применяется для запросов в Hive.
13) Мониторинг: весь внутренний, закрытый. Метрики, логи - все внутреннее. Как по мне, хуже, чем в Amazon.
14) ML Training: FBLearner. Внутренний.
15) RPC: Thrift. Разработан внутри, сейчас open-source.
16) ML: Pytorch. Разработан внутри, сейчас open-source.
17) Blob Storage: внутренний, закрытый. Используется для хранения видео и картинок.


В Мета куча других внутренних тулов и технологий: для дашбордов, ML, отладки запросов, код ревью, ETL и т.д.

Смотри также:
1) Некоторые подходы к архитектуре приложений в Amazon
2) Какие AWS сервисы мы часто использовали, когда я работал в Amazon?
3) Какие базы данных используются в FAANG?

Индекс по каналу

Кто я: я программист с ~18 годами опыта работы в IT. Из них 8 лет я проработал в двух FAANG-компаниях (Amazon, Facebook/Meta). Есть опыт жизни и работы в 4 странах (Россия, Германия, Люксембург, Великобритания). Из языков программирования лучше всего знаю Java. Провел более 100 собеседований в FAANG компании.
Закончил МФТИ. Там же вел семинары по информатике.

Про что я пишу: Разбираю задачи с собеседования по Java (включая многопоточность), задачи с собеседования в FAANG по алгоритмам и System Design. Пишу про то как работают процессы в FAANG-компаниях, про культуру инжиниринга, уровни и личный опыт работы в них. Пишу про релокацию, работу в Европе, работу в FAANG, собеседования в FAANG и много другое.

Мои статьи https://dev.to/faangmaster
Мой youtube: https://www.youtube.com/@faangmaster
Мой patreon: https://www.patreon.com/c/FAANGMaster
Мой boosty: https://boosty.to/faangmaster

Подборки постов:

Гайды:
1) Гайд по подготовке к собеседованию в FAANG: Как подготовиться к собеседованию в FAANG/Big Tech
2) Подготовка к System Design с нуля и для разных уровней
3) Как устроено System Design Interview в FAANG?
4) С чего начать изучать алгоритмы с полного нуля в 2025?
5) Какие ресурсы использовать для подготовки к алгосам в 2025?
6) Как выбрать язык программирования для алгоритмического собеседования?
7) Как решать алгоритмические задачи на подготовке, чтобы это было эффективно, часть 2.
8) Как решать алгоритмические задачи так, чтобы не забывать решение
9) Шпаргалка по основным алгоритмам для алгоритмического собеседования
10) Шпаргалка по Java для алгоритмического собеседования
11) Сбалансированная подборка из 100 задач для подготовки к алгоритмическому собеседованию.

Разборы алгоритмов, концепций и задач по Алгоритмам, System Design и Java:
1) Разобрал 26 тем и 7 реальных задач с System Design собеседований в FAANG
2) Разобрал все основные алгоритмы и 47 задач с собеседований на алгоритмы в FAANG
3) Разобрал 32 вопроса и задачи по Java и Многопоточность

Уроки по Алгоритмам и System Design:
1) Уроки по Алгоритмам и System Design

Другие большие подборки постов в канале:
1) Подборка постов в канале с рекомендациями по подготовке к собеседованию
2) Подборка постов в канале о работе в FAANG
3) Подборка книг для Java программиста
4) Ресурсы для подготовки к собеседованию по алгоритмам
5) Подборка постов в канале со случаями на собеседованиях
6) Подборка постов в канале про релокацию, жизнь и работу в Европе
7) Подборка постов в канале про онбординг, уровни и прочее
8) LLM vs программисты