Вопросы и ответы с собеседований в Google

Здесь опубликован список вопросов с собеседований 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)Опишите алгоритм обхода графа в глубину.

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