Здравствуйте, gandjustas, Вы писали:

G>Близко, но не то.
G>Проверь на таких последовательностях
G>{1,2,-1,2} — должно быть 4
G>{3,-3,2,-2,1,-1} — должно быть 3

Мне уже показали на ошибку. Двумя постами ниже я исправил решение, и на этих данных оно работае.

G>А также ход решения и сколько времени заняло.

Сначала увидел формулировку. Через какое-то время опять наткнулся на пост, и достаточно быстро решение пришло само.
Сложно посчитать сколько времени это заняло.

Здравствуйте, samius, Вы писали:

T>>В любой последовательности есть подпоследоваетльность, сумма которой больше любого отрицательного числа.
T>>Что это за подпоследовательность, предлагаю определить самосоятельно.

S>Но в любом случае то решение неверное.

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

Здравствуйте, samius, Вы писали:

S>Здравствуйте, Tissot, Вы писали:

T>>Здравствуйте, samius, Вы писали:

S>>>А разве что-то есть в условии, запрещающее максимальной сумме подпоследовательности быть отрицательной?

T>>В любой последовательности есть подпоследоваетльность, сумма которой больше любого отрицательного числа.
T>>Что это за подпоследовательность, предлагаю определить самосоятельно.

S>Я не видел точного условия, не могу сказать, будет сумма пустой подпоследовательности считаться решением.

Да, будет. Обратного нигде не говорилось.

Здравствуйте, Tissot, Вы писали:

T>Сначала увидел формулировку. Через какое-то время опять наткнулся на пост, и достаточно быстро решение пришло само.
T>Сложно посчитать сколько времени это заняло.

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

Алгоритм решения сложен. В стрессовой ситуации интуиция подведет.

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

Здравствуйте, gandjustas, Вы писали:

T>>Сложно посчитать сколько времени это заняло.

G>Вот видишь код решения простой. Ты говоришь "само пришло", причем не с первого раза. Ты не можешь ход решения расписать.

G>Алгоритм решения сложен. В стрессовой ситуации интуиция подведет.

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

Здравствуйте, Tissot, Вы писали:

T>Здравствуйте, gandjustas, Вы писали:

T>>>Сложно посчитать сколько времени это заняло.

G>>Вот видишь код решения простой. Ты говоришь "само пришло", причем не с первого раза. Ты не можешь ход решения расписать.

G>>Алгоритм решения сложен. В стрессовой ситуации интуиция подведет.

T>Наоборот, алгоритм оказался на удивление простым, не ожидал.
Это решение. Алгоритм сложен тогда когда его сложно придумать. Тут сложность именно алгоритма.

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

Здравствуйте, gandjustas, Вы писали:

G>>>Алгоритм решения сложен. В стрессовой ситуации интуиция подведет.

T>>Наоборот, алгоритм оказался на удивление простым, не ожидал.
G>Это решение. Алгоритм сложен тогда когда его сложно придумать.

Это какое-то странное определение сложности.

Здравствуйте, Undying, Вы писали:

U>Здравствуйте, vshemm, Вы писали:

V>>Это следует из моего поста

Автор: vshemm
Дата: 25.02.12

, где я уже ограничил круг вакансий (последняя строчка).
V>>Также есть вакансии на которые мыслящий работник не нужен (быдлокодерство по разжеванным требованиям). В этом случае задавать задачки — терять время.

U>Быдлокодер это человек пищуший говнокод. Решение рутинной задачи оптимальным образом быдлокодерством не может быть по определению.

По Вашему определению. Говнокод пишет говнокодер, хотя есть мнение, что это вообще не кодер
Свое мнение я уже сказал, и, так как ощутимая часть моей работы связана с написанием кода по
разжеванным требованиям — я быдлокодер. Какие проблемы?

Вопрос в том, кто это все разжевывает. Увы, это тоже мне приходится делать.
Но не будем углубляться в терминологию.

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

V>>См. мое решение выше. На ЭТО нужны часы?

U>В решении десяток строчек кода. Плюс нужны хоть какие-то тесты, это еще по меньшей мере десять строчек, т.е. всего двадцать. Вот здесь http://rsdn.ru/forum/job/4605175.1.aspx

Автор: Undying
Дата: 06.02.12

я писал, что программист в среднем пишет несколько сот строчек кода в день. На что получил гневный отлуп, что уважающий себя программист должен писать много меньше. Но ладно возьмем все-таки производительность труда суровых челябинских программистов, не изнеженных отладкой, документированием и митингами. Если средняя производительность 200 строк в день, то в среднем в спокойной обстановке, решая в основном привычные задачи, на написание двадцати строк кода программист тратит почти час грязного времени и около получаса чистого. Вы же хотите, чтобы на собеседовании в стрессовой обстановке, решая непривычную задачу (за десять лет практики я ни разу не работал с односвязным списком, т.к. это весьма экзотическая коллекция оптимальная на весьма экзотических задачах), программист написал двадцать строчек кода за 5 минут. Стоит ли после этого удивляться, что вам кажется, что на собеседования ходят одни идиоты?

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

V>>Так это прекрасно. На практике под списком понимается классическая структура данных, которая описана в не менее
V>>классических источниках (сиречь Кнут). Если человек меняет терминологию или путает фундаментальные сущности с
V>>конкретной реализацией — то до свидания. Задача успешно сделала отсев.

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

А вот это ложь. Я не проверяю чтение Кнута, как никогда и не жаловался на "никак не можете найти нормальных программеров".

Здравствуйте, gandjustas, Вы писали:

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

Воот. Сейчас я выдам пару бездоказательных утверждений:
1. Я до сих пор не знаю решения. Я знаю подход. И, каждый раз, когда мне будут задавать этот
вопрос — я буду заново его выводить. Хотя это вывод займет 20-30 сек, это правда.
2. Это решение мое личное, вряд ли вы его нагуглите. И его я "родил" в стрессовой ситуации с нуля
как раз за 5-10 минут (не на собеседовании).

Показать тоже самое на другой задаче на форуме невозможно. Времени много, я легко могу обратится к "гуру" и т.п.
Тем более, что в данной ветке кто-то уже выдал 80% решения. Так что смысла в этом я не вижу.

G>Покажи класс.

От 50 евро в час )) Или приглашайте на собеседование ))

Здравствуйте, gandjustas, Вы писали:

P.S. Кстати, вы внимательно читали мое решение?

	Скрытый текст
	#include <stdio.h> template< typename T > struct e_ { T val; e_<T> *next; }; template< typename T > void print( e_<T>*pH ) { if( NULL == pH ) { printf("\n"); return; } printf("%d ", pH->val); print(pH->next); } template< typename T > void reverse( e_<T>*& pH ) { typedef e_<T> e_t; if( NULL == pH || NULL == pH->next ) return; e_t *p = pH, *pn = p->next, *pT = NULL; while( NULL != pn ) { pT = pn->next; pn->next = p; p = pn; if( NULL == pT ) break; pn = pT; } pH->next = NULL; pH = pn; } template< typename T > e_<T>* reverse_recursive( e_<T>*& pH, e_<T>* pN ) { typedef e_<T> e_t; if( NULL == pH ) return pN; e_t* p = reverse_recursive(pH->next, pH); pH->next = pN; return p; } int main(int argc, char* argv[]) { typedef e_<int> e_int; e_int arr[] = { {1}, {2}, {3}, {4}, {5} }; for( unsigned int n = (sizeof(arr)/sizeof(e_int))-1; 0 != n; --n ) { arr[n-1].next = &arr[n]; } e_int* pHead = &arr[0]; print(pHead); reverse( pHead ); print(pHead); pHead = reverse_recursive<int>( pHead, NULL ); print(pHead); return 0; }

Здравствуйте, gandjustas, Вы писали:

G>Нужно найти подпоследовательность максимальной суммы за один проход, для упрощения берем конечный массив и нужно вернуть только сумму.

Вот конкретно эта задача, не очень удачный пример. И как раз таки не очень удачная задачка для тестирования. Потому, что она требует немного не тривиального/олимпиадного мышления. А та задача с переворотом списка, требует тривиальных знаний и базовых навыков программирования. Задачка уровня старших классов и первого курса технического ВУЗа.

G>Покажи класс.

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

И так, первым делом взял и от балды составил последовательность:
1 2 -1 2 -3 4 5
(кстати говоря, потом понял, что получил на самом деле очень удачную последовательность)

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

Выглядит это как-то так:
1 2 -1 2 -3 4 5
1 3 0 2 0 4 9 => 9 — максимум

Но я протупил. Понял я это тестируя на разных крайних случаях. Например, последовательность 2 -1 2, тут ответом должна быть 3-ка. Мой алгоритм даст 2-ку. Помните, я говорил выше, что получил изначально и чисто случайно удачную последовательность. Это потому, что на том примере мой алгоритм тоже работает неверно. Ответ там 10, а не 9-ка которую выдаст мой алгоритм.

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

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

Для проверки, я немного изменил свою исходную последовательность:
1 2 -1 2 -6 4 5
1 3 2 4 0 4 9 => 9

Ура! Чувство морального удовлетворения

PS: кстати, хорошая задачка. Я ошибся, ее можно задавать на собеседовании. Демонстрирует навык умения рассматривать крайние случаи (а это значит, на практике, умение писать юнит-тесты), находить решения задач в не стандартных ситуациях.

PSS: я не учел вариант, когда все элементы отрицательные, в этом случае нужно просто найти максимальное отрицательное число.

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

SVZ>Вы одним махом исключили из продакшена разработчиков библиотек, C-программистов, разработчиков, поддерживающих непопсовые платформы...
SVZ>Несколько лет назад компилятор под HP-UX не дружил с шаблонами и контейнеры приходилось реализовывать вручную. А в zOS до сих пор проблемы с использованием std::vector.

ничего подобного

я не против программирования на C (хе-хе. это было бы смешно), я против разворота списка "на месте"

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

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

IMHO...

чё? не понял..

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

я вот, например, не понял что ты там сказал про творог, значит, ты неясно выражаешься

во-во, вот оно:

Ф> от зубов отскакивает. думать над такими задачами не надо.

где-то я уже это слышал думать не надо! надо зубами отбивать!

Ф> на лабах ещё 4 решают
я ж и говорю — хорошая задачка для районной олимпиады по информатике. олимпиады! для школьников!

Здравствуйте, THESERG, Вы писали:

THE>я не против программирования на C (хе-хе. это было бы смешно), я против разворота списка "на месте"
THE>а что, если теперь его не развернуть надо, а отсортировать? всё, заново велосипед изобретаем?
А в чём проблема отсортировать список in-place? Даже односвязный сортируется влёт.

Здравствуйте, gandjustas, Вы писали:

G>Алгоритм решения сложен. В стрессовой ситуации интуиция подведет.

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

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

Для программиста С++ разворот списка не является такой задачей. Он обязан понимать как работают указатели,
"интуитивный затык" в этой задаче только в понимании как работает указатель, если это есть, то задача
вырождается в рутинную задачу на внимательность.
Твоя же задача, если забыл (или не знал) математику, чисто на интуицию.

Здравствуйте, THESERG, Вы писали:

THE>я не против программирования на C (хе-хе. это было бы смешно), я против разворота списка "на месте"
THE>а что, если теперь его не развернуть надо, а отсортировать? всё, заново велосипед изобретаем?

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

Рассуждаешь правильно, НО!
Думаю, ты со мной согласишься, что инженер-программист должен иметь представление, во что выливается использование различных контейнеров, алгоритмов. А если для него все едино, что массив, что связный список, то он такого наворотит в продакшене... А как определить, что он не только слышал о структурах данных и алгоритмах, но и умеет их распознать, выбрать нужный и правильно использовать? Ну вот только такими дурацкими синтетическими задачками. Потому что если ему дать реальную задачку (даже сильно ее упростив), то решаться она будет несколько часов. Есть у меня такие задачки, можем их обсудить.

Здравствуйте, THESERG, Вы писали:

THE>для школьников!

в школе не учился?

Здравствуйте, __lambda__, Вы писали:

___>Здравствуйте, gandjustas, Вы писали:

G>>Нужно найти подпоследовательность максимальной суммы за один проход, для упрощения берем конечный массив и нужно вернуть только сумму.

___>Вот конкретно эта задача, не очень удачный пример. И как раз таки не очень удачная задачка для тестирования. Потому, что она требует немного не тривиального/олимпиадного мышления. А та задача с переворотом списка, требует тривиальных знаний и базовых навыков программирования. Задачка уровня старших классов и первого курса технического ВУЗа.

Задача разворачивания списка не отличается. Разворачивание списка требует даже больше знаний.

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