Хабрахабр / Комментарии к посту «Устройство на работу» в блоге «Google»

30.09.2008 07:09:24 avsmal

avsmal — Tue, 30 Sep 2008 07:09:24 GMT

Зачем 10 лет — не понятно. Такую задачку обычно дают на кружке в пятом-шестом классе (первый год обучения) в теме делимость. Что-то вроде «Докажите, что если число является полным квадратом тогда и только тогда, когда количество его делителей нечётно».

29.09.2008 17:34:35 AlexCult

AlexCult — Mon, 29 Sep 2008 17:34:35 GMT

Вычислили его местоположение с помощью google-maps?

29.09.2008 07:49:03 Snipe

Snipe — Mon, 29 Sep 2008 07:49:03 GMT

Если зубрить, то да, ерунда выйдет.
А, знания — это то что остается, когда вы все забудете =)

27.09.2008 16:53:05 GreLI

GreLI — Sat, 27 Sep 2008 16:53:05 GMT

Блин, где бот, зачитывающий комментарие перед отправкой?

27.09.2008 16:51:12 GreLI

GreLI — Sat, 27 Sep 2008 16:51:12 GMT

(n+1)^2 − n^2 = 2*n + 1
Действительно, каждый следующий открытый ящик отстоит от предыдущего на два ящика больше, чем предшественник.

26.09.2008 22:54:54 fractalizator

fractalizator — Fri, 26 Sep 2008 22:54:54 GMT

куда, в Цюрих?

26.09.2008 14:32:06 bak1an

bak1an — Fri, 26 Sep 2008 14:32:06 GMT

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

26.09.2008 11:42:18 l2k

l2k — Fri, 26 Sep 2008 11:42:18 GMT

Совершенно верно :)
Тоже пришел к такому-же результату.

26.09.2008 09:28:55 Nuru

Nuru — Fri, 26 Sep 2008 09:28:55 GMT

если посмотреть на нижний ряд, то можно увидеть, что открытые ящики будут оставатся через n = n+2 ящиков

26.09.2008 09:27:11 Nuru

Nuru — Fri, 26 Sep 2008 09:27:11 GMT

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

26.09.2008 08:35:24 rukavruku

rukavruku — Fri, 26 Sep 2008 08:35:24 GMT

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

26.09.2008 08:24:20 afi

afi — Fri, 26 Sep 2008 08:24:20 GMT

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

26.09.2008 08:01:20 jeje

jeje — Fri, 26 Sep 2008 08:01:20 GMT

да я собственно это уже понял, не судьба многим туда попасть, но я думаю к лучшему.

26.09.2008 07:58:42 sero

sero — Fri, 26 Sep 2008 07:58:42 GMT

Я думаю, что эти методы достаточно оправданы для компании, которая имеет ткой широкое поле деятельности. Выучить Java API или, как строить SQL запросы может и гуманитарий, это лишь инструмент, но вот для грамотного использования этих инструментов необходимо аналитическое мышление, которое развивается исключительно математикой\физикой\другими точными науками. Программирование, конечно, тоже вносит свою лепту в развитие, но довольно специфическую. Любой программист легко написал бы программу, которая решит предложенную задачку — для данного N посчитать число открытых ящиков, но чтоб решать такие задачки математически, или аналитически, нужно в другой плоскости мыслить

26.09.2008 07:01:23 konopko

konopko — Fri, 26 Sep 2008 07:01:23 GMT

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

26.09.2008 06:53:26 m2x

m2x — Fri, 26 Sep 2008 06:53:26 GMT

И все же Вы не правы. Проверьте свой ответ хотя бы при n=1 и n=2.

26.09.2008 06:45:46 123

123 — Fri, 26 Sep 2008 06:45:46 GMT

Точнее — floor(sqrt(n))+1 (первая коробка всегда открыта) :)

26.09.2008 06:25:04 Snipe

Snipe — Fri, 26 Sep 2008 06:25:04 GMT

Т.е. 3 и 4 никакого отношения не имеют к знаниям, трудолюбию/лени/силе воли, разносторонности человека?
Я согласен, иногда, особенно на последних курсах бывают ситуации, что оценки ставятся накатом, например студент откровенно сдал на 3 или 4, но в зачётке у него одни пятерки и преподу приходится ставить 5, но именно на этот случай я написал «не просто так».

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

И опять же если человек решает подобную задачу, но учится на 3 и 4 — это говорит о том что он умен, но ленив, или ему неинтересен предмет (за редким исключением виноваты обстоятельства, в виде особо злобных преподов). Зачем Гуглу ленивые или не интересующиеся люди?

26.09.2008 06:23:26 glider

glider — Fri, 26 Sep 2008 06:23:26 GMT

Раз эти методы до сих пор применяются, есть подозрение, что они все-таки работают. И потом, в интернетах почему-то пишут только про заваленные собеседования — может, с теми, кто способен осилить задачки, уже говорят о том, какие они спецы?

26.09.2008 06:13:59 Snipe

Snipe — Fri, 26 Sep 2008 06:13:59 GMT

В общем надо коробки открывать/закрывать в порядке не по условию задачи (сначала каждую вторую, потом каждую третью и т.д.), а именно производить все действия сразу над одной коробкой: сначала делаем со второй все действия, потом с третьей, с четвертой — так проще.

26.09.2008 06:00:36 Snipe

Snipe — Fri, 26 Sep 2008 06:00:36 GMT

Утром, на свежую голову задачка показалась гораздо проще чем во второй половине рабочего дня )
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 подобный ряд предлагали дополнить в анкете в военкомат. =)

26.09.2008 05:08:42 creotiv

creotiv — Fri, 26 Sep 2008 05:08:42 GMT

да причем сдесь гугл… я вообще глобально говорю. Что человек спец своего дела. И решит он эту задачку или нет сути дела это не изменит. А посему появляется проблема проблема подбора персонала, ибо методы для выявления кандидатов не показывают реальную суть вещей. Возникает вопрос, зачем тогда эти методы юзать? Можно ведь и новый способ придумать.

26.09.2008 04:25:35 mkechinov

mkechinov — Fri, 26 Sep 2008 04:25:35 GMT

Да. Уже осознал. А ответ казался таким заманчивым.

26.09.2008 04:11:21 namor

namor — Fri, 26 Sep 2008 04:11:21 GMT

неправильно
Все коробки открыты. Закрываем вторую. Закрываем третью. ОТКРЫВАЕМ четвертую. Закрываем пятую…

25.09.2008 22:53:15 xpic99

xpic99 — Thu, 25 Sep 2008 22:53:15 GMT

Вроде работает:

Ответ: 3
Жирным шрифтом выделены изменения состояния.
Слева номера шагов.
Желтым выделены открытые коробки.

25.09.2008 21:27:49 glider

glider — Thu, 25 Sep 2008 21:27:49 GMT

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

25.09.2008 21:06:16 GreLI

GreLI — Thu, 25 Sep 2008 21:06:16 GMT

Не, всё-таки вниз.
Открыты: 1 (он же первый квадрат), 2-й квадрат — 4, 3-й — 9 и т.д. сколько умещается, по скольку искомый номер, одновременно является корнем, то ответ — округлённый корень.

25.09.2008 21:05:28 trisch

trisch — Thu, 25 Sep 2008 21:05:28 GMT

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

25.09.2008 21:03:26 GreLI

GreLI — Thu, 25 Sep 2008 21:03:26 GMT

Переглючило, закрытые считал, а их больше :).

25.09.2008 20:57:17 GreLI

GreLI — Thu, 25 Sep 2008 20:57:17 GMT

Не просто целая часть, а с округлением вверх, первая-то открыта всегда.

25.09.2008 20:53:56 GreLI

GreLI — Thu, 25 Sep 2008 20:53:56 GMT

Первый ход — половина закрылась, второй ход — треть из открытой половины закрылась, треть из другой половины открылась, осталась закрытой половина, и так далее :). В пределе выходит N/2. Но этот подход не учитывает конечность, так что N/2 — это нижний предел. С таким подходом не решишь.

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

25.09.2008 20:37:45 mkechinov

mkechinov — Thu, 25 Sep 2008 20:37:45 GMT

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

Задача:

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

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

Получится:

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

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

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

25.09.2008 19:48:42 el777

el777 — Thu, 25 Sep 2008 19:48:42 GMT

Точно!
После корпоративки неверно прочитал условие задачи! :)
Я понял так, что коробки по очереди на одном шаге закрываются, а на следующем открываются. А они меняют состояние, в таком случае ряд будет совсем другой, навроде:
1/2 - 1/8 + 1/16 - 5/128 + ...
А это именно разложение sqrt(N)
Сорри, кого сбил с толку!

25.09.2008 19:47:43 tapin13

tapin13 — Thu, 25 Sep 2008 19:47:43 GMT

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

25.09.2008 19:34:25 bruno

bruno — Thu, 25 Sep 2008 19:34:25 GMT

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

25.09.2008 18:54:40 GreLI

GreLI — Thu, 25 Sep 2008 18:54:40 GMT

Что-то я не пойму: у вас формула вида Const*N, а график-то не линейный.

25.09.2008 18:29:01 Rchernovol

Rchernovol — Thu, 25 Sep 2008 18:29:01 GMT

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

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

25.09.2008 18:27:47 Yevhen

Yevhen — Thu, 25 Sep 2008 18:27:47 GMT

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

25.09.2008 18:25:37 dkuznetsov

dkuznetsov — Thu, 25 Sep 2008 18:25:37 GMT

Да, им нужны не просто программисты. Если человек сходу решит такую задачку — он вероятно талантлив, что им подходит. Если человек знал о такой задачке — то он вероятно интересуется заковыристыми задачками, что говорит по крайней мере о том, что он не совсем уж глуп. Это тоже не так уж плохо. У Гугла эффективный способ отсева серой массы, как по мне.

25.09.2008 18:21:24 egorinsk

egorinsk — Thu, 25 Sep 2008 18:21:24 GMT

Значит, им нужны не просто программисты. Логично? А написать пару строк на php — тут конечно, каждый справится.