Найти счастье. Тестовое задание на собеседовании

26.08.24

Тестовое задание, которое повстречалось мне на собеседовании. В двух словах о задании - это просто поиск подстроки в строке.

Бесплатные

ВНИМАНИЕ: Файлы из Базы знаний - это исходный код разработки. Это примеры решения задач, шаблоны, заготовки, "строительные материалы" для учетной системы. Файлы ориентированы на специалистов 1С, которые могут разобраться в коде и оптимизировать программу для запуска в базе данных. Гарантии работоспособности нет. Возврата нет. Технической поддержки нет.

Узнавайте о новых бесплатных решениях в нашей телеграм-группе Инфостарт БЕСПЛАТНО

Наименование	Скачано	Бесплатно
Тестовое задание (без решения) .epf 26,89Kb 33	33	Скачать бесплатно
Тестовое задание (с решением) .epf 27,28Kb 56	56	Скачать бесплатно

Итак, несколько лет назад на собеседовании в одной московской IT-компании ~~в обычном франче~~ я получил тестовое задание. Выполнить его нужно было дома, а результат прислать по электронной почте. Вместе с описанием задания поставлялась и обработка. В одну из процедур этой обработки требовалось ввести свой алгоритм поиска подстроки в строке.

Сначала задание показалось мне простым, но как говорится, есть один нюанс - ограничение по времени выполнения не более 10 секунд.

Решить задание у меня получилось не сразу. Я перебрал несколько вариантов с каждым разом улучшая результат и через некоторое количество часов алгоритм получился быстрый и компактный, что меня полностью и устроило. Примерное общее время выполнения всех тестов, встроенных в обработку, составило 0.14 секунды (замер выполнялся на пустой конфигурации без метаданных).

На текущий момент других вариантов решения этого задания мне найти не удалось, кроме одного обсуждения на форуме инфостарта.

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

По итогам собеседования оффер мне предложили, но принимать его конечно же я не стал.

Далее привожу описание задания полностью как есть, без изменений.

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

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

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

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

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

Английское «c» (си) и русское «с» (эс) считаются разными буквами. Перевод строки считается одним символом.

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

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

Пример 1

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

Правильный ответ:
сачей
Только от жизни с

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

Пример 2

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

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

Правильный ответ:
Нет счастья

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

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

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

Если решение проходит все тесты, то 5 баллов. Если проходит все тесты со строками длиной < 2000, то 4 балла, если проходит все тесты со строками длиной < 1000, то 3 балла.

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

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

Рекомендации проверяющему

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

Вступайте в нашу телеграмм-группу Инфостарт

+5 –

См. также

Улучшенный алгоритм Левенштейна для 1С: интеллектуальное сравнение строк

Математика и алгоритмы Программист 1С 8.3 Абонемент ($m)

Данная внешняя обработка для платформы 1С:Предприятие реализует усовершенствованный алгоритм Левенштейна для вычисления схожести строк с учетом различных лингвистических особенностей русского языка. В отличие от классической реализации, этот алгоритм учитывает фонетические, визуальные и контекстные особенности набора текста.

1 стартмани

07.11.2025 3924 11 InFlach 17

Метод Дугласа-Пойкера

Математика и алгоритмы Программист 1C:Бухгалтерия Россия Абонемент ($m)

На написание данной работы меня вдохновила работа @glassman «Переход на ClickHouse для анализа метрик». Автор анализирует большой объем данных, много миллионов строк, и убедительно доказывает, что ClickHouse справляется лучше PostgreSQL. Я же покажу как можно сократить объем данных в 49.9 раз при этом: 1. Сохранить значения локальных экстремумов 2. Отклонения от реальных значений имеют наперед заданную допустимую погрешность.

1 стартмани

30.01.2024 12353 stopa85 12

Алгоритм симплекс-метода

Математика и алгоритмы Бесплатно (free)

Разработка алгоритма, построенного на модели симплекс-метода, для нахождения оптимального раскроя.

19.10.2023 19483 user1959478 57

Математический тренажер созданный для тестирования Вашего ребенка на предмет: умножения, деления, сложения и вычитания.

Математика и алгоритмы Разное 1С:Предприятие 8 1C:Бухгалтерия Россия Абонемент ($m)

Расширение (+ обработка) представляют собою математический тренажер. Ваш ребенок сможет проверить свои знание на математические вычисление до 100.

2 стартмани

29.09.2023 11807 maksa2005 8

Регулярки на 1С

Математика и алгоритмы Инструментарий разработчика Программист 1С:Предприятие 8 Россия Абонемент ($m)

Что ж... лучше поздно, чем никогда. Подсистема 1С для работы с регулярными выражениями: разбор выражения, проверка на соответствие шаблону, поиск вхождений в тексте.

1 стартмани

09.06.2023 19698 11 SpaceOfMyHead 20

Мини-обзор разных решений задач

Математика и алгоритмы Программист 1С:Предприятие 8 1C:Бухгалтерия Бесплатно (free)

Три задачи - три идеи - три решения. Мало кода, много смысла. Мини-статья.

03.04.2023 13284 RustIG 9

Тестирование средств 1С для решения СЛАУ

Механизмы платформы 1С Математика и алгоритмы Программист 1С:Предприятие 8 Россия Бесплатно (free)

В статье анализируются средства платформы для решения системы линейных уравнений в 1С. Приводятся доводы в пользу некорректной работы встроенных алгоритмов, а значит потенциально некорректного расчета себестоимости в типовых конфигурациях.

23.11.2022 12406 gzharkoj 15

Модель распределения суммы по базе

Математика и алгоритмы Программист 1С:Предприятие 8 Россия Абонемент ($m)

Обычно под распределением понимают определение сумм пропорционально коэффициентам. Предлагаю включить сюда также распределение по порядку (FIFO, LIFO) и повысить уровень размерности до 2-х. 1-ое означает, что распределение может быть не только пропорциональным, но и по порядку, а 2-ое - это вариант реализации матричного распределения: по строкам и столбцам. Возможно вас заинтересует также необычное решение этой задачи через создание DSL на базе реализации текучего интерфейса

1 стартмани

21.03.2022 11470 8 kalyaka 11

Комментарии

Подписаться на ответы Инфостарт бот

Свернуть все

1. SerVer1C 993 27.08.24 12:00 Сейчас в теме

Держите алгоритм на питоне:

with open('text.txt', 'r', encoding='utf-8') as f:
    happiness = f.read()

word = 'счастье'
markers = word + word.upper()

numbers = [(i, x.lower()) for i, x in enumerate(happiness) if x in markers]

pairs = []

count = len(numbers)

for i in range(count):
    j = i
    ost = list(word)
    while j < count and len(ost) > 0:
        if numbers[j][1] in ost:
            ost.remove(numbers[j][1])
        j += 1
    if len(ost) == 0:
        pairs.append((numbers[i][0], numbers[j-1][0]))

if not pairs:
    print('Нет счастья')
    exit()

m = min(pairs, key=lambda x: x[1] - x[0])

s = happiness[m[0]:m[1]+1]

print(s)

Показать

3. slknnk 80 27.08.24 12:44 Сейчас в теме

(1) Благодарю )

8. evilobot 3 15.02.25 19:18 Сейчас в теме

(1) Вот более оптимальная версия:

with open('text.txt', 'r', encoding='utf-8') as f:
    text = f.read()

word = 'счастье'
markers = word + word.upper()

numbers = [(i, x.lower()) for i, x in enumerate(text) if x in markers]

pairs = []
ost = list(word)
min_length = len(text) + 1
word_length = len(word)
start = -1

for i in range(len(numbers)):
    symb = numbers[i][1]
    if symb in ost:
        ost.remove(symb)
    else:
        for pair in pairs:
            if pair[1] == symb:
                pairs.remove(pair)
                break

    pairs.append(numbers[i])

    if not ost:
        length = numbers[i][0] - pairs[0][0] + 1
        if length < min_length:
            min_length = length
            start = pairs[0][0]
        if min_length == word_length:
            break

if start == -1:
    result = 'Нет счастья'
else:
    result = text[start:start + min_length]

print(result)

Показать

2. пользователь 27.08.24 12:22

Сообщение было скрыто модератором.

...

4. Азверин 3 29.08.24 11:23 Сейчас в теме

По итогам собеседования оффер мне предложили, но принимать его конечно же я не стал.

Поясните, почему "конечно" не стали?

5. slknnk 80 29.08.24 17:15 Сейчас в теме

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

6. Cyberhawk 137 29.08.24 19:23 Сейчас в теме

(5) Вкусвилл?

7. slknnk 80 06.09.24 12:54 Сейчас в теме

(6) Нет, просто ноунейм франч.

9. evilobot 3 15.02.25 19:29 Сейчас в теме

Вот более быстрый алгоритм, на моем ноуте выполняется в два раза быстрее приложенного к статье:

	
	ИскомаяКомбинация = "счастье";
	ТекСимвол = "_";
	НомерСимвола = 1;
	НеНайденныеСимволы = Новый Массив;
	Пока Истина Цикл
		ТекСимвол = Сред(ИскомаяКомбинация, НомерСимвола, 1);
		Если ТекСимвол = "" Тогда
			Прервать;
		КонецЕсли;
		
		НеНайденныеСимволы.Добавить(ТекСимвол);
		НомерСимвола = НомерСимвола + 1;
	КонецЦикла;
		
	ДлинаИскомойКомбинации = СтрДлина(ИскомаяКомбинация);
	НайденныеСимволы = Новый ТаблицаЗначений;
	НайденныеСимволы.Колонки.Добавить("Символ");
	НайденныеСимволы.Колонки.Добавить("НомерВСтроке");
	
	НомерНачала = 0;
	ДлинаСамойКороткойПодстроки = СтрДлина(ИсходныеДанные) + 1;
	НомерСимвола = 1;
	
	Пока Истина Цикл
		Символ = Нрег(Сред(ИсходныеДанные, НомерСимвола, 1));
		Если Символ = "" Тогда
			Прервать;
		КонецЕсли;
		
		Если СтрЧислоВхождений(ИскомаяКомбинация, Символ) = 0 Тогда
			НомерСимвола = НомерСимвола + 1;
			Продолжить;
		КонецЕсли;
		
		ИндексНеНайденного = НеНайденныеСимволы.Найти(Символ);
		Если ИндексНеНайденного <> Неопределено Тогда
			НеНайденныеСимволы.Удалить(ИндексНеНайденного);
		Иначе
			СтарыйСимвол = НайденныеСимволы.Найти(Символ, "Символ"); 
			НайденныеСимволы.Удалить(СтарыйСимвол);
		КонецЕсли;
		
		НоваяСтрока = НайденныеСимволы.Добавить();
		НоваяСтрока.Символ = Символ;
		НоваяСтрока.НомерВСтроке = НомерСимвола;
		
		Если НЕ ЗначениеЗаполнено(НеНайденныеСимволы) Тогда
			ТекущееНачало = НайденныеСимволы[0].НомерВСтроке;
			ДлинаТекущейПодстроки = НомерСимвола - ТекущееНачало + 1; 
			Если ДлинаСамойКороткойПодстроки > ДлинаТекущейПодстроки Тогда
				НомерНачала = ТекущееНачало;
				ДлинаСамойКороткойПодстроки = ДлинаТекущейПодстроки;
			КонецЕсли;
			
			Если ДлинаСамойКороткойПодстроки = ДлинаИскомойКомбинации Тогда
				// Самая короткая возможная подстрока, дальнейший поиск не имеет смысла
				Прервать;
			КонецЕсли;
		КонецЕсли;
			
		НомерСимвола = НомерСимвола + 1;
	КонецЦикла;
	
	Если НомерНачала <> 0 Тогда
		Возврат Сред(ИсходныеДанные, НомерНачала, ДлинаСамойКороткойПодстроки);
	Иначе
		Возврат "Нет счастья";
	КонецЕсли;

Показать

К рекомендациям еще можно добавить - не проверять скорость выполнения в режиме отладки, он увеличивает время выполнения кода в разы.