Работа с гео-данными через 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) - найти все пусти к листьям в дереве, которые в сумме дадут заданное число (тут понадобится алгоритм бектрекинга)

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

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

А что выберешь ты?
🐝 - пасека
💻 - опять фиксить баги

SQL на собесах

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

Чтобы повысить свои шансы на оффер, нужно уметь быстро писать простые SQL-запросы. Для этого нужна практика.

Для алгоритмов есть LeetCode, а сегодня я хочу поделиться хорошим сборником задач на SQL с автопроверкой — SQL-EX.

Там есть задания на различные механизмы SQL: от простых SELECT и JOIN до оконных функций, подзапросов и предикатов. Под каждой задачей есть ссылка на теоретический материал.

Вот ссылка на SQL-EX: https://sql-ex.ru/

Найти максимальную цену ПК, выпускаемых каждым производителем, у которого есть модели в таблице PC.

Схема БД:
 - Product (maker, model, type)
 - PC (code, model, speed, ram, hd, cd, price)

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

Свое решение выложил в комментариях 👇

Фактор автобуса | Как измерить взаимозаменяемость команды 🚌

Есть такое понятие в управлении командой - Bus Factor (Фактор автобуса).
Bus Factor — это метрика, показывающая, насколько зависима команда от отдельных сотрудников. Это полезный показатель, чтобы оценить риски, если важный человек из команды внезапно выйдет из строя, например заболеет или уволится. Но как его измерить?

Очень просто — посчитайте, сколько сотрудников вашей команды должно "попасть под автобус", чтобы работа остановилась. Чем больше людей могут выполнять аналогичные задачи, тем выше ваш Bus Factor.

Например у нас в команде есть
- Алина - backend разработчик
- Коля - backend разработчик
- Вася - backend разработчик
- Женя - frontend разработчик
- Маша - frontend разработчик
- Анатолий - тимлид, frontend разработчик

Пусть в нашей команде только тимлид Анатолий знает, какие задачи нужно делать в следующем спринте, причем он это нигде не записал, и планирует рассказать команде о новых задачах на созвоне в понедельник.

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

Для этой команды Bus factor - 1️⃣

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

Команда конечно будет грустить, но продолжит делать задачи по заранее составленному плану, а после релза пойдет навестить лида в травмпункт.

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

В таком случае bus factor - 3️⃣

А у вас в команде какой Bus Factor? Пишите в комментариях 👇

Теперь и на хабре ✅

Написал свою первую статью на хабре

Рассказываю, почему ни один программист не может знать всё, как оценивают сроки задач в IT и какой язык программирования обрабатывает 90% всех банковских транзакций в мире.

Если интересно, приходите читать

p.s. Если статья зашла и у вас есть аккаунт на хабре, не откажусь от плюсика в карму аккаунта и к самой статье