Здесь опубликован список вопросов с собеседований Google на должность разработчика.
Я не знаю правильных ответов на них, да и не на все из них есть правильные ответы, тем не менее, решить их будет интересной зарядкой для мозга. Буду рад любым комментариям.
Вопросов много, посему это растянется на несколько постов. Итак, поехали:
1)
Почему крышки для канализационных люков круглые?
Пожалуй, самый известный вопрос с собеседований гугл. Он уже столько раз обсуждался, что я даже не уверен, задавался ли он на самом деле в гугле. На самом деле, этот вопрос скорее проверяет способность рассуждать. Классический ответ на него можно найти в
википедии.
2)
Чем мутекс отличается от семафора? Кого из них вы будете использовать для того чтобы обезопасить операцию инкремент?
Прежде всего, мутекс бинарный, то есть либо занят – либо свободен. Либо открыт – либо закрыт. Семафор же может принимать множество значений от 0 до некоторого заданного максимального значения.
Но это еще не всё. Мутекс всегда приналежит одному единственному потоку. Этот поток его получает и он же обязан его вернуть. Семафор же, напротив, никому не принадлежит и может получить сигнал из любого потока (процесса).
Что же касается второй части вопроса, я буду использовать мутекс.
3)
Напишите программу на C которая измеряет скорость переключения контекста на UNIX/Linux.
В C я не силен, а вот написать программу измеряющую скорость переключения контекста на Java… давайте попробуем:
public class ContextSwitch implements Runnable{
private Object lock = new Object();
private volatile int counter = 0;
public static final int MAX_CNT = 1000000;
public void run() {
for(;;){
synchronized (lock){
counter++;
lock.notify();
if (counter<MAX_CNT){
try { lock.wait(10000); } catch (InterruptedException e) {}
}else{
break;
}
}
}
}
public static void main(String[] args) throws InterruptedException {
ContextSwitch cts = new ContextSwitch();
Thread t1 = new Thread(cts);
Thread t2 = new Thread(cts);
long startTime = System.currentTimeMillis();
t1.start();
t2.start();
t1.join();
long endTime = System.currentTimeMillis();
System.out.println(endTime - startTime);
}
}
На моем компьютере получается 100000 переключений в секунду.
4)
Вам дана функция возвращающая случайное число в диапазоне от 1 до 5. Напишите функцию которая будет возвращать случайное число в диапазоне от 1 до 7.
Дополнение: обе функции возвращают целые числа.
Т.к. вообще говоря, про распределение ничего не говорится, то можно написать всяческий бред. Я бы первым делом уточнил у собеседующего, какое распределение имеется в виду. Предположим, что равномерное, тогда ответ на эту задачу
int i;
do
{
i = 5 * (rand5() - 1) + rand5(); // i равномерно распределено между 1 и 25
} while(i > 21);
// i равномерно распределено между 1 и 21
return i % 7 + 1; // результат равномерно распределен между 1 и 7
Недостаток этого решения в том, что время его выполнения непредсказуемо и, пусть и с бесконечно малой вероятностью, может быть неограничено большим.
5)
Опишите алгоритм обхода графа в глубину.
Для каждой непройденной вершины необходимо найти все не пройденные смежные вершины и повторить поиск для них. Реализуется обычно либо с помощью стека либо с помощью рекурсии.
