Monday, December 6, 2010

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

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

Для желающих решать самостоятельно, сами вопросы:

11) Напишите функцию f(a,b) которая получает на вход две строки a и b и возвращает строку, содержащую символы содержащиеся в обеих строках, в том порядке, в котором они перечислены в строке a. Напишите версию с алгоритмической сложностью O(N2) и O(N)
12) Вам дана программа, которая падает во время работы. Вы запустили её 10 раз в дебаггере и обнаружили, что она никогда не падает в одном и том же месте. Известно что программа однопоточная и использует только стандартную библиотеку С. Что может вызывать подобное поведение? Как вы проверите свои гипотезы?
13) Объясните, как работает контроль насыщения (congestion control) в TCP?
14) В Java, в чем разница между final, finally и finalize?
15) Что такое многопоточное программирование и что такое взаимная блокировка (deadlock)?

Продолжение...


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


11) Напишите функцию f(a,b) которая получает на вход две строки a и b и возвращает строку, содержащую символы содержащиеся в обеих строках, в том порядке, в котором они перечислены в строке a. Напишите версию с алгоритмической сложностью O(N2) и O(N)

Первый вариант прост – это фактически двойной цикл по строкам:
public String fN2(String a, String b){
        StringBuilder res = new StringBuilder();
        Set<Character> used = new HashSet<Character>();
        for(int i=0; i< a.length(); i++){
            char ch = a.charAt(i);
            if (!used.contains(ch)){
                if (b.indexOf(ch) >= 0){
                    res.append(ch);
                    used.add(ch);
                }
            }
        }
        return res.toString();
}
Второй вариант сложнее, необходимо исключить внутреннюю итерацию по b, для этого я заменил её HashSet-ом, известно, что алгоритмическая сложность поиска в HashSet O(1). Стало быть, общая сложность алгоритма O(N)
public String fN(String a, String b){
        StringBuilder res = new StringBuilder();
        Set<Character> used = new HashSet<Character>();
        Set<Character> inB = new HashSet<Character>();
        for(char ch : b.toCharArray()){
            inB.add(ch);
        }
        for(int i=0; i< a.length(); i++){
            char ch = a.charAt(i);
            if (!used.contains(ch) && inB.contains(ch)){
                res.append(ch);
                used.add(ch);
            }
        }
        return res.toString();
    }
Если известно, какие символы могут содержать строки, например, известно что это ASCII строки, то можно заменить HashSet массивом boolean[] в котором, хранить информацию о наличии того или иного символа. Но, т.к. у нас диапазон символов по условию никак не ограничен, то этот вариант не подходит. Хотя, и требования по памяти у нас тоже не ограничены. В общем, это можно спросить на собеседовании.

12) Вам дана программа, которая падает во время работы. Вы запустили её 10 раз в дебаггере и обнаружили, что она никогда не падает в одном и том же месте. Известно что программа однопоточная и использует только стандартную библиотеку С. Что может вызывать подобное поведение? Как вы проверите свои гипотезы?

Вот опять, вопрос на который я не знаю ответа, т.к. никогда ничего серьезного на C не писал. Но, что приходит в голову, раз программа падает в разных местах, то скорее всего проблема в том, что где-то кто-то пишет не в ту область памяти, так называемая memory overwrite проблема. Возникает, например, в случае если memcpy вызвана с неправильными аргументами:
char *a = malloc(10*sizeof(char)); memcpy(a, data, dataLen); //dataLen слишком большой


13) Объясните, как работает контроль насыщения (congestion control) в TCP?


Подробно, его работа описана в RFC 2581
Если на пальцах…
Для чего это нужно? TCP протокол отправляет данные в виде пакетов, получатель, на каждый полученный пакет, отправлят подтверждение о доставке. Пакет может быть не доставлен по ряду причин. И тут с одной стороны, требуется обеспечить максимальную скорость передачи данных (т.е. идеальный вариант – отправлять пакеты подряд не дожидаясь подтверждения доставки). С другой стороны, получатель должен корректно обрабатывать ситуации, когда пакеты доставлены в неправильном порядке, полученны дубликаты, или требуется повторная доставка (т.е. идеальный вариант – отправлять следующий пакет только после получения подтверждения о предыдущем)
Таким образом, нужно контролировать, чтобы отправитель не посылал данные в сеть быстрее чем их может получить получатель.
Для этого используется механизм «окна»: принимающая сторона отправляет передающей стороне размер приемного буфера. Приемный буфер позволяет решать проблему пакетов полученных в неправильном порядке. Передающая сторона сохраняет этот размер и передает данных не более, чем указал приемник. Далее, передающая сторона основываясь на подтверждениях полученных от приемной стороны и времени отклика использует серию алгоритмов чтобы контролировать поток данных. Стандартный набор алгоритмов, перечисленный в RFC: slow start, congestion avoidance, fast retransmit и fast recovery


14) В Java, в чем разница между final, finally и finalize?


А что собственно между ними общего?
final – это ключевое слово определяющее неизменяемую переменную или не переопределяемый метод или ненаследуемый класс в Java.
finally – это блок в конструкции try{}catch{}finally{} который всегда выполняется, независимо от результатов выполнения try
finalize() – это метод класса Object, который служит для освобождения ресурсов при сборке мусора. Этот метод вызывается у объекта непосредственно перед тем как он будет собран сборщиком мусора.


15) Что такое многопоточное программирование и что такое взаимная блокировка (deadlock)?

 
Многопоточность это свойство платформы, состоящее в том, что процесс порожденный в операционной системе может состоять из нескольких потоков выполняющихся параллельно. По сути это квазимногозадачность на уровне одного исполняемого процесса, при этом все потоки имеют общее адресное пространство.
Взаимная блокировка это ситуация в многозадачной среде, при которой несколько процессов находятся в состоянии ожидания ресурсов, заблокированных самими этими процессами, простейший вариант дедлока:
Предположим, что у нас есть два процесса и каждый из них хочет захватить ресурсы A и B. При этом первый процесс сначала захватывает ресурс А, а потом пытается захватить ресурс B. А второй процесс наоборот, сначала захватывает ресурс B, а потом пытается захватить ресурс A. В таком случае, возможна ситуация:
ШагПроцесс 1Процесс 2
1Захватывает ресурс А
2Захватывает ресурс B
3Ожидает ресурс BОжидает ресурс A
4Взаимная блокировкаВзаимная блокировка

4 comments:

  1. 12) Еще может быть что программа работает с какими-нибудь случайными числами на входе, например ввод пользователя.
    Ну и конечно же утечки памяти, с ними у тебя программа точно будет в разных местах падать :)
    Еще как вариант, какой-нибудь внешний модуль, который работает нестабильно.

    Ты кстати последний вопрос про диагностику в этом пункте не осветил вообще:)

    ReplyDelete
  2. 14) Про finalize я бы поосторожнее отвечал. В твоем ответе меня смущает слово "непосредственно" перед тем как объект будет собран. Это непосредственно может весьма затянутся, например если объект попал уже в old generation и готов умереть, в первый запуск major сборки будет вызван finalize(), и только во второй он будет собран (по крайней мере CMS алгоритмом), а времени между ними может пройти ни один час :)

    ReplyDelete
  3. 12) Не написал, потому что не знаю ответа, я на C последний раз писал пару лет назад :) Вот если бы речь шла про Java...

    14) Согласен, спасибо за уточнение

    ReplyDelete
  4. Пример на 10й вопрос. Случай действительно похож на memory access violation. Как к этому случаю припарить стандартную библиотеку? Это можно сделать на примере такого контейнера как vector. Допустим переменную vector< my_obj> my_var;, где my_obj является классом, конструктор которого выделяет память под внутренние нужды. Таким образом, если для этого класса не переопределены конструктор копирования и оператор присваивания, то образцы данного класса, содержащиеся в контейнере vector могут лишиться выделенных областей памяти в том случае, когда vector сделает перевыделение памяти, содержащей эти образцы. Во время перевыделения, объекты в новом буфере примут значения объектов в старом буфере и для каждого объекта в старом буфере будет вызван его деструктор, который освободит память. Таким образом копии объектов в новом буфере будут поломаны и дальнейшее их использование будет приводить к непредсказуемым результатам.

    ReplyDelete