2010-03-21

juan_gandhi: (Default)
2010-03-21 11:05 am

алгоритмические интервью

Мне как-то всё по жизни на интервью кодирование попадалось. Пару раз с алгоритмами приставали, у меня как-то не получилось. В фейсбуке вместо prefix trees стал предлагать блумфильтры; недавно тут с одним человеком разговаривал, так вместо энграмм стал предлагать tries (ну или вообще patricia trees)...

На самом деле я не понимаю, как вообще алгоритмические интервью проводить. Даже минимальные: скажем, попросить нарисовать сортировку пяти элементов с семью сравнениями: если Третий Том Кнута читал, так знаешь, а нет, так попотеешь. Или вот ещё вопрос (сам придумал):

а) докажите, что в социальной сети из шести человек найдётся всегда или трое друзей, или трое недрузей (в смысле, никто из троих ни с одним из двух других не связан), или и то и другое;
(отношение симметрично но не рефлексивно и не транзитивно)

б) (обобщение) докажите, что для любых двух положительных целых n и k найдётся такое R(n,k), что в любой социальной сети размером R(n,k) найдётся или n друзей (все со всеми), или k недрузей (никто из них ни с кем из остальных k-1).

(Предлагать из решения задачи б сделать вывод о неполноте арифметики уже не будем, наверное...)

Я что хочу сказать - незнание того факта, что мир не так уж прост, похоже, играет конструктивную роль на производстве. А впрочем, про это ещё Кнут в одной статейке на тему парсинга естественного языка писал.
juan_gandhi: (Default)
2010-03-21 05:35 pm

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!