Работа с гео-данными через 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)

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

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