Задачка на сообразительность, впору задавать на собеседовании.
Задача
Вы находитесь в аэропорту и опаздываете на собеседование в Google, ваш мобильник сел, и вам приходится вызывать такси из таксофона находящемуся внутри здания. После этого вы идете на стоянку таксистов и должны найти именно вашего таксиста, так как только он повезет вас короткой дорогой и вы не опоздаете. У таксиста есть табличка с маркером, вопрос: Что вы должны попросить написать таксиста на табличке, чтобы опознать его.
Условие 1: На стоянке все остальные таксисты — очень логичны и меркантильны, и узрев действия вашего таксиста повторят их.
Условия 2: Вы разговаривали с оператором, который еще не знал какой таксист будет вас обслуживать, то есть вы не можете узнать о нем ничего.
Ответ
Поскольку задачка моя, то и о правильности ответов судить мне, пишите комментарии (и пропустите следующий абзац, если не хотите обламывать себе кайф от решения ;)
Для начала немного о неправильных решениях:
- Если вы попросите написать ваше имя — все таксисты напишут тоже самое
- Попросите написать номер своей машины — таксисты быстро сообразят, и напишут каждый свой
- Попросите написать координаты на стоянке — все остальные тоже напишут свои
А теперь несколько возможных вариантов ответа:
Одно из решений — водитель должен написать MD5(номер машины + соль которую я сообщу по телефону), но как вы будете это вычислять (да и таксист тоже).
Второй вариант — водитель должен написать номер машины зашифрованный Виженером, ключ вы сообщаете по телефону. (таксисты могут конечно успеть расшифровать, но тогда вам надо поторопится).
Третий вариант — водитель должен написать некую контрольную сумму из номера его машины и ключевого слова которое вы сообщите.
А теперь вторая задачка, каким образом можно ускорить поиск таксиста, что он должен написать?
А что если все таксисты слышат, что говорит оператор искомому таксисту?
Такой вариант подойдет? http://www.delphiplus.org/humor/images/work_for_meal.jpg :)
Нет, т.к. боян :)
Пускай напишет что-нить пошлое :) Типа “я – чмо!”. Неужели остальные таксисты настолько меркантильны, что смогут повторить это?
Ради денег и не на такое пойдешь.
1.Следующий клиент едет бесплатно
2.I’m gay
3.Писать на японском, его сложно повторить
Все меркантильны и логичны, что может один, могут и другие. Если один знает японский, значит и все остальные знают, а я вот нет :)
Пусть напишет: “Не работаю”
Или пусть напишет: “Отвезу за 1 рубль”, а сам не соглашается везти за рубль.
Стоит чуть-чуть доработать вашу версию, и получится еще один правильный вариант.
Достатньо простий варіант: таксист приїжджає на стоянку, пише на табличці “Не працюю”. Інші такого не повторять, бо тоді втратять інших клієнтів.
Если вы пишите любой пусть даже хэш – другие таксисты тоже повторят его, так что это не очень то и решение.
Они смогут повторить текст, либо тоже напишут хэш от номера, но не зная соли, их текст не пройдет проверку.
А нельзя перезвонить через некоторое время диспетчеру и узнать-таки номер машины.
Но если вдруг нельзя – надо попросить таксиста написать на табличке цену, в 10 раз превышающую тариф. То есть например “Сансет-бульвар (или где мы там) – $10 000”
Если все остальные таксисты логичны – то они попытаются цену перебить, и напишут меньше.
Ну или еще.
Если диспетчер может попросить таксиста что-то написать на табличке, стало быть, диспетчер с водителем общаться может. Значит, просим его “пусть напишет “Что сказал Константин Сергеевич Станиславский половом в трактире после выпитого на пару с Владимиром Ивановичем Немировичем-Данченко штофа водки?” и попросить запомнить “Не верю”. Прийдется обойти всех таксистов, но вряд ли кто-то угадает правильный ответ.
Второй вариант со связкой вопрос-ответ принимается.
А теперь постарайтесь ответить на вторую часть задачки скрытой в “ответе” – как ускорить процесс опознания, ведь у вас есть ограничение по времени.
Можно ничего не писать, просто поднять пустую табличку, таксисты не поймут зачем он это делает и кого встречает.. :)
Также можно написать:
– количество пальцев, которыми держит табличку + контрольное число известное вам
– две линии если двумя руками держит, 1 если одной (ну или цифры)
– ну и можно обеденить эти варианты
Интересный вариант с использованием пальцев, мне нравится.
номер машины + чексум какой-нибудь, пусть будет трехзначное число, равное сумме квадратов всех чисел номера машины, что проверить будет очень просто
сложно проверить – очень много вычислений даже если всего 10 машин, а нужно еще успеть на собеседование, правда есть калькулятор в мобильнике, но он разрядился, и еще номер может быть только из букв например “колян”
Или произвести алгоритмическое действие над номером автомобиля. И результат написать на табличке. Какое действие сообщит оператор.
Но этот вариант не проканает, если по рации другие водители слышали что нужно сделать.
порядковый номер, по которому стоит таксист считая например с левого верхнего угла автостоянки.
Другие таксисты будут долго очень думать что это за число такое.
Вам очень просто найти нужного таксиста.
1. Кроме надписи попросить поставить крестик на руке, который будет видно, когда держишь табличку.
2. Договориться, что в надписи одна из букв будет как-то помечена нестандартно (лишняя засечка или черта над/под или вместо кириллической буквы латинская).
3. Кроме надписи попросить открыть заднее правое окно и повернуть руль до отказа влево.
4. Написать сумму всех цифр номера и умножить на оговорённое число.
а…. а если таксист – кавказец с горного аула. Какие корни, какие чексамы? :)
Кстати, предлагаю номер убрать из обихода, ибо может состоять только из букв, тогда вычисления не проходят
Ещё у машины есть очень много параметров которые делают её уникальными, если составить их все вместе. Это как бы состовной первичный ключ.
Например марка машины + цвет машины + её пробег – на счетчике написанно
1. простой XOR номера машины с любым номером-паролем, который ты передал оператору. хотя если таксуют в кризис бывшие програмеры, то взломают.
кстати, таксистам заказы передают рацией, и все таксисты это слышат – так что вариант с секретным паролем отпадают.
2. попросить публичный ключ конкретного таксиста и пусть шифрует номер машины своим приватным. самый нормальный вариант, стойкий ко всякой фигне. дополнительный плюс – если другие таксисты и правда рациональны, то они даже не станут повторять его действия, т.к. понятно, что у них не получится.
3. самый, имхо, правильный вариант: пусть нарисует маршрут, которым повезёт, тогда даже если все скопируют его действия, то будут везти по нему, и тебе будет пофигу кого выбирать.
да, а приз-то какой?
Зачем просить его что-то писать? Зачем ограничивать себя, вышел и поймал любого свободного таксиста, раз их там так много и борются они за клиентов. Даже звонить не надо оператору. Вышел, поголосовал и поехал.
Провтыкал, извиняюсь. Только “наш” таксист повезет короткой дорогой – это я упустил.
Во многих фирмах вызов втрое дешевле чем голосование, а у аэропортов тем более ещё в трое дерут, проще вызвать…
Согласен, но если учесть, что человек опаздывает на собеседование в Гугл, то он не будет задумываться о стоимости (конкретно в данной ситуации). =)
Тогда какая ему разница на каком такси ехать ? (и тем более звонить) вышел-сел-поехал :)
а как он его попросит написать что то на табличке?… тогда уж пусть сразу номер спросит)))
Условие 2 нас ограничивает.
1. Пускай напишет на табличке мои ФИО (вобщем не важно, лишь бы хоть что-то написал). И заготовит секретную табличку с фразой “Авторизация пройдена! Садись в автомобиль, довезу :)”.
2. Потом, когда я буду проходить мимо него с табличкой с заготовленной для него фразой “Это я, тот самый, подвези меня!” (а заготовленную фразу диспетчер уже передал таксисту), то он ответит мне секретной табличкой и я его узнаю.
Конечно же секретную табличку он никому не показывает пока не увидит табличку с моей фразой :)
Но если таксисты слышат, что передает оператор таксисту, то ничего не поможет, даже хеш с номером и солью!
Нужно написать “Занят”, другие таксисты такого писать не станут точно, да и выглядеть это будет абсолютно нормально.
Пусть откроет капот и багажник типа чинится
Описать как ты выглядишь, затем таксист увидав тебя, должен подойти к тебе и дать денег=) Естественно, потом деньги возвращаются.
1. Можно написать: “Любимая/Солнышко/Дорогая, я тут” и поднять эту табличку над головой, будто таксист – это совсем не таксист, а, например, муж, который встречает жену.
Остальные таксисты будут повторять надпись – вряд ли жена не узнает своего мужа.
2. Таксист может открутить номера со своей машины и держать их вместо таблички.
3. Таксист должен по дороге в аэропорт захватить с собой некий предмет, который трудно найти в аэропорту, например набор сантехника или крышку для унитаза.
А вообще сабжект не подходит для работы в Гугл, потому что на собеседование нужно приезжать заранее и нечего было играться на мобильнике и сажать его – так ему и надо :)
описывать чек-сумму самой машины нельзя – таксисты стоят не возле своих машин
посему, потому можно оперировать только самой табличкой, маркером и водителем.
надпись – результат вычисления: “номер телефона таксо-службы” – “кол-во пальцев на табличке” – “номер вашего рейса”. кол-во пальцев можно считать как “только левая/правая рука” или “левая/правая сторона таблички”
Если остальные могут копировать то, что увидят, значит надо сделать так, чтобы они не смогли это увидеть или не смогли проанализировать увиденное.
Попросить сделать вызов по приезду,снять шапку или наоборот одетьв жару (ага, у всех шапки на готове), снять ботинок со словами “что-то запарился сегодня”. Можно при этом договориться встретися рядом с туалетом (в порядочных местах их должно быть достаточно).
вот это правильное решение :)
как переливные календарики или узконаправленные мониторы – сбоку видно одно (таксистам), а спереди другое (пассажирам)
ну или ещё добавить простой арифметики вида год рождения или контрольное число или номер вашего места в самолёте. в общем – для простой арифметики достаточно вариантов
Ребята, а как вы собираетесь просить таксиста, номер машины которого вы не знаете, написать что-нибудь? А если бы знали номер машины, стали бы просить что-то написать? Тем более, что оператор во время разговора с вами не сказал номер машины (и других данных) таксиста, который приедет за вами. По-моему, это задача вообще не имеет решения :-) Или я что-то не так понял?
В продолжение к вышенаписанному: в свете того, что все таксисты слышат разговоры других таксистов с диспетчером, бессмысленно просить что-то написать, т.к. и другие могут воспользоваться этим алгоритмом… Короче, вряд ли эта задача имеет решение
хинт: RSA как раз и работает в условиях абсолютной публичности.
Работает, если таксист тоже сможет передать пассажиру свой public-ключ ;)
Блин, а и правда сможет :) Почему-то подумал что он должен быть секретным :)
Тем не менее другие таксисты так же могут придумать свои публичные ключи и все равно не ясно кто из них нужный…
они придумают на “свои публичные”, а свои “пары публичны\приватный”. шифровка раскроется публичным, _только_ если была зашифрована приватным этой пары. так что всё ясно.
Если таксист в состоянии написать предложенные варианты, то почему он до сих пор работает таксистом?
Этопростопять!
1). если таксисты знают алгоритм, то получается, нужно сделать такой алгоритм, который другой человек не мог бы применить. По условию задачи есть только одно условие отличающее нашего таксиста от остальных – он знает короткую дорогу. Поэтому надо пользоваться этим условием – пусть таксисты пишут время, за которое они Вас доставят. Но возникает вопрос в том, что остальные захотят обмануть, поэтому нужно дополнительное условие, в случае просрачивания таксист выплачивает сумму сравнимую с компенсацией опоздания на собеседование. В этом случае вы или находите своего таксиста, или оказываетесь при деньгах.
При деньгах и без работы :)
> При деньгах и без работы :)
а остальные варианты вобще не работают =) а так хотя бы деньги есть. Да и можно попросить столько, что работа в гугле будет не нужна.
почему другие не работает:
1). т.к. у вас нету информации о таксисте (ни ключа публичного :D ничего)
2). у таксиста о вас информация доступная всем другим (считай ваш публичный ключ есть у всех таксистов, а так же информация о “шифровании”)
Есть ещё один вариант, о котором я специально умолчал. Таксист должен написать дорогу, которой он поедет. Таким образом меркантильным таксистам придётся ехать самой быстрой дорогой. Ну если они совсем уж меркантильные и хитрые, то они могут выдумать якобы более хитрый маршрут, в этом случае от вас необходимо минимальное знание города.
умолчатель :)
http://anton.shevchuk.name/company/logic-interview/comment-page-1/#comment-60815
может стоит почитать каменты, прежде чем “открывать америку”
По-моему всё просто :)
Как обычно бывает, диспетчер называет цену. Таксист на табличке должен написать “Отвезу в офис Гугль за Х долларов”.
Подходишь к первому меркантильному таксисту и едешь :)
Ээ, уточно сразу же свой ответ. Под “Х” подразумевается конкретная сумма. Т.е. “Отвезу в офис Гугль (Silicon аллея 15) за 50 долларов”. Типа такого
и он повезёт дальней дорогой, в итоге заплатишь денег и ничего не получишь.
А где гарантия что заказанный таксист повезёт ближней? :)
Ну можно расширить надпись с указанием маршрута (который построит диспетчер и продиктует мне).
В любом случае – это более вероятно, чем вычисление MD5(номер машины) таксистом ямайцем :))))
а да, написано в условии, что только “мой таксист” знает короткую.
добавлю, гарантия в условии задачи
если диспетчер продиктует маршрут, то проблема с таксистом решается автоматически.
Кстати это можно дополнить к моему варианту http://anton.shevchuk.name/company/logic-interview/comment-page-1/#comment-60851
У меня такое придумалось:
Пусть таксист не напишет, а будет постоянно писать что-то на табличке. Т.е. вот он взял в руки картонку и что-то сидит там и пишет, пишет, и так все 3-7 минут, пока я от телефона до него дойду. Пока он не допишет и не поднимет табличку — другие таксисты не смогут копировать, а я увижу, что один из таксистов «ненормальный» (занялся калиграфией) и подойду к нему. :-)
Надо написать то что совпадет с машиной.
Например “отвезу за 4030” где 4030 число номера*2.
Другие увидят повторят цифру. Человек пройдет просчитает и сядет именно в нужный. Т.е некая хеш-фунция. Удовлетворяет 2м условиям
Или номер машины – некое число. Т.е выбрать такую чтоб не сильно сложно, но в тоже время и не очевидна с первого взгляда для других таксеров.
Идея думаю ясна.
в комментариях предложено усложнение, в котором учитывается, что информация доступна всем таксистам. Т.е. тоже знают алгоритм хеширования. В этой ситуации работать не будет.
а иначе всё просто :)
кстати гугловская задача про проверку номера телефона через вражеский канал забавнее )
Из условия следует что таксисты меркантильны и у всех есть доступ к тому что я сообщу диспетчеру. Также известно что довезет вовремя только мой таксист. Поэтому можно сообщить диспетчеру нужное время прибытия в Гугл и добавить, что в случае опоздания за проезд платить не буду. Меркантильный таксист не повезет бесплатно. Так что пусть пишет на табличке просто слово Гугл. Кстати поиск этого таксиста будет очень быстрым :)
Якщо там багато таксистів, час обмежений, навіщо тратити час і викликати таксиста по телефону…
Краще брати першу з таксу, запитати скільки часу до кінцевої дороги і обіцяти подвійну(потрійну)оплату за коротший час (50%, 75%, підставити своє) від заявленого…
В даному час дорожчий за ціну проїзду….
собеседующий вас только что услышал буквально следующее: нахрена что-то оптимизировать? просто удвоим количество серверов.
хинт: это _логическая задачка_, а не пример из реальной жихни.
Пусть собеседующий научится ставить задачи.
Если это дешевле то этот вариант лучше.
http://anton.shevchuk.name/company/logic-interview/comment-page-1/#comment-60853
Ну все правильно, диспетчер должна зашифровать номер машины , клчюч от шифра сразу же сказать мне, а зашифрованный вариант потом сказать водителю, чтобы он написал на табличке.
Тогда, если остальные таксисты повторят надпись, то я расшифрую любую табличку и узнаю номер нужной машины.
А если остальные такиситы будут знать алгоритм шифрования и подберут ключ,а потом с этим ключом зашифруют свои номера. Если выбрать достаточно сложный алгоритм шифрования, то на расшифровку уйдет много времени.
А если остальные такиситы захотят запутать и начнут писать что попало на табличках?
Тогда прийдется расшифровывать все таблички, а потом искать машину у которой номер совпадает с одним из расшифрованных значений. Да, останется вероятность, пусть и ничтожно маленькая, что среди расшифрованных значений окажется более одного совпадения с реальными номерами на стоянке.
Не совсем понимаю зачем нужны все эти шифры? Этим только отнимаешь у себя время. Вначале шифровать будет оператор, потом расшифровывать буду я. Это всё равно, что писать к базе данных такиe запросы:
SELECT taxist FROM tbl_taxists WHERE MD5(taxist_id) = MD5($taxist_id)Я бы просто отрезал остальных с помощью дополнительного условия.
Оператор изначально не знает какой таксист поедет.
Ну да… и не надо, пусть мне ключ скажет-то, а зашифрует потом, когда будет знать какой таксист едет.
Про хеши тут уже сказали..поэтому усложню системой реального времени :) В случае когда канал не публичный и таксисты будут просто копировать очевидно что первым действие начнёт нужный таксист.
1. Таксист берёт трансформацию своего авто-номера в численной форме (ключ)
2. По приезду ко входу он начнёт каждую секунду писать число из последовательности трансцендентного числа полученного из дробной части произведения ключа на Пи например. тоесть для 100*пи это будет 1..5..9..2.. и тд.
3. Когда я прихожу то просто смотрю у кого самая длинная последовательность, проверяю правилен ли алгоритм и частота. Как вариант – произносить последовательсноть или писать на дощечке последнюю её часть, тогда мне надо будет вычислять всю последовательность и находить местонахождение его сейчас. Так я получаю сколько времени таксист стоит.
Поскольку изменить частоту произнесения или свою начальную позицию он не может из-за страха быть сразу обнаруженным лжецом, достаточно определить кто начал отсчёт первым. Легко :)))
Задача не сформулирована и потому гавно:
1. Формулировка изначально наводит на неверное решение с табличкой, так как первое условие не дает возможности использовать ее. Неужели всякая херня с пальцами и контрольными суммами может считаться за адекватное решение ?
2. Комментарии сбивают с толку – таксисты написать свои координаты могут, а найти короткий путь нет? Это не логично, значит логичного решения нет остаются только импровизации которые условно позволят ее “решить”.
Напомнила о таких же детских задачках о комнате и кошках когда “одна вернулась” которые использовались только чтобы почмырить кого-либо.
Мне вот интересно чем это она таким впору для собеседований? Решить ее нельзя, в лучшем случае она условно решаема, так что максимум что она позволит это оценить разносторонность мышления – выше были как и идиотские варианты с чексуммами (это просто тихий ужас) так и более адекватные основанные на некотором опыте общения с людьми.
Возвращаясь к решению можно пойти от противного и пусть таксист тебя ищет – остальные таксисты отсекаются сразу, это же в конце концов не атака клонов.
Зато приколите сколько лулзов словят таксист и диспетчер: “Ты не поверишь, звонил такой кадр, просил тебя написать *ржет* MD5 ОТ НОМЕРА *истерика*”. Кстати много ли таксистов смогут в уме произвести все эти вычисления?
Опять же если мыслить логически, то по цепочке Google / За граница / Перезвонить на таксофон дают еще одно решение – диспетчер сам свяжется и скажет номер машины. Не забываем вспомнить что условие гавно и диспетчер во время разговора с вами не может связаться с водителем по “рации”, но если дело за бугром то там куча всяких телефонных сервисов которые реально помогают в таких вот жизненных ситуациях, да даже если и нет – то у них стопудово есть рация.
зачем диспетчеру говорить “напиши MD5(‘АХ 00345 ВМ’)”? диспетчер просто передаст “напиши ‘f8f067f7fb0afa1cb13bdd3c6e88402c'”. диспетчер уж всяко за компом сидит.
вот только проверить это с севшим ноутом\телефоном анриал.
ну зачем обязательно md5, можно же и проще алгоритм какой-то придумать. например, номер умножаем на 2 и потом к каждой цифре результата прибавляем 1 (из 9 получается 0), к полученному числу добавляем “ключ”, число которое знаю только я и оператор.
оператор шифрует, говорит нашему такиситу, он пишет, мы приходим и быстренько расшифровываем в уме.
А почему просто не попросить водителя поставить машину в определенное место? К пример в левый дальний угол стоянки.
Ещё вариант что б таксист на карточке нарисовал путь по которому вы поедите, то есть самый короткий и тогда будет без разницы кто вас повезет, хотя к условиям задачи и не совсем подходит, так как искомый таксист найден не будет.
и этот вариант был предложен выше :)
Ответ на самом деле был озвучен, надо просто договориться не только о пароле, но и об отзыве…
Т.е таксист помимо того чтоб показать табличку должен сделать что-то ещё чего другие знать не могут.
Т.е диспетчер может сказать таксисту “подними табличку, и клиент тебя спросит а ты ему ответь ” вот и всё :)
Типа “ты вася ?” а таксист ответит “я не курю” и всё (вполне легко реализуется в данных условиях.)
Кстати, тут решил постебаться немного…
Все кто предлагает варианты с MD5 и SHA1 – а вы уверены что при достаточном количестве “остальных” таксистов у вас не будет коллизий? :)))))
Я почему то подумал, что таксист мог бы написать маршрут поездки, тогда другие его перепишут, ну и надеюсь поймут как ехать по быстрому в офис)
А если сказать оператору чтобы водитель поставил машину в определённом месте на стоянке. Например 1 ряд 7 с конца. Так как в одно место на стоянке мы можем поставить только одну машину, то скопировать поведение искомого водителя будет невозможно. Даже если другие таксисты будут знать о том, что оператор сказал таксисту.
Нужно попросить написать водителя: “Хочу работать в Google”.
Или что-нить такое: “Googl`ить, – не баньку топить. //bash.org.ru”.
Хотя второй вариант врядли оператор точно сможет транслировать таксисту, но этого в ограничениях не было. :)
В процессе обмозгования задачи возникли вопросы:
1) Насколько остальные таксисты умны? Тоесть допустим сообщаем чтобы наш водитель написал номер наоборот, тоесть с конца. Это не решение, но если другие таксисты в условиях задачи не могут догадаться и до такого, то это порождает другие решение.
2) Машины таксистов различаются только по номеру? Цвета и модели одинаковые?
Направление на руль такси относительно взгляда водителя (как в США делают — по стрелочным часам, типа 4:00, если машина сзади и по правую руку от водителя)
Плюс можно добавить что-то, например случайную цифру и первую цифру из номера машины. Случайная цифра: номер машины минус 4 с отбрасыванием знака:
4:40, 4:31, 4:22, 4:13, 4:04, 4:15, 4:26, 4:37, 4:48, 4:59
Это же всё относительно ускоряет процесс (в сравнении со всякими MD5 и похожим)
Желательно что бы “будущим” и в ближайшем часу, т.е. заранее сказать как стать относительно машины.
Если остальные догадваются, что стоять нажно в определённом месте, то это плохо, но тогда остаётся номер машины, а значит 1/10 водителей отсеивается.
Можно предложить еще проще: Написать расценки платы в зависимости от времени
0.5 нужного времени — $4x
0.75 нужного времени — $2x
Нужное вам время — $x
1.25 нужного — таксист платит $x
1.5 нужного — таксист платит $2*x
1.75 нужного — таксист платит $4*x
Другим таксистам будет просто не выгодно вас брать, если будут довозить с опозданием, а если довезут вовремя, то без разницы, что таксист не торт.
В задачке ничего не сказано про наличие табличек у других таксистов, нехай пишет че хочет, остальным писать негде
Вот что-что, а задачи на логику на собеседовании терпеть не могу, т.к. мозг отказывается выдавать решения, когда на тебя сидит и смотрит работодатель, хотя в спокойной обстановке смог бы решить.
Подобные темы уже поднимались. Вот статья про логические задачи, в принципе я согласен с позицией автора.