альтернатива физзбаззу

[avva]

Цитирую из подзамочной записи с разрешения автора, который работает в американской компании и интервьюирует программистов:

Интесная закономерность выявляется. Мы начинаем интервью с того, что просим кандидата прочитать вот такой код, и сказать, что он делает. Как бы он назвал эту функцию?

private static int ok(int a, int b) {
   while (a >= b) a -= b;
   return a;
}

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

Comments

[piter239.livejournal.com]

Без гарантии "все числа различные" сортировать таки надо. Гарантия была в задании?

[gineer.livejournal.com]

"массив чисел от 0 до 255 размером 256"

ну, собственно, я сам тоже не сразу дотумкал, в чом подвох,
хоть и сразу, что он есть.
просто предствьте на более очевидном примере, что ли.
типа массив из 4 чисел, от 0 до 3. ;)

[mtyukanov.livejournal.com]

Ну и? Типа массив из 4 чисел, от 0 до 3: {2,1,0,1}. Отсортируем, пользуясь знанием о возможных значениях 0..3. Задача на самом деле довольно интересная.

[d-ohrenelli.livejournal.com]

сортировать все равно не нужно.
Посчитать количество каждого номера и сгенерировать массив.
O(n)

[gineer.livejournal.com]

да, я тоже так понял, сперва
но, там, всетаки, еще было ЭТО требование -- каждое из чисел встречается один раз. ;)

[mtyukanov.livejournal.com]

Так "подсчитать количество каждого номера и сгенерировать массив" -- это и есть "сортировать" для данного случая. Если бы под "сортировать" имелось в виду "пользоваться стандартными методами сортировки" -- это было бы просто глупо.

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

Можно развить ее до более задумчивой, если запретить использовать для подсчета внешний контейнер -- предположим, дело происходит в условиях жестких ограничений по памяти, нужен чистый inplace. Или просто порассуждать, когда для хранения количеств лучше пользоваться массивом, а когда динамической структурой вроде списка. Ну и, да, спросить, а что будет, если добавить условие "неповторяющиеся числа". Все легкое, но все вполне осмысленное.

[gineer.livejournal.com]

дык... там и была эта оговорка, про "неповторяющиеся числа",
которая обессмысливает вообще сам вопрос
по крайней мере с моей т.з.
с точки зрения интервбюера -- все было ок :)

[d-ohrenelli.livejournal.com]

Я проверил, это, кстати, стандартный алгритм сортировки, на3ывается сортировка подсчетом или
counting sort.

Так что я был не прав.

[unbe.livejournal.com]

http://en.wikipedia.org/wiki/Counting_sort

[unbe.livejournal.com]

ой, поздно заметил ваш ответ на собственный комментарий.

[piter239.livejournal.com]

Берем пример 0 0 0 1

В чем подвох?

[gineer.livejournal.com]

http://avva.livejournal.com/2625137.html?thread=95997041#t95997041

[piter239.livejournal.com]

да это-то сразу понятно.

Непонятно другое: с какой целью (или по какой причине) Вы КЛЮЧЕВОЕ требование -- каждое из чисел встречается один раз

не упомянули ни в первом своем комментарии, ни в ответе на мой прямой вопрос о гарантии "все числа различные"?