2010-03-21
(10x ![[livejournal.com profile]](https://www.dreamwidth.org/img/external/lj-userinfo.gif){kind=small}
алгоритмические интервью
Мне как-то всё по жизни на интервью кодирование попадалось. Пару раз с алгоритмами приставали, у меня как-то не получилось. В фейсбуке вместо prefix trees стал предлагать блумфильтры; недавно тут с одним человеком разговаривал, так вместо энграмм стал предлагать tries (ну или вообще patricia trees)...
На самом деле я не понимаю, как вообще алгоритмические интервью проводить. Даже минимальные: скажем, попросить нарисовать сортировку пяти элементов с семью сравнениями: если Третий Том Кнута читал, так знаешь, а нет, так попотеешь. Или вот ещё вопрос (сам придумал):
а) докажите, что в социальной сети из шести человек найдётся всегда или трое друзей, или трое недрузей (в смысле, никто из троих ни с одним из двух других не связан), или и то и другое;
(отношение симметрично но не рефлексивно и не транзитивно)
б) (обобщение) докажите, что для любых двух положительных целых n и k найдётся такое R(n,k), что в любой социальной сети размером R(n,k) найдётся или n друзей (все со всеми), или k недрузей (никто из них ни с кем из остальных k-1).
(Предлагать из решения задачи б сделать вывод о неполноте арифметики уже не будем, наверное...)
Я что хочу сказать - незнание того факта, что мир не так уж прост, похоже, играет конструктивную роль на производстве. А впрочем, про это ещё Кнут в одной статейке на тему парсинга естественного языка писал.
На самом деле я не понимаю, как вообще алгоритмические интервью проводить. Даже минимальные: скажем, попросить нарисовать сортировку пяти элементов с семью сравнениями: если Третий Том Кнута читал, так знаешь, а нет, так попотеешь. Или вот ещё вопрос (сам придумал):
а) докажите, что в социальной сети из шести человек найдётся всегда или трое друзей, или трое недрузей (в смысле, никто из троих ни с одним из двух других не связан), или и то и другое;
(отношение симметрично но не рефлексивно и не транзитивно)
б) (обобщение) докажите, что для любых двух положительных целых n и k найдётся такое R(n,k), что в любой социальной сети размером R(n,k) найдётся или n друзей (все со всеми), или k недрузей (никто из них ни с кем из остальных k-1).
(Предлагать из решения задачи б сделать вывод о неполноте арифметики уже не будем, наверное...)
Я что хочу сказать - незнание того факта, что мир не так уж прост, похоже, играет конструктивную роль на производстве. А впрочем, про это ещё Кнут в одной статейке на тему парсинга естественного языка писал.
Java progress: 3 years after
3 years ago I wrote about Java closures proposal. We still don't have them. Looking the same as they are implemented in Scala now. But Java... it still does not have it. Nice!