Пример задачи с собеседования⁠⁠

Всем привет, работаю java разработчиком больше 10 лет. В этом посте хотел бы вспомнить задачу, которая однажды попалась мне на собеседовании.

Постановка задачи следующая: определить, являются ли две заданных строки перестановкой символов друг друга. Примеры:

abc, acb - является

abba, abab - является

abb, aab - не является

Первыми вспоминаются формулы для количества перестановок, в них количество вариантов стремится к факториалу, что явно не подходит для задачи по программированию. Однако можно заметить, что задача сводится к более простой: определить, совпадают ли две строки по количеству соответствующих символов. Например:

abb -> [a=1, b=2]

aab -> [a=2, b=1]

Количество соответствующих символов не совпадает

Посчитать количество символов займет линейное время (сортировка подсчетом), а дополнительная память будет пропорциональна количеству уникальных символов (алфавит).

Эта несложная задача показывает, что нужно попробовать упростить постановку, прежде чем заниматься реализацией. Такой же принцип действует при решении продуктовых задач заказчика.

Всем удачи на собеседованиях и работе!