Группировка людей по городу

Решение

Группировка элементов — одна из самых частых операций в обработке данных. Нужно создать объект, где ключ — город, значение — массив людей из этого города. Временная сложность O(n) означает один проход по массиву.

Подход 1: Простой цикл (самый понятный)

interface Person {
  name: string;
  city: string;
}

type GroupedByCity = Record<string, Person[]>;

function groupByCity(people: Person[]): GroupedByCity {
  const result: GroupedByCity = {};
  
  for (const person of people) {
    // Если города нет в результате, создаём пустой массив
    if (!result[person.city]) {
      result[person.city] = [];
    }
    // Добавляем человека к его городу
    result[person.city].push(person);
  }
  
  return result;
}

Анализ:

• Временная сложность: O(n) — один проход по массиву
• Пространственная сложность: O(n) — хранение всех людей в новом объекте
• Простая и понятная логика
• Не требует понимания продвинутых методов

Подход 2: С использованием reduce (функциональный)

function groupByCity(people: Person[]): GroupedByCity {
  return people.reduce((acc, person) => {
    if (!acc[person.city]) {
      acc[person.city] = [];
    }
    acc[person.city].push(person);
    return acc;
  }, {} as GroupedByCity);
}

Анализ:

• Временная сложность: O(n)
• Более декларативный стиль
• Функция не имеет побочных эффектов (чистая функция)
• Создаёт замыкание (acc)

Подход 3: С использованием метода Map (более элегантно)

function groupByCity(people: Person[]): GroupedByCity {
  const grouped = new Map<string, Person[]>();
  
  for (const person of people) {
    if (!grouped.has(person.city)) {
      grouped.set(person.city, []);
    }
    grouped.get(person.city)!.push(person);
  }
  
  // Конвертируем Map в обычный объект
  const result: GroupedByCity = {};
  for (const [city, people] of grouped) {
    result[city] = people;
  }
  
  return result;
}

Когда использовать Map:

• Более эффективна для больших объёмов данных
• Методы .has() и .get() явнее по смыслу
• Можно использовать любые типы ключей, не только строки

Подход 4: Коротко с проверкой ОР

function groupByCity(people: Person[]): GroupedByCity {
  return people.reduce((acc, person) => ({
    ...acc,
    [person.city]: [...(acc[person.city] || []), person]
  }), {} as GroupedByCity);
}

Плюсы:

• Компактно
• Функциональный стиль

Минусы:

• Может быть медленнее на больших данных (создание новых массивов)
• Менее читаемо

Подход 5: С использованием современной группировки (если доступна)

// Object.groupBy() — новый метод в ES2024
function groupByCity(people: Person[]): GroupedByCity {
  const grouped = Object.groupBy(people, (person) => person.city) as GroupedByCity;
  return grouped;
}

Примечание: этот метод не поддерживается во всех средах. Используйте с полифилом для Node.js < 21.

Тестирование и примеры

const people = [
  { name: "Alice", city: "Moscow" },
  { name: "Bob", city: "London" },
  { name: "Charlie", city: "Moscow" },
  { name: "David", city: "London" },
  { name: "Eve", city: "Paris" }
];

const result = groupByCity(people);

console.log(result);
// {
//   Moscow: [{ name: "Alice", city: "Moscow" }, { name: "Charlie", city: "Moscow" }],
//   London: [{ name: "Bob", city: "London" }, { name: "David", city: "London" }],
//   Paris: [{ name: "Eve", city: "Paris" }]
// }

// Проверка
console.log(result.Moscow.length);  // 2
console.log(result.London.length);  // 2
console.log(result.Paris.length);   // 1
console.log(Object.keys(result).length); // 3

Сравнение подходов

Рекомендация для интервью

Начните с простого цикла — это ясно показывает понимание алгоритма и O(n) сложности. Если интервьюер спросит про reduce, покажите альтернативу.

Если упомянут большие данные, переходите на Map или reduce с объяснением, что reduce создаёт замыкание и работает с существующим объектом.

Ключевые моменты:

• Проверяем, есть ли город в результате перед добавлением
• O(n) значит один проход по входному массиву
• Результирующий объект занимает O(n) памяти
• reduce — функциональный и элегантный способ
• Обязательно типизируем в TypeScript