Федеральная Служба Опасности


Previous Entry Share Next Entry
Google job interviews
manandmoon
malaya_zemlya
Примеры вопросов, задаваемых на интервью компании 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) Программа рисует трехмерный полупрозрачный многогранник. В результате ошибки некоторые из сторон многогранника иногда не рисуются. В чем могут быть причины ошибки?

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

  • 1
6-z понравилась :) scaling of probabilities.

Вопрос 6 задавал на интервью один товарищ из Amazon Personalization несколько лет назад.

Программа из вопроса 7 на Яве и на C++ даст разные ответы. Вообще вызывать виртуальные функции из конструктора - моветон.

Ага. Именно про моветон и следовало ответить. А если пофиг моветон, тогда что?

Тогда, оказывается, программа напечатает:

A!!!
B!!!

(проверено на gcc и MSVC. Ни я, ни интервьюер этого не знали :)

пригорюнившись

Не работать мне в Гугле...

Re: пригорюнившись

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

5а. Разбить массив на две половины, как в быстрой сортировке, но применить процедуру рекурсивно не к обеим половинам, как в быстрой сортировке, а только к содержащей средний элемент.

5б подумаю.

5а. Так O(n log n) выходит, нет?

стильно. особенно впечатляет разброс областей, из которых взяты задачи

Для именно 8 у 6й задачки предлагаю так... a=rand5(); b=rand5(); return (a&3)<<1 ^ (b&3).
Есть какой-нибудь способ лучше?

Ах от 1, а не от 0... Ну значит 1+((a-1)&3)<<1 ^ ((b-1)&3)

(6) Почему бы не выводить rand_5 до первой пятерки, которая перекинет flag, и далее выводить 4+rand_5, которая перекинет флаг -- и так далее.
flag=0;
function rand_8() {
x=rand_5();
if x==5 {flag=(flag+1)%2; next}
print x+flag*4
}

По моему, я как-то не так понял...
чтобы получить из приведенной функции число, ну скажем, тройку, нужно, чтобы либо в первом же раунде выпало 3, либо чтобы в первом и втором раунде выпало 5, а в третьем раунде 3, либо в раундах с первого по четревтый выпадали споршные 5ки, а потом выпало 3 итп
p(3)=1/5+1/125+..=5/24>1/8

А нам хотелось бы 1/8


(Deleted comment)
(no subject) (Anonymous) Expand
(no subject) (Anonymous) Expand
(no subject) (Anonymous) Expand
А так

int rand4()
{
int res;
do
{
res = rand5();
}
while (res == 5);
return res;
}
int rand8()
{
return rand4() + rand4();
}

Почти правильно, но так, как написано, распределение будет не от 1 до 8, а от 2 (1+1) до 8(4+4). Равномерным оно тоже не будет
8 выпадет с вероятностью 1/16 (если оба раза выпадет 4), а 3, скажем, - с вероятностью 1/8 (если выпадет 1 и 2 или 2 и 1)

Ух тыж-ка, я такое люблю:

1. Деление, есть последовательное вычитание, фперед
int div(int a, int b) {
for( unsigned int aa = abs(a), ab = abs(b), nVal = 0; aa >= ab; ++nVal, aa -= ab );
return nVal * (a > 0 ? 1 : -1) * (b > 0 ? 1 : -1);
}
Можно было сразу вычесть ab-1 из aa и сравнивать с нулем.
2. void line( int x1, int x2, int y ) {
if( y < 0 || y >= h ) return;
if( x1 > x2 ) swap(x1, x2);
x1 = max( 0, x1 ); x2 = min( w - 1, x2 );
for( int i = x1, nPoint = x1 + y * w; i <= x2; ++i , ++nPoint) {
const int nByte = nPoint / 8;
const int nBit = nPoint % 8; (или 8 - nPoint % 8)
screen[nByte] |= 1 << nBit;
}
}
Можно оптимальней написать, вынести деление за цикл, а в цикле прибавлять 1 к биту, если перевалит за байт, то +1 байт и 0 бит.
3.Решение в лоб. Пусть пересекает в некой точке M. Проведем луч AM и пусть он пересекает сторону BC в точке M’. Выпишем уравнения: M лежит на прямой PQ. M лежит на прямой AM’. M’ лежит на прямой BC добавим неравенства, у нас же отрезки, а не прямые. Как-то там преобразуем, думаю оно решится. Но слишком громоздко.

Второй вариант, строим уравнения плоскостей: ABC, PAB, PBC, PAC. Подставляем во все уравнения точки P и Q. Если для ABC знаки разные, а для остальных трех одинаковые, то пересекает.
4. void grip( int *a, int *b ) {
//двигаем B до упора вправо
for( int i = sizeb-1; i >= 0; --i )
b[i+sizea] = b[i];
//сливаем
for( int nA = 0, nB = sizeb, nBMax = sizea + sizeb, i = 0; nA < sizea; ++i )
if( nA >= sizea )
b[i] = b[nB++];
else if( nB >= nBMax )
b[i] = a[nA++];
else if(a[nA] > b[nB])
b[i] = a[nA++];
eles
b[i] = b[nB++];

}
5. a) Ну за NlogN тривиально, думаем как сделать за N. нет ничего другого, как сделать декомпозицию. Разобьем все множества на под-множества (берем нечетную длину, нам так удобней) там по 5 или 7 или ... эллементов. Понаходим медианы во всех маленьких подмножествах. Дальше получим массив медиан. Ничего не остается, как сделать ту же процедуру опять, нам в конце концов нужен один кандидат на медиану, зная его мы потом разобьем первоначальный масив относительно этого кандидата и найдем правильную медиану. Все бы хорошо, но эта рекурсивная процедура поиска кандидата нам даст опять таки log в сложности. Так что я не знаю пока как решить

b) Смысл по идее должен быть тот-же. Просто прйдется разбивать распределенные массивы относительно кандидата в медиану, но по идее это не должно увеличить сложность.

6. Если надо 8, то значит задача сгенерить равномерно распределенные кол-вом кратным 8. Вызываем rand5 два раза, получаем 25 вариантов, надо 24. Решение простое, просто откидываем один любой вариант, какой угодно (в случае его выпадания повторяем процедуру), на решение это не повлияет, rand5 независим от предыдущего значения, так что вызовем мы его два раза или 10 разницы нет. Все бы хорого, но приведенная выше схема не является алгоритмом, надо еше думать.
7. По стандарту unexpected behavior, а в реальности:A, B. Во время вызова конструктора vTable еще не существует, конструктора вызываются снизу вверх.
8. Пишу на мета-языке:
template
[Error: Irreparable invalid markup ('<class [...] _t,>') in entry. Owner must fix manually. Raw contents below.]

Ух тыж-ка, я такое люблю:

1. Деление, есть последовательное вычитание, фперед
int div(int a, int b) {
for( unsigned int aa = abs(a), ab = abs(b), nVal = 0; aa >= ab; ++nVal, aa -= ab );
return nVal * (a > 0 ? 1 : -1) * (b > 0 ? 1 : -1);
}
Можно было сразу вычесть ab-1 из aa и сравнивать с нулем.
2. void line( int x1, int x2, int y ) {
if( y < 0 || y >= h ) return;
if( x1 > x2 ) swap(x1, x2);
x1 = max( 0, x1 ); x2 = min( w - 1, x2 );
for( int i = x1, nPoint = x1 + y * w; i <= x2; ++i , ++nPoint) {
const int nByte = nPoint / 8;
const int nBit = nPoint % 8; (или 8 - nPoint % 8)
screen[nByte] |= 1 << nBit;
}
}
Можно оптимальней написать, вынести деление за цикл, а в цикле прибавлять 1 к биту, если перевалит за байт, то +1 байт и 0 бит.
3.Решение в лоб. Пусть пересекает в некой точке M. Проведем луч AM и пусть он пересекает сторону BC в точке M’. Выпишем уравнения: M лежит на прямой PQ. M лежит на прямой AM’. M’ лежит на прямой BC добавим неравенства, у нас же отрезки, а не прямые. Как-то там преобразуем, думаю оно решится. Но слишком громоздко.

Второй вариант, строим уравнения плоскостей: ABC, PAB, PBC, PAC. Подставляем во все уравнения точки P и Q. Если для ABC знаки разные, а для остальных трех одинаковые, то пересекает.
4. void grip( int *a, int *b ) {
//двигаем B до упора вправо
for( int i = sizeb-1; i >= 0; --i )
b[i+sizea] = b[i];
//сливаем
for( int nA = 0, nB = sizeb, nBMax = sizea + sizeb, i = 0; nA < sizea; ++i )
if( nA >= sizea )
b[i] = b[nB++];
else if( nB >= nBMax )
b[i] = a[nA++];
else if(a[nA] > b[nB])
b[i] = a[nA++];
eles
b[i] = b[nB++];

}
5. a) Ну за NlogN тривиально, думаем как сделать за N. нет ничего другого, как сделать декомпозицию. Разобьем все множества на под-множества (берем нечетную длину, нам так удобней) там по 5 или 7 или ... эллементов. Понаходим медианы во всех маленьких подмножествах. Дальше получим массив медиан. Ничего не остается, как сделать ту же процедуру опять, нам в конце концов нужен один кандидат на медиану, зная его мы потом разобьем первоначальный масив относительно этого кандидата и найдем правильную медиану. Все бы хорошо, но эта рекурсивная процедура поиска кандидата нам даст опять таки log в сложности. Так что я не знаю пока как решить

b) Смысл по идее должен быть тот-же. Просто прйдется разбивать распределенные массивы относительно кандидата в медиану, но по идее это не должно увеличить сложность.

6. Если надо 8, то значит задача сгенерить равномерно распределенные кол-вом кратным 8. Вызываем rand5 два раза, получаем 25 вариантов, надо 24. Решение простое, просто откидываем один любой вариант, какой угодно (в случае его выпадания повторяем процедуру), на решение это не повлияет, rand5 независим от предыдущего значения, так что вызовем мы его два раза или 10 разницы нет. Все бы хорого, но приведенная выше схема не является алгоритмом, надо еше думать.
7. По стандарту unexpected behavior, а в реальности:A, B. Во время вызова конструктора vTable еще не существует, конструктора вызываются снизу вверх.
8. Пишу на мета-языке:
template <class _T, std::string _Name>
class CSingelton {
CSingelton() {}
~ CSingelton() {}
//
class CMutexLock {
public:
CMutexLock() : m_hMutex(CreateMutex(_Name)) {}
void Lock() { … }
private:
HANDLE m_hMutex;
};
public:
static _T& GetObject() {
if( ! m_pInst ) {
CMutexLock Lock;
if( ! m_pInst ) m_pInst = new _T;
}
return * m_pInst;
}
private:
static volatile _T* m_pInst;
};
template <class _T, std::string _Name> volatile typename _T* CSingelton:: m_pInst = NULL;

9. Даже не знаю, что это такое
10. Только фантазирую, ибо далек от этого: округление, специфика представление машинного числа.

Ultras

P.s. а сколько времени давали, я же понимаю это было интевью, то есть отвечать надо было сходу?

Почти сходу. Минут 5 обычно все-таки можно было поразмышлять..

1. В принципе правильно, конечно, но страшно неэффективно. (попробуйте 1000000 поделить на 10). (Hint:Лучше столбиком...)
2. Аналогично
3. Вторым вариантом все реально и пользуются
4. Есть простой способ оптимизировать раза в 2.
5а. В комментах есть хороший алгоритм. Можно еще воспользоваться Radix Sort-ом (ибо все int). Идея Radix Sort-a почему-то спрашивающему не понравилась : \
5b. Есть несколько вариантов, все довольно хитрые. Как я понял, это был "вопрос на засыпку"
6. На самом деле ответ совершенно правильный, если подумать, то можно доказать, что не пропуская чисел решить задачу нельзя. Призовая игра: подсчитайте среднее время выполнения алгоритма.
7. Все верно
8. Все, хорошо, но по-моему мутекс может создаться дважды (если процессы переключатся в момент присваивания m_hMutex)
9. Это разные методы определения какие части 3х мерного объекта видны на экране. Один работеат лучше для близких объектов, другой - для далеких.
10. Если не знать ответа на 9, то объяснить тяжело. Грубо говоря, с этими алгортитмами непрозрачные предметы можно рисовать в любом порядке, а прозрачные и полупрозрачные -только от дальних к ближним.

(no subject) (Anonymous) Expand
int rand8()
{
int val=0;
for(int i=0;i<8;i++)
val+=rand5();
return val/5;
}

int rand01() // returns 0 or 1
{
int r;
while((r=rand5()) > 2);
return r-1;
}

int rand8()
{
return 4*rand01() + 2*rand01() + rand01() + 1;
}


  • 1
?

Log in

No account? Create an account