Как получить максимальное число из перестановок цифр заданного числа

Что проверяют

Видите ли вы, что перебирать перестановки не нужно: максимум получается сортировкой цифр по убыванию. Дальше смотрят на граничные случаи и знание особенностей JavaScript: сортировки по умолчанию и точности Number. Частое продолжение: найти следующую по величине перестановку.

Как отвечать

Решение в одну строку:

const maxFromDigits = (n) =>
  Number(String(n).split('').sort((a, b) => b - a).join(''));

Что стоит проговорить:

• сложность: сортировка d цифр стоит O(d log d). Видов цифр всего десять, поэтому можно посчитать частоты в массиве из 10 элементов и собрать ответ за O(d);
• компаратор: sort() без аргумента сравнивает элементы как строки. Для одиночных цифр результат совпадёт, но явный (a, b) => b - a показывает, что вы знаете эту особенность;
• toSorted: неизменяющая версия sort из ES2023, если исходный массив нужно сохранить;
• большие числа: выше Number.MAX_SAFE_INTEGER, то есть 9007199254740991, точность теряется. Вход лучше принимать и возвращать строкой или работать с BigInt;
• отрицательные числа: для них максимум даёт сортировка по возрастанию, ведь чем меньше модуль, тем больше число. Знак отделяют до сортировки, иначе минус попадёт в массив цифр.

Перебор всех перестановок стоит упомянуть как тупиковый путь: это O(d!), и уже на 12 цифрах выходит почти полмиллиарда вариантов.

Где спотыкаются

Пишут генерацию всех перестановок через рекурсию. Интервьюер ждёт, что вы заметите сортировку, и такое решение считают неудачным даже при правильном результате.

Забывают про ведущие нули у отрицательных чисел. Для -120 сортировка по возрастанию даёт -012, и нужно договориться, допустим ли ведущий ноль, то есть ответ -12 или -102.

Путают задачу с похожей: составить максимальное число из массива чисел. Там сортировка по цифрам не работает, сравнивают склейки a + b и b + a как строки.