Comments 19
Раз уж вы приводите пример и устойчивых и неустойчивых сортировок, то было бы здорово привести пример устойчивой сортировки за O(n * log(n)), потому что про них тоже довольно часто спрашивают, например Merge Sort хорошо бы подошел - https://ru.wikipedia.org/wiki/Сортировка_слиянием.
Еще думаю у Quick Sort было бы полезно показать худший случай, где сортировка за O(n ** 2), раз вы его упоминаете.
Big O — нотация, которая позволяет определить верхнюю границу скорости работы алгоритма. Она описывает отношение входных данных ко времени, за которое алгоритм сможет их обработать.
Это тоже не совсем верно, Big O - асимптотическая сложность, которая описывает верхнюю границу сложности алгоритма при увеличении размера входных данных, или как рост размера входных данных влияет на количество шагов. Но никак не отношение данных ко времени.
"Поначалу может показаться нелогичным, что функция с один циклом и функция с двумя циклами оцениваются по Big O как эквивалентные по временной сложности" - они не оцениваются как эквивалентные, функция с одним циклом это n, с двумя 2n(в вашем случае), если вложенный цикл n^2. Все логично.
в целом поддерживаю, но!!!! мне кажется через 3-5 лет про это просто забудут и переключатся на что-то ещё и вот почему - я программирую с 1987 года и явно сортировку реализовывал только в двух случаях - когда пишу на ассемблере и когда пишу в академических целях. Во всех остальных случаях есть имплементации в стандартных библиотеках или есть подключаемые сторонние библиотеки с какой-то еще реализацией, может ТимСорт какой.
а я сторонник контекстного программирования, уж не знаю есть вообще такое в терминологии. Суть в том, что я считаю верным сначала анализировать данные, а потом под эти данные разрабатывать алгоритм. Несомненно есть масса случаев где это вообще не нужно и достаточно алгоритма общего назначения, например MergeSort или Deflate и у вас всё в шоколаде. Но я говорю именно о случаях, когда вам обязательно нужно заморочиться. Иначе совсем непонятно зачем учить все эти алгоритмы.
И почему я говорю о том, что это всё пройдёт? Потому что 20 лет назад об этом вообще не было разговоров. С вас же сегодня никто не спрашивает о том как вам преобразовать вещественное число, как работать с мантиссой. А я в начале 90-х активно это изучал и этим пользовался. А сегодня это никому не интересно.
Поэтому достаточно под стекло на столе положить листок с распечатанной таблицей видов сортировок, их BigO() и устойчивость. И в 99% случаев вы будете использовать устойчивый O(n * log(n)).
То есть собеседоваться по алгоритмам как таковым абсолютно бессмысленно. (только если вы не пишете для какого-то микроконтроллера, для которого еще нет стандартной сишной реализации).
PS: пишу я в основном на C#, если речь про современный язык, и там я использую Order, OrderBy, LINQ и т.п. И я проверял, писал свою реализацию сортировки и работала они сильно хуже, то есть те кто писали реализацию на C# несколько поумнее меня будут. Это не значит что они не ошибаются или что они всегда пишут идеальный код. Не об этом речь. И если уж в вашей компании появился человек, который уверен что стандартные сортировки не подходят, то чем ему поможете вы, собственно эти самые стандартные сортировки и знающий?
или есть подключаемые сторонние библиотеки с какой-то еще реализацией, может ТимСорт какой.
ТимСорт, кстати, уже несколько лет как внутри Array.prototype.sort
мне кажется через 3-5 лет про это просто забудут
Ну, что вы! Через 3-5 лет задача отсеивать на собеседованиях никчёмных вошедших в ай-ти выпускников суперкурсов не только не исчезнет, но станет гораздо более актуальной. Судя по скорости с которой плодятся эти курсы.
И почему я говорю о том, что это всё пройдёт? Потому что 20 лет назад об этом вообще не было разговоров
Ничего подобного. 20 лет назад на собеседованиях спрашивали практически то же самое (минус кафка, докер, кубер).
С вас же сегодня никто не спрашивает о том как вам преобразовать вещественное число, как работать с мантиссой. А я в начале 90-х активно это изучал и этим пользовался. А сегодня это никому не интересно.
Про это и в 90х не спрашивали массово. Просто вы тогда с этим работали, поэтому и изучали. Сейчас не работаете, поэтому вам кажется, что это никому не интересно. Но это только кажется. Например, недавно на хабре была интереснейшая статья про ошибки в вещественных расчётах в gcc, волшебным образом исчезавшие при меньшей разрядности целевой архитектуры. Кто-то это вполне изучает и пользуется.
Поэтому достаточно под стекло на столе положить листок с распечатанной таблицей видов сортировок, их BigO() и устойчивость.
Довольно бессмысленно. Если не понимать как это работает, то есть риск принятия решения на основе глупости. Как у автора этой статьи написано про "пузырёк": Когда нет ограничений по памяти, так как этот алгоритм выполняет операцию перестановки элемента практически на каждой итерации. - ну, что за бред? Как тут "ограничения по памяти влияют"? Или про "быструю": 5. Запускаем цикл по массиву i, в котором сравниваем текущий элемент с pivot и помещаем его либо в массив с большими значениями, либо в массив с меньшими значениями. 6. Возвращаем массив, состоящий из объединения массивов с меньшими и большими значениями, а между ними помещаем pivot. - поняли, да? Заводим два массива, помещаем туда-сюда, объеденяем массивы... Не, ну так тоже можно, но автор в принципе не понимает почему так не надо делать. Кроме того, "алгоритм" в таком виде вообще не рабочий, в нём нет шага рекурсии - надо не возвращать подмассивы, а применять к ним рекурсивно этот же алгоритм и уж потом "возвращать". Теперь контрольный вопрос - возьмёте автора к себе на работу? :) Даже на условиях что ему никогда не придётся писать квиксорты? :) вот то-то же!
То есть собеседоваться по алгоритмам как таковым абсолютно бессмысленно.
Как видите, смысл есть. Задача таких собеседований не в том, чтобы набрать людей для написания квиксортов, а в том, чтобы отсеять людей отчего-то решивших, что "пузырьёк" не следует использовать когда есть ограничения на память(!). На память, Карл! У него перед глазами и словесное описание алгоритма и его реализация и биг оу оценка, но он всё равно пишет, что у алгоритма проблемы с памятью. Я не читал статью дальше бредового описания квиксорта, стало слишком страшно. А вы говорите бессмысленно... :)
И если уж в вашей компании появился человек, который уверен что стандартные сортировки не подходят, то чем ему поможете вы, собственно эти самые стандартные сортировки и знающий?
В этом случае я хотя бы смогу понять причину по которой в каком-то случае стандартные реализации не подходят. Или аргументированно возразить, что существует подходящий вариант и не стоит изобретать велосипед. И это будет аргументированный ответ, а не как написано в бумажке под стеклом, которой пользовался автор данной статьи, что пузырёк не подходит когда есть ограничения на память (рука-лицо)
К слову отсеивания "послекурсников" есть действенный способ всех их и курсы в один клик помножить на ноль, но никто этого делать не будет - начать требовать диплом о профильной вышке. Но как мне сказал мой друг и без дипломов много толковых спецов. Они тоже попадут под фильтр.
Действительно, пункт, где говорится, что алгоритм стоит использовать, если нет ограничений по памяти, был ошибочным. Текст скорректировали. Спасибо за замечание!
Ну, что вы! Через 3-5 лет задача отсеивать на собеседованиях никчёмных вошедших в ай-ти выпускников суперкурсов не только не исчезнет, но станет гораздо более актуальной. Судя по скорости с которой плодятся эти курсы.
я знаю массу хороших специалистов не понимающих какие-то, как мне кажется, банальные вещи, можно сказать фундаментальные, то есть эти люди никогда не пройдут собеседования подобного рода. Мой спич как раз об этом в том числе.
Ничего подобного. 20 лет назад на собеседованиях спрашивали практически то же самое (минус кафка, докер, кубер).
ну значит мы в разных местах собеседовались.
Про это и в 90х не спрашивали массово
я с 80-х ни разу не слышал ни одного вопроса про алгоритмы, репрезентативно?
Просто вы тогда с этим работали, поэтому и изучали
Нет, я с этим совсем не работал, но спрашивали. Я писал на Clipper, как сейчас бы выразились - фронтэнд.
Сейчас не работаете, поэтому вам кажется, что это никому не интересно
Никогда не работал с этим, но про мантиссу спрашивали регулярно, про алгоритмы - никогда. Я про BigO по сути узнал в том виде как оно есть только в середине 10-х годов, и то с академической целью, так как стал программировать для себя сортировки и компрессию. Мы её даже в ВУЗе на курсе "теория и технология программирования" не изучали.
Например, недавно на хабре была интереснейшая статья
Читал, но недавно там же была и моя статья про MOS 6502, это не говорит о том, что на собеседовании у вас будут про этот ЦПУ спрашивать.
Кто-то это вполне изучает и пользуется.
Не совсем ясен ваш пример в контексте разговора, какой тезис он опровергает?
Ну вот, уже про тупой поиск перебором в массиве в статье прочитал. Подметил пару косяков:
При описании быстрой сортировки у вас между шагами 5 и 6 отсутствует указание, что массивы тоже надо отсортировать. Рекурсия пропала. В примере кода всё норм. А, ещё не обработан случай, когда есть значения, совпадающие с pivot.
При двоичном поиске в отсортированном массиве обычно возвращают индекс первого элемента, который больше заданного, то есть индекс вставки.
ни одно современное собеседование в крупную компанию не обходится без вопросов про алгоритмы,
Потому что позеры без кретивного мышления они вот и все там. Писать алгоритмы сортировки, да ещё из головы - последнее что нужно в жизни.
Размер компании не аргумент правильности действия. Ищите нормальный коллектив, а не выбирайте компанию
ни одно современное собеседование в крупную компанию не обходится без вопросов про алгоритмы,
Сразу нужно разворачиваться и уходить собеседования поставив галочку "неадекваты" напротив этой компании.
Знание всех алгоритмов сортировки (например) понадобится только в одно случае: нужно написать программу сортировки на необитаемом острове за 5 минут (пока не кончился заряд в ноутбуке) и нет вообще ни связи с чем то ни, ни чего.
За много много лет программером мне ни разу не понадобилось знание базовых алгоритмов досконально. Достаточно общих представлений о их критериях (память/сложность), что бы в редких случая иметь критерии выбора одного из них и заглянуть в стандартную реализацию не особо вникая в детали.
"Собеседование на знание базовых алгоритмов" мне напомнило случай когда я сдавал на deep сертификат (PADI). Там одно из упражнений - выполнить задачу на 40м (тест на азотку).
И предлагают мне поделить в столбик 4-х значное число на 3-х значное. Пришлось показать средний палец и написать на дощечку "give me something else".
Потому еще 5 минут, на боте уже, вспоминал как делится в столбик. Зная принцип - вспомнить (скорее вывести) не долго. Но когда последний раз это делал в школе (25 лет назад), то быстро это не сделать.
Ну или такой вопрос про алгоритмы можно задать, что бы срезать. Как мне срезали 5 на 4 на экзамене, задав вопрос про разрядность регистров сопроцессора (x86). Ну там хоть понятно было "за что". Я на лекции эти принципиально не ходил и это препода похоже задело.
Нет ещё статьи (на хабре или где бы то ни было ещё), прочитав которую, человек сможет спустя год или 6 месяцев после прочтения, написать с нуля быструю сортировку, кроме элементарных типа пузырьковой. Просто потому что это в том числе математическая проблема, а точнее на стыке информатики и математики. На которую нужно потратить некоторое количество часов (от 120 полагаю), обязательно запачкав руки. А ещё, хорошо бы, если бы человек это делал не для того, чтобы собеседование пройти, а потому что действительно понимает ценность, имеет неподдельную мотивацию. Алгоритмы ради алгоритмов - (ИМХО) чушь, которая точно растает со временем.
Также, мне кажется, что фронтендеру в первую очередь необходим другой набор компетенций, который включает в себя, к примеру, понимание вёрстки (box модели и всякого такого), языка(ов), сборщиков, фреймворков, понимание UI/UX и прочего. Банально общая эрудиция в вэбе - более важные критерии, которые говорят о кандидате. Касательно алгоритмов и структур данных, умение написать быструю сортировку, после того, как тебя разбудили - совершенно не говорит о том, что ты хороший фронтендер. Достаточно, чтобы человек доказал, что понимает, как работает о-нотация, заикнулся об аппроксимации. Структуры данных, как правило, люди лучше понимают, но и тут можно делать скидку. Последние два пункта (алгоритмы и структуры) я бы отнёс к категории компетенций - общая IT-эрудиция. Туда же - сети, которые тоже более важны для веба, чем умение написать быструю сортировку. Банально ответ на вопрос, а что происходит, когда я ввожу в адресной строке браузера что-то и нажимаю ENTER - даёт больше информации и простора для раскопок, в процессе которых можно прощупать общую эрудицию.
Фактически, эта (и аналогичные ей) статья поможет скорее самому автору (разложить всё по полочкам), чем читающему. Не обижайтесь, но существует же тонна книг, серий лекций, (да банально тех же курсов), которые в совокупности дают более качественные знания. Так что вклад в проблематику - изучение/обучение алгоритмов(ам), невелик.
9 алгоритмов сортировки и поиска для JS, о которых вас спросят на собеседовании