Comments 47
Секундочку, какая то у вас сводная таблица по алгоритмам неверная. Например у алгоритма Insertion Sort сред сложность пролегает стабильно в O(n^2), а вот лучший случай является Ω(n). Тоже самое, если не ошибаюсь можно сказать про сред сложность у Binary Insertion Sort. Интересное по теме.
Я исходил из того, что имеет смысл применять дополнительный алгоритм, если он показывает производительность лучше основного.Совершенно верно, но если посмотрите на условия, когда происходит переход, то поймёте, что к Big O всё это отношения не имеет.
Переход на «вспомогательные» алгоритмы происходит не тогда, когда у них лучшая сложность (как мы это вообще можем узнать заранее???), а когда, несмотря на то, что в терминах Big O сложность велика, в терминах элементарных операций она невелики — за счёт константы, очевидно. Которая у «вспомогательных» алгоритмов, очевидно, меньше…
Вы можете заниматься высокоинтеллектуальной деятельностью типа натягивания шаблонов на CMS типа Drupal'а. Или создания формочек в 1С или Excel'е. Тогда вам этот «армейский тупняк» действительно не нужен.
А можете — заниматься разной ерундой типа создания операцинок и браузеров, иструментов ИИ и распределённых систем — вот тут вам этот «армейский тупняк» таки понадобится.
А выбор, как всегда, за вами.
Если это «домашнее задание» то почему бы и нет — покажет, что человек может в комфортной обстановке.
Так же в офисе могут попросить реализовать алгоритм на доске — вполне хорошее упражнение. Так как тут есть диалог между у частниками, даже если человек затрудняется реализовать алгоритм, видно как он мыслит (что в основном и должно быть целью собеседования).
А Вы, khim, можете тут вот реализовать все операции RB-tree или Radix-tree не заглядывая в wikipedia(или другие источники информации).
Если необходимо реализовать timsort на листочке на собеседовании в офисе — я согласен с fzn7 — ничего это задание не показывает.В такой формулировке — таки нет. А в той формулировке, которая написана в статье — таки да.
Речь идёт не о фотографической памяти, а о понимании общих принципов. Если в качестве «стандартной сортировки» будет предьявлен MergeSort (как, собственно и было до Java7) — то можно будет поговорить про сложность и TimSort, если будет рассказано про TimSort — можно будет это обсудить тоже.
Так же в офисе могут попросить реализовать алгоритм на доске — вполне хорошее упражнение. Так как тут есть диалог между у частниками, даже если человек затрудняется реализовать алгоритм, видно как он мыслит (что в основном и должно быть целью собеседования).Для этого, собственно, подобные вопросы и задаются.
А Вы, khim, можете тут вот реализовать все операции RB-tree или Radix-tree не заглядывая в wikipedia(или другие источники информации).С первого раза безошибочно? Не факт. Особенно удаления. Но вы же сами указали на то, что этого, в общем, и не требуется. Важно посмотреть на то, как эта задача будет постепенно доводиться до ума. Все операции RB-tree сложнее, кстати, чем Timsort (про MergeSort я вообще молчу).
А откуда вы берёте это "не заглядывая в википедию"? Как правило, такое условие никогда не ставится за бессмысленностью, а если вы боитесь задавать вопросы, то это очевидный преогромный минус вам, а не интервьюерам.
А откуда вы берёте это «не заглядывая в википедию»?На онлайновых интервью — это типичное требование.
Но почему-то все, кто слышит про подобные вещи считают, что от них ожидают фотографической памяти и умения воспроизвести 100-200-500 строк кода из Википедии «как стихи». Чего, в общем, и близко нет. Вот тут человек описывает — зачем такие вопросы задаются и чего хочется в результате увидеть.
а если вы боитесь задавать вопросы, то это очевидный преогромный минус вам, а не интервьюерам.А вот это — не в бровь, а глаз.
Иногда достаточно знать где посмотреть, иногда нужно уметь сделать руками.
Писать на Java такие продукты как Hazelcast, Apache Ignite, Apache Cassandra и так далее. Чем вы недовольны?
Понимать как устроена сортировка нужно для другого. Вы можете сортировать данные один раз — в конце. А можете засунуть из в TreeSet и иметь их сортированными всегда. И то и другое — O(N log N), но в некоторых случаях лучше делать одно, в некоторых — другое. А иногда — лучше и вообще без сортировки обойтись.
Как вы, например, делаете выбор? Не зная ничего то том, как у вас сортировка устроена?
А где я был против знания и понимания алгоритмов сортировки?Ох.
Я против просьб написания реализации по памяти.А кто просит вас «реализовать по памяти»? Если вы «знаете и понимаете» алгоритмы сортировки — то почему для вас такая проблема один из них написать?
Вы разницу видите или вам еще детальнее расписать?Пожалуйста поподробнее. Потому как судя по вашему негодованию вы протестуете против просьбы написать код на тему, которую вы хорошо знаете и понимаете. Что, как по мне, является совершенно необходимым минимумом для того, чтобы можно было говорить о приёме на работу…
То есть получается такая цепочка:
1. Кандидат хорошо знает и понимает проблему (с этим вы вроде как не спорите).
2. Кандидат не помнит наизусть решение этой проблемы (тут как бы тоже всё хорошо: кто, действительно, в зравом уме и твёрдой памяти будет помнить все эти ньюансы?)
3. Однако при этом он неспособен написать решение задачи!'
Если обьеденить первый и третий пункты то это значит, что кандидат неспособен написать код для решения даже задачи, которую он хорошо знает и понимает! С которой он сталкивался 100 раз за время своей работы! Ну и нафига такой «работник» кому-то нужен?
Неужели вам совершенно западло было бы ответить на такой запрос горячо любимым и таким пушистым heapsort-ом. Вас же не просят water trapping задачу решить или замкнутый список поправить с помощью алгоритма Флойда для поиска зацикливаний.
Перебор или нет а это таки уже экзекутору экзаменатору тов Киселоффа решать. Попросили написать алгоритм сортировки на доске? Не помнишь QuickSort, но не хочешь позорится с пузырем, HeapSort таки для тебя.
То есть могу поверить, что такие бывают, но… не видел. Концептуально — HeapSort на порядок сложнее. Хотя код и не очень сложный…
Если тебя попросили написать алгоритм сортировки без рекурсии но с использованием классических структур данных (без Sorted* разумеется) то HeapSort тут на много проще и будет. Да и сама куча не такая уж и сложная.
Да, куча — штука относительно несложная. Но она заведомо сложнее примитивного QuickSort'а.
Сделать стек на массиве проще, чем «кучу», даже если рекурсия на уровне языка запрещена. Сделать так, чтобы размер этого стека не превысил O(log N) — тоже несложно (hint: хвостовая рекурсия).
P.S. Но на самом деле, открою маленький секрет, если вы напишите HeapSort вместо QuickSort'а — то это не будет большой проблемой. Материала для «поговорить во время интервью» это даст достаточно. Так что если вы фанат HeapSort'а — ну пишите его в качестве «стандартной сортировки». Проблемой будет изобретение 100500 причини «ничего не делать» по типу fzn7 — вот это действительно к отказу приведёт достаточно быстро.
Да в том то и дело что естественных примеров вокруг нас миллионы. Вы доблестный защитник израильского неба от самопала палестинцев, разработайте систему способную гасить в сортире на подлете эти самые самодельные ракеты, в учет должны приниматься скорость и расстояние ракеты до потенциальной цели.
Высосано из пальца но для собеседования потянет. Кстати такое вот например у вас могут спросить на одном из 6 технических собеседований в Amazon.
На псевдокоде. Накопившегося у человечества математического аппарата хватит на сто или двести лет вперед. Сегодняшние алгоритмы основаны на открытиях математиков 50, 100, 300 летней давности. Дейкстра свой алгоритм не за пол часа написал на каком нибудь собеседовании, на это иногда уходят годы.
Сегодня невероятное количество компаний работают над интереснейшими и очень реальными задачами. Что бы вас допустить до решения таковых задач такие компании должны быть в вас уверены, поэтому и прощупывают ваши знания на собеседованиях. Так устроен мир, увы.
Поверьте, я тоже исхожу из подобных убеждений. Мне тоже ближе к сердцу когда работодатель дает комплексное тестовое задание без отрыва от своего контекста. Это гораздо более качественный подход чем решение вот такой задачи по телефону за 30 мин.
Но большие конторы предпочитают другой подход, который может привести к вот таким вот результатам (Обсуждение того как Max Howell создатель Homebrew, которым пользуются 90 проц инженеров в гугле, не прошел собеседование в корпорацию добра). Так устроен мир, что тут можно сказать. Вопрос, на что готовы вы что бы работать на них...
Если всё, как вы говорите — то Гугл скоро потяряет своё первое место среди работодателей и все успокоятся.
Вам-то какое дело?
Кстати про несоответствующие (простите нерелевантные не русское слово) фильтры. Я так понимаю это часть IT менталитета англосаксонского мира, поработав в нем я в этом убедился. Устраиваясь там на работу у вас всегда спросят какое-нибудь упражнение и довольно часто у доски во время собеседования. Мне казалось в России дела обстоят точно так же. А вот во Фр и Бельгии дела обстоят не так весело, там просто с вами побеседуют, зададут какие нибудь вопросы типа про алгоритмы сборки мусора в JVM и вроде все на этом, ибо голод кадров просто ужасающий.
Я считаю, что отсутствие нерелевантных фильтров при трудоустройстве позволит каждому разработчику занять более справедливое положение на рынке и получить более высокий оклад,Если «каждый разработчик еа рынке начнёт получать более высокий оклад» — то за чей счёт будет банкет?
а компаниям, осознание собственных целей и грамотный подбор персонала, позволит увеличить эффективность и сократить издержки.А за счёт чего сократятся издежки при повышении оклада «каждому работнику»?
Возможно кто-то из коллег прочитает тред и сочтет мои доводы убедительнымиНе виду доводов пока, вижу демагогию. Противоречащие друг другу отверждания в пределах одного предложения — да ещё и не следующие из всего остального.
Но большие конторы предпочитают другой подход, который может привести к вот таким вот результатам (Обсуждение того как Max Howell создатель Homebrew, которым пользуются 90 проц инженеров в гугле, не прошел собеседование в корпорацию добра).Слышал эту историю от разных людей, но так и не понял где подвох. То, что человек смог создать пакетный менеджер скорее говорит о том, что он может работать PM'ом, а не программистом, тот факт, что с решением простейшей задачи на доске возникли сложности — этот факт скорее подтверждает.
Не знаю конкретно насчёт Homebrew, но все системы управления пакетами, с которыми я разбирался, «в младенчесте» имели ужасный код (квадратичная, а то и кубическая, сложность вместо O(N log N), плохие интерфейсы и т.д. и т.п.) и если Homebrew хоть сколько-нибудь их напоминает, то я ни разу не удивлён тем, что его не взяли.
Более того, есть ощущение, что решение Макса не взять — было лучшим для обоих сторон.
Начнем с того что вас тов Ким там не было, и свечку другой держал. А что про качество кода и черезмерную сложность то этим, увы, могут похвастаться даже такие продукты как Windows или некоторые продукты корпорации добра. TensorFlow не всегда был таким привлекательным а про AngularJs я вообще молчу.
Начнем с того что вас тов Ким там не было, и свечку другой держал.Что не помешало вам приводить этот пример в качестве доказательство «плохого решения». Назвались груздем — полезайте в кузов. В смысле обьясняйте почему вы считаете, что оно плохое. Никто вас за язык не тянул и историю с Максом не навязывал.
А что про качество кода и черезмерную сложность то этим, увы, могут похвастаться даже такие продукты как Windows или некоторые продукты корпорации добра.Совершенно с вами согласен — но это обозначает что, тем более, не стоит брать на работу людей, которые про них забывают или не знают, не так ли?
Что не помешало вам приводить этот пример в качестве доказательство «плохого решения». Назвались груздем — полезайте в кузов. В смысле обьясняйте почему вы считаете, что оно плохое. Никто вас за язык не тянул и историю с Максом не навязывал.
Я нигде не сказал что это было плохое решение. Все что вы тут указываете — полный бред, я ничего такого не говорил, вы лжец. Я лишь указал на вероятность появления таких ситуаций. К которой я совершенно никак не отношусь, в отличие от вас.
Совершенно с вами согласен — но это обозначает что, тем более, не стоит брать на работу людей, которые про них забывают или не знают, не так ли?
Это так же означает и обратное, не так ли?
Алгоритм быстрой сортировки с двумя опорными элементами разработан нашим соотечественником Владимиром Ярославским и реализован на python. Позже он был адаптирован на Java в классе DualPivotQuickSort
Кажется, вы что-то путаете. В статье Ярославского Python упоминается ровно ноль раз, а пример реализации как раз на Java.
Просто бесследно перетереть переосмысленный кусок текста или как-то это оформить с указанием на то, что ранее было неверно, а верно так-то.
Arrays, Collections: Алгоритмический минимум