Классная задача с собеседования. Описание довольно длинное, но не поленитесь прочитать и попробовать решить, это будет интересно. Необходимо не только решить задачу, но и сделать это оптимально: на тестовых данных алгоритм должен отрабатывать не дольше 10 секунд. Достаточно интересно посоревноваться с коллегами, кто сделает быстрее и/или оптимальнее.
Описание задачи
Задача: В строке символов найти минимальную по длине подстроку, в которой есть все буквы, необходимые для того, чтобы сложить из них слово «счастье». Если есть несколько вариантов с минимальной длиной, то результатом будет подстрока, расположенная ближе остальных к началу входной строки. Если из символов входной строки слово «счастье» сложить невозможно, результат должен быть равен «Нет счастья».
На регистр букв (строчные/прописные) внимания не обращать. Т.е. подстрока «Есть час» может быть корректным ответом, несмотря на то, что в этой строке прописная «Е».
Английское «c» (си) и русское «с» (эс) считаются разными буквами.
Перевод строки считается одним символом.
Входные данные: строка символов (см. примеры ниже).
Ограничения:
- Длина входной строки <= 10000;
- Ограничение по времени (ориентировочное) – 10 секунд.
Пример 1
Входные данные:
Собака бывает кусачей
Только от жизни собачьей
Правильный ответ:
сачей
Только от жизни с
Объяснение: из всех подстрок, имеющих как минимум 2 буквы «с», и как минимум по одной букв «ч», «а», «е», «т» и «ь», эта имеет минимальную длину.
Пример 2
Входные данные:
Всё упало, всё пропало
Правильный ответ:
Нет счастья
Объяснение: во входной строке для счастья не хватает букв «е», «т», «ь» и «ч».
Другие примеры
Всего в обработку встроено 5 примеров:
Куда вписать алгоритм
Алгоритм вписать в заранее созданную функцию НайтиСчастье(ИсходныеДанные) (расположена в самом начале модуля формы обработки):
Скачать обработку «Найти счастье»
Если и Вам понравилось задание, делитесь впечатлениями и способами реализации.
Другие задачи с собеседований:
Поменять значения переменных местами
Получение ряда чисел от 1 до 1000 в запросе
Избавиться от условия в выражении
Функция НайтиСчастье(ИсходныеДанные)
ИсходныеДанные1 = Врег(ИсходныеДанные);
с1 = СтрНайти(ИсходныеДанные1,»С»,,,);
с2 = ?(с1>0,СтрНайти(ИсходныеДанные1,»С»,,с1+1,),0);
ч = СтрНайти(ИсходныеДанные1,»Ч»,,,);
а = СтрНайти(ИсходныеДанные1,»А»,,,);
т = СтрНайти(ИсходныеДанные1,»Т»,,,);
ь = СтрНайти(ИсходныеДанные1,»Ь»,,,);
е = СтрНайти(ИсходныеДанные1,»Е»,,,);
мин = мин(с1,с2,ч,а,т,ь,е);
макс = макс(с1,с2,ч,а,т,ь,е);
Если мин = 0 тогда
текст = «Нет счастья»;
иначе
а = 1;
мин = 1;
Длина = 10000;
Пока мин>0 цикл
а = а+1;
с1 = СтрНайти(ИсходныеДанные1,»С»,,,);
с2 = ?(с1>0,СтрНайти(ИсходныеДанные1,»С»,,с1+1,),0);
ч = СтрНайти(ИсходныеДанные1,»Ч»,,,);
а = СтрНайти(ИсходныеДанные1,»А»,,,);
т = СтрНайти(ИсходныеДанные1,»Т»,,,);
ь = СтрНайти(ИсходныеДанные1,»Ь»,,,);
е = СтрНайти(ИсходныеДанные1,»Е»,,,);
мин = мин(с1,с2,ч,а,т,ь,е);
если мин = 0 тогда
прервать
конецесли;
макс = макс(с1,с2,ч,а,т,ь,е);
Текст1 = Текст;
текст = сред(ИсходныеДанные1,мин,макс-мин+1);
Если СтрДлина(текст)<длина тогда
текст = текст
иначе
текст = текст1
конецесли;
ИсходныеДанные1 = сред(ИсходныеДанные1,мин+1);
длина = СтрДлина(текст);
конеццикла;
конецесли;
возврат текст
КонецФункции
Что-то ваш «мегакод» не работает. Не один из примеров))
У меня работает. Все примеры. Может у вас платформа старая и не все встроенные функции работают?
Ну или вы с кавычками текстовыми не все исправили, тут же их перевело
могу вам на мыло обработку кинуть с решением, если нужно
Интересная задачка. Вроде оптимально — 0,4 сек максимум