Их легион, скажу тебе я.

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

это понятно. просто есть же базис без которого никак - бабл сорт, квик сорт, обход графов и т.п. что еще?

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

Н. Вирт - Алгоритмы и структуры данных;
А. Ахо, Дж. Хопкрофт, Дж. Ульман - Структуры данных и алгоритмы;
Д. Кнут - Искусство программирования, том 1-3

>Д. Кнут - Искусство программирования, том 1-3

должен на память знать любой

Что-то здесь не так. Всего Кнута на память? Зачем?

Всего Кнута на память? Зачем?

Чтобы в психушке уютнее себя чувствовать было :)

Ну всё, что ещё?

Кем вы себя видите в компании через 5 лет.

)))

Годный вброс.

Кстати, недавно взялся кое-какие главы перечитывать.

В основном это спрашивают. Я, во всяком случае, всегда спрашиваю у кандидатов про графы и пузырёк.

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

• Код, которым вы гордитесь.
• Ваши 5 лучших/худших качеств.
• Конусообразные пожарные ведра и круглые люки.

всегда спрашиваю у кандидатов про графы

А что ты сам знаешь о графах?

я например смутно помню что 3 дома 3 колодца в плоскость не укладывается

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

Наверное те, которые касаются работы, на которую устраиваешься.

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

Плюсую, но меня спрашивали, хотя шёл вроде бы на java сайто клепательство
А ты из тех, кто пишет библиотеки и реализует алгоритмы?
Какая область?

Может в компаниях, куда не жалко не попасть нормальные вопросы задавать и не будут?

это code monkey какой то.

о) про вёдра ни разу не слышал.

Тенденция такая - уровень программиста опускается. И не удивительно - куча языков с низким порогом вхождения. У меня несколько товарищей гумунитариев сайтики на пехапе фигачат. Они программисты? Вроде бы да - ведь пишут и работает... но какая там теория графов с алгоритмами?

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

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

Нет, я из тех, которых здесь не любят - Ъ-Ынтерпрайз.

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

> зы а вообще программист должен знать язык программирования, а алгоритмы ему какие скажут - те и нафигачит.

Скорее, наоборот - программист должен знать алгоритмы, а языки ему какие скажут - на тех и нафигачит

Быстрая сортировка массива. Как минимум.

Правильно. А еще какой граф не является планарным? И какой есть критерий планарности/непланарности графа?

Теорема о цикле Эйлера в графе. Теорема о цикле Гамильтона в графе. Это то, что пришло на ум.

баян конечно, но все же

http://grompe.org.ru/static/prog_comp_matrix_ru.html

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

Ты сам то много раз в реальных промышленных задачах реализовывал вручную обход дерева?

> Тенденция такая - уровень программиста опускается.

Тенденция такая - одни дрочат на алгоритмы обхода дерева, другие решают реальные задачи и зарабатывают нормальные деньги.

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

Ты сам то много раз в реальных промышленных задачах реализовывал вручную обход дерева?

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

Тенденция такая - одни дрочат на алгоритмы обхода дерева.

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

другие решают реальные задачи и зарабатывают нормальные деньги.

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

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

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

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

Согласен.

Я к тому, что количество бабла - не показатель ума и/или полезности человека.

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

И еще потом жаль потраченного времени и тех, кто до этого еще не понял.

Кормен и три тома Кнута, в принципе, должно хватить.

дональд кнут. «искусство программирования».

> Ты сам то много раз в реальных промышленных задачах реализовывал вручную обход дерева?

не надо путать программирование ПЛК/SCADA готовыми программными средствами и решение сложных задач АСУТП типа управления электролизом алюминия. если нормальное управление (тем же электролизом, или тем же турбоагрегатом, или той же пусковой установкой), то и обход деревьев будет, и сортировки, и фильтры и куча всего ещё.

но в массе - да, стараниями специалистов siemens, rockwell, allen-bradley и прочих ненаших специалистов АСУТП более не требует умения программировать.

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

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

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

Вспомнил забавную задачку про двух роботов с одного собеседования:

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

шаг влево

шаг вправо

проверка, лежит ли на текущей клетке парашют

цикл типа while

временные переменные, счётчики и тд использовать нельзя

Надо написать алгоритм (один для обоих роботов), при котором роботы 100% встретятся.

первый раз вижу, спасибо)

самый здравый совет.

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

> шаг влево

шаг вправо

проверка, лежит ли на текущей клетке парашют

роботы 100% встретятся.

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

цикл типа while

временные переменные, счётчики и тд использовать нельзя

вообще без переменных чет не получается. покажешь как?

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

всякие проверки на нахождение паращюта два раза требуют хоть каких-то переменных.

Решетка замкнутая или функции «шаг влево» и «шаг вправо» возвращают таки результат, удалось ли сделать шаг? В обоих вариантах решение будет, но будет разным.

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

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

для радиуса нужен счетчик. нужно примерно так:

while(NOT_FOUND)
do
  right
  right
  left
done

while(NOT_FOUND)
do 
  right
  right
  right
done

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

Упс, конечно же перед первым циклом надо поставить ещё один

right

чтобы условие не выполнилось сразу же на своём же парашюте )

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

дональд кнут. «искусство программирования».

Мне всегда было интересно: те, кто советуют читать кнута, сами его читали?

> Мне всегда было интересно

не вижу, что могло бы вас заинтересовать.
это не так сложно, как «капитал» маркса или собрание сочинений Ленина. «искусство» - это просто справочник, или сборник рецептов. тем более, что нет привязки к какому-то реальному языку. нужны вам способы сортировок - в оглавление и быстренько пробежали по сути. мозголомного там ничего нет.