Задачка про локальные максимумы

[Izh]

... хорошо дает понять, каково отношение к программированию
у соискателя.

Итак:

Написать функцию, которая имеет массив целых чисел на
входе и возвращает количество локальных экстремумов
(максимумов) в данном массиве. Возможный прототип на
C:

Code: Select all

unsigned int num_local_maximums( const int array[], size_t size );

[KP580BE51]

... хорошо дает понять, каково отношение к программированию
у соискателя.

Итак:

Написать функцию, которая имеет массив целых чисел на
входе и возвращает количество локальных экстремумов
(максимумов) в данном массиве. Возможный прототип на
C:

Code: Select all

unsigned int num_local_maximums( const int array[], size_t size );

n += ((array[i-1] < array[i]) && (array[i] > array[i+1])) ? 1 : 0;

Ы?

[Izh]

... хорошо дает понять, каково отношение к программированию
у соискателя.

Итак:

Написать функцию, которая имеет массив целых чисел на
входе и возвращает количество локальных экстремумов
(максимумов) в данном массиве. Возможный прототип на
C:

Code: Select all

unsigned int num_local_maximums( const int array[], size_t size );

n += ((array[i-1] < array[i]) && (array[i] > array[i+1])) ? 1 : 0;

Ы?

Задание понято неверно -- была просьба написать
функцию, которая возвращает количество локальных
максимумов. Не могли бы вы написать полное решение?

[KP580BE51]

Задание понято неверно -- была просьба написать
функцию, которая возвращает количество локальных
максимумов. Не могли бы вы написать полное решение?

В Москве все такие зануды?

unsigned int num_local_maximums( const int array[], size_t size )
{
unsigned int n=0,i;
for(i=1;i<size-1;i++) n += ((array[i-1] < array[i]) && (array[i] > array[i+1])) ? 1 : 0;
return n;
}

[Izh]

В Москве все такие зануды?

unsigned int num_local_maximums( const int array[], size_t size )
{
unsigned int n=0,i;
for(i=1;i<size-1;i++) n += ((array[i-1] < array[i]) && (array[i] > array[i+1])) ? 1 : 0;
return n;
}

Ваша функция не работает для массива, длина которого
равна 0 (в этом случае последствия катастрофичны), 1 или 2.

[kostia00]

Зависит от определения локального максимума. Работает, imho.

[KP580BE51]

В Москве все такие зануды?

unsigned int num_local_maximums( const int array[], size_t size )
{
unsigned int n=0,i;
for(i=1;i<size-1;i++) n += ((array[i-1] < array[i]) && (array[i] > array[i+1])) ? 1 : 0;
return n;
}

Ваша функция не работает для массива, длина которого
равна 0 (в этом случае последствия катастрофичны), 1 или 2.

Это раздел "головоломки".

[KP580BE51]

Зависит от определения локального максимума. Работает, imho.

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

[Izh]

Zavisit ot opredeleniya lokal'nogo maksimuma.

В этом-то и состоит подвох задачи. Эта задачка
на аккуратность и осознание человеком, того, что
он делает. Подразумевается, что человек попросит
определение локального максимума. Или задаст
его самостоятельно и укажет при решении.

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

[Izh]

Зависит от определения локального максимума. Работает, imho.

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

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

О последствиях -- они очевидно вытекают из того,
факта, что тип i у вас unsigned int и параметр size
равен 0. Наводящий вопрос: что произойдет при
этом с циклом?

[Izh]

Это раздел "головоломки".

И задачки для интервью, если я еще не разучился
читать.

[KP580BE51]

Zavisit ot opredeleniya lokal'nogo maksimuma.

В этом-то и состоит подвох задачи. Эта задачка
на аккуратность и осознание человеком, того, что
он делает. Подразумевается, что человек попросит
определение локального максимума. Или задаст
его самостоятельно и укажет при решении.

А если человек довольствуется тем, которое принято в математике, то интервью завалено?

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

Скажите, вы давно заглядывали в листинг? Который компилятор генерит?
А вообще, хотелосьбы посмотреть на решение задачи с одним сравнением.

Про отстутствие форматирования вообще
говорить не хочеться.

Все! Интервью завалено! Аднозначно!

[Izh]

А если человек довольствуется тем, которое принято в математике, то интервью завалено?

Определение из какой области математики?
Сформулируйте его, пожалуйста. Например,
ваше решение совершенно игнорирует существование плоских максимумов (то есть
есть таких, которые >= своих соседей).
Например, для массива 1,1,1 ваша функия
вернет 0.

Скажите, вы давно заглядывали в листинг? Который компилятор генерит?

Не так уж давно. Беда даже не в сравнении,
как таковом, а в том, что вы обращаетесь к
элементам массива несколько раз подряд,
что не очень хорошо, если ваш массив лежит
в медленной памяти. К тому же ваше решение
совершенно неприемлемо для последовательного
потока данных. (Тут, впрочем, можно спорить
будете ли вы представлять этот поток в виде
массива).

А вообще, хотелосьбы посмотреть на решение задачи с одним сравнением.

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

Про отстутствие форматирования вообще
говорить не хочеться.

Все! Интервью завалено! Аднозначно![/quote]

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

[Taffi]

unsigned int num_local_maximums( const int array[], size_t size )
{
BOOL bGrow = FALSE;
unsigned int n = 0, i;

for(i = 1; i < size; i++) {
if (array[i] >= array[i-1])
bGrow = TRUE;
else if (bGrow) {
n++;
bGrow = FALSE;
}
}
return n;
}

[KP580BE51]

А если человек довольствуется тем, которое принято в математике, то интервью завалено?

Определение из какой области математики?
Сформулируйте его, пожалуйста. Например,
ваше решение совершенно игнорирует существование плоских максимумов (то есть
есть таких, которые >= своих соседей).
Например, для массива 1,1,1 ваша функия
вернет 0.


Не так уж давно. Беда даже не в сравнении,
как таковом, а в том, что вы обращаетесь к
элементам массива несколько раз подряд,
что не очень хорошо, если ваш массив лежит
в медленной памяти. К тому же ваше решение
совершенно неприемлемо для последовательного
потока данных. (Тут, впрочем, можно спорить
будете ли вы представлять этот поток в виде
массива).

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

Определение максимума в математике достаточно однозначно - это точка в которой первая производная меняет знак. Но на практике, к примеру поиск максимума, в зашумленном сигнале, часто требует предварительной фильтрации, и введения гистерезиса. Это наверно вы приготовили на потом.

Я давно заметил что есть 2 типа интервью. На одних мне говорили (как здесь) что я бездарь, неуч, что я вообще ничего не понимаю в программировании, что к компютеру мне подходить вообще нельзя итд. Другой вариант, диаметрально противоположен. Такое ощущение, что средины просто не бывает. Я конечно, понимаю, что у каждого есть родственники, что никто не хочет принимать сильного человека, который сможет обойти по служебной лестнице, но зачем устраивать такой цирк на форуме?
Такое построение задач, далеко не уникально. И подвох тут совсем не в поиске максимума. Подвох в том, что:
Если человек сделал обработку исключенией, то можно сказать что в задаче про это не говорилось. Если не делал, то соответственно как сейчас.
Если человек сделал обработку "плоских максимумов", то можно сказать что это не нужно. Можно на ходу придумывать громадное количество "уточнений". Вот пришло уточнение про медленную память. А чего она вдруг стала медленной? Это как-то описывалось? Я вот могу сказать что задача решена абсолютно не правильно, так как на одно сравнение приходится 1 бранч, который на многих процессорах, сбарсывает pipe-line и вызывает жесточайшие тормоза. Да, постоянно идет выборка из масива. Мне сказали что это не правильно. Я могу сказать, что если у процессора есть кеш память, то эти все данные прокешируеются, а мне могут сказать что кеш памяти нету. Или сказать что данные у примеру в EEPROM находятся. Еслибы я сделал, как тут сказали в "виде последовательного потока данных", можно былобы придумать что-то про выравнивание по страницам, про страничную организацию памяти итд. (Это если интервьюирующий слышал про такие слова). Вот к примеру мне тут чего-то забыли сказать про коментарии. ЖУТЬ в программе нет коментариев, как-же ее другие будут понимать? Правда сказали что если программа из 3 строчек, то ее невозможно понять по тому что она не форматирована.

[KP580BE51]

unsigned int num_local_maximums( const int array[], size_t size )
for(i = 1; i < size; i++) {
}
return n;
}

Форматирования нет. Еще одно интервью завалено.

[dimp]

Определение максимума в математике достаточно однозначно - это точка в которой первая производная меняет знак.

Определение локального максимума функции действительно однозначно, но никакой "производной" там нет, вобще говоря, производная может быть вобще неопределена в этой точке, как тогда говорить о том, что она "меняет знак". Точка x0 является локальным максимумом f(x), если существует такое e>0, что для любого x, |x-x0|<e, выполняется f(x0)>=f(x)

[kostia00]

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

Каково ваше определение: что считается сранвением? if (x) где x - bool, это тоже сравнение по-моему.

[KP580BE51]

Определение максимума в математике достаточно однозначно - это точка в которой первая производная меняет знак.

Определение локального максимума функции действительно однозначно, но никакой "производной" там нет, вобще говоря, производная может быть вобще неопределена в этой точке, как тогда говорить о том, что она "меняет знак". Точка x0 является локальным максимумом f(x), если существует такое e>0, что для любого x, |x-x0|<e, выполняется f(x0)>=f(x)

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

a maximal extremum (maximal turning point or relative maximum) is one where the derivative of the function changes from positive to negative;

В этом смысле что искать точку где array[i-1]- array[i] "changes from positive to negative" более правильно. математически, а не по мнению "lzh"

[Izh]

Определение максимума в математике достаточно однозначно - это точка в которой первая производная меняет знак.

Определение локального максимума функции действительно однозначно, но никакой "производной" там нет, вобще говоря, производная может быть вобще неопределена в этой точке, как тогда говорить о том, что она "меняет знак". Точка x0 является локальным максимумом f(x), если существует такое e>0, что для любого x, |x-x0|<e, выполняется f(x0)>=f(x)

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

a maximal extremum (maximal turning point or relative maximum) is one where the derivative of the function changes from positive to negative;

В этом смысле что искать точку где array[i-1]- array[i] "changes from positive to negative" более правильно. математически, а не по мнению "lzh"

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

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

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

point x* is a local (or relative) maximum of a function f if there exists some ε > 0 such that f(x*) ≥ f(x) for all x with |x-x*| < ε. On a graph of a function, its local maxima will look like the tops of hills.

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

[Izh]

Определение максимума в математике достаточно однозначно - это точка в которой первая производная меняет знак.

Определение локального максимума функции действительно однозначно, но никакой "производной" там нет, вобще говоря, производная может быть вобще неопределена в этой точке, как тогда говорить о том, что она "меняет знак". Точка x0 является локальным максимумом f(x), если существует такое e>0, что для любого x, |x-x0|<e, выполняется f(x0)>=f(x)

Вы меня опередили.

[KP580BE51]

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

Ну и хорошо. Удачи в поиске телепатов.

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

Вы спорите с правильностью решения задачи.

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

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

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

Еще раз. Удачи в поиске телепатов.

[Иоп]

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

ППКС!
Не знаю как в программировании, а в нашей области, если потенциальный работодатель задаст подобную задачку на интервью, то потенциальный сотрудник его пошлет лесом. Потому что любая работа - это сотрудничество. И если работодатель позволяет себе неточности в постановке задачи, но требует точности в решении, то сотрудничества не получится! Мы называем это профессиональной этикой, которой похоже нет в программировании.

[KP580BE51]

ППКС!
Не знаю как в программировании, а в нашей области, если потенциальный работодатель задаст подобную задачку на интервью, то потенциальный сотрудник его пошлет лесом. Потому что любая работа - это сотрудничество. И если работодатель позволяет себе неточности в постановке задачи, но требует точности в решении, то сотрудничества не получится! Мы называем это профессиональной этикой, которой похоже нет в программировании.

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

[Izh]

Ну и хорошо. Удачи в поиске телепатов.

Интересно то, что довольно много народу решило эту
задачку правильно.

Вы спорите с правильностью решения задачи.

Разумеется. Она не работает для массива нулевой длины.

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

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