Эту задачу предлагали решить разработчикам на собеседовании программного обеспечения. Задача скорее на алгоритмическое мышление.

Имеется морфологический словарь объемом примерно 100 000 входов, в котором глаголы совершенного и несовершенного вида помещены в отдельные статьи (то есть «делать» и «сделать» считаются разными словарными входами). Вам требуется найти в словаре такие видовые пары и «склеить» статьи в одну.

Вопрос: Опишите общий сценарий решения такой задачи и примерный алгоритм поиска видовых пар.


+ -

Ответ

Решение задачи

Ваши ответы на задачу

ответов: 6

не представился 2018-02-15 17:05:25 пишет:

Я знать Русский нехорошо очень. Вы искать два: "складывать - сложить."

R-2 2018-02-12 18:58:44 пишет:

Если это задача по лингвистики, то я вижу только два интересных момента.
1. У глагола может быть несколько приставок: "поподприкрыть (глаза.)"
Такие случаи надо аккуратно отслеживать.
2. У глагола может не быть приставки, хотя лексикографически он на нее начинается: "простить."
За этим тоже надо следить.

R-2 2018-02-12 18:51:47 пишет:

Если это задача по программированию, то их должна волновать скорость работы программы. В данном случае O(N).
Меньше не получиться, т.к. надо перебрать все глаголы. Можно сделать два прохода - все равно будет O(N).
Еще их могут волновать структура данных. На первом проходе можно записать все глаголы в хеш-таблицу. Тогда на втором проходе время поиска основного глагола будет O(1).
Но, честно говоря, 100.000 - это очень маленькое число чтобы разводить всю эту теорию.

Виталий 2018-02-12 15:07:39 пишет:

1 вариант.
Делишь по 50 000.
Берешь из первой половины первый совершенный глагол. Если не находишь в этой группе, перекидываешь во второй. Если находишь, склеиваешь, и дописываешь вконец.

такой же алгоритм выполняешь для второй 50 000.
2 вариант
100.000 первым проходом разделить на Совершенные и несовершенные по 50.000.
Из первого ищешь соответствие во втором и записываешь в итоговый файл, со склееными.

Евгений Николаев 2015-10-25 09:09:13 пишет:

искать в совершенных несовершенные+приставка из массива допустимых {c-,со-,по-,у-, и т.д.}, если есть совпадение - осуществить перенос.

KoKos 2015-07-09 00:28:23 пишет:

Хм... Не уверен, что возьмусь за такое на собеседовании, где время, мягко говоря, :))) ограниченно... Но пара вопросов у меня бы сразу же возникла навскидку: во-первых, только ли глаголы содержит словарь? и во-вторых, по сколько входов будут занимать различные "любопытные" глаголы - типа "бежать", "жать", и т.п.? 8)

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

© 2009-201x Логические задачи