Иерархия коллекций

На собеседованиях часто спрашивают о коллекциях. Обычно начинают с вопроса о том, как выглядит иерархия классов. Вот достаточно полное описание:

➡️В Java Collection Framework на вершине иерархии находятся два интерфейса: Collection и Map. Они разделяют коллекции на простые последовательные наборы элементов и наборы пар «ключ — значение» (словари).

➡️Collection наследуется от интерфейса Iterable. Он представляет собой набор однородных элементов, которые могут повторяться определённое количество раз.

➡️Интерфейс Collection определяет основные методы работы с простыми наборами элементов, которые будут общими для всех реализаций этого интерфейса. Например add(), remove() и size().

➡️Реализации интерфейса Map включают HashMap, LinkedHashMap и TreeMap. Есть ещё WeakHashMap, но для понимания этой реализации нужно разбираться с типами ссылок в Java.

➡️Реализации интерфейса List включают Vector, Stack, ArrayList и LinkedList.

➡️Интерфейс Set — это абстракция над математическим понятием множества. Главная особенность множества — отсутствие дубликатов. Его реализации: HashSet, LinkedHashSet и TreeSet.

➡️Интерфейс Queue описывает коллекции с предопределённым способом вставки и извлечения элементов — очереди FIFO. Его реализует, например, LinkedList.

📹На канале новый видос с разбором самых частых вопросов по Java Core которые задают на собесах

Кого ты, блядь, выберешь? Java или Go? Go или Java?

Недавно писал о том, как меня позвали проходить собесы на позицию Go разработчика в Авито.

Из запланированных 5 этапов уже пройдено 3

✔️ Скоринг - пол часа общих вопросов, чтобы отсеять тех кто точно совсем не шарит, подробно писал здесь

✔️ Алгоритмическая часть - такие я провожу сам в Т-Банке, было непривычно оказаться с другой стороны. По ощущениям в авито проще, надо решить две задачи а не три, и код не обязательно должен запускаться, главное описать верный алгоритм. В итоге решил две задачки, первая по уровню сложности примерно как easy с литкода, вторая сначала тоже казалась не очень сложной, пока интервьюер не сказал, что решать ее надо без сортировки. Додумался до оптимального решения только после небольшой подсказки интервьюера.

✔️ Секция по языку - На удивление была отдельная секция именно по Java, кажется хотели просто проверить насколько хорошо кандидат владеет тем инструментом которым пользуется в данные момент, понятное дело что для Go разработки знание Java не нужно. Поговорили про особенности реализации стримов, разницу между анонимными классами и лямбда выражениями, также была практическая задача на то, чтобы реализовать свою структуру данных алгоритмически эффективно.

Что еще осталось:

⏰ System design - нормально проходил его только один раз, и на тот момент прошел не очень, секция запланирована на вторник, сейчас активно перечитываю две книги по проектированнию распределенных систем которые у меня есть, очень хочется пройти хорошо. По результатам этой секции будет решаться итоговый грейд между Middle+ и Senior

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

Про что из прошедших этапов рассказать подробнее?


👾 - алгоритмы
✍️ - секция по языку

📹 Первая тысяча просмотров на ютуб

Из этой тысячи некоторые подписались и сюда, так что добро пожаловать)

Хочу спросить здесь - какое видео интересно было бы посмотреть дальше?

Опрос ниже
🔽🔽🔽

💸Торговаться ли за бо́льшую сумму в оффере?

Конечно да!

Я могу привести аргументы, почему это так, но, не буду.

Вместо этого поделюсь скрином переписки с HR компании, где мне изначально предложили зарплату около 360 000 рублей на руки.

Работа с гео-данными через MongoDB / Делаем свой Tinder 🌐 (1/2)

Уже второй раз в своей бэкендерской жизни приходится работать с гео-данным (координатами) каких-то точек. Раньше это были точки оплаты, по сути физические терминалы, теперь это ПВЗ, в которые может прийти посылка.
Способы работы тоже разные, в Т-Банке это был Clickhouse, а теперь MongoDB, про которую и хочу рассказать в этом посте.

➡️Общая формулировка задачи
1. В базе хранятся координаты каких-то точек
2. Найти все точки, которые находятся не расстоянии не больше чем N метров от заданной.

Оба раза бизнес-задача сводилась к такой формулировке, здесь для примера импортозаместим тиндер, в котором пользователь хочет найти людей, находящихся не дальше 1 км от него.
А чтобы как-то разнообразить контент, писать будем на Go, но на Java концепция примерно та же)

Представьте, что пользователь хочет найти людей, находящихся не дальше 1 км от него, чтобы начать общение.

1️⃣Создадим класс/структуру User

type Location struct {
  Type        string     `bson:"type"`
  Coordinates [2]float64 `bson:"coordinates"`
}

type User struct {
  ID       primitive.ObjectID `bson:"_id,omitempty"`
  Name     string             `bson:"name"`
  Location Location           `bson:"location"`
}


primitive.ObjectID - тип данных, отображающий ID в MongoDB

bson:"_id,omitempty" - тег, для сохранения структуры в виде bson, по сути определяет маппинг поля структуры на поле в документе MongoDB.

omitempty - опция, которая позволяет пропустить поле, если оно пустое. Например, ID будет автоматически сгенерирован MongoDB при вставке

Location.Type - MongoDB ожидает определенный формат данных для работы с гео-запросами. Тип 'Point' обязателен для хранения точки на местности."

2️⃣Напишем функцию для генерации случайных пользователей

func generateUser() *User {
  lon := minLon + rand.Float64()*(maxLon-minLon)
  lat := minLat + rand.Float64()*(maxLat-minLat)

  return &User{
    Name: randomStr(),
    Location: Location{
      Type:        "Point",
      Coordinates: [2]float64{lon, lat},
    },
  }
}

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

Мы генерируем случайных пользователей с координатами, чтобы симулировать базу данных. Все точки находятся в пределах заданного диапазона (например, в одном городе).

3️⃣Запускаем MongoDB в Docker

Эта команда запускает MongoDB-сервер. Убедитесь, что он работает, например, через docker ps или подключившись к mongodb://localhost:27017 через MongoDB Compass.

docker run --name mongodb -p 27017:27017 -d mongodb/mongodb-community-server:latest

4️⃣ Пишем основную логику

func main() {
  // Подключаемся к БД
  clientOptions := options.Client().ApplyURI("mongodb://localhost:27017")
  client, _ := mongo.Connect(context.Background(), clientOptions)
  // Задаем поведение при завершении программы
  defer client.Disconnect(context.Background())

  //Сколько пользователей будем создавать
  count := 1000

  // Определяем название БД и коллекции
  db := client.Database("Test")
  collection := db.Collection("TinderUsers")

  // Создаем 1000 пользователей
  var users []interface{}
  for i := 0; i < count; i++ {
    users = append(users, *generateUser())
  }

  // Сохраняем их в БД
  collection.InsertMany(context.Background(), users)
}

И запускаем 👣

5⃣ Смотрим что получилось

MongoDB Compass умеет красиво отрисовывать точки на карте, вот они все слева направо

Работа с гео-данными через MongoDB / Делаем свой Tinder 🌐 (2/2)

Данные, с которыми мы будем работать - есть
Теперь найдем тех, кто близко к нам, чтобы Tinder заработал на полную

6⃣ Создадим индекс, чтобы можно было искать по координатам на 2D сфере

func main() {
  // Подключаемся к БД
  clientOptions := options.Client().ApplyURI("mongodb://localhost:27017")
  client, _ := mongo.Connect(context.Background(), clientOptions)
  // Задаем поведение при завершении программы
  defer client.Disconnect(context.Background())

  // Определяем название БД и коллекции
  db := client.Database("Test")
  collection := db.Collection("TinderUsers")

  indexModel := mongo.IndexModel{
    Keys: bson.M{
      "location": "2dsphere", // Тип индекса
    },
  }

  // Создаем индекс
  collection.Indexes().CreateOne(context.Background(), indexModel)
}

Индекс типа 2dsphere позволяет MongoDB эффективно выполнять гео-запросы, такие как поиск ближайших точек на сфере (поверхности Земли).

7️⃣ Ищем людей в 1 километре от нас

// Задаем нашу локацию
location := bson.M{
  "type":        "Point",
  "coordinates": []float64{37.4672807794374, 55.76727558121088},
}

maxDistance := 1000

// Запрос для поиска людей максимум в 1000 метрах от нашей локации
filter := bson.M{
  "location": bson.M{
    "$nearSphere": bson.M{
      "$geometry":    location,
      "$maxDistance": maxDistance,
    },
  },
}

// Выполняем запрос
cursor, _ := collection.Find(context.Background(), filter)
defer cursor.Close(context.Background())

// Печатаем кого нашли
for cursor.Next(context.Background()) {
  var result User
  cursor.Decode(&result)
  fmt.Println("User", result.Name, maxDistance, "метров от вас")
}

$nearSphere — это запрос для поиска ближайших точек
$geometry — описывает, от какой точки ищем
$maxDistance — ограничивает поиск радиусом в метрах

8️⃣PROFIT, идем пилить стартап

User thupqs 1000 метров от вас
User tyltdb 1000 метров от вас
User hzzwms 1000 метров от вас
User fvirnt 1000 метров от вас

🌟P.S. Ради интереса проверил на 10 000 000 пользователей, запрос выполнился за 2 миллисекунды

...
User fxbmmh 1000 метров от вас
User nxyvev 1000 метров от вас

Duration 1.880375ms

А при поиске в радиусе 100км - 600 миллисекунд

...
User gccaab 100000 метров от вас
User nvondt 100000 метров от вас

Duration 602.639417ms

🌳 Кстати насчет деревьев

На алгоритмических интервью часто попадаются задачи на деревья (tree), поэтому сделал подборку с литкода на эту тему. Очень похожие я решал на реальных собесах несколько раз.

Вот 4 задачи - от Easy до Medium уровня сложности, примерно такие и дают на собесах.

🔤Same tree (Easy) - проверить, являются ли два дерева одинаковыми

🔤Symmetric tree (Easy) - проверить, является ли дерево симметричным

🔤Balanced binary tree (Easy) - проверить, является ли оно сбалансированным

🔤Path sum 2 (Medium) - найти все пусти к листьям в дереве, которые в сумме дадут заданное число (тут понадобится алгоритм бектрекинга)

✉️ Специально для тех, кому лень решать, но посмотреть на код хочется, решил эти задачки и скинул решения в комментах

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