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

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

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

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

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


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


11) Напишите функцию f(a,b) которая получает на вход две строки a и b и возвращает строку, содержащую символы содержащиеся в обеих строках, в том порядке, в котором они перечислены в строке a. Напишите версию с алгоритмической сложностью O(N²) и 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	Взаимная блокировка	Взаимная блокировка