Интервью

Сейчас прошёл телефонное интервью с известной конторой. Волновался так, что забыл слово Socket. Ещё бы! Пять лет не собеседовался...

Интервью проходило где-то час и на английском языке. Хорошо, что ещё с русским коллегой из Питера. А то из-за волнения английский у меня тоже хромал.

Сначала меня спросили, что происходит с данными с момента ввода URL в браузере до получения ответа сервера. Я вспомнил лекции, которые читал студентам в ЛИАПе, и добрался аж до протокола TCP.

Далее меня спросили про двоичные деревья поиска. С математикой у меня что-то стало туго, но я таки вспомнил про сложность алгоритма поиска O(lg n), хотя вывести не мог. Потом надо было найти пересечение двух деревьев. Программу писал в Google Docs, а интервьюер её там смотрел синхронно. Написал простой перебор всех элементов сложностью O(n) и метод поиска сложностью O(lg n). Предложил способ оптимизации поиска для этого случая.

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