Немало воды утекло со времен лихих девяностых, и теперь 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

Хроники битвы при Denuvo. Как «непробиваемая» игровая защита EA Origin оказалась пробиваемой

Защита от пиратства Denuvo пришла на смену SecuROM и связана с одним действующим лицом – Р…