1. (Algorithms) Написать функцию
int div(int a, int b)
, выполняющую целочисленное деление без использования оператора /2. (Graphics) Дан массив байтов screen, представляющий собой буфер для картинки размером w на h пикселей с разрешением 1 бит на пиксель. Нарисовать на изображении горизонтальную линию от точки (x1,y) до точки (x2,y)
3. (Graphics) Даны 3х-мерные координаты точек A,B,C,P и Q. Написать функцию, которая определяет, пересекает ли отрезок PQ треугольник ABC
4. (Algorithms) Даны два массива чисел:
int *a, *b
. Размеры массивов sizea
и sizeb
соответственно. После конца массива b у нас есть дополнительно памяти на sizea
чисел. Оба массива отсортированы по возрастанию. Слить их в один отсортированный массив, располагающийся по адресу b
, не используя никаких временных буферов. Разумеется, желательно, чтобы на это ушло не более O(sizea+sizeb
) времени5а.(Algorithms) Дан массив
int a[n]
, найти его медиану (т.е. такое число, что половина элементов массива имеют большее значение, а половина — меньшее). Желательно затратить на процедуру O(n) времени.5b. Теперь предположим, что числа эти находятся не на одном компьютере, а на M компьютерах, и никак в память одного компьютера одновременно не помещаются. Написать распределенный алгоритм нахождения медианы. Оценить скорость его выполнения.
6. (Algorithms) Дана функция
int rand5()
, которая с равной вероятностью выдает числа от 1 до 5. Написать на ее основе функциюint rand8()
, которая, соответственно, с равной вероятностью возвращает числа от 1 до 87. (C++) Что напечатает программа
#include <iostream> using namespace std; class A { public: A() { PrintStuff(); } virtual void PrintStuff() { cout<<"A!!!"<<endl; } }; class B : public A { public: B() { PrintStuff(); } virtual void PrintStuff() { cout<<"B!!!"<<endl; } }; int main(int argc, char* argv[]) { B b; return 0; }
8. (C++) Написать Singleton, правильно работающий в multi-threading режиме.
9. (Graphics) Сравнить z-buffering и w-buffering, какие преимущества и недостатки у каждого подхода?
10.(Graphics) Программа рисует трехмерный полупрозрачный многогранник. В результате ошибки некоторые из сторон многогранника иногда не рисуются. В чем могут быть причины ошибки?
Вопросы, вообще говоря, могут быть самые разные. Никаких стандартных списков у них, вроде, нет, каждый интервьюер сам решает, что спрашивать. Некоторые вообще задачек не задают, а ведут разговоры за жизнь. В целом, тенденция такая, что самые сложные вопросы оставляют на конец.