24.02.2012 16:08, Lloyd пишет:

> Извини, забыл тег [sarcasm]
Ну почему же. Подавляющее большинство компании достаточно вменяемые и
собеседования у них вменяемые. Но встречаются некоторые, которых к
вменяемым я бы не отнес. Вот и хочется выяснить, куда не соваться., не
тратить время не свое не чужое.

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

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

V>24.02.2012 16:07, Lloyd пишет:

>> Это не суть важно. В переделе то же самое будет.
V>Вот и пролетел ты со школьными своими знаниями — это важно. Можешь на
V>вики посмотреть, можешь пару учебников качнуть.

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

>> Зачем им это делать, если им это не нужно?
V>Тут я тебя уже не понял. Кому им и что не нужно?

Собеседователям не нужно от соискателя знание хардкорной математики.

Здравствуйте, Паблик Морозов, Вы писали:

ПМ>Я тут и должен быть отсев. Если 9 из 10 кандидатов с такой задачей справится не могут, их надо отсеивать и не тратить по полтора часа на собеседование каждого. Ведь тогда на работу времени не останется.

А построить процесс так чтобы не надо было собеседовать каждого — никак?

Ну ок, понеслась, еще раз.

Обобщенный процесс найма в большинстве организаций где я работал и куда собеседовался (все совпадения с реальными ситуациями и людьми случайны):

В программерский оффис врывается Босс с радостным воплем "мы оторвали новый супермегапроект, нам срочно нужны программисты!". Осторожные попытки выяснить что это за проект и кто именно нужен и сколько платят — результатов не приносят, он сам этого еще не знает. В результате генерится вакансия с некими обобщенными требованиями и отправляется HR для распространения. Начинается поток резюме. С ними нужно что-то делать, встает вопрос кто будет проводить интервью. Ответственным выбирают естесственно самого умного — задрота Васю (не хочу никого обидеть, я и сам был в этой роли когда-то). Задрот Вася с толком подходит к делу, с помощью интернета и умных книжек составляет кучу вопросов, которые по мнению сообщества железно помогают отделить зерна от плевел. И вот к Васе вводят первую жертву. Вася не любит и не умеет общаться с людьми, от его грозного взгляда жертва сразу впадает в легкий ступор. Начинается экзекуция — Вася исподтишка заглядывает в шпаргалку и вопрошает: "что такое виртуальный деструктор" (и т. д. на ваш выбор). Все попытки жертвы сначала представиться, выяснить с кем он говорит, куда он попал, что это за проект и сколько платят — обречены на провал, "сначала мы должны выяснить подходите ли вы нам". Наконец, где-нибудь через час, Вася находит вопрос на который вымотанная жертва не может ответить. От взгляда полного презрения, жертва впадает уже в нелегкий ступор и начинает мямлить что он/она знал, но забыл. Вася выдерживает эффектную паузу, потом задает следующий вопрос, но подавленная жертва уже не в состоянии продолжать собеседование. Со временем у Васи появляется все больше опыта по эффективному отсеиванию кандидатов, а Босс кусает локти — новый проект стоит, Вася тоже не работает, но ничего не поделаешь, достойных противников для Васи, который с каждым собеседованием все матереет — не найти, а на меньшее мы не согласны. В конце концов отчаявшийся босс обращается с призывом к сотрудникам: поискать по знакомым. Нужный человек находится, но он хочет больше денег. Босс с тоской соглашается, он уже сто раз пожалел что взялся за этот проект, но ничего не поделаешь, договор подписан. Дальше вариант — или новичка берут в обход Васи или ему заранее сообщают что будут за вопросы, не суть важно, человек будет принят.

Знакомо до боли, не правда ли? У меня было пожалуй всего пара нормальных интервью (не считая тех, где я был в роли того знакомого которого нашли), которые не проходили по такому сценарию (были и ненормальные не по такому сценарию, например когда меня собеседовали пара обкуренных, но это уже из другой оперы). Самое идеальное было — прислали вакансию, приехал, пообщался с HR, она подробно рассказала что за организация, что за проект, какая в нем роль, сколько платят, как проходит процесс принятия на работу, с кем придется работать (20 минут). Потом простенькое ТЗ на 2 часа на дом (я как раз ЗА ТЗ, но только за составленное с умом и с уважением к кандидату), близкое к предметной области. Потом собеседование с тимлидом и менеджером, оба люди немолодые, с большим опытом в своей области. Рассказали о себе, показали офис, напоили кофе, познакомили с потенциальными коллегами. Рассказали чем именно придется заниматься, немного поговорили про особенности предстоящего проекта, про то чем занимался я и насколько оно пересекается с их проектом. В результате выяснили, что мы друг другу не подходим, расстались безо всяких взаимных обид (еще 20 минут).

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

Здравствуйте, Паблик Морозов, Вы писали:

ПМ>Здравствуйте, Sni4ok, Вы писали:

S>>конечно сразу нафиг

ПМ>Но как-то они же работали на предыдущих работах несколько лет? Или от того новую работу и ищут, что так набыдлокодили, что теперь легче работу сменить, чем разбираться?

Много где работа сводится к написанию программ, которые дёргают библиотечные функции, и вся квалификация сводится к знанию тонкостей этих библиотек.
И этим можно заниматься годами, а потом гордо писать — "5 лет опыта разработки на C++".

Здравствуйте, Паблик Морозов, Вы писали:

A>>Отсеивать надо, если ты считаешь, что приобрести такой навык сложно. Если человека можно научить за пару часов решать подобные задачи — то стоит ли отсеивать людей по этому критерию?

ПМ>Навык писать нормальный рабочий код приобрести сложно.

Но ты же проверяешь навык переворачивания строки. А это не одно и тоже, что и навык писать нормальный код.

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

ПМ>>Мы говорим про быструю сортировку. Думаю те, кто её видели, со мной согласятся.
G>Зря ты так думаешь.

Видимо те, кто не могут вспомнить квиксорт примерно того же уровня, как и те, кто не могут обратить список.

ПМ>>Что значит "максимальная подпоследовательность" я не знаю
G>http://www.google.ru/search?aq=f&sourceid=chrome&ie=UTF-8&q=%D0%BC%D0%B0%D0%BA%D1%81%D0%B8%D0%BC%D0%B0%D0%BB%D1%8C%D0%BD%D0%B0%D1%8F+%D0%BF%D0%BE%D0%B4%D0%BF%D0%BE%D1%81%D0%BB%D0%B5%D0%B4%D0%BE%D0%B2%D0%B0%D1%82%D0%B5%D0%BB%D1%8C%D0%BD%D0%BE%D1%81%D1%82%D1%8C

Там куча ссылок на разные задачи.

G>list = x::list | nil
G>reverse nil = nil
G>reverse x::xs = (reverse xs)::[x]

Это не in-place и сложность тут приходит из сложности ::. Если уж говорить в терминах базовых операций (конструкторов списка nil и cons) то вообще не понятно, что тут делает :: (вторая — я так понял одним символом тут обозначается как a -> [a] -> [a], так и [a] -> [a] -> [a]) и почему в таком разе не foldl (flip (:)) []? Кароче, если бы кандидат мне такое выдал, я бы посоветовал ему не выпендриваться и написать на C#.

G>Угу, вот только разворота линейного списка на месте среди них нет, потому что связные списки редко используются в чистом виде. Чаще всякие stl и другие контейнеры.

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

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

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

G>>>Больших как ни странно.
ПМ>>каких именно?
G>А вот каких знаний требует задача выбора N случайных элементов массива?

Алгоритма случайной перестановки за O(n), если решать её как это делаю я. Или каких-либо других структур и алгоритмов, смотря как решать.

G>К чему тут "поэтому"?

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

G>Ты пытаешься приуменьшить сложность задачи, которую сам знаешь.

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

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

A>Но ты же проверяешь навык переворачивания строки. А это не одно и тоже, что и навык писать нормальный код.

Нормальный рабочий код, который решит эту задачу. Не?

24.02.2012 17:03, Lloyd пишет:

> Для той задачи, о которой идет речь не важно, в какой точке интервала мы
> будем брать значение функции.
Ты прав , меня немного дальше понесло по численному интегрированию.
Вот так и на старуху бывает проруха. Читаешь одно, а пишешь немного о
другом.

> Собеседователям не нужно от соискателя знание хардкорной математики.
Вот это я не понял. Если спрашивают математику, то она им нужна или нет?
Или это вопрос, чтобы время потянуть, не охота работать — с соискателем
интереснее потрепаться бывает?
А если математика им нужна, то ныне без "хардкорной" не много сделаешь.
Да и развивается все сейчас быстро (не успеваешь отслеживать новое),
особенно в прикладных областях.

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

H>Я бы задумался. Человек 10 лет программирует, а все не научился стандарные библиотеки использовать
Если бы я получил такое задание, я бы понял, что надо продемонстрировать алгоритмические способности, умение объяснить придуманный алгоритм собеседнику и быстро выразить в виде кода. Во многих серьёзных конторах подобные задачки и дают. Правда обычно пытаются выбрать задание, для решения которого нет стандартной функции в библиотеке. Хотя вот в Amazon мне задавали найти подстроку в строке, очевидно, что std::string.find их не интересовал.

H>std::reverse(list.begin(), list.end())
Если в некой конторе будут ожидать такое решение, то лучше оттуда бежать, ибо требование знания наизусть функций стандартной библиотеки ни о чём хорошем не говорит.

Здравствуйте, Паблик Морозов, Вы писали:

ПМ>Я сам пишу им представление, если возникают проблемы (а для себя ставлю галочку "ООП головного мозга"), что тоже не плюс.
Чтож у вас за задачи то там такие, что навыки абстрагирования являются минусом? Сколько ни читал книг — везде говорится, что абстракция, это просто священный грааль для программиста (без фанатизма естественно если этим пользоваться, а случай со списками как раз и является отсутствием этого фанатизма). Ибо очень помогает следовать DRY принципу, который тоже священен. Ладно, не ООП — берем функциональный подход, конкретно книгу SICP. Вдалбливают эти абстракции черти как! Берем императивный подход — Си, тоже абстракции вбивают, вбивают и вбивают в голову. Типа написали алгоритм — он должен работать вообще с любыми данными! Копипаст отстой, реюз форева, с момента зарождении индустрии причем! Здесь же в качестве эталонной реализации приводится решение, работающее только для одной конкретной структуры данных. И на основе того, насколько близко ты мыслишь именно этой конкретной структурой данных, а не чем то более общим, судится о квалификации разработчика — однако.

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

H>>>40 строк кода на переизобретение велосипеда в стиле C, полное неумение пользоваться C++, шаблонами и STL, страсть к низкоуровневому решению задачи и концентрация не на решении проблемы а на показывании "мастерства".

о_О>>надо подтверждать статус профессионала, а так же, за что платить от 150 килорублей в месяц

H>Профи напишет
H>std::reverse(list.begin(), list.end())

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

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

А>А построить процесс так чтобы не надо было собеседовать каждого — никак?

А как? Домашние задания? Не хотят. Жесткий отсев по резюме? Во-первых писать их толком не умеют, во-вторых аббривеатур себе навписывать много ума не надо. Давать компьютер и закрывать в комнате на 3 часа, пока не напишет сапёр — издевательство. Небольшая задача, которую можно сделать прямо на собеседовании вместе с кандидатом — самый гуманный вариант ИМХО.

А>Знакомо до боли, не правда ли?

Нет, у меня никогда такого не было.

А>К чему это все? Ведь если подумать, не так уж и трудно сделать чтобы неподходящие кандидаты отсеивались сами, с минимальными затратами времени и при этом никто не пострадал, правда?

Да, и первый пост в теме как раз об этом, не правда ли? (заметьте, в моём случае кандидату не понадобилось тратить два часа на выполнение тестового задания)

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

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

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

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

C>Вообще, имхо, задача собеседования — определить адекватность кандидата и способность мыслить. Остальное обычно проистекает из желания показать собственное превосходство.

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

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

Я ничего не писал про навыки абстрагирования, я написал именно про ООП. Тип данных — это абстракция. Если человек не знает, что такое список, а слово это у него ассоциируется только с классом list — это как раз показатель, что абстрагировать человек не умеет.

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

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

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

L>Ты можешь ответить на простой вопрос "зачем для разворота списка нужна рекурсия"?
Я тут в соседнем посте писал:

list = x::list | nil
reverse nil = nul
reverse x:xs = (reverse xs)::[x]

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

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

А вот как вывести нужный вариант:

Для начала попробуем определить разворот списка через другую, "родную" для списков операцию — свертку.

reverse xs = fold f (startS) (xs)
f :: 'a -> 'b -> 'a

Далее попробуем подставить nil:

reverse xs = fold f startS nil
== /*по определению fold*/
strartS
== /*потому что reverse*/
nil :: 'a

далее подставляем xs = x::y::nil

reverse xs = fold f nil x::y::nil 
== /*по определению fold*/
f( f(nil, x), y)
== /*потому что reverse*/
y::x::nil

Но функции fold в C нету и надо написать. Обобщенный fold писать смысла нет, можно сразу написать (fold f)

reverseHelper = fold f
reverseHelper yx nil = ys
reverseHelper ys x::xs = reverseHelper x::ys xs
reverse xs = reverseHelper nil xs

Теперь можно и в C попробовать написать такой хелпер для С (пишу прямо в форуме не проверяя)

Node* reverseHelper(Node* left, Node* right)
{
    if(right == null) return left;

    Node* n = right;
    right = right -> next;
    n->next = left;
    return reverseHelper(n, right);
}

Node* reverse (Node* list)
{
    return reverseHelper(null, list);
}

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

Node* reverseHelper(Node* left, Node* right)
{
    while(right != null);
    {
        Node* n = right;
        right = right -> next;
        n->next = left;
        left = n;
    }
    return left;
}

Далее убираем лишнюю косвенность из reverse

Node* reverse (Node* list)
{
    Node* rev = null;
    while(list != null);
    {
        Node* n = list;
        list = list -> next;
        n->next = rev;
        rev = n;
    }
    return rev;
}

Здравствуйте, Паблик Морозов, Вы писали:

а вы именно код просите написать? или и рассказ алгоритма пойдет?

24.02.2012 17:27, . пишет:

> H>std::reverse(list.begin(), list.end())
> Если в некой конторе будут ожидать такое решение, то лучше оттуда
> бежать, ибо требование знания наизусть функций стандартной библиотеки ни
> о чём хорошем не говорит.
Это говорит о том, что чел не будет лишний раз придумывать велосипед с
треугольными колесами, а будет писать понятный, правильно работающий
код. А заниматься безумствами с оптимизацией будет только тогда, когда
это очень нужно.

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

H>std::list<int> list;
H>...
H>std::reverse(list.begin(), list.end())

так каждый может, задача-то в том, чтобы реализацию reverse написать (за 5 минут)

Здравствуйте, Паблик Морозов, Вы писали:

G>>Угу, вот только разворота линейного списка на месте среди них нет, потому что связные списки редко используются в чистом виде. Чаще всякие stl и другие контейнеры.
ПМ>На это всё и рассчитано. Мне не нужны люди, которые знают, как разворачивать списки. Мне нужны люди, которые в состоянии написать алгоритм для решения задачи.
Да, но ты почему-то уверен что это знание выводится из умения разворачивать список на месте.
Хотя это неверно.

G>>Ничего она не показывает, не надо тешить свое самолюбие. Вот ты например не напишешь выборку N случайных чисел массива не заглядывая в гугл за 5 минут. О чем это говрит? А ни о чем
ПМ>За O(от длинны массива) могу сходу написать (случайная перестановка массива индексов и взятие по нему N элементов).
Это будет O(длина массива), а не O(кол-во элементов)

ПМ>Если подумать, может что получше напишу. Кстати, есть подозрение, что это сложнее обращения списка.
Ну вот. Ты проверку не прошел. Код очень простой, даже проще чем разворот списков.

[сcode]
i=0;
k = arr.length();
assert(n <= k);

while(n>0)
{
if(rand(k) < n)
{
result.push_back(arr[i]);
n--;
}
i++;
k--;
}
[/сcode]
И я уверен что ты его хотя бы раз видел. Но не писал с тех пор ни разу, вот и не смог родить.

Это значит что алгоритм сложен, несмотря на то что код простой.

А с максимальной подпоследовательностью еще проще код.

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