Задачи на собеседованиях. Задачи от компании Abbyy

Когда на собеседовании задают вопросы в стиле «почему крышка от канализационного люка круглая?» — это как минимум странно. Простыни с сишным кодом, который нужно скомпилировать в голове и представить конечный результат, — нудно. Считаю, что самые интересные задачки — это задачи на общетехническое и логическое мышление. Очень рад, что сегодня товарищи из компании Abbyy подкинули нам именно такие задания. Вперед, решаем!

Задача 1: Константин и комиксы

Константин очень разносторонняя личность, и в числе прочего у него есть хобби — чтение комиксов про бобра-супергероя. Хоть он покупает и не все номера, они ему очень нравятся. Однажды Константин задумался, в какой момент он пропустил больше всего номеров подряд. Задачу усложняет тот факт, что все журналы перемешаны. Помогите Константину найти номера комиксов, между которыми он пропустил наибольшее количество выпусков. Учитывайте, что журнал очень старый и у него может быть миллиард выпусков, коллекция Константина может достигать миллиона журналов. Константин очень нетерпеливый и хочет получить ответ как можно быстрее.

Подумайте над оптимальным по времени решением.

INFO

Предыдущий выпуск задач от компании Abbyy смотри здесь.

Задача 2: Даша и сейф

Умная Даша умеет хранить секреты и держит их в специальном сейфе. Чтобы открыть сейф, нужно ввести цифровой код длины K (K > 2). К тому же сейф устроен таким образом, что он валидирует последние введенные K цифр независимо от предыстории. Например, если код 1998, а Даша введет 911998, то сейф откроется. К сожалению, Даша забыла правильный код, но помнит все цифры, которые могли встречаться в коде.

Подскажите Даше последовательность, в которой нужно набирать цифры, чтобы она как можно скорее открыла сейф.

Задача 3: ABBYY и обеденный перерыв

Сотрудники ABBYY не любят ходить на обед по одному. Поэтому каждый день в определенное время группа сотрудников собирает по всему офису желающих пообедать. В какой-то из дней Антон начал процесс сбора коллег для совместной трапезы. Процесс устроен следующим образом: Антон подходит к очередному своему другу, каждый из которых соглашается пойти с ним на обед с вероятностью ½. Если друг отказывается, то Антон расстраивается и прекращает процесс сбора, а если соглашается, то идет к следующему своему другу и предлагает ему тоже пойти вместе на обед. Антон достаточно общительный, так что у него бесконечно много друзей в компании.

Найдите математическое ожидание количества людей, которые придут в столовую (включая Антона).

Задача 4: Что будет выведено на экран?

Не ожидал я, что в четвертой задачке все же всплывет простыня сишного кода. 🙂 Но что поделать? Из песни слов не выкинешь!

#include <iostream>
using namespace std;
struct InnerBase {
      InnerBase() { cout << "InnerBase()" << endl; }
      virtual ~InnerBase() { cout << "~InnerBase()" << endl; }
};
struct InnerDerived : public InnerBase {
      InnerDerived() { cout << "InnerDerived()" << endl; }
      ~InnerDerived() { cout << "~InnerDerived()" << endl; }
};
struct Base {
      InnerBase B;
       Base() { cout << "Base()" << endl; }
      Base( const Base& der ) { cout << "Base(const Base&)" << endl; }
      virtual ~Base() { cout << "~Base()" << endl; }
};
struct Derived : public Base {
      InnerDerived D;
       Derived() { cout << "Derived()" << endl; }
      ~Derived() { cout << "~Derived()" << endl; }
};

int main()
{
      Derived derived;
}

Итак, что будет выведено на экран?

Правильные ответы

Присылай их сюда: maria.petrova@abbyy.com. Три победителя получат сертификаты с бессрочной лицензией на Abbyy FineReader 14 standard. На этот раз попробуем выбирать победителей случайным образом (а не вручать подарки первым троим), чтобы не заставлять читателей торопиться и дать время на обдумывание задач всем желающим.

Комментарии (7)

  • Если кто может, напишите пожалуйста решение задачи Даша и сейф. Конкурс наверное закончен уже, так что напишу тут - у меня пока есть только идея набрать все перестановки (или, правильнее сказать, размещения) из цифр, которые помнит Даша. Сортировать их. И потом, скормив первую перестановку, искать среди отсортированных ту, которая начинается с последних цифр только что скормленной. Брать подходящую, удалять из списка сохраненных, и так до победного конца. Выглядит простовато, потому любопытно решение)

  • Поддержка унылого легаси-кода - для самых послушных и усидчивых. Уж если ты настолько ботанист и усидчив, что решил все задачки, то будешь отлично выполнять такую нудную рутину как "поддержка легаси-кода".

  • Так и есть :-) По опыту знаю, что в конторах, в которых на собеседованиях устраивают настоящий экзамен, с дифф.уравнениями и т.п., работа заключается в поддержке кучки говнокода.

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

  • Не, в пень это всё. Никогда не умел решать дурацкие абстрактные задачи, что абсолютно не мешает мне 22 года разрабатывать софт...

    • Задачи, приведенные здесь, предполагают использование стандартных алгоритмов, поэтому назвать их абстрактными нельзя. Любой, кто прочитал хотябы одну классическую книжку - Скиену, Седжевика или Кормена без труда решит все предложенные задачи. Комментарии вида: "10 лет разрабатываю и не могу решить" меня всегда поражают. С какой предметной областью вы работаете, что вам не нужны алгоритмы?

      • Вполне поддерживаю первый коммент. Не везде в программировании нужна математика. Бизнеслогика приложений не всегда требует математических решений. И на этом можно долго и плодотворно работать.

        >>поэтому назвать их абстрактными нельзя
        Абстрактные они потому, что в задачах похода на обед все сотрудники ведут себя одинаково. Не это ли является первым признаком абстракции?

        Я, конечно, не считаю, что знать математику не нужно, но всё-таки на собеседовании надо спрашивать больше о задачах, которые реально встанут перед кандидатом, чтобы понимать, что кандидаты годятся именно для той работы на которую его хотят нанять.

        По хорошему ведь в компании Abbyy работают не только программисты, но и администраторы, и рекламщики, и продавцы. Поэтому название раздела следовало бы назвать "Задачи от компании Abbyy в отдел разработки ПО" (или как там он у них называется).