Тестовое задание «Найти счастье»

Тестовое задание «Найти счастье»

Классная задача с собеседования. Описание довольно длинное, но не поленитесь прочитать и попробовать решить, это будет интересно. Необходимо не только решить задачу, но и сделать это оптимально: на тестовых данных алгоритм должен отрабатывать не дольше 10 секунд. Достаточно интересно посоревноваться с коллегами, кто сделает быстрее и/или оптимальнее.

Описание задачи

Задача: В строке символов найти минимальную по длине подстроку, в которой есть все буквы, необходимые для того, чтобы сложить из них слово «счастье». Если есть несколько вариантов с минимальной длиной, то результатом будет подстрока, расположенная ближе остальных к началу входной строки. Если из символов входной строки слово «счастье» сложить невозможно, результат должен быть равен «Нет счастья».

На регистр букв (строчные/прописные) внимания не обращать. Т.е. подстрока «Есть час» может быть корректным ответом, несмотря на то, что в этой строке прописная «Е».
Английское «c» (си) и русское «с» (эс) считаются разными буквами.

Перевод строки считается одним символом.

Входные данные: строка символов (см. примеры ниже).

Ограничения:

  1. Длина входной строки <= 10000;
  2. Ограничение по времени (ориентировочное) – 10 секунд.

Пример 1

Входные данные:

Собака бывает кусачей
Только от жизни собачьей

Правильный ответ:

сачей
Только от жизни с

Объяснение: из всех подстрок, имеющих как минимум 2 буквы «с», и как минимум по одной букв «ч», «а», «е», «т» и «ь», эта имеет минимальную длину.

Пример 2

Входные данные:

Всё упало, всё пропало

Правильный ответ:

Нет счастья

Объяснение: во входной строке для счастья не хватает букв «е», «т», «ь» и «ч».

Другие примеры

Всего в обработку встроено 5 примеров:

Обработка Найти счастье

Куда вписать алгоритм

Алгоритм вписать в заранее созданную функцию НайтиСчастье(ИсходныеДанные) (расположена в самом начале модуля формы обработки):

Функция НайтиСчастье

Скачать обработку «Найти счастье»

Если и Вам понравилось задание, делитесь впечатлениями и способами реализации.

Другие задачи с собеседований:

Поменять значения переменных местами
Получение ряда чисел от 1 до 1000 в запросе
Избавиться от условия в выражении

4 комментария

  1. Функция НайтиСчастье(ИсходныеДанные)

    ИсходныеДанные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);

    длина = СтрДлина(текст);

    конеццикла;

    конецесли;
    возврат текст

    КонецФункции

    1. Что-то ваш «мегакод» не работает. Не один из примеров))

      1. У меня работает. Все примеры. Может у вас платформа старая и не все встроенные функции работают?
        Ну или вы с кавычками текстовыми не все исправили, тут же их перевело
        могу вам на мыло обработку кинуть с решением, если нужно

  2. Интересная задачка. Вроде оптимально — 0,4 сек максимум

Добавить комментарий

Ваш e-mail не будет опубликован.