Map, Set і масиви: вибір структури даних на співбесіді

Коротка відповідь. У 90% задач на співбесіді достатньо чотирьох структур: масив, об'єкт, Map і Set. Вибір між ними – це не смак, а складність операцій: пошук у масиві коштує O(n), у Set і Map – у середньому O(1). Якщо твоє рішення містить includes або find усередині циклу – майже напевно його можна прискорити з O(n²) до O(n), просто замінивши структуру. Нижче – коли що брати і дві задачі з кодом «до/після».

Шпаргалка складності

Операція	Масив	Об'єкт	Map	Set
Пошук за ключем/значенням	O(n) (`includes`, `find`)	O(1) за ключем	O(1) (`get`, `has`)	O(1) (`has`)
Додавання	O(1) у кінець (`push`)	O(1)	O(1) (`set`)	O(1) (`add`)
Видалення	O(n) (`splice`, пошук індексу)	O(1) (`delete`)	O(1) (`delete`)	O(1) (`delete`)
Збереження порядку вставки	так	практично так, з нюансами	так	так
Розмір	`length`	`Object.keys(obj).length` – O(n)	`size` – O(1)	`size` – O(1)

Оцінки для Map/Set – середньостатистичні (у специфікації «sublinear on average»); на співбесіді достатньо казати «в середньому O(1)».

Коли Map замість об'єкта

Об'єкт – теж «ключ → значення», але Map варто обирати, коли:

ключі не рядки: у Map ключем може бути число, об'єкт, будь-що; об'єкт мовчки перетворить ключ на рядок (obj[1] і obj['1'] – одне й те саме поле);
колекція динамічна: часто додаєш і видаляєш записи – Map для цього створений, має size і зручну ітерацію for (const [key, value] of map);
потрібна чистота: в об'єкта є прототип, і ключ на кшталт 'toString' може здивувати; new Map() порожній по-справжньому.

Об'єкт лишається кращим для фіксованої структури – конфіг, DTO, параметри функції: там працює деструктуризація і типізація полів. Довідково: Map на MDN.

Навіщо Set

Set – це «колекція унікальних значень із миттєвим has». Два типові застосування:

// 1. Унікалізація
const tags = ['js', 'react', 'js', 'ts', 'react'];
const unique = [...new Set(tags)]; // ['js', 'react', 'ts']

// 2. Швидка перевірка членства
const blockedIds = new Set(blockedUsers.map((user) => user.id));
const visible = posts.filter((post) => !blockedIds.has(post.authorId));

У другому прикладі важлива деталь для співбесіди: Set будується один раз (O(n)), а потім кожна перевірка – O(1). Якби замість цього був blockedUsers.some(...) усередині filter, вийшло б O(n·m).

Задача 1: перший дубль у масиві

Наївно, O(n²):

function firstDuplicate(items) {
  for (let i = 0; i < items.length; i++) {
    // indexOf сам пробігає масив – цикл у циклі
    if (items.indexOf(items[i]) !== i) return items[i];
  }
  return null;
}

Із Set, O(n):

function firstDuplicate(items) {
  const seen = new Set();
  for (const item of items) {
    if (seen.has(item)) return item;
    seen.add(item);
  }
  return null;
}

На масиві з 10 000 елементів різниця – мільйони зайвих порівнянь проти одного проходу. Саме вміння побачити прихований цикл (indexOf, includes, find всередині ітерації) і назвати складність вголос відрізняє підготовленого кандидата.

Задача 2: злиття двох списків за id

Треба доповнити список користувачів даними з іншого списку.

Наївно, O(n·m):

function mergeUsers(users, profiles) {
  return users.map((user) => ({
    ...user,
    profile: profiles.find((profile) => profile.userId === user.id) ?? null,
  }));
}

Із Map-індексом, O(n + m):

function mergeUsers(users, profiles) {
  const profileByUserId = new Map(
    profiles.map((profile) => [profile.userId, profile])
  );
  return users.map((user) => ({
    ...user,
    profile: profileByUserId.get(user.id) ?? null,
  }));
}

Патерн «спочатку побудуй індекс, потім звіряйся з ним» покриває величезний клас задач: групування, join двох API-відповідей, підрахунок частот. Він же з'являється в React-задачах з дедуплікацією стану.

Задача 3: підрахунок частот через Map

Третій наскрізний патерн – частотний словник. Класика: перевірити, чи два слова є анаграмами.

function charCount(word) {
  const counts = new Map();
  for (const char of word) {
    counts.set(char, (counts.get(char) ?? 0) + 1);
  }
  return counts;
}

function isAnagram(a, b) {
  if (a.length !== b.length) return false;
  const counts = charCount(a);
  for (const char of b) {
    const left = counts.get(char);
    if (!left) return false;        // символа немає або вже вичерпано
    counts.set(char, left - 1);
  }
  return true;
}

console.assert(isAnagram('кіт', 'тік') === true, 'анаграма');
console.assert(isAnagram('кіт', 'кit') === false, 'різні алфавіти');

Рядок counts.get(char) ?? 0 – маленький, але показовий: оператор ?? замість || не сплутає збережений 0 з «немає значення». Той самий частотний патерн розв'язує «найпопулярніший елемент», «перший неповторюваний символ» і половину задач про рядки.

Окремо згадай Object.groupBy / Map.groupBy – відносно нові вбудовані методи групування. Якщо середовище співбесіди їх підтримує, можна використати; якщо ні – написати групування через Map руками, як вище, і це навіть виграшніше: видно, що ти розумієш механіку, а не лише API.

А що з сортуванням?

Сортування – найдорожча з «побутових» операцій: Array.prototype.sort працює за O(n·log n). Тому відповідь «відсортую і порівняю сусідів» для пошуку дублів формально правильна, але гірша за Set: O(n·log n) проти O(n), плюс sort без копії мутує вхідний масив. Якщо все ж сортуєш – кажи явно: «зроблю копію через toSorted або spread, щоб не мутувати вхід». Такі деталі й складають враження від відповіді.

WeakMap за 30 секунд

WeakMap тримає ключі-об'єкти «слабко»: якщо на об'єкт більше немає посилань, збирач сміття забере і його, і зв'язане значення. Типове застосування – прив'язати метадані до чужих об'єктів (наприклад, DOM-вузлів), не заважаючи їх звільненню. На співбесіді достатньо знати це і те, що WeakMap не ітерується.

Що тренувати далі

Візьми три свої розв'язані задачі й перевір кожну питанням: «чи є тут пошук усередині циклу?» Якщо є – перепиши через Set або Map і сформулюй уголос стару та нову складність. Більше задач цього типу – у добірці JavaScript live coding, а загальна структура підготовки – у гайді з JavaScript-співбесіди.