January 5th, 2006

manandmoon

Google job interviews

Примеры вопросов, задаваемых на интервью компании Google.  Взято из жизни.

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 до 8

7. (C++) Что напечатает программа

Collapse )

8. (C++) Написать Singleton, правильно работающий в multi-threading режиме.

9. (Graphics) Сравнить z-buffering и w-buffering, какие преимущества и недостатки у каждого подхода?

10.(Graphics) Программа рисует трехмерный полупрозрачный многогранник. В результате ошибки некоторые из сторон многогранника иногда не рисуются. В чем могут быть причины ошибки?

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