Wednesday, December 1, 2010

Вопросы и ответы с собеседований в 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 &gt; 21);
// i равномерно распределено между 1 и  21
return i % 7 + 1; // результат равномерно распределен между 1 и 7

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


5)Опишите алгоритм обхода графа в глубину.

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

12 comments:

  1. Равномерно распределенное в интервале 1..7 можно и по другому получить.
    3/2*(rand5()-1)+1
    В скобках случайно распределенное в интервале 0..4. После умножения распределение меняется на равномерное в интервале 0..6. После прибавления единицы на 1..7.

    ReplyDelete
  2. Упс, спасибо, я забыл уточнить, что имеются в виду целые числа. В случае рациональных чисел задача действительно существенно упрощается.

    ReplyDelete
  3. 3/2*(rand5()-1)+1 - ответ неправильный.
    Возьмем возможные результаты rand5()-1:
    (каждый такой результат случается в одном из 5 случаев)
    1)0 * 1.5 = 0
    2)1 * 1.5 = 1.5
    3)2 * 1.5 = 3
    4)3 * 1.5 = 4.5
    5)4 * 1.5 = 7

    Здесь равным распределением даже не пахнет, не так ли?

    ReplyDelete
  4. 3/2*(rand5()-1)+1 - любой коэффициент, на который вы умножите результат Rand5() просто раздвинет или сдвинет 5 равновероятных модальных значений.

    И не важно будут ли они находиться в отрезке с 1 до 7 или с 1 до 5. В этом отрезке всегда будут лишь 5 равновероятных значений, а все остальные значения будут выпадать с вероятностью 0.

    Такой путь не ведет к решению задачи.

    ReplyDelete
  5. Насколько я понял, Anonymous имел в виду случай, когда rand5 возвращает не целые, а рациональные числа в диапазоне от 1..5

    ReplyDelete
  6. Мутекс принадлежит всегда одному едиственному потоку?

    Это высказывние неверно! Мютекс, как и Семафор принадлежит ядру или операционной системе.

    А вообще, проще будет сказать, что семафор, где count=1 - это и есть mutex.

    Mutex - регулирует эксклюзивный допуск к одному объекту, а семафор - к пулу объектов.

    В задаче с инкрементом - объект один.

    ReplyDelete
  7. mutex гарантирует, что только тот, кто его взял может его отпустить. Но он может быть также и полностью свободным, то есть не принадлежать никакому потоку.

    ReplyDelete
  8. count=1 это не единственное отличие. Мутекс может отпустить только тот поток, который его захватил. Семафор может освободить любой поток. Именно это я подразумевал под принадлежностью.

    http://en.wikipedia.org/wiki/Semaphore_%28programming%29#Semaphore_vs._mutex

    "In many cases a mutex has a concept of an "owner": the process which locked the mutex is the only process allowed to unlock it. In contrast, semaphores generally do not have this restriction, something the producer-consumer example above depends upon."

    ReplyDelete
  9. >>>>Насколько я понял, Anonymous имел в виду >>>случай, когда rand5 возвращает не целые, а >>>рациональные числа в диапазоне от 1..5

    Во-первых в условии задачи указаны целые числа... :-)

    А во-вторых, если он имел ввиду вещественные числа, то задам вопрос:

    Между 1 и 5 бесконечное количество вещественных чисел, не так ли?

    То есть вероятность выпадания каждого числа = 1/бесконечность -> 0.

    Представим, что число 2 у нас в этом случае выпадает в 2 раза чаще, чем число 3.

    Значит вероятность выпадания 2-х = 2/бесконечность, а 3-х = 1/бесконечность. То есть и в том и в другом случае она стремится к нулю.

    Вопрос: тогда как вообще написать функцию, которая дает не unified distribution на бесконечном пространстве значений?

    Может ли такая задача вообще иметь смысл?
    Или иными словами - почувствуйте разницу между 1/бесконечность и 0/бесконечность.
    :-)

    ReplyDelete
  10. >>>Мутекс может отпустить только тот поток, который его захватил. Семафор может освободить любой поток. Именно это я подразумевал под принадлежностью.

    Это верное замечание, но если вставить слова "всегда принадлежит", то и оно немного режет слух.

    Впрочем, наверное не стоит комментировать по мелочам, это правда.

    ReplyDelete
  11. >>> Вопрос: тогда как вообще написать функцию, которая дает не unified distribution на бесконечном пространстве значений?
    >>> Может ли такая задача вообще иметь смысл?

    Может, и имеет.
    Есть такое понятие как плотность вероятности: http://ru.wikipedia.org/wiki/%D0%9F%D0%BB%D0%BE%D1%82%D0%BD%D0%BE%D1%81%D1%82%D1%8C_%D0%B2%D0%B5%D1%80%D0%BE%D1%8F%D1%82%D0%BD%D0%BE%D1%81%D1%82%D0%B8
    которое, собственно и описывает случайные распределения в множестве R.

    И, пожалуй, самый известный пример неравномерного распределения на бесконечном пространстве: это нормальное распределение, оно же Гаусово
    http://ru.wikipedia.org/wiki/%D0%9D%D0%BE%D1%80%D0%BC%D0%B0%D0%BB%D1%8C%D0%BD%D0%BE%D0%B5_%D1%80%D0%B0%D1%81%D0%BF%D1%80%D0%B5%D0%B4%D0%B5%D0%BB%D0%B5%D0%BD%D0%B8%D0%B5

    ReplyDelete
  12. сумма двух равномерно распределённых случайных величин не будет равномерно распределённой!!!

    Смотрите пример 2 на http://sernam.ru/book_tp.php?id=60

    ReplyDelete