Пришло время продолжить серию вопросов с собеседований. Следующие пять вопросов ниже. Начало этой серии тут и тут
Для желающих решать самостоятельно, сами вопросы:
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 | Взаимная блокировка | Взаимная блокировка |
12) Еще может быть что программа работает с какими-нибудь случайными числами на входе, например ввод пользователя.
ReplyDeleteНу и конечно же утечки памяти, с ними у тебя программа точно будет в разных местах падать :)
Еще как вариант, какой-нибудь внешний модуль, который работает нестабильно.
Ты кстати последний вопрос про диагностику в этом пункте не осветил вообще:)
14) Про finalize я бы поосторожнее отвечал. В твоем ответе меня смущает слово "непосредственно" перед тем как объект будет собран. Это непосредственно может весьма затянутся, например если объект попал уже в old generation и готов умереть, в первый запуск major сборки будет вызван finalize(), и только во второй он будет собран (по крайней мере CMS алгоритмом), а времени между ними может пройти ни один час :)
ReplyDelete12) Не написал, потому что не знаю ответа, я на C последний раз писал пару лет назад :) Вот если бы речь шла про Java...
ReplyDelete14) Согласен, спасибо за уточнение
Пример на 10й вопрос. Случай действительно похож на memory access violation. Как к этому случаю припарить стандартную библиотеку? Это можно сделать на примере такого контейнера как vector. Допустим переменную vector< my_obj> my_var;, где my_obj является классом, конструктор которого выделяет память под внутренние нужды. Таким образом, если для этого класса не переопределены конструктор копирования и оператор присваивания, то образцы данного класса, содержащиеся в контейнере vector могут лишиться выделенных областей памяти в том случае, когда vector сделает перевыделение памяти, содержащей эти образцы. Во время перевыделения, объекты в новом буфере примут значения объектов в старом буфере и для каждого объекта в старом буфере будет вызван его деструктор, который освободит память. Таким образом копии объектов в новом буфере будут поломаны и дальнейшее их использование будет приводить к непредсказуемым результатам.
ReplyDelete