воскресенье, 22 июня 2008 г.

Вопросы на собеседовании в Микрософт.



15 марта 2008-го года блоггер из Болгарии Светлин Наков опубликовал пост о своем, успешном, по его словам, собеседовании на позицию Program Manager в подразделении Микрософт в Дублине. Эта должность в Микрософт - аналог позиции team-leader в большинстве софтверных компаний.

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

Кстати, автор не утверждает что его ответы верны, он просто приводит свои ответы и говорит что именно с этими ответами он прошел собеседование...


Вопрос 1: Как бы вы обеспечивали безопасность при проектировании банковского ПО?

На этот вопрос нет точного ответа. Это вопрос мышления: следовать существующим стандартам в банковском секторе, установить общие политики безопасности (security policy и auditing policy), обеспечить безопасность сетевой инфраструктуры, серверов приложений, баз данных, обеспечить безопасность рабочих станций операторов, выхода в Интернет, мобильного банкинга и т.д. Подумать об аутентификации (смарт-картах), авторизации, безопасных протоколах и т.д.

Вопрос 2: У вас есть строка. Вы хотите перевернуть слова в ней. Например, “this is a string” –> “string a is this”. Спроектируйте алгоритм и реализуйте его. Вы не должны использовать String.Split. После того как напишите код, протестируйте его. Что вы будете тестировать? Какие тесты напишете?

Элегантное решение в 2 шага:

1) Перевернуть всю строку символ за символом.
2) Затем перевернуть символы в каждом слове.

Сначала надо будет написать метод

Reverse(string s, int startPos, int endPos);

Этот метод сначала протестировать в нормальных случаях (перевернуть середину слова, начало слова, конец слова, 1 символ, все буквы в строке). Проверить границы (на invalid range). Проверить с Unicode символами (состоящими из нескольких символов). Выполнить стресс-тест (строка размером 50Мб).

Написать метод

ReverseWords(string s);

Этот метод также сначала протестировать в нормальных случаях (несколько слов в одной строке с одним пробелом между словами), затем - с одним словом, с пустой строкой, со словами, разделенными несколькими пробелами. Проверить это со строкой, содержащей заглавные буквы.

Вопрос 3: В чем разница между тестированием методом черного ящика и методом белого ящика?

Тестирование методом черного ящика это тестирование без заглядывания в код. Просто проверка на некорректное поведение.

Тестирование методом белого ящика это инспектирование кода и предугадывание что может пойти не так. Этот метод дает возможность посмотреть внутри массивов (и проверить на проблемы с границами), циклов (проблемы лишней итерации), указателей, управления памятью (выделение/освобождение памяти) и т.д.

Вопрос 4: Что такое cross-site scripting (XSS)?

В контексте веба XSS, это когда текст пришедший от пользователя вставляется в HTML документ без фильтрации. Это может привести к выполнению JavaScript-кода в клиентском веб-браузере, доступу к куки, логированию клавиатурного ввода и важных данных (таких как номера кредитных карт).

Вопрос 5: Что такое SQL-injection?

SQL-injection это уязвимость пришедшая из динамического SQL, создаваемая конкатенацией строк с тем, что вводит пользователь. Например, строка

cmd = “SELECT * from USERS where LOGIN=’” + login + “‘ and PASS=’” + password + “‘”

Если вмесо имени пользователя ввести

“‘ OR 1=1 ‘;”

то сработает любое сочетание логин/пароль. Чтобы избежать SQL-injection атак нужно использовать параметрические команды или хотя бы фильтрацию [специальных символов].

Вопрос 6: Какой аспект мультитрединга наиболее спорный?

Возможно, это синхронизация и избегание дедлоков.

Вопрос 7: Разъясните по поводу дедлков. Как их избегать.

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

Вопрос 8: Вам известны какие-либо классические проблемы синхронизации?

Самая важная классическая проблема это проблема "производитель - потребитель". У вас есть несколько производителей и несколько потребителей. Производители время от времени производят какой-либо тип продукции, а потребители время от времени потребляют продукцию. У вас есть ограниченный размер буфера для продукции. Когда буфер полон, производитель ждет пока не появится место в буфере. Когда буфер пуст, потребитель ждет пока какой-либо производитель не положит что-либо в буфер.

Практическое использование паттерна "производитель - потребитель" например, такое: рассылка 1 000 000 е-мейлов (продукция) при помощи 25 запущенных тредов (потребители).

Вопрос 9: Вам нужно спроектировать большую распределенную систему с веб-интерфейсом и мобильным интерфейсом.
Через веб-интерфейс пользователи подписываются на котировки акций (выбирая тикер и временной интервал) и получают уведомление по SMS на свои мобильные телефоны для выбранного тикера и интервала.
Веб-сервис для получения цены с выбранного тикера считается уже cуществующим.


Использовать 3-уровневую архитектуру (ASP.NET, C # бизнес уровень, БД SQL Server).

Использовать очередь задач на бизнес уровне и пул работающих тредов (около 100 тредов) для выполнения задач.

Задача разбивается на 2 шага: запрос на цену к тикеру и отправка SMS. Эти шаги осуществляются синхронно (с разумными таймаутами).

У нас будет еще один тред, который осуществляет SQL-запрос к БД для получения подписчиков, соответствующих текущему времени и добавляющий задачи для уведомления по SMS.

Мы рассматриваем SMS-шлюз как внешнюю систему.

Вопрос 10: Как вы обеспечите безопасность системы уведомления о котировках?

Мы должны обеспечить безопасность всех ее частей:

1) Регистрация пользователей - должны проверять номер телефона при помощи кода подтверждения, присылаемого по смс. Должны хранить пароль в солтед хэш. Должны производить взаимодействие через HTTPs/SSL.
2) Сервер приложения с бизнес-логикой. Обезопасить хост, установив разумные ограничения, чтобы избежать перегрузки сервера.
3) Обеспечить безопасность БД (например, установив Windows-аутентификацию без использования пароля).
4) Обеспечить безопасность сети (например, используя IPSEC)
5) Обеспечить безопасность доступа к Web-сервису (WS Security).
6) Обеспечить безопасность мобильного телефона (например, посылая криптованные SMS-сообщения и декриптуя их проприетарным ПО, запущенным на телефоне).

Вопрос 11: Как бы вы писали распределенный веб-сканер (т.н. web-spider)? Вспомните Windows Live Search который обходит интернет каждый день.

У вас есть очередь URL для обработки и асинхронные сокеты которые обрабатывают URL-ы в этой очереди. Каждый обработчик имеет несколько состояний и вы описываете их в машине состояний. Использование тредов с блокирующими сокетами не будет масштабироваться. Вы можете использовать несколько тредов, если используется несколько процессоров. Веб-сканер не должен иметь состояния и не должен хранить свое состояние в базе. Это обеспечит хорошую масштабируемость.

Большой проблемой будет распределение БД. Это будет очень, очень большая БД. Ключ к масштабируемости базы это разделение на партиции, например, по домену сайта. Берем домен, вычисляем хэш-код и распределяем данные между узлами БД, основываясь на хэш-коде. Никакой БД сервер не сможет хранить все страницы из интернета, так что нужно будет использовать тысячи серверов БД и разделение на партиции.

Вопрос 12: У вас есть некоторое количество из пар символов, которые создают частичную последовательность между символами.
Каждая пара (a, b) означает, что a идет перед b.
Напишите программу, которая отображает последовательность символов, сохраняющую частичную последовательность (топологическая сортировка).


Есть 2 алгоритма:

1). Подсчитать количество прямых предшественников для каждого символа. Найти символ у которого нет предшественников, вывести [на экран] его и удалить его. Удаление уменьшает число предшественников у каждого его чайлда.
Повторять, пока не будут выведены все символы. Если обнаружится ситуация, где каждый символ имеет хотя бы одного предшественника, это будет означать зацикливание в графе (вывести "нет решения").
Использовать Dictionary<string, int> для хранения числа предшественников для каждого символа.
Использовать Dictionary<string, List<char>> для хранения чайлда для каждого символа.
Использовать PriorityQueue<char, int> для хранения символов, используя количество предшественников символа в качестве приоритета.
Время выполнения будет O(max(N*log N, M)), где N - количество символов и M - количество пары.

2) Создать граф из этих пар.
Использовать рекурсивный обход графа в глубину (DFS), начиная со случайной вершины и выводить вершины, когда происходит возврат из рекурсии. Повторять, пока не закончится. Топологическая сортировка будет выведена в обратном порядке. Время выполнения составит O(N + M).

Вопрос 13: У вас есть кокос. Имеется большое здание (n этажей). Если вы сбросите кокос с первого этажа,он может разбиться или не разбиться. Если не разбился, вы можете сбросить его со 2-го этажа. Сделав n попыток вы можете найти максимальный этаж, сбросив с которого кокос, вы его не разобьете.

Теперь, предположим, у вас есть 2 кокоса. Сколько попыток вам нужно сделать, чтобы найти максимальный этаж?


Эта проблема похожа на пазл. Вы можете использовать первый кокос и сбрасывать его с этажей: sqrt(n), 2*sqrt(n), …, sqrt(n) * sqrt(n). Это займет sqrt(n) попыток. После этого у вас будет интервал из sqrt(n) этажей, с которых можно последовательно сбрасывать второй кокос. Это займет 2*sqrt(n) попыток.

Вопрос 14: У вас есть 1000 рекламных кампаний. Для каждой из них у вас есть возвращение каждодневных инвестиций за определенный период времени в прошлом (например, за 1 год).

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

Если вы визуализируете только одну кампанию, вы можете использовать классический бар-чарт или круговую диаграмму, чтобы показать эффективность на еженедельной или ежемесячной основе. Если вы визуализируете все кампании за фиксированную дату, неделю или месяц, вы можете также использовать классические бар-чарт или круговую диаграмму. Проблема заключается в том, как совместить оба варианта.
Одним из решений является использование баров для каждой кампании и использование различных цветов для каждой недели в каждом баре.
Например, первая неделя - черная, затем вторая неделя - на 90% черная, а затем третья неделя - на 80% черная, и т.п. Наконец, мы будем иметь последовательность баров и самые темные бары будут показывает лучшие кампании, а наиболее светлые бары покажут худшее кампании.

Р.S. Автор пишет, что были 2 группы в Дублине, которые хотели пригласить его на работу по результатам собеседования: группа, работающая над Windows Live, и группа Office Tube, работающая над функциональностью записи и обмена видео для Microsoft Office.

1 комментарий:

En-Ru translations комментирует...

Спасибо за интересный материал. Перевод ваш?