За сто с хвостом собеседований, в которых я участвовал, набралось несколько заданий, которые успели мне ужасно наскучить. Я честно делаю озадаченный вид и секунд 30 «думаю», но на деле уже напишу этот код с закрытыми глазами по первому слову вопроса. Сегодня хочу поделиться своим любимым решением одного из таких заданий с вами. Задача такая:
Анаграммы — слова, которые состоят из одинаковых букв: например, "нора" и "рано" (но не "пара" и "пар")
Напишите функцию, которая принимает на вход массив строк и группирует анаграммы, например:
groupAnagrams(["пара", "Арап", "пар", "бор", "бро"])
// [["пара", "Арап"], ["пар"], ["бро", "бор"]]
Для начала предлагаю вам самим немного подумать над этой задачей — тут нет никакого подвоха!
.
.
.
.
.
.
.
Решение
Главное в таких заданиях — не кидаться сразу писать код, а продумать план действий.
Для начала научимся определять анаграммы. Нам поможет что-то, что у анаграмм всегда совпадает. Первым на ум обычно приходит счетчик символов:
"пара" -> { "п": 1, "a": 2, "р": 1 }
Дальше можно пробежаться по массиву, найти слова с одинаковым счетчиком и сгруппировать их. Но постойте — объекты в JS не очень удобно сравнивать! Гораздо проще работать со строкой из отсортированных по алфавиту символов:
"пара" -> "аапр"
Так и поступим. На JS записывается довольно просто:
const normalize = str => str
.toLowerCase() // большие и маленькие буквы не различаем
.split('') // разбили на массив символов
.sort() // отсортировали массив
.join('') // соединили обратно в строку
По-умному это можно назвать нормальной формой или инвариантом — впечатлите собеседующего!
Теперь дело за малым — сгруппировать слова с одинаковой нормальной формой. Для хранения групп используем обычный JS- объект:
const groups = {}
words.forEach((word) => {
const normal = normalize(word)
// создали группу, если ее еще нет
groups[normal] = groups[normal] || []
// и положили в нее слово
groups[normal]push(word)
})
// возвращаем сами группы
return Object.values(groups)
Готово! Обязательно прокручиваем код в голове на нескольких простых примерах.
---
Вот такое интересное (первые раза два) задание на базовый JS без подвохов мне давали не меньше 10 раз, да и сам я часто его задавал. Может, у вас есть решение получше? Поделитесь в комментариях!
По этой теме есть еще несколько очень частых заданий. А популярное задание по CSS я уже разбирал на прошлой неделе. Если интересно, подписывайтесь на мой канал — буду чаще проводить такие разборы!