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

[avva]

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

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

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

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

Comments

[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]

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