Федеральная Служба Опасности (malaya_zemlya) wrote,
Федеральная Служба Опасности
malaya_zemlya

Category:

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++) Что напечатает программа


#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) Программа рисует трехмерный полупрозрачный многогранник. В результате ошибки некоторые из сторон многогранника иногда не рисуются. В чем могут быть причины ошибки?

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

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 47 comments