Вопрос с 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.

Собеседовал недавно разработчика из Яндекс

К нам часто подаются разработчики из Яндекса и многие работают. У меня много бывших Яндексоидов среди коллег.
У кандидата были явные сложности с разговорным английским. У кандидата занимало много времени понять, что я от него хочу, потом много времени сформулировать, как он бы решал эту задачу и долго формулировал свои мысли во время написания кода. Также старался лишний раз не переспрашивать. Из-за этого решение заняло много времени и кандидат не смог до конца правильно решить и не успел протестировать.
На систем дизайне он не драйвил обсуждение, не погружался в детали и не мог порассуждать на тему трейдофов разных подходов. Вероятно, из-за языкового барьера. А поведенческое провалил, т.к. примеры из опыта были не валидными или демонстрировали его с негативной для данного уровня стороны. При этом решение алгосов было ~ок. Но по факту все 4 собеседования на full loop были провалены.
Поэтому убеждение, что нужно просто задрочить литкод, то тебя примут в FAANG - это заблуждение.

Нужно ли учить многопоточность в Java?

С многопоточностью в Java ситуация примерно такая же как и с алгоритмами.
И то и другое спрашивают в топ компании. И то и другое сложно в освоении. И то и другое редко используется на практике.
Типичное приложение на Java - это какой-то бэкенд, который работает в обертке какого-то контейнера, типа Tomcat. На каждый новый реквест он создает новый поток, в рамках которого работает ваша бизнес логика. В таком случае вам не нужно заботиться о создании потоков вообще. За вас это сделает контейнер. Более того, часто в рамках приложения у вас нет shared состояния/переменных. Все обьекты создаются и живут в рамках одного потока(thread confinment). Обычно оно на уровне SQL базы, доступ к которой происходит с ACID транзакциями. Поэтому 90% кода на Java не требует особых знаний по многопоточности. При этом, при приеме в Яндекс, Сбер, Одноклассники, Mail и т.д. вас обязательно спросят многопоточность на собеседовании. Дело в том, что в таких компаниях это используется несколько чаще, т.к. пишутся кастомные и более сложные вещи + нет времени на освоение многопоточности, а ошибки могут стоить очень дорого. Поэтому если вы хотите попасть в топ компании(не обязательно FAANG), то учите и многопоточность и алгоритмы.
В FAANG многопоточность не спрашивают, но и вероятность пройти собес в FAANG меньше.