"Логические задачи" - это познавательно-развлекательный проект для непрокисших мозгов. Задачи на логику, нестандартное мышление. Не всегда самое очевидное решение - правильное. Но иногда всё оказывается проще, чем кажется на первый взгляд.

Задачи на логику и сообразительность




О сайте
Гостевая книга
ЧаВо

Пользователи
RSS

Поиск на сайте





запомнить меня
Зарегистрироваться


Задачи



Данетки


Текущие:

  «Геометрическая»
  Высказывание Ломоносова
  Наверное, не про яблоки
  Комерция
  Везде градусы
  Вагончик тронется, вагончик тронется..
  Спасибо медикам и католикам))
  Специальная купюра
  Студенческая смекалка
  Эллипс vs Круг
  Современные технологии. Немецкий стандарт.
  Спортивная
  философская
  Про газету
  печатная монета
  Купюра евро
  Древние изобретения
  Биометрические паспорта
  Новый глава
  В далеком созвездии тау Кита... 8)))
  Огородное
  Средневековое строительство
  Жестокое наказание
  Их нравы - 4
  Европейский стандарт

Разгаданные недавно:

  этот модный тандыр
  Из Что-Где-Когда
  Может ли такое быть?
  Что изображено?
  Да на тебе пахать надо!


Справочная



Признаки делимости
Площади фигур


Реклама






задача: Опять собеседование в Яндекс

Задачу прислал: Админ


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



Имеется морфологический словарь объемом примерно 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)

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

Комментарий:

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



 





Обсуждаем

  Задача Кофе с молоком:
ivana2000 : [скрыто]
ivana2000 : [скрыто]
Гостевая книга:
Ganckasl : These enhanced sensors would prompt many more codes at a high straight as a replacement for take exc...
Ganckasl : Enquire of give imminent stressors such as kindergarten concerns, conflicts with parents, dating iss...
Задача Кофе с молоком:
не представился : [скрыто]
не представился : [скрыто]
Гостевая книга:
LarryDrent : Howdy! [url=http://trustnlineph rmacy.us/]best online pharmacy mexico[/url] very good web page
Sanuyemsl : Feeding disorders or nutriment rejection may occur in infants or children who arrange required prolo...
Sanuyemsl : Manufacture sure to explain what you are doing to the young man, especially in the vanguard the pinp...
Aschnutut : Atonic bladder leads to fastidious urinary retention, refractory urinary infec- tions, and even pers...
Задача магия умножения:
скажите откуда вы взяли эту задачу : [скрыто]
Гостевая книга:
HjalteSr : The trunk is aligned withtrunk/hip guides, straps, or pads. ThisMessage carried descending pathway s...
Mojokoa : Drunkenness astronomical amounts of drink hawthorn dissemble the trouble for a some instrument hours...
RaidFup : It occurs most commonly in the occipital region but can manifest itself to another place, such as fr...
GrimbollOn : Battery existence, which depends on output and magnet use, is nowadays qualified to better 6 years s...



Реклама



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