How to become an author
Search
Write a publication
Pull to refresh

Comments 260

Первая должна остаться, вроде как.
Total votes 5: ↑3 and ↓2+1
черт, прошу прощения, не дочитал, думаю дальше. а методы и правда… конкурс, конкуренция…
This comment wasn’t rated yet0
Я думаю, при любом N открытыми останется M коробок.
Total votes 27: ↑27 and ↓0+27
Ответ прост: Целая часть от корня числа N =)
Total votes 8: ↑6 and ↓2+4
UFO just landed and posted this here
UFO just landed and posted this here
Если уж интересуетесь, могу вот это посоветовать — www.koob.ru/poundstone_w/kak_sdvinut_goru_fudzi
Небольшая книжечка, в которой рассказывется откуда ноги растут такой методики приёма на работу… поверьте, бывает и хуже =)
+ там много подобных и не очень задач и пояснения какими методами их решать. В частности эта задача там есть насколько я помню, только не с коробками а со шкафчиками в раздевалке.
Total votes 3: ↑3 and ↓0+3
садистские методы приема на работу.
Total votes 14: ↑13 and ↓1+12
меня вопрос теперь мучает, действительно решение такой задачи отображает на реальное качество работы человека?
Total votes 13: ↑12 and ↓1+11
ну по результатам работы гугла видим, что да.
Total votes 19: ↑13 and ↓6+7
Результат работы гугла = результату его отдела маркетинга :)
Total votes 3: ↑3 and ↓0+3
Нет, только знание мат. методов.
This comment wasn’t rated yet0
да зажрались они уже, звонят и говорят «мол ты тупица и не нас достоин»
Total votes 11: ↑6 and ↓5+1
меня они по телефону заставляли писать реализацию очереди :)
ну и прочие задачки на теорию вероятности, комбинаторику и производительность алгоритмов
Total votes 3: ↑3 and ↓0+3
даже боюсь спросить… успешно?
This comment wasn’t rated yet0
Увы-увы :) как раз теория вероятности и комбинаторика у меня оказались слабоваты.
Там были еще вопросы по языку и API (java) и общие вопросы по технологиям (сети, SQL, скриптовые языки), но это всё достаточно традиционно для IT-собеседований
Вообще, по совокупности впечатлений от нескольких людей, собеседовавшихся в гугле, можно заключить, что там ценят в большей степени «академические» знания, чем практический опыт.
Уж не знаю, оправдано ли это их процессом разработки или это особенность тех людей, которые проводят собеседования.
Было бы интересно узнать, какие требования к людям у них были лет 6 назад.
Total votes 4: ↑4 and ↓0+4
Такое ощущение что они нейронные там сети строят. Выход им нужны просто специалисты в области математики и т.п. нежели программисты.
Total votes 1: ↑1 and ↓0+1
Я думаю, что эти методы достаточно оправданы для компании, которая имеет ткой широкое поле деятельности. Выучить Java API или, как строить SQL запросы может и гуманитарий, это лишь инструмент, но вот для грамотного использования этих инструментов необходимо аналитическое мышление, которое развивается исключительно математикой\физикой\другими точными науками. Программирование, конечно, тоже вносит свою лепту в развитие, но довольно специфическую. Любой программист легко написал бы программу, которая решит предложенную задачку — для данного N посчитать число открытых ящиков, но чтоб решать такие задачки математически, или аналитически, нужно в другой плоскости мыслить
Total votes 1: ↑1 and ↓0+1
да я собственно это уже понял, не судьба многим туда попасть, но я думаю к лучшему.
This comment wasn’t rated yet0
может они просто хотели посмотреть как человек отреагирует на нестандартную ситуацию?
Total votes 4: ↑3 and ↓1+2
Вычислили его местоположение с помощью google-maps?
This comment wasn’t rated yet0
Кандидат мог вполне сказать, когда ему удобно пройти телефонное интервью.
В случае телефонного интервью условия должны быть аналогичные обычному интервью. А именно — нет отвлекающих факторов, возможность записать уловие и набросать решение на листе бумаги.
Total votes 3: ↑2 and ↓1+1
а если коробок к примеру пять?
Total votes 2: ↑1 and ↓10
я сомневаюсь, что тут участвуют нечетные числа.
Total votes 29: ↑6 and ↓23-17
ну не прав, я не прав
Total votes 14: ↑12 and ↓2+10
проверил я сейчас 5, 10 и 20 коробок. или я чего-то непонял в условии, или не половина остается.
This comment wasn’t rated yet0
x — закрыта
_ — отрыта

1 _ _ _ _ _ _ _ _ _ _
2 _ x _ x _ x _ x _ x
3 _ x x x _ _ _ x x x
4 _ x x _ _ _ _ _ x x
5 _ x x x x _ _ _ x _
6 _ x x x x x _ _ x _
7 _ x x x x x x _ x _
8 _ x x x x x x x x _
9 _ x x x x x x x _ x
10 _ x x x x x x x x _

1 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
2 _ x _ x _ x _ x _ x _ x _ x _ x _ x _ x
3 _ x x x x _ x x x x x _ x x x x x — x x
4 _ x x _ x x x _ x x x x x x x _ x x x _
5 _ x x x _ x x x x _ x x x x _ x x x x x
6 _ x x x x _ x x x x x _ x x x x x _ x x
7 _ x x x x x _ x x x x x x _ x x x x x x
8 _ x x x x x x _ x x x x x x x _ x x x x
9 _ x x x x x x x _ x x x x x x x _ x x x
10 _ x x x x x x x x _ x x x x x x x x x x
11 _ x x x x x x x x x _ x x x x x x x x x
12 _ x x x x x x x x x x _ x x x x x x x x
13 _ x x x x x x x x x x x _ x x x x x x x
14 _ x x x x x x x x x x x x _ x x x x x x
15 _ x x x x x x x x x x x x x _ x x x x x
16 _ x x x x x x x x x x x x x x _ x x x x
17 _ x x x x x x x x x x x x x x x _ x x x
18 _ x x x x x x x x x x x x x x x x _ x x
19 _ x x x x x x x x x x x x x x x x x _ x
20 _ x x x x x x x x x x x x x x x x x x x

вообще м да, но где то в первом ошибка у меня
Total votes 5: ↑3 and ↓2+1
Первый график, пятая строка, четвёртый ящик у вас самопроизвольно закрылся…
Total votes 1: ↑1 and ↓0+1
и во втором уже ошибку нашел.
3-я строка изменился почему то и 5-й и 6-й символ, хотя должен только 6-й измениться. Ну и соответственно дальше по цепочке все неправильно.
Вот оно…

____________________
_X_X_X_X_X_X_X_X_X_X
_XXX___XXX___XXX___X
_XX_____XX_X_XX_____
_XX_X___X__X_X_____X
_XX_XX__X____X___X_X
_XX_XXX_X________X_X
_XX_XXXXX______X_X_X
_XX_XXXX_______X___X
_XX_XXXX_X_____X____
_XX_XXXX_XX____X____
_XX_XXXX_XXX___X____
_XX_XXXX_XXXX__X____
_XX_XXXX_XXXXX_X____
_XX_XXXX_XXXXXXX____
_XX_XXXX_XXXXXX_____
_XX_XXXX_XXXXXX_X___
_XX_XXXX_XXXXXX_XX__
_XX_XXXX_XXXXXX_XXX_
Total votes 2: ↑1 and ↓10
ну по идее N/2 коробок останется открытыми.
Total votes 4: ↑1 and ↓3-2
половина коробок останется открыта?
Total votes 4: ↑1 and ↓3-2
Опытным путем получается, что одна коробка останется открытой

<?
$bcount=123; // число коробок

// массив состояний коробок, true — open, false — close
$b=array();
for($x=0; $x<$bcount; $x++)
  $b[]=true;

// решаем задачу
for($x=1; $x<=$bcount; $x++)
  for($y=1; $x<=$bcount; $x++)
    if($x%$y==0) // если нету остатка от деления, инвертируем состояние коробки
      $b[$x]=!$b[$x];

// подсчитываем число открытых коробок
$n=0;
for($x=0; $x<$bcount; $x++)
  if($b[$x])$n++;

echo $n;
?>* This source code was highlighted with Source Code Highlighter.


И она как раз первая и будет
Total votes 13: ↑6 and ↓7-1
начертил на листике и совсем по другому вышло, первая половина коробок изменяет состояние всего один раз, вторая половина 2 раза.
This comment wasn’t rated yet0
Ну если уж на листике чертить…
допустим, для простоты, что у нас 8 коробок
Будет сколько проходений человека, открывающего-закрывающего коробки? Правильно: 7, потому что он сначала он меняет состояние каждой 2-й коробки, потом каждой 3-й… потом каждой 8-й.

Получаем:
ОООООООО
ОЗОЗОЗОЗ
ОЗЗОЗООЗ
ОЗЗЗЗООО
ОЗЗЗЗЗОО
ОЗЗЗЗЗЗЗ
ОЗЗЗЗЗЗЗ

где:
О — открыто, З — закрыто

P.S.: В моноширинном шрифте нагляднее бы смотрелось))
Total votes 4: ↑1 and ↓3-2
а почему в третьей строке четвертый символ из З стал О? меняли же каждый третий…
Total votes 3: ↑3 and ↓0+3
а почему у вас все коробки только закрываются? ведь если коробка закрыта, её открывают… ну, по условиям задачи…
This comment wasn’t rated yet0
ой, сори, недоглядел…
This comment wasn’t rated yet0
моноширинным бы шрифтом было бы действительно наглядней…
This comment wasn’t rated yet0
Ваш цикл неверный. Проверьте хотя бы для 4-х коробок. Результат должен быть 2 (открыты первая и четвёртая).
This comment wasn’t rated yet0
<? php
$n = (int)$_GET['n'];
$boxes = array_fill(1, $n, 1);
for($i = 2; $i <= $n; $i++)
{
    for($j = $i; $j <= $n; $j = $j + $i)
    {
        $boxes[$j] = !$boxes[$j];
    }
}
//print_r($boxes);
echo array_sum($boxes);
Total votes 5: ↑4 and ↓1+3
Все кто задачу разгадал — милости просим в гуголь :)
This comment wasn’t rated yet0
Короче, я поспешил… и Хабрасообщество насмешил…
Total votes 3: ↑3 and ↓0+3
Есть анекдот на эту тему.
Два менеджера по персоналу опытный и стажёр сидят в офисе и обсуждают
дела. Молодой достает огромную пачку резюме, штук 300: «Мы должны просмотреть
их все, чтобы подобрать кандидатов на эту вакансию». Опытный
хладнокровно берет у него пачку, делит ее пополам, одну часть на стол,
вторую в шреддер. У молодого глаза по пятаку: «А как же претенденты?!»
Опытный невозмутимо: «А зачем нам неудачники?»
Total votes 83: ↑82 and ↓1+81
$n — кол-во коробок

$openboxes = floor(sqrt($n));
Total votes 16: ↑15 and ↓1+14
Да, закрыты останутся те, которые тронуты нечетное число раз, а это в точности полные квадраты.
Total votes 3: ↑2 and ↓1+1
Ну все же открыты сначала.
У предыдущего докладчика ошибка, там надо
$openboxes = n — floor(sqrt($n));
This comment wasn’t rated yet0
Больше похоже на то что закрытыми останутся четные степени простых чисел.

для 2-ки:
2^2 = 4
2^4 = 8
2^6 = 32

3-ка:
3^2 = 9
3^4 = 81

И т. д. Но нужно
1) доказать что они и только они
2) как-то выразить всю эту лабуду через N
This comment wasn’t rated yet0
Думаю, это правильный ответ.
This comment wasn’t rated yet0
Нет, не правильный) Вы рассматривали малые N, где делителями являются лишь пары чисел. Рассмотрите 2*3*4, например. Этот ящик тоже останется открытым, хотя и не является квадратом целого числа.
Total votes 2: ↑1 and ↓10
oxoxoxoxoxoxoxoxoxoxoxox
oxxxoooxxxoooxxxoooxxxoo
oxxoooooxxoxoxxoooooxxox
oxxoxoooxooxoxoooooxxxox
oxxoxxooxooooxoooxoxxxoo
oxxoxxxoxooooooooxoxoxoo
oxxoxxxxxooooooxoxoxoxox
oxxoxxxxoooooooxoooxoxox
oxxoxxxxoxoooooxoooooxox
oxxoxxxxoxxooooxooooooox
oxxoxxxxoxxxoooxoooooooo
oxxoxxxxoxxxxooxoooooooo
oxxoxxxxoxxxxxoxoooooooo
oxxoxxxxoxxxxxxxoooooooo
oxxoxxxxoxxxxxxooooooooo
oxxoxxxxoxxxxxxoxooooooo
oxxoxxxxoxxxxxxoxxoooooo
oxxoxxxxoxxxxxxoxxxooooo
oxxoxxxxoxxxxxxoxxxxoooo
oxxoxxxxoxxxxxxoxxxxxooo
oxxoxxxxoxxxxxxoxxxxxxoo
oxxoxxxxoxxxxxxoxxxxxxxo
oxxoxxxxoxxxxxxoxxxxxxxx
Total votes 2: ↑1 and ↓10
Открытыми остаются коробки 1, 4, 9, 16, 25 и т.д.

Но решать такие задачки на улице без чего-нить под рукой, где даже не сконцентрируешься — нафик, нафик…
Total votes 11: ↑10 and ↓1+9
Будет закрыт при любых N.
This comment wasn’t rated yet0
Попробуйте вручную это проверить. 24 — это первое число из ряда тех, которые не соответствуют вашему предположению.
This comment wasn’t rated yet0
24, такс проверим.
2 — закр
4 — откр
6 — закр
12 — откр
24 — закр.
This comment wasn’t rated yet0
24 будет закрыто. Его коснутся 7 раз (2,3,4,8,6,12,24) => т.к. изначально коробки открыты, то коробка под номером 24 будет закрыта.
Total votes 1: ↑1 and ↓0+1
Проверил вручную. 24-я — закрыта. Простыни сюда выкладывать? ;)
This comment wasn’t rated yet0
24 закрта. Делители ее номера 1,2,3,4,6,8,12,24. На 2,4,8,24 шаге ее закрыват, на 3,6,12 открывают.
This comment wasn’t rated yet0
UFO just landed and posted this here
UFO just landed and posted this here
UFO just landed and posted this here
читайте внимательнее условие
This comment wasn’t rated yet0
Вручную посчитайте для 4-х коробок. Открытыми будут 1-я (её никто не закрывал) и 4-я (её 1 раз закрыли-открыли)
This comment wasn’t rated yet0
А если мне звонят, и я, например, на важной встрече. Или просто не могу говорить? Я бы сказал им что мне сейчас не удобно разговаривать.

Мне кажется это был тест на личные качества, а не про коробки.
Total votes 25: ↑24 and ↓1+23
а если Вам звонят и у Вас есть возможность говорить и Вы сидите в тихом местечке?
то на личные качества тест пройден, а теперь на умение решать подобные задачи?!
Total votes 2: ↑0 and ↓2-2
Я бы все равно отказался собеседоваться по телефону.
Total votes 3: ↑3 and ↓0+3
с этим согласен, думаю, я поступил также
Total votes 1: ↑1 and ↓0+1
Респект!
Человеку — человеческое.
А на точность вычислений пусть google арифметику тестирует.
Total votes 2: ↑2 and ↓0+2
N-2, если на последнюю тоже «нажимаеем».
Total votes 2: ↑0 and ↓2-2
На сколько я слышал — задачи они постоянно такие дают при приеме, но чтоб по телефону и прямо на улице — впервые слышу…
This comment wasn’t rated yet0
по-моему ряд будет 1 открыта 2 закрыты 1 открыта 3 закрыты 1 открыта 4 закрыты и т.д.
Total votes 2: ↑1 and ↓10
UFO just landed and posted this here
сомневаюсь что именно такой ответ их устроил бы. Хотя он абсолютно верен
Total votes 1: ↑0 and ↓1-1
А почему? Тут и ответ и решение (почти все). Просто и ясно, говорит о хорошей математичсекой подготовке и хорошей способности к абстракции.
This comment wasn’t rated yet0
Хороший ответ (имхо) — это:

Ответ = f(N)
f(N) =… <тут ответ>
This comment wasn’t rated yet0
согласен, техническое образование заставляет искать ответ именно в такой форме.
This comment wasn’t rated yet0
просто я думал что ответ в виде функции их устроил бы, но покопавшись сам не смог составить эту функцию (только на уровне програмного кода), а посему теперь уже думаю что вполне устроит и данная формулировка.
This comment wasn’t rated yet0
есть теория, что их устроил бы любой оригинальный ответ
Total votes 1: ↑1 and ↓0+1
тоесть гугль хотели услышать:
открытыми останутся коробки в количестве равном округленному в меньшую сторону корню из N?
Total votes 1: ↑1 and ↓0+1
думаю к вашему ответу следует прибавить единицу
This comment wasn’t rated yet0
Поясните, пожалуйста, логический переход: если у М четное количество делителей от 2 до N>=М, то М является полным квадратом.
Понятно, что решение верное, но никак не могу понять этот переход.
Total votes 1: ↑1 and ↓0+1
UFO just landed and posted this here
2x2x3x3 — тоже подходит под «полный квадрат». Уточню — все простые делители в четных степенях.
Разобрался таки с решением. Опишу — вдруг кому также как и мне — «не очевидно».

Из вышестоящих ответов ясно, что коробка останется открытой, если у ее номера — числа М — будет четное количество делителей от 2 до М включительно (т.е. ее тронут четное количество раз).

Разложим число М на простые множители. Каждый из них будет в четной или нечетной степени.
пусть — i, j, k… и т.д. степени простых множителей. Каждый делитель нашего числа М состоит из всех его простых множителей в степенях от 0 до i (до j, до k и т.д.). Т.е. всего делителей будет Д = ((i+1)(j+1)(k+1)… — 1 ) вычитаем 1 т.к. вариант, когда все множители в степени 0 нам не нужен (1 не считаем делителем в нашем случае). Чтобы число делителей Д было четным, нам нужно, чтобы произведение было нечетным. Произведение чисел может быть нечетным тогда и только тогда, когда все они нечетные. Таким образом — все степени i, j, k… простых множителей должны быть четными. Если все степени простых множителей четные — то число является полным квадратом. чтд.

ps. не знаю, как это может быть очевидным… Уж тем более смутно представляю как такое можно провернуть в уме и по телефону.
Total votes 1: ↑1 and ↓0+1
Например 24-я коробка 2^3 х 3^1 имеет 4 кратных простых делителя, и будет открытой, хотя не есть полным квадратом.

F(N) = sum(1 — A(i) mod 2)
i=1… N
A(i) — количество простых множителей с учетом кратности.

Попроще не придумывается формулы…
This comment wasn’t rated yet0
… а всё-таки 24-я будет закрыта :)
This comment wasn’t rated yet0
Точно, это я недосмотрел… Надо не только простые делители учитывать
This comment wasn’t rated yet0
Совершенно верно :)
Тоже пришел к такому-же результату.
This comment wasn’t rated yet0
Не надо было соглашаться на такого формата собеседование. Нужно уважать себя.
Total votes 17: ↑14 and ↓3+11
Писал им в том году, до отъезда за бугор.
Ответ пришел через 2 месяца, когда уже был, по сути, не нужен.
Тормоза.
This comment wasn’t rated yet0
Google не виноват, что он испугался попросить перезвонить ему позже. Я думаю там работают адекватные люди, и если они уж заинтересовались резюме, то наверняка перезвонили бы еще раз.
Total votes 5: ↑5 and ↓0+5
Где-то была очень простая статистика: в Гугль в минуту поступает N резюме. N резюме в минуту, понимаете? Что это значит? Это значит, что по определению гугль не испытывает недостатка в отличниках, в людях с опытом работы, в людях с хорошим портфолио, в олимпиадниках, в людях со светлой головой — в общем, какой бы критерий отбора вы не выбрали, таких людей у них в очереди на собеседование больше, чем им нужно. Поэтому они могут себе позволить, и более того, имеют моральное право выбрать среди них например того, кто может решить задачку в уме на шумной улице посреди каких-то своих дел. Погуглите, как бы цинично это не звучало, в Сети на предмет собеседований в гугле. Очень много людей до вас интересовалось этим вопросом. И в общем, выясняется следующее: поскольку выбирать гуглерам приходится, по определению, среди и так уже лучших, выбирают часто по принципу личной совместимости. То есть, человека возьмут потому, что с ним приятно общаться. Или не возьмут потому, что лично в ту команду, которая его собеседует, он не впишется. И т.д. И то, каким выдающимся программистом он был до собеседования, особо роли не играет — высокий профессионализм подразумеватся по умолчанию.

Примерно так.
Total votes 20: ↑20 and ↓0+20
собственно как в анекдоте vrakhmanov.
This comment wasn’t rated yet0
это в целом. а на конкретную вакансию в конкретном городе обычно поступает не так много резюме. просто в силу естественных ограничений рынка работы
Total votes 1: ↑1 and ↓0+1
Ну, не знаю. Когда в России открылся первый офис гугла, я к ним летал собеседоватся из Новосибирска, и, насколько я знаю, не я один, пяток моих знакомых там точно побывали. Кандидатов со всей России, я думаю, порядочно набралось, даже в пересчете на количество вакансий.
This comment wasn’t rated yet0
так то пиковый случай :)
This comment wasn’t rated yet0
Ну и фиг с ними тогда — мы построим свой гугл, с блэкджеком и шлюхами =)
Total votes 18: ↑17 and ↓1+16
Да, жесткие методы у них: поставить человека в экстремальную ситуацию и посмотреть как он из нее выберется. Думаю, в такой ситуации я бы им не подошел.
This comment wasn’t rated yet0
Эту экстремальную ситуацию человек сам себе создал.
Total votes 1: ↑1 and ↓0+1
Думаю, ничего страшного и экстремального в предложении решить задачку нет))
This comment wasn’t rated yet0
Но, согласитесь, далеко не каждый программист решит ее сходу посередине улицы. Для этого надо быть либо очень смышленным, либо просто уже знать эту задачу. Иначе интервью автоматом проваливается.
This comment wasn’t rated yet0
Значит, им нужны не просто программисты. Логично? А написать пару строк на php — тут конечно, каждый справится.
Total votes 2: ↑2 and ↓0+2
Да, им нужны не просто программисты. Если человек сходу решит такую задачку — он вероятно талантлив, что им подходит. Если человек знал о такой задачке — то он вероятно интересуется заковыристыми задачками, что говорит по крайней мере о том, что он не совсем уж глуп. Это тоже не так уж плохо. У Гугла эффективный способ отсева серой массы, как по мне.
This comment wasn’t rated yet0
Они не задачу проверяли небось, а как всегда замуты с личными качествами типа лидер бы сказал, что сейчас не время и предложил бы перезвонить.
Total votes 4: ↑1 and ↓3-2
Ну не все лидеры и не должны ими быть определению. Не думаю, что они искали менеджера проектов. И вообще сомнительная проверка на мой взгляд. Мне кажется, что это обычный звонок для галочки, типа, на интервью был, не прошел.
Total votes 3: ↑3 and ↓0+3
UFO just landed and posted this here
Ну если это шутка, то правильнее было-бы написать, скажем, M, т.к. N исходное количество.
This comment wasn’t rated yet0
UFO just landed and posted this here
По моим расчётам ответ будет таким:
$M=floor(sqrt(N));
т.е. при любом значении N количество открытых коробок будет корень из N с округлением до меньшего целого.
This comment wasn’t rated yet0
Задачка вообще математически решается?
По моему посчитать количество простых чисел на интервале и то проще ;/
This comment wasn’t rated yet0
У меня тоже задача вызвала ассоциации с «решетом Эратосфена» :)
Total votes 1: ↑1 and ↓0+1
Оценить нормально человека только задачкой — «бред» их HR-менеджера, а так же показывает, что они (скорей отдел по поиску персонала) изначально неуважительно относятся к сотруднику.
Total votes 2: ↑1 and ↓10
имхо, отличный формат отбора — так как ты вынужден решить задачу сразу, то не имеешь возможности воспользоваться тем же гуглом :) а так как заведомо большинство не пройдет и первую стадию, то они не тратят твоего и своего времени на встречу в офисе. А с улицей… тут не угадаешь, можно было бы сказать об этом
This comment wasn’t rated yet0
это больше смахивает на какой-то «трюк». Тут вот и с гуглом пока решения не нашли.
Имхо, таким способом можно потерять кучу толковых ребят )
This comment wasn’t rated yet0
Зато те, которые останутся…
This comment wasn’t rated yet0
Не факт, что останутся гении )
This comment wasn’t rated yet0
Все так, но похоже что им надо не совсем нормальные люди, а именно такие, которые могут решить эту задачку в любое время. Вероятно к сотруднику они будут относиться уважительно. А человеку, который им прислал резюме они в принципе вообще ничем не обязаны.
This comment wasn’t rated yet0
вы думаете, что нет людей, способных решить эту задачу в уме?
This comment wasn’t rated yet0
суть не в этом. Если да же есть такие люди и эта задача решается, не факт, что они лучше специ, чем те, кто не решил эту задачу… слишком простое отсеивание
This comment wasn’t rated yet0
Если N коробок = 1, то открыты все коробки
Если N коробок = 2, то открыто N/2 коробок
Если N коробок = 3, то открыто (N/2)-1 коробок
Если N коробок = 4, то открыто N/2 коробок
Если N коробок >= 5, то открыто (N/2)-1 коробок

тестировал только на маленьких значениях, но мне кажется что тенденция (N/2)-1 сохраняется
Total votes 5: ↑1 and ↓4-3
Только не (N/2) -1, а (N-1)/2.
Т.е. для чётных N/2, а для нечётных (N-1)/2.
Total votes 2: ↑1 and ↓10
UFO just landed and posted this here
1 не вляется простым числом
Total votes 2: ↑1 and ↓10
нет, ибо на тех же 3 и 5 вы получите открытыми 0.5 коробки и 1.5 коробки. А при 6-ти коробка что получите?
This comment wasn’t rated yet0
черт, посчитал еще немного и пришел к выводу, что:
При четном количестве коробок — остается 2 открытых коробки
А при нечетном — 3 коробки открыты
Total votes 1: ↑0 and ↓1-1
UFO just landed and posted this here
UFO just landed and posted this here
UFO just landed and posted this here
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()
This comment wasn’t rated yet0
>countBoxes = 40
а если ящиков больше 40? скажем 400?
Total votes 1: ↑0 and ↓1-1
ну? а в чем проблема?
This comment wasn’t rated yet0
Зачем использовать sys.stdout.write если есть print?
This comment wasn’t rated yet0
Я считаю, что хорошо было бы сказать хоть какой-то вариант, аргументировав свою точку зрения, и рассказав ход своих мыслей. Если мыслите в правильном направлении даже в такой ситуации, то найти полное верное решение уже не так важно.
This comment wasn’t rated yet0
Ему нужно было сказать хоть что то. Хотябы 45 или 1 или 256. Так как любой пусть и не правильный ответ лучше чем никакой.
This comment wasn’t rated yet0
Вот сейчас на работе маркетолог мне минут 10 предлагала наугад кучу вариантов, типа «В таких задачах ответ обычно '1', либо 'все'.........». Так что отвечать наугад — самый имхо глупый вариант, показывающий вашу неспособность подумать самому, тем более зная контору, с которой вам дали задание.
Total votes 1: ↑1 and ↓0+1
Хм… 1 либо все… у человека явно мистическое восприятие реальности. Вроде бы, уже чисто умозрительно должно быть понятно, что всегда получатся закрытыми вторая коробка, последняя коробка и все коробки между ними, чьи номера являются простыми числами, и это еще далеко не ответ :)
Total votes 1: ↑1 and ↓0+1
Насчёт последней коробки — вы погорячились. При N=4 или 9 последняя открыта.
Но самой логики ваших абстрактных рассуждений это не меняет.
This comment wasn’t rated yet0
Да, на счёт последней коробки я жостко прогнал — число хитов по ней есть величина переменная, значит, она может быть как открытой, так и закрытой.
This comment wasn’t rated yet0
По-моему, гадать — самое худшее, что тут можно сделать. После самых поверхностных размышлений становится ясно, что красивого ответа не будет, а в лучшем случае может получиться функция от N. Следовательно, догадаться нереально, и кроме того, игра в угадайку — это явно не то, что от адекватного кандидата ожидают услышать в процессе интервью.
This comment wasn’t rated yet0
Ну вы же не будите говорить: «И так мой ответ наугад такой то»
Вы серьезным голосом скажите мой ответ 666.
This comment wasn’t rated yet0
Ага, а они мне: «Неправильно.» А я тогда: «Ну… эээ… 665?...»
This comment wasn’t rated yet0
Да это элементарное распи№;%йство с их стороны, они этим еще два года назад страдали при приеме, когда я к ним поступал.

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

Надо был говорить «сейчас не могу, давайте позже».
Total votes 2: ↑1 and ↓10
То есть, если я когда-то такую задачу решал(для интереса, препод в школе задал, в инете ответ увидел и т.д.), и ответил правильно, то прошел бы собеседование, а кто-то, кто умнее меня, но с такой задачей не сталкивался — не прошел бы?
Total votes 2: ↑2 and ↓0+2
Тут задачка простого решения не имеет, как и все задачки, связанные с подсчетом простых чисел. Рекруте, судя по всему, просто хотел узнать ход рассуждений, увидеть в каком направлении работает у человека мысль.
Теперь по поводу решения задачи: тут сразу понятно, что все коробки с номером, которое является простым числом, будут закрыты, поскольку по ним можно пройти только один раз. Остальные же коробки будут закрыты или открыты в зависимости от количества простых делителей номера коробки и степеней их вхождения. В общем, какую-то универсальную формулу вывести довольно-таки сложно, тем более на ходу по телефону.
Total votes 2: ↑1 and ↓10
Кстати, вот формула: если есть число M=(p1^n1)*(p2^n2)*(p3^n3)*...*(pk^nk), то
количество разных делителей будет равно ((2^k)-1)*n1*n2*n3...*nk. Если это число четное, то коробка будет открытой, нечетная — закрытой.

This comment wasn’t rated yet0
нету нету… есть!
Ответ: Целая часть от корня числа N.
Total votes 1: ↑1 and ↓0+1
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
Total votes 3: ↑3 and ↓0+3
Ваше решение надо поместить в тему топика, иначе ответы так и будут сыпаться ;)
This comment wasn’t rated yet0
Опытным путём получается таки $openboxes = floor(sqrt($n)); как и написано выше.
На счёт сложности посчитать в уме… На сколько я помню, в вышке есть некий метод для примерного вычисления корня. И наверное, зная этот метод можно было бы, наверное, и догадаться.

Total votes 2: ↑1 and ↓10
Вы тут все математики, а задача-то лигическая.
This comment wasn’t rated yet0
Фигасе логика :) на два коммента выше (на данный момент на 2) есть результаты для всех вариантов до 100. Даже там логически сложно вывести формулу посреди улицы и выдать в трубку ответ в виде формулы, не говоря уже об ответе сразу на задачу.
This comment wasn’t rated yet0
Логика не в том как решить задачу, а что ответить интервьюеру.
Total votes 1: ↑1 and ↓0+1
Конечное состояние каждой коробки зависит от числа натуральных делителей её порядкового номера в диапазоне [2; Nкор.]:
— если число делителей четное, то коробка открыта;
— если число делителей нечетное — коробка закрыта.
Т.е. подсчитав кол-во чисел от 1 до N, имеющих четное число делителей можно узнать кол-во открытых коробок.
Total votes 1: ↑1 and ↓0+1
открытыми остануться только коробки, которые открыли/закрыли четное кол-во раз, т.е. которые имеют четное кол-во разных делителей (не считая 1) и НЕЧЕТНОЕ, если 1 считать. Но любое число k, делящееся нацело на l, делится и на k/l тоже, т.е. разные делители входят парами. Исключение составляют квадраты целых, т.е. искомые номера коробок — квадраты целых, таких квадратов SQRT(N). Отсюда ответ SQRT(N) (с отброшенной дробной частью)
Total votes 6: ↑6 and ↓0+6
UFO just landed and posted this here
+1. я тоже пришел к такому решению.

Вообще, имхо, если можешь решить задачку — тебе нефиг делать в Гугле… Делай свой ГУГЛ!!! В смысле -стартап ;-)
This comment wasn’t rated yet0
UFO just landed and posted this here
а вот и не все n^2 будут открыты. 36 например будет закрыта :)
Total votes 1: ↑0 and ↓1-1
UFO just landed and posted this here
Ответ — количество простых чисел, не превосходящих N — функция Эйлера.
Total votes 1: ↑0 and ↓1-1
Требуется отобрать коробки, которые будут затронуты четное кол-во раз.

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

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

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

Значит, другие открытые ящики, кроме четных степеней простых чисел, невозможны.
This comment wasn’t rated yet0
поправлюсь, там где мы имеем четное кол-во комбинаций, нужно отбросить единицу, соответствующую случаю, когда не выбран ни один из множителей. Т.е. количество проходов будет четным
This comment wasn’t rated yet0
может быть в такой ситуации лучше объяснить ситуацию и самому перезвонить им было?
Total votes 1: ↑1 and ↓0+1
UFO just landed and posted this here
я посреди улицы посчитал бы вслух итерации для 5 и 6 коробок и слелал бы какое то предположение насчет зависимости открытых коробок от N и его четности. Ну и если б знал математику наверное что то загнул бы про квадраты и эйлера быть может. Проверяется то не правильность решения а то растеряется ли ли человек и каким путем пойдет решение.
This comment wasn’t rated yet0
Многие что-то сложное пытаются придумать — понять четное или нечетное число делителей у числа, не считая единицу (что нам собственно и нужно), очень просто:

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

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

Таким образом (как уже несколько раз написнао выше), ответ — количество точных квадратов до n, то есть floor(sqrt(n)).
Total votes 2: ↑2 and ↓0+2
Точнее — floor(sqrt(n))+1 (первая коробка всегда открыта) :)
This comment wasn’t rated yet0
И все же Вы не правы. Проверьте свой ответ хотя бы при n=1 и n=2.
This comment wasn’t rated yet0
ппц компания. ГееПидорги программисты. И Hr-ы с садистскими наклонностями :)
Total votes 7: ↑1 and ↓6-5
Напомнило как сам в западную контору из-за разницы во времени собеседовался по телефону в 10 часов вечера.
This comment wasn’t rated yet0
сумма (фунция эйлера(i) mod 2) по i от 1 до n?
This comment wasn’t rated yet0
По-моему, быть не может, чтобы ему предлагали пройти телефонное интервью без предварительного согласования с ним времени. В России так точно не делают. В других странах по идее тоже не должны, так как стандарты общие для всего гугла. Может, с ним договорились о времени собеседования, а он забыл?
Total votes 2: ↑1 and ↓10
По-моему, вполне принимается решение с обоснованием, что открытыми останутся только коробки с теми номерами, которые являются точными квадратами. В принципе, решение реально находится за одну минуту, в другом месте встречал такую задачку, вполне очевидная на мой взгляд.
Total votes 1: ↑1 and ↓0+1
А откуда гугл узнал что он на улице и так не кстати ему позвонил? Может он дома в тапочках, рядом столик ручка и бумага?
This comment wasn’t rated yet0
помойму давно известно, что гугл знает все…
This comment wasn’t rated yet0
>А откуда гугл узнал что он на улице и так не кстати ему позвонил? Может он дома в тапочках, рядом столик ручка и бумага?
Может, он дома в тапочках, а рядом… компьютер, браузер и Гугл!
This comment wasn’t rated yet0
У меня здесь два варианта — либо Гуглю нужны математики-полугении ( ;) ), либо вопрос стоит в области психологии — сможете ли вы отказаться от чрезвычайно выгодного предложения (пусть на время, то есть — отложить рассмотрение этого предложения). Ну хорошо, человек на улице просто шел, а если бы он был на совещании, за рулем, решал иную задачу?…
This comment wasn’t rated yet0
UFO just landed and posted this here
Он возможно эту б задачу и не решил, но зато он такие трояны под винду пишут, который покупаются за бешенные деньги.
Сомневаюсь, что гугл интересуется троянами под винду.
Total votes 1: ↑1 and ↓0+1
UFO just landed and posted this here
Раз эти методы до сих пор применяются, есть подозрение, что они все-таки работают. И потом, в интернетах почему-то пишут только про заваленные собеседования — может, с теми, кто способен осилить задачки, уже говорят о том, какие они спецы?
This comment wasn’t rated yet0
чорт! это реально количество квадратов, меньшее или равное N!
This comment wasn’t rated yet0
это не факториал, а восклицательный знак.
This comment wasn’t rated yet0
а вот тут некто Макс Чубин изобразил флешку с экспериментом для наглядности :-)))
test.chubin.ru/task/
Total votes 4: ↑4 and ↓0+4
Ха-ха-ха… повеселили, спасибо! :-)
This comment wasn’t rated yet0
Решение верное, а объяснение неверное.
>>У всех чисел от 1 до N (кроме полных квадратов) есть четное (2k) количество делителей — то есть действие
>>«закрыл-открыл» происходит k раз и в результате всё равно коробка открыта остается
Для всех чисел кроме квадратов коробки как раз останутся закрытыми, потому что каждую первую мы никогда не закрывали. А открытыми останутся только квадраты.
Именно поэтому решением и является floor(sqrt(N)), как вы верно и сказали.

Спасибо за пост.
Total votes 1: ↑1 and ↓0+1
Для наглядности:

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))
This comment wasn’t rated yet0
UFO just landed and posted this here
UFO just landed and posted this here
Я не совсем понял утверждение «нечетное число делителей имеют квадраты» — число 3*5*7=105 имеет три делителя, отличных от самого себя и единицы и не является квадратом
По самой задаче — если честно, в условиях, описанных автором, не решил. Но в целом вы идете правильным путем. Надо было сказать, что их будет столько, сколько чисел от 1 до N имеют нечетное количество делителей.
This comment wasn’t rated yet0
UFO just landed and posted this here
Автор топика дал не много информации, но по видимому это было стресс-интервью. Во-первых, не понятно в каком городе/стране интервьюировали человека. Судя по тому, что образование — 1 степень университет по Computer Sciences, это не Россия и не московский гугл, так что не пугайтесь раньше времени потенциальные соискатели. Во-вторых, не понятно на какую должность претендовал человек. Стресс-интервью проводят для должностей подразумевающих стрессовые перегрузки. Похоже это была должность программиста. На первый взгляд, для программиста стрессоустойчивость не ключевой параметр, но как отметил EaE, в условиях большого количества соискателей, логично брать тех, кого потом можно будет растить на другие должности, так называемый «кадровый резерв». Тот же программист потенциально может стать управляющим проектами, а там стрессоустойчивость важна.
тут все указывает на стресс-интервью, человеку звонят неожиданно, и дают задачу, практически не решимую за короткое время. HR-менеджеры тоже не идиоты и все понимают. Важно то, как среагирует кандидат, будет мямлить, предложит нестандартный выход или что-то еще
This comment wasn’t rated yet0
UFO just landed and posted this here
Раз пошла такая пьянка, добавлю и свои пять копеек, которые навели на прав ответ:

public static void main(String[] args) {
// TODO code application logic here
int count = 50;
boolean[] items = new boolean[count];
for (int i = 0; i < count; ++i)
items[i] = false;
for (int i = 2; i <= count; ++i)
{
for (int j = i; j <= count; j+=i)
{
items[j-1] =! items[j-1];
}
}
for (int i = 0; i < count; ++i)
if (! items[i])
System.out.print(« „ + ++i);
System.out.println();
}
Total votes 1: ↑0 and ↓1-1
UFO just landed and posted this here
В какой офис гугла устраивался друг, если не секрет
Total votes 1: ↑1 and ↓0+1
Я объясняю, в такого рода ситуациях и задачках важно увидеть, что человек умеет мыслить так как нужно для решения таких задачек. Я бы в любых условиях, спросонья и на улице решил бы эту задачку. Ну и как минимум в ближайшие 30 секунд бы продемонстрировал бы адекватному слушателю, что эту задачку для меня решить вопрос времени и бумажки, чтобы внимательно все случаи проанализировать, а скорее всего дал бы и ответ.
Видимо, у них столько народу просится, что они могут искать не просто людей решаюзих таких задачки, но людей решающих такие задачки без напряга и походу. Когда я учился в институте, в моей группе человек 5 было, которые вполне способны были на такой трюк, я не про точный ответ, я про то, что сразу бы нашли правильный способ найти этот ответ. Это как правило те люди, что побеждали на олимпиадах по матиематике, физике или програмированию.
Total votes 1: ↑0 and ↓1-1
> Я бы в любых условиях, спросонья и на улице решил бы эту задачку.

«Потому что до этого поросята видели волка только на картинке» — из детской сказки…
Total votes 1: ↑1 and ↓0+1
Возможно и так. Но 10 лет надрочки маткружка врядли совсем уж бесследно для меня прошли.
Total votes 1: ↑0 and ↓1-1
Зачем 10 лет — не понятно. Такую задачку обычно дают на кружке в пятом-шестом классе (первый год обучения) в теме делимость. Что-то вроде «Докажите, что если число является полным квадратом тогда и только тогда, когда количество его делителей нечётно».
This comment wasn’t rated yet0
еще одно подтверждение того, что красивый диплом не особо ценная бумажка. серьёзным конторам нужны не отличники, заучившие книги наизусть, а люди с головой на плечах.
Total votes 1: ↑1 and ↓0+1
Ну если человек не просто так отлично получал на физмате, например, то, думаю, он решит подобную задачу.
This comment wasn’t rated yet0
учусь на прикладной математике. 90% из получающих отлично — тупо задроты, при виде задачи не описанной в учебниках уходят в глубокий даун. а вот участвующих в разных там acm-icpc и надо гуглам. так что «получать отлично на физмате» можно и не то чтобы просто так, но не особо напрягая извилины. в итоге получается очередной кодер, знающий пару шаблонов, да клепающий энтерпрайз проги по 5 штук в неделю. с отличным дипломом.
This comment wasn’t rated yet0
Т.е. 3 и 4 никакого отношения не имеют к знаниям, трудолюбию/лени/силе воли, разносторонности человека?
Я согласен, иногда, особенно на последних курсах бывают ситуации, что оценки ставятся накатом, например студент откровенно сдал на 3 или 4, но в зачётке у него одни пятерки и преподу приходится ставить 5, но именно на этот случай я написал «не просто так».

В общем я считаю, что если человек учится на 5, и 5 соответствует знаниям, а не стечению обстоятельств — то он обязан решить такую задачку. =)

И опять же если человек решает подобную задачу, но учится на 3 и 4 — это говорит о том что он умен, но ленив, или ему неинтересен предмет (за редким исключением виноваты обстоятельства, в виде особо злобных преподов). Зачем Гуглу ленивые или не интересующиеся люди?
This comment wasn’t rated yet0
я не совсем о том…
как пример могу привести зазубривание теорем перед экзаменом. ведь можно понять как её доказать, что и сотворить при необходимости, а можно выучить доказательство как стишок да забыть через месяц. так вот многие из получающих пять очень любят второй метод. но ведь это не знания?
This comment wasn’t rated yet0
Если зубрить, то да, ерунда выйдет.
А, знания — это то что остается, когда вы все забудете =)
This comment wasn’t rated yet0
Ващето, как раз там написано, что они берут только отличников. Всех кто ниже они даже не пробуют прогонять через эти тесты.
This comment wasn’t rated yet0
В городе N тоже решили провести телефонное интервью:
— Как к свехрурочным относишься? Хорошо?
— Хорошо
— А если надо, обжать кабель вместо админа сможешь?
— Смогу.
Ну ладно… Слушай задачу. К бассейну подведены две… а ну и фиг сней! Берем!
Total votes 2: ↑2 and ↓0+2
А я с Гуглом не согласен. Я никто, а Гугл — великий, но все равно не согласен. Бог создал разных людей. Кто-то не стрессоустойчивый от природы, кто-то не умеет решать быстро, потому что глубоко копает, но все типы нужны и в какой-то ситуации могут играть решающую роль.
This comment wasn’t rated yet0
Задача математическая на знание численных методов. Тут даже программировать не надо.

Вначале было 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

Самый главный вопрос в какую сторону округлить :)
This comment wasn’t rated yet0
Пардон, поспешил…
я подсчитал кол-во коробок, которые изменят свое состояние, то есть будут закрыты.
Открытых соответственно будет N * (1 – ln 2)   ~   0.31 * N
This comment wasn’t rated yet0
UFO just landed and posted this here
Точно!
После корпоративки неверно прочитал условие задачи! :)
Я понял так, что коробки по очереди на одном шаге закрываются, а на следующем открываются. А они меняют состояние, в таком случае ряд будет совсем другой, навроде:
1/2 - 1/8 + 1/16 - 5/128 + ...
А это именно разложение sqrt(N)
Сорри, кого сбил с толку!
This comment wasn’t rated yet0
UFO just landed and posted this here
UFO just landed and posted this here
UFO just landed and posted this here
На самом деле вопрос совершенно не в этом.
А в том, что действительно не надо дергать человека посреди улицы.
This comment wasn’t rated yet0
Извините за занудство, но UPD 2 неправильный — проверьте задачу при 10 коробках.
Total votes 1: ↑0 and ↓1-1
Вроде работает:
Image and video hosting by TinyPic
Ответ: 3
Жирным шрифтом выделены изменения состояния.
Слева номера шагов.
Желтым выделены открытые коробки.
This comment wasn’t rated yet0
да, печально.
можно было бы не растеряться, и сказать, мол, извините, сейчас не могу говорить (вдруг он ведет авто), перезвоните через n минут, или позвольте, я вам перезвоню.
Это нормальная ситуация, и нечего перед гуглем падать на колени и боготворить его.
Но это в идеале.

… И такой случай НЕ показывает высокую компетентность их эйчарников.
Total votes 1: ↑1 and ↓0+1
а 50 на 50? или з звонок другу? :)
This comment wasn’t rated yet0
если звонят из Гугля, отвечаем «Извините это уже не актуально» :)
This comment wasn’t rated yet0
До меня только сейчас дошло, а жена после того, как я задал эту задачу, решила ее еще до того, как я конечный вопрос задал!

Задача:

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

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

Получится:

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

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

Хотя вот сейчас сомнения закрались… завтра опыт поставлю.
Total votes 1: ↑1 and ↓0+1
неправильно
Все коробки открыты. Закрываем вторую. Закрываем третью. ОТКРЫВАЕМ четвертую. Закрываем пятую…
Total votes 1: ↑1 and ↓0+1
Да. Уже осознал. А ответ казался таким заманчивым.
This comment wasn’t rated yet0
а я хотела бевербунг писать…
как-то страшно стало :)
This comment wasn’t rated yet0
UFO just landed and posted this here
Утром, на свежую голову задачка показалась гораздо проще чем во второй половине рабочего дня )
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 подобный ряд предлагали дополнить в анкете в военкомат. =)
This comment wasn’t rated yet0
В общем надо коробки открывать/закрывать в порядке не по условию задачи (сначала каждую вторую, потом каждую третью и т.д.), а именно производить все действия сразу над одной коробкой: сначала делаем со второй все действия, потом с третьей, с четвертой — так проще.
This comment wasn’t rated yet0
Похоже Гуглу нужны работники, которые рассчитывают маршрут до магазина и обратно в уме с помощью рядов Фурье. Представляете как должен выглядеть этот «кадр»? ;)
This comment wasn’t rated yet0
сдается мне, что их интересовал не точный ответ, сама реакция на поставленную задачу… наверное они хотели узнать, что человек не растеряется, а начнет искать решение. Правильное или неправильное, это пока неважно.
This comment wasn’t rated yet0
Ответ может найти практически каждый, если посидеть и подумать. А вот сообразить в экстремальной ситуации мало кому под силу. Получается, что в гугле не лучшие из лучших, а люди, обладающие высоким уровнем самоконтроля)
This comment wasn’t rated yet0
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
This comment wasn’t rated yet0
если посмотреть на нижний ряд, то можно увидеть, что открытые ящики будут оставатся через n = n+2 ящиков
This comment wasn’t rated yet0
UFO just landed and posted this here
Sign up to leave a comment.

Articles

Show the best of all time

Your account

Sections

Information

Services

Support
© 2006–2024, Habr