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

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




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

Пользователи
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)

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

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

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



 





Обсуждаем

  Гостевая книга:
R-2 : Ты решил: Ну, и наконец, то решение, которое тут видимо предполагается в идеале, я не буду говори...
Так, по старой памяти заглянул :) : R-2, условие неплохо бы конкретизировать. ;)) А то так вариантов может быть масса, хотя все обладают...
Задача 4 хода:
колд : [скрыто]
Задача Кот и мышка:
Дмитрий : [скрыто]
Задача Черная Жемчужина:
mskfirst : [скрыто]
Задача Квадратный торт:
не представился : [скрыто]
Задача Задача с ведрами: 9 и 4 = 6.:
ИносОйЧанбин : [скрыто]
Дкгк7 : [скрыто]
Задача Геометрическая 3:
не представился : [скрыто]
Алексей : [скрыто]
Гостевая книга:
R-2 : Дано: листочек бумаги и ручка. На листочке написаны три нуля. О О О Задача: «как из трёх нулей...
Задача Мышки и бутылки:
Никита : [скрыто]
Задача Вписанные квадратики:
Маргарита : [скрыто]
Задача Немножко ПДД:
Пушкин : [скрыто]
Задача Последняя спичка:
дед мороз : [скрыто]



Реклама



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