Thursday, December 2, 2010

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

Продолжаю решать вопросы с собеседований в Google. Первый пост тут

Итак, сначала вопросы, для тех кто хочет решить самостоятельно:

6) Спроектируйте библиотеку классов для создания карточных игр
7) Вам нужно проверить, что у вашего друга есть ваш правильный телефонный номер, но вы не можете спросить его напрямую. Вы должны написать вопрос на открытке и дать её Еве, которая отнесет открытку Бобу и потом вернет ответ вам. Что следует написать на открытке помимо вопроса, чтобы Боб смог закодировать сообщение так, чтобы Ева не смогла расшифровать ваш телефонный номер? 
8) Как передаются Cookies в HTTP протоколе?
9) Спроектируйте таблицы SQL базы данных для системы проката автомобилей.
10) Напишите регулярное выражение которое матчит email-адрес.



А теперь, как бы я стал отвечать на эти вопросы. Повторюсь, тут нет 100% правильных ответов,  я не работаю в Google и не имею к никакого отношения к этой компании. Все, что написано ниже, должно рассматриваться исключительно как возможный вариант решения задачи, может быть не верный. Да, и, кстати, буду рад любым замечаниям и предложениям.

6) Спроектируйте библиотеку классов для создания карточных игр

Думаю, что это как раз тот вопрос, на который нет правильного ответа. Он призван проверить способность собеседуемого мыслить и выяснять детали задания. Непосредственно в вопросе недостаточно информации чтобы дать ответ. Посему, бы начал с дополнительных вопросов: Для чего нужна библиотека? Должна ли она реализовывать алгоритмы или визиуализацию? Какие карты? Стандартные черви-пики-буби-крести или таро и MTG тоже? Какие требования к безопасности, должны ли мы технически скрыть от игроков карты не принадлежащие им?

7) Вам нужно проверить, что у вашего друга есть ваш правильный телефонный номер, но вы не можете спросить его напрямую. Вы должны написать вопрос на открытке и дать её Еве, которая отнесет открытку Бобу и потом вернет ответ вам. Что следует написать на открытке помимо вопроса, чтобы Боб смог закодировать сообщение так, чтобы Ева не смогла расшифровать ваш телефонный номер?

Тут возможно много вариантов, самый простой попросить Боба перезвонить вам а на карточке написать смог ли он дозвониться. Хотя, это не по IT-шному.
По IT-шному, можно попросить Боба посчитать хэш телефонного номера и написать его. Но это не самый удачный способ, т.к. Ева сможет восстановить телефонный номер простым перебором (всевозможных номеров ведь не так много) Хэш мог бы сработать, если бы мы включить в сообщение соль (модификатор ключа) но в этом случае встает вопрос, что выбрать в качестве соли. Это должно быть что-то что знаете вы и знает Боб, но не знает Ева.

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

Не самый надежный способ: попросить Боба прислать сумму цифр. Ева вряд ли получит какую-то полезную информацию (если конечно ваш номер не 9-99-99) но и гарантий в 100% правильности проверки дать нельзя.
А еще, если Ева не знает телефонный номер Боба, а вы его знаете, то можно попросить Боба прислать XOR ваших телефонных номеров. В этом случае, применив XOR повторно вы сможете восстановить номер.

Фантазируем фантазируем, думаю, собеседующий будет доволен.


8) Как передаются Cookies в HTTP протоколе?

В HTTP-заголовке. Сначала сервер присылает заголовок вида:
Set-Cookie: name=value
Потом, если у клиента установлен сookie то он включает следующий заголовок в каждый ответ серверу:
Cookie: name=value
И снова за деталями, в википедию Удивительным образом, она содержит большинство ответов на вопросы собеседований.

9) Спроектируйте таблицы SQL базы данных для системы проката автомобилей.

Вопрос сродни 6-ому. Чем больше встречных вопросов получится задать – тем лучше. Я ничего не знаю о прокате автомобилей, а вы? Не думаю, что гугл ищет людей всю жизнь проектировавших базы для автопроката, скорее они предпочтут взять человека способного провести анализ. Так что, я бы начал с выяснения сути бизнеса: сдают машины в прокат, так да? А что они хотят от базы данных? А какие именно данные им нужны? А по каким признакам они классифицируют автомобили? А какие есть параметры у автомобилей? А какие характеристики у точек проката? итд. итп.

10) Напишите регулярное выражение которое матчит email-адрес.

А кто-нибудь задумывался на вообще, каким может быть email-адрес? Очень просто написать регулярное выражение которое будет проверять 99% email-адресов, думаю, что-то вроде этого:
^[A-Z0-9._%+-]+@[A-Z0-9.-]+\.[A-Z]{2,4}$
Но при желании, легко придумать адреса которые не являются валидными и тем-не менее матчатся этим выражением, и наоборот.
И речь идет не только о синтаксисе. Вот например asdweq@sdfsd.rtrw это валидный или нет? MS Word его подсвечивает, но мы же знаем что домена первого уровня с именем rtrw не существует.
Да, кстати, есть официальный стандарт, описывающий, каким должен быть email-адрес http://tools.ietf.org/html/rfc2822#section-3.4.1

8 comments:

  1. По задаче с телефоном и Евой - есть вариант попроще - это попросить Боба написать последовательность нечетных цифр своего телефона.

    В этом случае вероятность угадывания ничеожна мала - как для Боба, если он не знал телефона, так и для Евы, если Боб напишет правильные цифры.

    ReplyDelete
  2. Выражение для валидирования E-mail в пункте 10 будет работать только при Case-insensitive сравнении, иначе вероятность будет меньше 99 процентов.

    ReplyDelete
  3. А что если у Боба опечатка в одной цифре, причем именно в четной? Вероятность опечатки именно в одной цифре достаточно велика.

    ReplyDelete
  4. Согласен, эта проверка лишь позволяет ответить на вопрос знает ли он номер или нет. Опечатки так установить нельзя.

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

    Тут я могу добавить к упомянутым решениям лишь одно - чтобы усложнить жизнь Еве и упростить алгоритм - можно сделать ключом, например, те же нечетные цифры телефона, или любые другие из них.

    Например, каждую цифра D = f1(D(d+1)) * f2(D(d+d^2)), где D - значение, а d - позиция цифры в замкнутой по кругу последовательности номера.

    Впрочем от такого решения даже самому смешно. :-)

    Тут главное принцип, конечно.

    ReplyDelete
  5. Пусть Боб пришлет СМС на номер с содержимым, которое мы ему передадим на карточке.

    ReplyDelete
  6. нужно попросить Боба зашифровать сообщение, которое я написал на открытке ключом, в качестве которого выступает мой номер телефона :)
    Так я проверю,что он знает мой номер телефона, а Ева ничего не сможет узнать.А инструкции по алгоритму я напишу на открытке :)

    ReplyDelete
  7. Я пишу : Боб возьми алгоритм 3Des ,возьми мой номер телефона как ключ и зашифруй 1234 и пришли мне.(про padding я не говорю)У себя я сделаю ту же операцию и сравню с тем,что прислал Боб.
    Классный вопрос!!!5 балов !!!Или я не прав ? :)

    ReplyDelete
  8. Все правильно :) По-моему отличный вариант решения

    ReplyDelete