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

Задача

Дан целочисленный массив nums. Вначале мы находимся на первом индексе массива, и каждое значение в массиве представляет максимальную длину прыжка с этой позиции.

Нужно вернуть true, если мы можем достичь последний индекс, иначе false.

Пример 1:

nums = [2,3,1,1,4]
Результат: true
Прыжок на 1 шаг с индекса 0 до 1, затем прыжок на 3 шага до последнего индекса.

Пример 2:

nums = [3,2,1,0,4]
Результат: false
Вы всегда окажетесь на индексе 3, независимо от выбора. Максимальная длина прыжка на этом индексе — 0, что делает невозможным достижение последнего индекса.

Ссылка на leetcode: https://leetcode.com/problems/jump-game

Решение

Решение описал тут: Jump Game

Код решения:

public boolean canJump(int[] nums) {
 int goal = nums.length - 1;
 for (int i = nums.length - 2; i >= 0; i--) {
  if (i + nums[i] >= goal) {
   goal = i;
  }
 }
 return goal == 0;
}

Смотри также разбор 44 других типичных алгоритмических задач в FAANG: https://t.me/faangmaster/648

ИИ скоро нас всех заменит. ChatGPT o3 модель превосходит всех в своих размышлениях.

Утечки всех промптов, крупнейших AI стартапов

Продукты, вроде Cursor (AI среда разработки), Devin (AI программист) и им подобные - это просто враперы поверх LLM. Они делают вызовы через API к LLM моделям вроде Claude, ChatGPT и т.д. Т.е. их интеллектуальная собственность - это просто промпты, которые они отправляют.

Стоимость, таких компаний достигает десятков миллиардов долларов.

Вот утечки всех промптов, которыми владеют эти компании: https://github.com/x1xhlol/system-prompts-and-models-of-ai-tools/tree/main

Например, Devin: https://github.com/x1xhlol/system-prompts-and-models-of-ai-tools/blob/main/Devin%20AI/Prompt.txt

Все таки есть польза от современных нейронок. Можно мемасы генерить.

Врываемся в FAANG из деревни

Собеседовал сегодня кандидата из России

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

Мета перенаправляет все ресурсы в AI

На следующей неделе начнется очередное перформанс ревью. Планируют 20% компании пометить как BE (Below Expectation) и возможно уволить из компании.
С учетом покупки Scale AI за $14B, слухов про оферы в $100M текущим сотрудникам Open AI, все кто не работает над AI под угрозой...

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

Кто я: я программист с ~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) Разобрал 24 темы и реальных задач с System Design собеседований в FAANG
4) Разобрал все основные алгоритмы и 44 задачи с собеседований на алгоритмы в FAANG
5) Разобрал 30 вопросов и задач по Java и Многопоточность

6) Подборка постов в канале с рекомендациями по подготовке к собеседованию
7) Подборка постов в канале о работе в FAANG
8) Подборка книг для Java программиста
9) Ресурсы для подготовки к собеседованию по алгоритмам
10) Подборка постов в канале со случаями на собеседованиях
11) Подборка постов в канале про релокацию, жизнь и работу в Европе
12) Подборка постов в канале про онбординг, уровни, LLM vs программист и прочее

С чего начать изучать алгоритмы с полного нуля в 2025?

Эта рекомендация для тех, кто ещё ни разу не изучал алгоритмы и структуры данных.

Я бы рекомендовал начать с книги:

1) Grokking Algorithms by Aditya Bhargava (Грокаем алгоритмы, Бхаргава Адитья). Можно даже не покупать, в интернете гуглится pdf. Если нацелены на FAANG, то рекомендую сразу читать в оригинале на английском (как и всю другую техническую литературу). Книга рассказывает все очень понятно и на пальцах. Топовым олимпиадником она вас не сделает, но плавно вкатиться поможет.

Читать сразу книги:
Алгоритмы, Седжвик Роберт
Алгоритмы: построение и анализ, Томас Кормен; Чарльз Лейзерсон; Рональд Ривест; Клиффорд Штайн
Искусство программирования, Кнут

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

Далее можно изучить введение в несколько глав из книги
2) Cracking the Coding Interview by Gayle Laakmann Mcdowell:

1) Chapter 1. Arrays and Strings
2) Chapter 2. Linked Lists.
3) Chapter 3. Stacks and Queues.
4) Chapter 4. Trees and Graphs.
5) Chapter 8. Recursion and Dynamic Programming
6) Chapter 10. Sorting and Searching

В начале каждой главы есть описание ключевого алгоритма для решения задач на данную тему. Это 2-3 странички. Изучите очень детально алгоритмы из 6 введений до такой степени, что сможете спокойно в любой момент на листочке выписать алгоритмы из этих 6 глав без подсказок и их рассказать другу.

Мира Мурати - ex-CTO Open AI в феврале 2025 основала свою компанию Thinking Machines Lab.
Сразу получила посевных инвестиций(посевных Карл) на $2B с оценкой стоимости компании в $10B. На данный момент у нее нет никакого продукта или даже прототипа. Просто слоган компании.

Краткая биография:
36 лет, родилась в Албании. В 16 переехала в Канаду. Получила бакалавра по искусству и в 2013 бакалавра инжинерии.
В 2013 начала работать в Tesla на позиции PMа.
В 2016-2018 работала в стартапе Leap Motion.
В 2018(в возрасте 30 лет и 5 годах опыта работы) пришла в Open AI на позицию VP (через 3 года после основания Open AI).
Вскорее стала CTO в Open AI.

В 2024 уволилась из Open AI, чтобы основать свою компанию.

Нет ли у вас чувства нарастающего пузыря в AI?

Какие ресурсы использовать для подготовки к алгосам в 2025?

Начальный уровень
Смотри пост, с чего можно начать тут (там я рекомендую 2 книги и конкретные главы): С чего начать изучать алгоритмы с полного нуля в 2025?

По сути, это книги:
1) Grokking Algorithms by Aditya Bhargava (Грокаем алгоритмы, Бхаргава Адитья)
2) Cracking the Coding Interview by Gayle Laakmann Mcdowell

Изучаем введение в эти 6 глав и выучиваем реализации основных алгоритмов:

1) Chapter 1. Arrays and Strings
2) Chapter 2. Linked Lists.
3) Chapter 3. Stacks and Queues.
4) Chapter 4. Trees and Graphs.
5) Chapter 8. Recursion and Dynamic Programming
6) Chapter 10. Sorting and Searching
3) Смотри мои посты тут: Подборка алгоритмических задач с решениями и описание алгоритмов уже опубликованных в этом канале

Средний уровень

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

Это можно сделать на одном из/нескольких ресурсах:

1) hellointerview: https://www.hellointerview.com/learn/code - Бесплатно
2) algoexpert: https://www.algoexpert.io/questions - Платно, но на каждую задачу там большой и подробный видео разбор. Не обязательно решать все 200. Главное затронуть каждую тему, а при желании можно сосредоточиться на какой-то конкретной теме для прокачки. Там я прокачивал задачи на деревья и графы, а также динамическое программирование.
3) neetcode: https://neetcode.io/roadmap - Бесплатно, но есть и платный расширенный набор задач.
4) Курс на educative - Grokking the Coding Interview Patterns.
5) Смотри мои посты тут: Подборка алгоритмических задач с решениями и описание алгоритмов уже опубликованных в этом канале
6) Решаем задачи из книги Cracking the Coding Interview by Gayle Laakmann Mcdowell из глав:
1) Chapter 1. Arrays and Strings
2) Chapter 2. Linked Lists.
3) Chapter 3. Stacks and Queues.
4) Chapter 4. Trees and Graphs.
5) Chapter 8. Recursion and Dynamic Programming
6) Chapter 10. Sorting and Searching
7) Chapter 16. Moderate
Там подробные разборы решений в текстовом виде. Правда некоторые задачи немного устарели. В 2025 возможно не самый лучший вариант.

Продвинутый уровень

1) Leetcode. Решаем задачи также по основным темам. Вначале решаем до 100 easy задач. Далее делаем упор на medium. После решения по темам, выбираете компанию/компании, куда хотите попасть, сортируете по частоте встречаемости и решаете первые 100 задач. Решаете c периодическим повторением, так, чтобы они отложились в памяти и на собеседовании более 50% задач вы просто воспроизводили из памяти. А остальные были бы похожи на то, что вы уже видели и можете решить за несколько минут.

Обновление рейтинга по стартовым оферам

Включил в обзор больше компаний. Кроме FAANG, добавил AI стартапы, low frequency trading, хэдж фонды, банки, Big Tech.

Зп брал с levelsfyi. Компании, для которых данных мало, в рейтинг не включал, поэтому, вероятно, есть компании, которые небольшие, но платят тоже много. Брал типичное распределение по уровням, которое характерно для большинства компаний. Поэтому цифра, которую вы увидете в рейтинге это медианный стартовый офер по всем уровням. Оферы стартовые. В FAANG компаниях, существенная часть компенсации в виде акций. Также там дают рефрешеры, поэтому на одном и том же левеле через 3-5 лет работы человек может в разы больше получать. Где акций не дают, без промоушена, ваша компенсация не сильно изменится. Также в некоторых компаниях уровней мало, поэтому есть потолок. В FAANG, такой проблемы нет.

Топ 20:

1) Hudson River Trading (HRT) $593k
2) OpenAI $582k
3) Databricks $547k
4) Meta $498k
5) Netflix $496k
6) Optiver $465k
7) Two Sigma $457k
8) Uber $440k
9) Airbnb $428k
10) The Trade Desk $420k
11) Jane Street $393k
12) Google $390k
13) Nvidia $344k
14) Lyft $321k
15) Apple $310k
16) Bloomberg $299k
17) Amazon $268k
18) Microsoft $265k
19) JP Morgan $219k
20) Goldman Sachs $173k

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

Рейтинг топ компаний по отзывам сотрудников, без учета компенсаций

Рейтинг брал на основе отзывов на teamblind и glassdoor. Оценку по компенсации не учитывал, т.е. это то, как вы себя будете чувствовать на работе на ежедневной основе, а не только в момент прихода зп.
Некоторые параметры брал с коэффициентом. Например, карьерный рост брал с коэффициентом 0,5, т.к. промоушены бывают не так часто и не сильно влияют на ежедневный опыт. Также diversity and inclusion брал с коэффициентом 0,25. Вначале думал вообще его не брать, но по факту, он тоже влияет. Например, на отношение менеджера к вам, ваш промоушен и перфоманс ревью. Иногда, люди одной национальности чаще промоутят коллег той же национальности (китайцы китайцев, индусы индусов).

Итоговый рейтинг из тех же 20 компаний, чем выше в рейтинге, тем лучше вы будете себя чувствовать работая там:

1) Jane Street 31,05
2) Nvidia 31,05
3) OpenAI 31
4) Google 30,05
5) Two Sigma 29,45
6) Microsoft 29,1
7) Hudson River Trading (HRT) 29,05
8) Bloomberg 29,05
9) The Trade Desk 28,8
10) Netflix 28,75
11) Airbnb 28,1
12) DataBricks 27,7
13) Apple 27,3
14) Lyft 26,5
15) JP Morgan 26,15
16) Optiver 26,15
17) Meta 25,2
18) Uber 24,9
19) Goldman Sachs 24,9
20) Amazon 23,2

Отобразил все на диаграмме. По оси x - зп, по y - отзыв. В правом верхнем углу компании с хорошими отзывами и высокой зп: OpenAI, HRT. В левом нижнем - плохие отзывы, низкая зп - Goldman, Amazon. Справа внизу - высокая зп, но плохие отзывы: Meta, Uber, Optiver. Слева вверху - невысокая зп, но хорошие отзывы: Bloomberg, Microsoft.

В Майкрософт новая волна сокращений. В этот раз 9000 человек. Не так давно они сократили 6.8k.
Говорят, что сильнее постадают sales, marketing и отдел, который занимается играми/xbox.