Первая должна остаться, вроде как.

садистские методы приема на работу.

Есть анекдот на эту тему.
Два менеджера по персоналу опытный и стажёр сидят в офисе и обсуждают
дела. Молодой достает огромную пачку резюме, штук 300: «Мы должны просмотреть
их все, чтобы подобрать кандидатов на эту вакансию». Опытный
хладнокровно берет у него пачку, делит ее пополам, одну часть на стол,
вторую в шреддер. У молодого глаза по пятаку: «А как же претенденты?!»
Опытный невозмутимо: «А зачем нам неудачники?»

$n — кол-во коробок

$openboxes = floor(sqrt($n));

Открытыми остаются коробки 1, 4, 9, 16, 25 и т.д.

Но решать такие задачки на улице без чего-нить под рукой, где даже не сконцентрируешься — нафик, нафик…

А если мне звонят, и я, например, на важной встрече. Или просто не могу говорить? Я бы сказал им что мне сейчас не удобно разговаривать.

Мне кажется это был тест на личные качества, а не про коробки.

На сколько я слышал — задачи они постоянно такие дают при приеме, но чтоб по телефону и прямо на улице — впервые слышу…

по-моему ряд будет 1 открыта 2 закрыты 1 открыта 3 закрыты 1 открыта 4 закрыты и т.д.

Не надо было соглашаться на такого формата собеседование. Нужно уважать себя.

Писал им в том году, до отъезда за бугор.
Ответ пришел через 2 месяца, когда уже был, по сути, не нужен.
Тормоза.

Google не виноват, что он испугался попросить перезвонить ему позже. Я думаю там работают адекватные люди, и если они уж заинтересовались резюме, то наверняка перезвонили бы еще раз.

Где-то была очень простая статистика: в Гугль в минуту поступает N резюме. N резюме в минуту, понимаете? Что это значит? Это значит, что по определению гугль не испытывает недостатка в отличниках, в людях с опытом работы, в людях с хорошим портфолио, в олимпиадниках, в людях со светлой головой — в общем, какой бы критерий отбора вы не выбрали, таких людей у них в очереди на собеседование больше, чем им нужно. Поэтому они могут себе позволить, и более того, имеют моральное право выбрать среди них например того, кто может решить задачку в уме на шумной улице посреди каких-то своих дел. Погуглите, как бы цинично это не звучало, в Сети на предмет собеседований в гугле. Очень много людей до вас интересовалось этим вопросом. И в общем, выясняется следующее: поскольку выбирать гуглерам приходится, по определению, среди и так уже лучших, выбирают часто по принципу личной совместимости. То есть, человека возьмут потому, что с ним приятно общаться. Или не возьмут потому, что лично в ту команду, которая его собеседует, он не впишется. И т.д. И то, каким выдающимся программистом он был до собеседования, особо роли не играет — высокий профессионализм подразумеватся по умолчанию.

Примерно так.

Да, жесткие методы у них: поставить человека в экстремальную ситуацию и посмотреть как он из нее выберется. Думаю, в такой ситуации я бы им не подошел.

По моим расчётам ответ будет таким:
$M=floor(sqrt(N));
т.е. при любом значении N количество открытых коробок будет корень из N с округлением до меньшего целого.

Задачка вообще математически решается?
По моему посчитать количество простых чисел на интервале и то проще ;/

Оценить нормально человека только задачкой — «бред» их HR-менеджера, а так же показывает, что они (скорей отдел по поиску персонала) изначально неуважительно относятся к сотруднику.

Гугл жестокий)

import sys

# True = open; False = close

countBoxes = 40

_boxes = range(1, countBoxes + 1)
_count = [True] * countBoxes

def stat():
	[sys.stdout.write('%s ' % ('x' if not _count[i] else '-')) for i, box in enumerate(_boxes)] and sys.stdout.write('\n')
stat()
for step in xrange(1, countBoxes):
	for box in _boxes[step::step + 1]:
		try:
			box = _boxes.index(box)
		except:
			pass
		else:
			_count[box] = not _count[box]
	stat()

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

Ему нужно было сказать хоть что то. Хотябы 45 или 1 или 256. Так как любой пусть и не правильный ответ лучше чем никакой.

Да это элементарное распи№;%йство с их стороны, они этим еще два года назад страдали при приеме, когда я к ним поступал.

А как я добивался возврата денег за самолет — это вообще песня, я прозрел от несоответствия всем тем красивым картинкам в интернете. С их конкурсом на место они действительно могут себе позволить и иногда позволяют неуважительное отношение к кандидатам. Погуглите «google job interview».

Надо был говорить «сейчас не могу, давайте позже».

То есть, если я когда-то такую задачу решал(для интереса, препод в школе задал, в инете ответ увидел и т.д.), и ответил правильно, то прошел бы собеседование, а кто-то, кто умнее меня, но с такой задачей не сталкивался — не прошел бы?

Тут задачка простого решения не имеет, как и все задачки, связанные с подсчетом простых чисел. Рекруте, судя по всему, просто хотел узнать ход рассуждений, увидеть в каком направлении работает у человека мысль.
Теперь по поводу решения задачи: тут сразу понятно, что все коробки с номером, которое является простым числом, будут закрыты, поскольку по ним можно пройти только один раз. Остальные же коробки будут закрыты или открыты в зависимости от количества простых делителей номера коробки и степеней их вхождения. В общем, какую-то универсальную формулу вывести довольно-таки сложно, тем более на ходу по телефону.

function calcOpenBoxes($n) {
$boxes = array();
for ($i=0; $i<$n; $i++) {
$boxes[] = true;
}
for ($del = 2; $del <= $n; $del++) {
for ($num = ($del-1); $num <= ($n-1); $num += $del) {
if (isset($boxes[$num])) {
unset($boxes[$num]);
} else {
$boxes[$num] = true;
}
}
}
return count($boxes);
}

for ($i=1; $i<100; $i++) {
echo $i.':'.calcOpenBoxes($i).«\n»;
}

Результат:
1:1
2:1
3:1
4:2
5:2
6:2
7:2
8:2
9:3
10:3
11:3
12:3
13:3
14:3
15:3
16:4
17:4
18:4
19:4
20:4
21:4
22:4
23:4
24:4
25:5
26:5
27:5
28:5
29:5
30:5
31:5
32:5
33:5
34:5
35:5
36:6
37:6
38:6
39:6
40:6
41:6
42:6
43:6
44:6
45:6
46:6
47:6
48:6
49:7
50:7
51:7
52:7
53:7
54:7
55:7
56:7
57:7
58:7
59:7
60:7
61:7
62:7
63:7
64:8
65:8
66:8
67:8
68:8
69:8
70:8
71:8
72:8
73:8
74:8
75:8
76:8
77:8
78:8
79:8
80:8
81:9
82:9
83:9
84:9
85:9
86:9
87:9
88:9
89:9
90:9
91:9
92:9
93:9
94:9
95:9
96:9
97:9
98:9
99:9

Опытным путём получается таки $openboxes = floor(sqrt($n)); как и написано выше.
На счёт сложности посчитать в уме… На сколько я помню, в вышке есть некий метод для примерного вычисления корня. И наверное, зная этот метод можно было бы, наверное, и догадаться.

Вы тут все математики, а задача-то лигическая.

Конечное состояние каждой коробки зависит от числа натуральных делителей её порядкового номера в диапазоне [2; Nкор.]:
— если число делителей четное, то коробка открыта;
— если число делителей нечетное — коробка закрыта.
Т.е. подсчитав кол-во чисел от 1 до N, имеющих четное число делителей можно узнать кол-во открытых коробок.

открытыми остануться только коробки, которые открыли/закрыли четное кол-во раз, т.е. которые имеют четное кол-во разных делителей (не считая 1) и НЕЧЕТНОЕ, если 1 считать. Но любое число k, делящееся нацело на l, делится и на k/l тоже, т.е. разные делители входят парами. Исключение составляют квадраты целых, т.е. искомые номера коробок — квадраты целых, таких квадратов SQRT(N). Отсюда ответ SQRT(N) (с отброшенной дробной частью)

Коробка с номером i останется открытой, если число делителей нечетно. Подсчитать для каждого номера число делителей. Все числа являющиеся квадратами подходят, так что их можно смело называть не раздумывая, а остальные придется считать.

Требуется отобрать коробки, которые будут затронуты четное кол-во раз.

это, как показывает опыт, квадраты, четрвертые, восьмые и т.д. степени простых чисел.

А возможно ли это для других?

Число можно разложить на простые. Если их n и они не повторяются, то количество комбинаций из них будет равно 2^n. То есть будет четным.
Если среди же мы добавим n+первое число, равное числу x из присутствующих n чисел, то добавится еще одна комбинация на каждую комбинацию, где есть x.
А остальных комбинаций, где x нет — их четное количество, так как они собраны из n-1 простых чисел!
То есть полюбому в сумме получаем четное число комбинаций

Значит, другие открытые ящики, кроме четных степеней простых чисел, невозможны.

может быть в такой ситуации лучше объяснить ситуацию и самому перезвонить им было?

я посреди улицы посчитал бы вслух итерации для 5 и 6 коробок и слелал бы какое то предположение насчет зависимости открытых коробок от N и его четности. Ну и если б знал математику наверное что то загнул бы про квадраты и эйлера быть может. Проверяется то не правильность решения а то растеряется ли ли человек и каким путем пойдет решение.

Ничего не напоминает?

Целая часть от корня числа N.

Многие что-то сложное пытаются придумать — понять четное или нечетное число делителей у числа, не считая единицу (что нам собственно и нужно), очень просто:

Если число не является квадратом, то все его делители идут парами: если a — делитель, то n/a — тоже делитель.
Если же является квадартом, то все делители идут парами, кроме собственно корня из n.

Но так как мы не берем в расчет единицу, то у всех чисел не являющихся точными квадратами нечетное число делителей, а у квадартов — четное.

Таким образом (как уже несколько раз написнао выше), ответ — количество точных квадратов до n, то есть floor(sqrt(n)).

Напомнило как сам в западную контору из-за разницы во времени собеседовался по телефону в 10 часов вечера.

сумма (фунция эйлера(i) mod 2) по i от 1 до n?

По-моему, быть не может, чтобы ему предлагали пройти телефонное интервью без предварительного согласования с ним времени. В России так точно не делают. В других странах по идее тоже не должны, так как стандарты общие для всего гугла. Может, с ним договорились о времени собеседования, а он забыл?

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

А откуда гугл узнал что он на улице и так не кстати ему позвонил? Может он дома в тапочках, рядом столик ручка и бумага?

У меня здесь два варианта — либо Гуглю нужны математики-полугении ( ;) ), либо вопрос стоит в области психологии — сможете ли вы отказаться от чрезвычайно выгодного предложения (пусть на время, то есть — отложить рассмотрение этого предложения). Ну хорошо, человек на улице просто шел, а если бы он был на совещании, за рулем, решал иную задачу?…

чорт! это реально количество квадратов, меньшее или равное N!

а вот тут некто Макс Чубин изобразил флешку с экспериментом для наглядности :-)))
test.chubin.ru/task/

Решение верное, а объяснение неверное.
>>У всех чисел от 1 до N (кроме полных квадратов) есть четное (2k) количество делителей — то есть действие
>>«закрыл-открыл» происходит k раз и в результате всё равно коробка открыта остается
Для всех чисел кроме квадратов коробки как раз останутся закрытыми, потому что каждую первую мы никогда не закрывали. А открытыми останутся только квадраты.
Именно поэтому решением и является floor(sqrt(N)), как вы верно и сказали.

Спасибо за пост.

Для наглядности:

import sys
from math import sqrt

n = int(sys.argv[1])
data = [True for x in xrange(n)]
for i in xrange(2, n + 1):
for j in xrange(i, n + 1, i):
data[j-1] = not data[j-1]
print len(filter(lambda x: x, data))
print int(sqrt(n))

Решил минут за пять.
Поставил на антиспам-бот в ICQ.
В прошлом году ходил к ним на собеседование — не взяли.
Жаль не объясняют почему.
Впрочем, у меня 2 варианта:
а) ужасный английский
б) мы не поняли друг друга со вторым человеком, который проводил собеседование

Для начала слегка изменим задачу и предположим что началось все с ряда закрытых коробок и был шаг № 1, который все коробки открыл.

Рассмотрим коробку с номером X. Человек касается этой коробки на шагах i = 1… X таких, что X делится на i. После шага X человек этой коробки уже не касается и она остается открытой или закрытой.

Конечное состояние зависит, таким образом, от числа делителей X. Например, у 6 четыре делителя: 1, 2, 3, и 6. Соответственно человек коснется коробки номер 6 четыре раза, а раз мы начали с закрытого состояния (см. самое начало), то она и останется закрытой.

Очевидно, что нам не нужно знать все число делителей, а достаточно только знать четное оно или нечетное. Нечетное число делителей бывает только в том случае, если при делении получается тот же результат, т. е. у квадратов: 1, 4, 9, 16, 25 и т. д.

Таким образом, все коробки с данными номерами будут открыты, а все остальные закрыты.

(Ни за что бы не решил по телефону. Пойду почитаю, что другие написали.)

Автор топика дал не много информации, но по видимому это было стресс-интервью. Во-первых, не понятно в каком городе/стране интервьюировали человека. Судя по тому, что образование — 1 степень университет по Computer Sciences, это не Россия и не московский гугл, так что не пугайтесь раньше времени потенциальные соискатели. Во-вторых, не понятно на какую должность претендовал человек. Стресс-интервью проводят для должностей подразумевающих стрессовые перегрузки. Похоже это была должность программиста. На первый взгляд, для программиста стрессоустойчивость не ключевой параметр, но как отметил EaE, в условиях большого количества соискателей, логично брать тех, кого потом можно будет растить на другие должности, так называемый «кадровый резерв». Тот же программист потенциально может стать управляющим проектами, а там стрессоустойчивость важна.
тут все указывает на стресс-интервью, человеку звонят неожиданно, и дают задачу, практически не решимую за короткое время. HR-менеджеры тоже не идиоты и все понимают. Важно то, как среагирует кандидат, будет мямлить, предложит нестандартный выход или что-то еще

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

В какой офис гугла устраивался друг, если не секрет

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

В городе N тоже решили провести телефонное интервью:
— Как к свехрурочным относишься? Хорошо?
— Хорошо
— А если надо, обжать кабель вместо админа сможешь?
— Смогу.
Ну ладно… Слушай задачу. К бассейну подведены две… а ну и фиг сней! Берем!

А я с Гуглом не согласен. Я никто, а Гугл — великий, но все равно не согласен. Бог создал разных людей. Кто-то не стрессоустойчивый от природы, кто-то не умеет решать быстро, потому что глубоко копает, но все типы нужны и в какой-то ситуации могут играть решающую роль.

Задача математическая на знание численных методов. Тут даже программировать не надо.

Вначале было N открытых коробок, затем стало N/2, потом N/2-N/3, таким образом после k-того шага открытых коробок будет:

M = N - N/2 + N/3 - N/4 + N/5 + ... — в сумме должно быть k членов.

Запишем это проще:

M = N * (1 - 1/2 + 1/3 - 1/4 + 1/5 + ...)
Ничего не напоминает? Это разложение в ряд Тейлора значения натурального логарифма 2. Кстати, тут один товарищ построил график этого логарифма :)
Но ln 2 из этого ряда получится только в случае бесконечного количества членов. Если же их конечно, и как мы знаем их ровно N, то мы получим какое-то приближение к значению логарифма. Давайте оценим насколько оно точное.
Легко видеть (а можно строго математически доказать), что ряд сходится к какой-то совершенно определённой величине. Более того, я имею смелость утверждать, что ошибка для ряда длинной k членов не превышает 1/k. Это очевидно, т.к. каждый следующий член меньше предыдущего и все они болтаются вверх-вниз относительно какого-то значения.
Для нашего случая при k=N получаем: ΔM = N * 1/N = 1. Замечательный вывод! Значит, при длине последовательности N ошибка будет всегда меньше 1! А раз дробных коробок не бывает, то мы подсчитываем значение с точностью до одной коробки. Это нас полне устроит.

Итак: Открытых коробок = N * ln 2

Самый главный вопрос в какую сторону округлить :)

На самом деле вопрос совершенно не в этом.
А в том, что действительно не надо дергать человека посреди улицы.

да, печально.
можно было бы не растеряться, и сказать, мол, извините, сейчас не могу говорить (вдруг он ведет авто), перезвоните через n минут, или позвольте, я вам перезвоню.
Это нормальная ситуация, и нечего перед гуглем падать на колени и боготворить его.
Но это в идеале.

… И такой случай НЕ показывает высокую компетентность их эйчарников.

а 50 на 50? или з звонок другу? :)

если звонят из Гугля, отвечаем «Извините это уже не актуально» :)

До меня только сейчас дошло, а жена после того, как я задал эту задачу, решила ее еще до того, как я конечный вопрос задал!

Задача:

Все коробки открыты. Проходим по КАЖДОЙ второй и закрываем ее. Проходим по КАЖДОЙ третьей и если она открыта, закрываем, если закрыта, открываем. Проходим по КАЖДОЙ четвертой…

Уберите слово «КАЖДОЙ».

Получится:

Все коробки открыты. Закрываем вторую. Закрываем третью. Закрываем четвертую. Закрываем пятую…

Необходимость закрывать КАЖДУЮ сбивает с толку.

Хотя вот сейчас сомнения закрались… завтра опыт поставлю.

а я хотела бевербунг писать…
как-то страшно стало :)

Утром, на свежую голову задачка показалась гораздо проще чем во второй половине рабочего дня )
2 коробка нажимается один раз
3 — 1 (3)
4 — 2 (2, 4)
5 — 1 (5)
6 — 3 (2, 3, 6)
7 — 1 (7)
8 — 3 (2, 4, 8)
9 — 2 (3, 9)
и т.д.

Открытыми остаются коробки 1, 4, 9 подобный ряд предлагали дополнить в анкете в военкомат. =)

Похоже Гуглу нужны работники, которые рассчитывают маршрут до магазина и обратно в уме с помощью рядов Фурье. Представляете как должен выглядеть этот «кадр»? ;)

сдается мне, что их интересовал не точный ответ, сама реакция на поставленную задачу… наверное они хотели узнать, что человек не растеряется, а начнет искать решение. Правильное или неправильное, это пока неважно.

Ответ может найти практически каждый, если посидеть и подумать. А вот сообразить в экстремальной ситуации мало кому под силу. Получается, что в гугле не лучшие из лучших, а люди, обладающие высоким уровнем самоконтроля)

public class Boxes {

private int iterations = 39, from = 2;
private boolean[] box;

public void makeAction() {
box = new boolean[iterations];
//initial fill
for (int cr = 0; cr < iterations; cr++) {
box[cr] = true;
}

for (int outer = 1; outer <= iterations; outer++) {
System.out.print(outer + «)\t»);
for (int inner = 1; inner <= iterations; inner++) {
if (outer >= from) {
if (inner % outer == 0) {
box[inner — 1] =! box[inner — 1];
}
}
System.out.print((box[inner — 1]? «O»: «X») + « „);
}

System.out.println();
}
}

public static void main(String[] args) {
Boxes crb = new Boxes();
crb.makeAction();
}
}

Результат:

1) O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O O
2) O X O X O X O X O X O X O X O X O X O X O X O X O X O X O X O X O X O X O X O
3) O X X X O O O X X X O O O X X X O O O X X X O O O X X X O O O X X X O O O X X
4) O X X O O O O O X X O X O X X O O O O O X X O X O X X O O O O O X X O X O X X
5) O X X O X O O O X O O X O X O O O O O X X X O X X X X O O X O O X X X X O X X
6) O X X O X X O O X O O O O X O O O X O X X X O O X X X O O O O O X X X O O X X
7) O X X O X X X O X O O O O O O O O X O X O X O O X X X X O O O O X X O O O X X
8) O X X O X X X X X O O O O O O X O X O X O X O X X X X X O O O X X X O O O X X
9) O X X O X X X X O O O O O O O X O O O X O X O X X X O X O O O X X X O X O X X
10) O X X O X X X X O X O O O O O X O O O O O X O X X X O X O X O X X X O X O X X
11) O X X O X X X X O X X O O O O X O O O O O O O X X X O X O X O X O X O X O X X
12) O X X O X X X X O X X X O O O X O O O O O O O O X X O X O X O X O X O O O X X
13) O X X O X X X X O X X X X O O X O O O O O O O O X O O X O X O X O X O O O X O
14) O X X O X X X X O X X X X X O X O O O O O O O O X O O O O X O X O X O O O X O
15) O X X O X X X X O X X X X X X X O O O O O O O O X O O O O O O X O X O O O X O
16) O X X O X X X X O X X X X X X O O O O O O O O O X O O O O O O O O X O O O X O
17) O X X O X X X X O X X X X X X O X O O O O O O O X O O O O O O O O O O O O X O
18) O X X O X X X X O X X X X X X O X X O O O O O O X O O O O O O O O O O X O X O
19) O X X O X X X X O X X X X X X O X X X O O O O O X O O O O O O O O O O X O O O
20) O X X O X X X X O X X X X X X O X X X X O O O O X O O O O O O O O O O X O O O
21) O X X O X X X X O X X X X X X O X X X X X O O O X O O O O O O O O O O X O O O
22) O X X O X X X X O X X X X X X O X X X X X X O O X O O O O O O O O O O X O O O
23) O X X O X X X X O X X X X X X O X X X X X X X O X O O O O O O O O O O X O O O
24) O X X O X X X X O X X X X X X O X X X X X X X X X O O O O O O O O O O X O O O
25) O X X O X X X X O X X X X X X O X X X X X X X X O O O O O O O O O O O X O O O
26) O X X O X X X X O X X X X X X O X X X X X X X X O X O O O O O O O O O X O O O
27) O X X O X X X X O X X X X X X O X X X X X X X X O X X O O O O O O O O X O O O
28) O X X O X X X X O X X X X X X O X X X X X X X X O X X X O O O O O O O X O O O
29) O X X O X X X X O X X X X X X O X X X X X X X X O X X X X O O O O O O X O O O
30) O X X O X X X X O X X X X X X O X X X X X X X X O X X X X X O O O O O X O O O
31) O X X O X X X X O X X X X X X O X X X X X X X X O X X X X X X O O O O X O O O
32) O X X O X X X X O X X X X X X O X X X X X X X X O X X X X X X X O O O X O O O
33) O X X O X X X X O X X X X X X O X X X X X X X X O X X X X X X X X O O X O O O
34) O X X O X X X X O X X X X X X O X X X X X X X X O X X X X X X X X X O X O O O
35) O X X O X X X X O X X X X X X O X X X X X X X X O X X X X X X X X X X X O O O
36) O X X O X X X X O X X X X X X O X X X X X X X X O X X X X X X X X X X O O O O
37) O X X O X X X X O X X X X X X O X X X X X X X X O X X X X X X X X X X O X O O
38) O X X O X X X X O X X X X X X O X X X X X X X X O X X X X X X X X X X O X X O
39) O X X O X X X X O X X X X X X O X X X X X X X X O X X X X X X X X X X O X X X