Немало воды утекло со времен лихих девяностых, и теперь ABBYY разрабатывает решения в области интеллектуальной обработки информации и лингвистики, известные во всем мире. А мы не только знаем, что ABBYY читается как «Аби», но и котируем эту компанию как достойного работодателя.

Мощный приз решателю!

Первый читатель, верно решивший все задачи, получает ABBYY FineReader 12 Professional.

 

Задача 1

Дан массив из целых чисел. Найти такие m <= k, чтобы сумма a[m] + a[m + 1] + ... + a[k] была максимальна. Время работы должно быть порядка длины массива.

 

Задача 2

Дан текст, состоящий из N слов, длина которых не превосходит некоторой небольшой константы. Предложите хотя бы два способа вывести частоты вхождения слов в текст за субквадратичное время, объясните их преимущества и недостатки.

 

Задача 3

Даны числительные языка хауса:

đari bakwai da hamsin da shidda 756
sitta da đari bakwai da biyar 6705
saba’a da đari biyar da sittin 7560

A. Переведите с хауса: saba’in da biyar, đari shidda da sittin da shidda
B. Запишите на хауса: 67 и 5605

 

Задача 4

Есть генератор случайных чисел, который с равной вероятностью генерирует дискретные значения 1, 2, 3, 4 и 5. Как, имея этот генератор, получить генератор, который бы равновероятно выдавал дискретные значения 1, 2, 3, 4, 5, 6 и 7?

Читатели, шлите ваши ответы!

Правильные ответы принимает Татьяна Поташева:
Tatiana_P@abbyy.com

IT-компании, шлите нам свои задачки!

Миссия этой мини-рубрики — образовательная, поэтому мы бесплатно публикуем качественные задачки, которые различные компании предлагают соискателям. Вы шлете задачки на lozovsky@glc.ru — мы их публикуем. Никаких актов, договоров, экспертиз и отчетностей. Читателям — задачки, решателям — подарки, вам — респект от нашей многосоттысячной аудитории, пиарщикам — строчки отчетности по публикациям в топовом компьютерном журнале.

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

  1. schoolboy

    11.04.2016 at 17:03

    Как-то криво первая задача сформулирована.

  2. vertexodessa

    11.04.2016 at 23:47

    Та вроде понятно сформулирована, стандартная задача на наибольшую сумму подмассива..

    def max_subarray(A):
    max_ending_here = max_so_far = 0
    for x in A:
    max_ending_here = max(0, max_ending_here + x)
    max_so_far = max(max_so_far, max_ending_here)
    return max_so_far

    • schoolboy

      12.04.2016 at 02:54

      Понятно то понятно, но криво.
      Например: «Время работы должно быть порядка длины массива.» Можно догадаться, что имеется в виду временная сложность алгоритма T(n)=O(n) (а может и o(n), хотя вряд ли). Но написано как «массив из 30 элементов алгоритм обработает за время порядка 30». Во 2й задаче про субквадратичное время вспомнили, а тут про линейное забыли?
      Или вот задание. Они хотят не саму сумму найти, а индексы границ подмассива. Но слов «индексы» или «границы» не написали.
      Криво же.

Оставить мнение

Check Also

Господин Самоуничтожение. Как в домашних условиях смастерить Rubber Ducky со встроенной пиротехникой

Представь: ты втыкаешь в USB какую-то флешку, и вдруг в браузере открывается окно, где гру…