Хотелось бы рассказать о частном случае пробы устройства на работу (сразу оговорюсь, действие происходит не в России).
Итак, мой друг (закончил 1-ую степень одно из университетов по специальности Computer Sciences) послал резюме в местное отделение Google. Чтобы они вообще пригласили кого-либо на собеседование, нужен средний бал не меньше 85 (считается отличником). У него, естественно средний бал выше (около 90, точно не помню). Есть опыт работы на Java.
Так вот, он послал резюме и вообще забыл про это. Недели через три, когда он шел куда-то по своим делам, ему звонят, представляются как Google, мол вы Такой-то Такой-то прислали нам резюме, всё хорошо, давайте проведем интервью. Он: естественно, давайте, давайте. Ему говорят: вот, решите задачку: (чтоб вы понимали, человек посреди шумного города, ни листика ни ручки. Сказать «перезвоните позже» он тоже не может (а вдруг не перезвонят), в общем, это шанс и за него надо хвататься):
Задача:
Есть N коробок. Все они открыты. Человек проходит и закрывает каждую вторую коробку. Затем проходит по каждой третей коробки, если она открыта закрывает, если закрыта открывает. Потом по каждой четвёртой и так до N. Сколько коробок останутся открытыми после всех этих действий.
Он в полном ступоре, потому как до сих пор не приходилось решать задачи для интервью на УЛИЦЕ!
Подумал немного, но решить так и не смог (слишком волновался, я думаю). Они его поблагодарили и отключились. Вот так вот. Хотя я думаю будь он у них в офисе, решил бы без проблем.
Вывод: либо не сильно хотели, либо слишком много желающих и надо было отсеить хотя бы половину вот таким «интервью». Ни от кого из моих знакомых я больше подобных случаев не слышал, так что похоже это были разовые меры.
P.S. Попробуйте решить задачу, если интересно, выложу решение.
UPD 2: Некто Макс Чубин сделал на флеше наглядное решение данной задачи.
Ссылка
UPD: Ответ:
Целая часть от (корень N)
Почему?
У всех чисел от 1 до N (кроме полных квадратов) есть четное (2k) количество делителей — то есть действие «закрыл-открыл» происходит k раз и в результате всё равно коробка открыта остается. А у полных квадратов нечетное количество делителей. Поэтому ответить на этот вопрос это все равно что посчитать сколько полных квадратов есть до N, то есть целая часть корень N.
Вроде правильно...
