Войти Регистрация
Код-ревью

11. Назначение заказов ближайшим курьерам

Сложная

Go · 59 строк

Каждые 2 секунды Assign получает пачку новых заказов и назначает каждому ближайшего свободного курьера. Координаты курьеров приходят из приложений раз в 5 секунд через UpdatePosition, параллельно с Assign.

В Москве в час пик — 30 000 курьеров онлайн и до 2 000 заказов в пачке. Отметьте строки с ошибками.

В работе: Ядро диспетчеризации доставки: от него зависит, через сколько минут приедет еда.

Как проверяем Нажмите на строку с ошибкой и коротко напишите, что не так. Баг засчитан, если отмечена хотя бы одна его строка. Зачёт — найдено не меньше 60 % багов с учётом серьёзности (критичный весит 3, обычный 2, мелкий 1), а лишних отметок не больше, чем багов в коде. Пустые строки, скобки и комментарии лишними не считаем. Ответ один на подход: после него показываем разбор.
геометриягонкисложность алгоритмаграничные случаи

Источник: на задачах Яндекса: диспетчеризация курьеров Доставки. Условие пересказано своими словами.

Давали на собеседовании? Ответов пока мало — ваш поможет.
  1. package dispatch
  3. import (
  4. "math"
  5. "sort"
  6. "sync"
  7. "time"
  8. )
  10. type Courier struct {
  11. ID string
  12. Lat float64
  13. Lon float64
  14. Busy bool
  15. Updated time.Time
  16. }
  18. type Order struct {
  19. ID string
  20. Lat float64
  21. Lon float64
  22. }
  24. type Dispatcher struct {
  25. mu sync.Mutex
  26. couriers map[string]*Courier
  27. }
  29. func (d *Dispatcher) UpdatePosition(id string, lat, lon float64) {
  30. c := d.couriers[id]
  31. c.Lat, c.Lon, c.Updated = lat, lon, time.Now()
  32. }
  34. func dist(lat1, lon1, lat2, lon2 float64) float64 {
  35. dx := lat1 - lat2
  36. dy := lon1 - lon2
  37. return math.Sqrt(dx*dx + dy*dy)
  38. }
  40. // Assign подбирает каждому заказу ближайшего свободного курьера.
  41. func (d *Dispatcher) Assign(orders []Order) map[string]string {
  42. d.mu.Lock()
  43. defer d.mu.Unlock()
  44. result := map[string]string{}
  45. for _, o := range orders {
  46. var free []*Courier
  47. for _, c := range d.couriers {
  48. if !c.Busy {
  49. free = append(free, c)
  50. }
  51. }
  52. sort.Slice(free, func(i, j int) bool {
  53. return dist(o.Lat, o.Lon, free[i].Lat, free[i].Lon) < dist(o.Lat, o.Lon, free[j].Lat, free[j].Lon)
  54. })
  55. best := free[0]
  56. result[o.ID] = best.ID
  57. }
  58. return result
  59. }