Home » Работа и карьера » Тесты при приеме на работу в ABBYY Software – Ответы 2

Тесты при приеме на работу в ABBYY Software – Ответы 2

Что-то я затянул с ответами на вопросы с собеседования в ABBYY. Да и вообще, давно ничего не писал в блоге. Надо срочно исправляться.

Сегодня рассмотрим вторую задачу:

2. Дан массив a[1],..a[N].. найти m,k (m<k) такие что a[m] + ..+a[k] — максимальна. Сложность алг-ма = N.

Вообще-то, не зная заранее решения, найти алгоритм, работающий за время O(N), в течение короткого времени (на собеседовании) довольно сложно. Те же, кто это действительно могут, работают не в ABBYY. Гораздо более полезное собеседование можно провести, убрав требование быстродействия O(N). Нетрудно написать алгоритм работающий со скоростью O(N3). Далее, легко его оптимизировать до O(N2). На этом этапе можно многое узнать о сообразительности кандидата. Используя подсказки, можно прийти к алгоритму O(N log N). Лично я именно так проводил бы собеседование, основанное на этой задаче.

Что касается решения O(N), то оно, наряду с другими вариантами, прекрасно описано в книге Джона Бентли “Жемчужины программирования” (глава 7). Этой замечательной книги, к сожалению, сейчас нет в продаже. Найти ее можно только в электронном виде.

Приведу реализацию алгоритма из книги на C#:

В этом примере вычисляется только максимальная сумма, без определения индексов m,k.  Заменив методы Max на конструкции if … else с запоминанием индексов, несложно найти m и k.

Ключевой момент этого алгоритма заключается в том, что любой положительный подвектор массива увеличивает максимальную сумму.

  • Михаил

    Обясните мне дураку, почему Лингво периодически вешает мне PocketPC, если они так программеров набирают? И почему они Tutor для PocketPC несколько лет писали, если его сложность – курсовая студента.

  • Sergiy Oliynyk

    Как программист, скажу, что в разработке ПО предусмотреть все варианты работы программы практически невозможно. Тем более, в случае с Pocket PC.
    Кстати, я на своем Fujitsu-Siemens N560 прочитал несколько англоязычных книг с активным использованием Лингво и проблем с зависанием небыло ни разу.
    А то, что они в 12 Лингво отрубили поддержку вызова из ХаалиРидера, конечно ламерство.

    P.S. В новой версии ридера уже работает.

  • vertur

    Так неверная реализация.
    На последовательности { -4, -5, -6, -1, -2, -1, -8, -20 } хотя очевидно должно быть -1

  • vertur

    У меня получился следующий алгоритм (язык Си, C99),
    хотя может и он содержит ошибки.

    —-cut–
    #include <stdio.h>

    void main()
    {
    // 0 1 2 3 4 5 6 7
    //int a[] = { -4, -5, -6, -1, -2, -1, -8, -20 }; // -1
    //int a[] = { -4, -5, -6, 1, 2, -1, 8, -20 }; // 10
    int a[] = { 2, 2, 2, -1, 2, 2, 2 }; // 11

    int N = sizeof(a)/sizeof(int);

    int m = 0;
    int k = 0;
    int cur_sum = a[0];
    int last_sum = 0;
    int last_i = -1;
    int max_sum = cur_sum;

    for (int i = 1; i < N; ++i) {
    cur_sum = cur_sum + a[i];

    if (cur_sum – last_sum > max_sum) {
    max_sum = cur_sum – last_sum;
    m = last_i + 1;
    k = i;
    }

    if (cur_sum < last_sum) {
    last_sum = cur_sum;
    last_i = i;
    }
    }

    printf("m=%d, k=%d, max_sum=%d\n", m, k, max_sum);
    }
    —-cut–