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

Содержание статьи

• Задача 1: Константин и комиксы
• Задача 2: Даша и сейф
• Задача 3: ABBYY и обеденный перерыв
• Задача 4: Что будет выведено на экран?
• Правильные ответы

Когда на собеседовании задают вопросы в стиле «почему крышка от канализационного люка круглая?» — это как минимум странно. Простыни с сишным кодом, который нужно скомпилировать в голове и представить конечный результат, — нудно. Считаю, что самые интересные задачки — это задачи на общетехническое и логическое мышление. Очень рад, что сегодня товарищи из компании 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. На этот раз попробуем выбирать победителей случайным образом (а не вручать подарки первым троим), чтобы не заставлять читателей торопиться и дать время на обдумывание задач всем желающим.

Источник