Классная задача с собеседования. Описание довольно длинное, но не поленитесь прочитать и попробовать решить, это будет интересно. Необходимо не только решить задачу, но и сделать это оптимально: на тестовых данных алгоритм должен отрабатывать не дольше 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 сек максимум
Алгоритм будет крайне быстрым за счет функции СтрНайти, которая позволяет искать подстроки начиная с определенной позиции или находить заданное по номеру вхождение.
Если использовать более старый вариант — функцию Найти, то придется потратить ресурсы при поиске второй «С» — то есть, отрезать подстроку, начиная с позиции первой найденной С и искать в ней.
Оптимизировать особо и нечего будет. Извратиться можно, но это не вызовет особого выигрыша по времени.
Например, можно запоминать, с какой буквы начиналась текущая подходящая подстрока, и при попытке поиска новой потенциальной подстроки искать только эту букву. При этом начальная позиция нового поиска будет определяться уже не как Мин+1, а как Макс+1, что в принципе сэкономит количество вызовов основной функции поиска
Вот более структурированный вариант кода Сергея (само тело функции):
//это разные входные данные, закомментируйте ненужные
ИсходныеДанные = «Собака бывает кусачей
|Только от жизни собачьей»;
ИсходныеДанные = «Есть час»;
ИсходныеДанные = «Только от жизни собачьей
|Собака бывает кусачей
|Только от жизни собачьей»;
ИсходныеДанные = «Всё упало, всё пропало»;
//подготовка длинной строки для имитации нагрузки
ДлинаВходнойСтроки = 10000;
ДлинныеДанные = «»;
Для Сч = 1 По (ДлинаВходнойСтроки/СтрДлина(Строка(Новый УникальныйИдентификатор))+1) Цикл
ДлинныеДанные = Строка(Новый УникальныйИдентификатор) + ДлинныеДанные;
КонецЦикла;
ТестовыеДанные = Лев(ДлинныеДанные, ДлинаВходнойСтроки — СтрДлина(ИсходныеДанные)) + ИсходныеДанные;
ИсхСтрока = ВРЕГ(ИсходныеДанные);
ВремяСтарта = ТекущаяДата();
Выполнять = ИСТИНА;
минДлина = СтрДлина(ИсхСтрока);
Результат = «»;
ПоискС = 1;
Пока Выполнять Цикл
поз1 = СтрНайти(ИсхСтрока, «С»,,ПоискС);
поз2 = СтрНайти(ИсхСтрока, «С»,,ПоискС,2);
поз3 = СтрНайти(ИсхСтрока, «Ч»,,ПоискС);
поз4 = СтрНайти(ИсхСтрока, «А»,,ПоискС);
поз5 = СтрНайти(ИсхСтрока, «Т»,,ПоискС);
поз6 = СтрНайти(ИсхСтрока, «Ь»,,ПоискС);
поз7 = СтрНайти(ИсхСтрока, «Е»,,ПоискС);
Начало = Мин (поз1, поз2, поз3, поз4, поз5, поз6, поз7);
Конец = Макс(поз1, поз2, поз3, поз4, поз5, поз6, поз7);
Если Начало = 0 Тогда
Выполнять = ЛОЖЬ;
Прервать;
КонецЕсли;
тДлина = Конец — Начало;
Если тДлина < минДлина Тогда
минДлина = тДлина;
Результат = Сред(ИсхСтрока, Начало, тДлина + 1);
КонецЕсли;
ПоискС = Начало + 1;
КонецЦикла;
Время = ТекущаяДата() — ВремяСтарта;
Сообщить(Результат + ";" + Время);
//для функции
//Возврат(?(Результат="", "Нет счастья", Результат));
ИсхСтрока = ВРЕГ(ИсходныеДанные);
Заменить на
ИсхСтрока = ВРЕГ(ТестовыеДанные );