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

ОК>>Забывается то с чем дела не имеешь напостоянку.

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

Я тоже раньше думал как Олег К. Но однажды разобрался хорошенько с сортировками и по прошествии лет все еще помню как их писать. По крайней мере основные вроде quicksort да mergesort. Там же элементарщина, как можно забыть? Это все равно что забыть как работает хэш-таблица. Принцип простой, а там уж логически детали восстановить можно.

KP>"смотрите как Олежка пыхнул в личке" — Слушай, ДЕБИЛ, я к этому "Олежке" никакого отношения не имею. Я вообще не принимаю участие на этом форуме. Я — сторонний читатель.. Просто уже никаких сил нет читать твою ДЕБИЛЬНУЮ ЧУШЬ.

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

ОК>>>Забывается то с чем дела не имеешь напостоянку.

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

K>Я тоже раньше думал как Олег К. Но однажды разобрался хорошенько с сортировками и по прошествии лет все еще помню как их писать. По крайней мере основные вроде quicksort да mergesort. Там же элементарщина, как можно забыть? Это все равно что забыть как работает хэш-таблица. Принцип простой, а там уж логически детали восстановить можно.

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

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

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

R>>"могу её написать" и "могу её написать без ошибок" две большие разницы, в данном случае Вам намекают про второй случай, а Вы упорно давите на первое))
+1 пациент не вполне понимает смысл, но выглядит "что-то похожее".

G>Написать на бумаге\на форуме и на компьютере — две большие разницы, я говорю про первый случай, а все упорно делают вид, что это второй
Нет ничего предосудительного спросить про сортировку на собеседовании. Но в случае quick sort там всё очень неоднозначно, это не просто "разделяй и властвуй". Ты сходу накидал решение, которое работать не будет. Даже не подумал о подвохе. Дальше всё зависит от принципиальности собеседующего, например он мог бы намекнуть про граничные условия и дать тебе возможность реабилитироваться. Или промолчать, и отметить "кандидат негоден". Если ты единственный, кто хоть что-то выдал- значит такой рынок труда, тебе повезло. Ну и в любом случае, сортировки это слишком прямолинейно и легко в наше время. У меня даже такое подозрение, что сортировки как фильтр не отсеивают дебилов от слова совсем. Народ тупо зубрит. Потом в реальной ситуации возникают ужасы кода от сна разума.
Обход лабиринта или гномики но с такой загогулиной, чтобы известные в интернете решения под копирку не подходили- интереснее.

Здравствуйте, Тёмчик, Вы писали:

Тё>Нет ничего предосудительного спросить про сортировку на собеседовании. Но в случае quick sort там всё очень неоднозначно, это не просто "разделяй и властвуй". Ты сходу накидал решение, которое работать не будет. Даже не подумал о подвохе.
Кончай фантазировать. Я скопировал код в студию, поправил в трех строках +\-1, граничные условия и все заработало.

Тё>Дальше всё зависит от принципиальности собеседующего, например он мог бы намекнуть про граничные условия и дать тебе возможность реабилитироваться.
Ты и многие другие не смогли без запуска в студии найти все ошибки. Думаешь интервьювер найдет? И надо оно ему? Это же помнить наизусть весь код надо и только для того, чтобы потешить самолюбие.

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

Тё>Если ты единственный, кто хоть что-то выдал- значит такой рынок труда, тебе повезло.
Я единственный кто хоть что-то выдал в этой теме

Тё>Ну и в любом случае, сортировки это слишком прямолинейно и легко в наше время. У меня даже такое подозрение, что сортировки как фильтр не отсеивают дебилов от слова совсем.
Судя по твоему первому посту тебя как раз и отсеяли

K>Там же элементарщина, как можно забыть? Это все равно что забыть как работает хэш-таблица. Принцип простой, а там уж логически детали восстановить можно.

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

SL>Гугление даст результат.

Оставьте этот снисходительный тон)) Я прекрасно понимаю, почему qSort нельзя использовать для списков. Проблема в том, что базовая реализация qSort, когда за pivot принимается первый элемент — бессмысленная и беспощадная. Эта реализация хуже, чем её отсутствие. Реализация qSort для реальной жизни должна как минимум использовать рандомизированный выбор pivot. А в реальности и ещё ряд приседаний для оптимизации производительности. А в списке за время O(1) нельзя получить доступ к случайному элементу. Можно получить только доступ к первому элементу. То, что асимптотика в среднем для случайного списка будет O(n log n) не достаточна для реальной жизни, так как в реальной жизни частично упорядоченные массивы в качестве входных данных встречаются гораздо чаще, чем просто случайные массивы.

Здравствуйте, De-Bill, Вы писали:
DB>Блин, меня всегда пугали люди, которые говорят о хэш-таблицах, что это элементарщина. Потому что они явно никогда не пытались сделать хорошую хэш-функцию, что является сверх не элементарной задачей.
кстати, в одном из финалов олимпиад по программированию, может даже ACM, задачей была разработка хэш-фии, способной выдать наиболее равномерное распределение

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

__>кстати, в одном из финалов олимпиад по программированию, может даже ACM, задачей была разработка хэш-фии, способной выдать наиболее равномерное распределение

Imho хэш функция- это из раздела криптографии, там можно зайти очень далеко для удовлетворения каких-то требований. Сама по себе хэш-таблица- тривиальный массив с связными списками. Ну и для строк например, есть простая (good enough) хэш функция из коробки, а указатели уже сами по себе можно использовать как хэш.

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

Тё>>В случае quick sort ты можешь получить вырожденный случай и глубину рекурсии N. Не проверил граничных условий — провалил задание.
G>Если что ты всегда можешь его получить, независимо от того, как ты напишешь Быстрая сортировка в худшем случае имеет O(n^2)

Глубина рекурсии в quick sort минимальными усилиями ограничивается логарифмом, об этом ещё Хоар писал в своей изначальной статье.

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

KP>>Иногда ты очень хорошо накидываешь, смотрите как Олежка пыхнул в личке!!! Я бы сказал что просто взрыв какой-то!!!
K>Если это личная переписка, то ты как минимум не прав выкладывая её.

Сообщение даже с запикаными матами вообще говоря оскорбительное. Фактически — насилие. Ты точно уверен, что kaa.python не имеет права защитится от такого насилия ?

Здравствуйте, Олег К., Вы писали:

ОК>Это не я был, но до тебя не доходит одна простая вещь. Ты можешь считать сколько угодно что ни я ни написавший тебе лично не разбираемся в алгоритмах. Считай. Считай какой ты крутой в программировании. Твое право. Но... Рано или поздно тебя отинтервьюирует такой же, хм, спец как и ты. Либо в силу своей глупости либо просто умышленно. Это сделать проще простого даже на задачке в десять строк кода. Ты этого не понимаешь.

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

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

M>На лицо явное непонимание обязанностей архитекторов в больших конторах. В маленьких они нафиг не нужны. Код архитекторы не пишут, алгоритмы не применяют, высокоуровневое видение продукта — это как заставить 500+ стратегических приложений работать вместе, а для этого нужно строчить стандарты и со всеми договариваться.

Видишь ли, есть много разных архитектов. Артем, скорее всего, говорит от Software Architect, а ты описываешь что то похожее на Infrastructure Architect.

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

DB>Оставьте этот снисходительный тон))

Да не, тон обычный. Ничего такого
Это я не так давно к одному собеседования готовился и освежил алгоритм.

DB>Я прекрасно понимаю, почему qSort нельзя использовать для списков. Проблема в том, что базовая реализация qSort, когда за pivot принимается первый элемент — бессмысленная и беспощадная. Эта реализация хуже, чем её отсутствие. Реализация qSort для реальной жизни должна как минимум использовать рандомизированный выбор pivot. А в реальности и ещё ряд приседаний для оптимизации производительности. А в списке за время O(1) нельзя получить доступ к случайному элементу. Можно получить только доступ к первому элементу. То, что асимптотика в среднем для случайного списка будет O(n log n) не достаточна для реальной жизни, так как в реальной жизни частично упорядоченные массивы в качестве входных данных встречаются гораздо чаще, чем просто случайные массивы.

Тут только один нюанс могу добавить.
Когда готовился, то я посмотрел две реализации:
1. В .Net Framework
2. В STL, идущий с Visual С++

В обоих берется медиана из [First, Mid, Last].

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

K>>Там же элементарщина, как можно забыть? Это все равно что забыть как работает хэш-таблица. Принцип простой, а там уж логически детали восстановить можно.

DB>Блин, меня всегда пугали люди, которые говорят о хэш-таблицах, что это элементарщина. Потому что они явно никогда не пытались сделать хорошую хэш-функцию, что является сверх не элементарной задачей.

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

I>Принцип в самой таблице простой.

Также как и принцип, например, любого автомобиля. Есть коробка и 4 колеса. Элементарщина.

I>Написание хеш-таблицы это примерно экзамен за первый курс унивеситета.

Написание хеш-таблицы без хеш-функции — абсолютно бессмысленное дело. Это также как делать автомобиль приколотив к бревну 4 колеса. Вся соль хэш-таблиц заключается именно в хеш-функциях. Если у вас у университете на экзамене было задание написать массив списков, то университет очень хиленький.

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

KP>Иногда ты очень хорошо накидываешь, смотрите как кто-то пыхнул в личке!!! Я бы сказал что просто взрыв какой-то!!!

Выплескивать эмоции полезнее, чем держать в себе

Здравствуйте, Тёмчик, Вы писали:

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

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

И да, я сам хоть уже 10 лет не кодирую, но даже ночью готов рассказать quick/radix и т.п. sort, пересказать алгоритмы построения/нормализации/обхода деревьев, алгоритмы поиска, десяток основных паттернов и прочее что въелось мне в мозг так, что похоже уже никогда не забудется.

Чем может быть полезен архитектор, который нихрена не знает, я не представляю

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

K>Если это личная переписка, то ты как минимум не прав выкладывая её.

А она не личная — личность писателя не установлена.

Здравствуйте, Олег К., Вы писали:

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