Задачи на собеседованиях

Спецподгон: задачи от компании «Яндекс»

Работали мы как-то с компанией «Яндекс» в соседних бизнес-центрах. Заходили к ним в гости и удивлялись, что в то время, как сотрудники нашей редакции отливают свинцовые литеры для печатных прессов, стоя по пояс в радиоактивных отходах в непроветриваемых помещениях, сотрудники Яндекса сидят в креслах за 800 евро и наслаждаются теплом от обогреваемых стен-перегородок. Хочешь работать так же? Легко! По вопросам трудоустройства в нашу редакцию пиши Степану на step@glc.ru, а по поводу Яндекса… впрочем, дадим им слово.

Больше половины сотрудников Яндекса вовсе не менеджеры по руководству общими вопросами и не операторы кофейных машин, а самые что ни на есть разработчики. Яндексу как воздух нужны front-end и back-end разработчики на С++, Python, Perl, Java, JavaScript. В основном в компании используются UNIX-плафтормы, но есть и разработка под Windows. Во многих сервисах формируются команды мобильной разработки, которые пишут под iOS, Android и Windows Phone.

Самая острая потребность в разработчиках C++. При этом все чаще появляются вакансии, связанные с машинным обучением, big data, распознаванием изображений и голоса, распределенными вычислениями. Далеко не всегда опыт работы с этими технологиями требуется обязательно. Есть команды разработчиков, которые занимаются исследовательскими задачами.

Вакансии открыты в Поиске, Браузере, Картах, Диске, Маркете. И в каждой из команд — своя специфика. Так, в Поиске и Картах больше востребовано знание алгоритмов, причем в Поиске уклон в сторону теории вероятностей и математической статистики, а в Картах — на графы. В Браузере больше сложных инженерных задач, поэтому требуются в первую очередь технические знания и в меньшей степени — алгоритмы.

Разработчики Яндекса подготовили читателям ][ задачи, которые могут встретиться на собеседовании в компании.

Спрашивает Андрей Плахов, руководитель службы функциональности поиска в Яндексе:

Задача 1

Дана функция на языке Python. Завершится ли когда-нибудь вызов dio()? Почему?

def dio():
   x = 1L
   while 1:
       for y in xrange(1, x):
           for z in xrange(1, y):
               if x*x == y*y + 12752041*z*z:
                   return "Found it"
       x = x + 1

Задача 2

Что делает эта программа на языке С++?

#include <cstdio>
struct EmptyList {
};
template <int N, class T>
struct IntList {
    static const int Head = N;
    typedef T Tail;
};
 
#define LIST1(N1) IntList<N1, EmptyList>
#define LIST2(N1,N2) IntList<N1, LIST1(N2) >
#define LIST3(N1,N2,N3) IntList<N1, LIST2(N2,N3) >
#define LIST4(N1,N2,N3,N4) IntList<N1, LIST3(N2,N3,N4) >
#define LIST5(N1,N2,N3,N4,N5) IntList<N1, LIST4(N2,N3,N4,N5) >
 
#define NUM2(x,y) 10*(x) + (y)
#define NUM3(x,y,z) 100*(x) + 10*(y) + (z)
#define NUM4(w,x,y,z) 1000*(w) + 100*(x) + 10*(y) + (z)
#define NUM5(v,w,x,y,z) 10000*(v) + 1000*(w) + 100*(x) + 10*(y) + (z)
 
#define DIFFER3(x,y,z) ((x) != (y) && (x) != (z) && (y) != (z))
#define DIFFER4(x,y,z,w) ((x) != (y) && (x) != (z) && (x) != (w) && DIFFER3(y,z,w))
#define DIFFER5(x,y,z,w,v) ((x) != (y) && (x) != (z) && (x) != (w) && (x) != (v) && DIFFER4(y,z,w,v))
 
template <class T> struct LSolve {
    static const int Answer0 = LSolve<IntList<0, T> >::Answer;
    static const int Answer1 = LSolve<IntList<1, T> >::Answer;
    static const int Answer2 = LSolve<IntList<2, T> >::Answer;
    static const int Answer3 = LSolve<IntList<3, T> >::Answer;
    static const int Answer4 = LSolve<IntList<4, T> >::Answer;
    static const int Answer5 = LSolve<IntList<5, T> >::Answer;
    static const int Answer6 = LSolve<IntList<6, T> >::Answer;
    static const int Answer7 = LSolve<IntList<7, T> >::Answer;
    static const int Answer8 = LSolve<IntList<8, T> >::Answer;
    static const int Answer9 = LSolve<IntList<9, T> >::Answer;
    static const int Answer = Answer0 + Answer1 + Answer2 + Answer3 + Answer4 + Answer5 + Answer6 + Answer7 + Answer8 + Answer9;
};
 
template <int U, int D, int A, int R, int K> struct LSolve<LIST5(U,D,A,R,K) > {
    static const int Answer =  
       NUM4(U,D,A,R) + NUM4(U,D,A,R) == NUM5(D,R,A,K,A) && (U != 0) && (D != 0) && DIFFER5(U,D,A,R,K) ?
        NUM5(D,U,R,A,K) : 0;
};
 
typedef LSolve<EmptyList> Solve;
 
int main(int argc, const char* argv[]) {
    printf("ДУРАК=%d\n", Solve::Answer);
}

Спрашивает Кирилл Сюзев, руководитель группы разработки Яндекс.Картинок

Задача 3

Есть исходный код программы:

#include <iostream>
#include <unistd.h>
#include <stdlib.h>
int main() {
std::cout << 1;
fork();
exit(0);
}

Что напечатается на экране и почему? Как изменится вывод, если заменить cout на cerr?

Задача 4

В программировании есть понятие LRU-кеша.

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

LRU-кеш таким образом выбирает: если места под элементы больше нет, он выбрасывает элемент, к которому дольше всего не обращались, и вместо него кладет новый.

Задача — написать такой кеш в виде С++ класса/классов.