Здравствуйте, k55, Вы писали:
D>>Откуда N^2 на уже упорядоченном массиве? k55>Все зависит от выбора серединного элемента. В случае если это будет всегда левый элемент и на вход подают отсортированном массиве "1234567"
И причем тут отсортированный массив? Единственная причина N^2 на квиксорте — это плохо выбранный пивот.
Здравствуйте, Donz, Вы писали:
k55>>Все зависит от выбора серединного элемента. В случае если это будет всегда левый элемент и на вход подают отсортированном массиве "1234567"
D>И причем тут отсортированный массив? Единственная причина N^2 на квиксорте — это плохо выбранный пивот.
А есть метод его правильно выбирать, кроме как используя рандом?
Здравствуйте, NikeByNike, Вы писали:
NBN>Здравствуйте, Donz, Вы писали:
k55>>>Все зависит от выбора серединного элемента. В случае если это будет всегда левый элемент и на вход подают отсортированном массиве "1234567"
D>>И причем тут отсортированный массив? Единственная причина N^2 на квиксорте — это плохо выбранный пивот.
NBN>А есть метод его правильно выбирать, кроме как используя рандом?
M>Очень интересно стало вот по этому кусочку, прокоментируете?
M>
M>Начало. С ходу предложили отсортировать массив целых положительных чисел. Сказал, что не буду изобретать ничего, а возьму std::sort, если сортировать надо часто подумаю о более подходящем алгоритме и структурах данных. Если сортировать надо много и набор данных специфический изучу вопрос и подберу подходящий метод сортировки. Посмотрели разочарованно. Поинтересовались что внутри std::sort, ответил, что скорее всего quick sort. Спросили про его сложность, сказал, что O(n * log n) и O(n * n) на уже упорядояенном массиве. Попросили рассказать как он работатет. Рассказал в общих чертах, что делится массив на 2 части, затем рекурсивно повторяется алгоритм к двум частям и т.д. до конца. Снова посмотрели разочарованно.
M>Ибо совсем непонятно в каком контексте вы ожидаете услышать ответ (задачу то уже спалили).
Данный вопрос — это повод поговорить про алгоритмы сортировки: какие алгоритмы эффективны в той или иной ситуации, каков принцип их работы, сложность и т.д. Приведенный ответ — это шаг в верном направлении. Он не плох по форме, но плох по содержанию, т.к. с одной строны он неполный, а с другой — содержит грубые ошибки и ряд неточностей, на некоторые из которых уже указали в комментариях.
V>Так, небольшое замечание, имхо, для успешного решения этих задач вам V>скорее нужен специалист, который знает матан, га, твимс, цос V>и не на уровне института, ну и матлаб (как язык программирования и V>инструмент), чтобы это описать не только в формулах, V>но и в виде работающего алгоритма,
С++ и алгоритмы — это необходимое требование к данным вакансиям, но не для всех вакансий оно достаточное. Более полную информацию можно получить в описаниях вакансий по ссылкам.
V>и только в последнюю очередь "хорошо V>знаете С++ и алгоритмы, обладаете смелостью браться за V>сложные задачи и желанием постоянно изучать что-то новое, мы ждем вас на V>собеседовании."
Это не вполне справедливо. Если мы видим, что канидат обладает высоким потенциалом, мы можем закрыть глаза на отсутствие у него некоторых специальных знаний с тем расчетом, что он быстро восполнит их недостаток.
D>Данный вопрос — это повод поговорить про алгоритмы сортировки: какие алгоритмы эффективны в той или иной ситуации, каков принцип их работы, сложность и т.д. Приведенный ответ — это шаг в верном направлении. Он не плох по форме, но плох по содержанию, т.к. с одной строны он неполный, а с другой — содержит грубые ошибки и ряд неточностей, на некоторые из которых уже указали в комментариях.
Ну, тема сортировки это эпическая проблема в Yandex. Еще в первом пришествии "Собеседование в Яндекс" на тысяче постов разбиралась Radix Sort c разбором личностных качеств кандидатов и психологическими портретами собеседователей в Yandex. Такое ощущение, что других задач в Yandex нет.
Я думаю, что сортировка является стандартным отработанным фильтром кандидатов в Яндекс. Все кого берут в компанию как правило проходят через "сортировочные" тесты, в результате которых кандидаты сортируются на первый и второй сорт. Потом эти люди применяют сортировку когда становятся собеседователями. А еще говорят что в Yandex нет корпоративной культуры
В отношении работников Yandex — всегда остается чувство недосказанности, Дмитрий Котляров удивительно неубедителен. Я не слышал ответа в оригинале, но в посте идут уже придирки к достаточно вменяемому ответу кандидата. Анатоликс был куда убедительней и лояльней.
Я работаю на последнем месте почти три года, сортировку не написал ни разу. C++ конечно позволяет издеваться над кандидатами, а вот как например сделать сортировку на node.js? myArray.sort( function(item1, item2) { item1.id-item2.id; }); Любой сорт написанный на JavaScript проиграет внутреннему sort написанному на C++ кроме самых вырожденных случаев. В реальных сервисах time to market куда важнее написания собственного сорта.
H>Я работаю на последнем месте почти три года, сортировку не написал ни разу. C++ конечно позволяет издеваться над кандидатами, а вот как например сделать сортировку на node.js? myArray.sort( function(item1, item2) { item1.id-item2.id; }); Любой сорт написанный на JavaScript проиграет внутреннему sort написанному на C++ кроме самых вырожденных случаев. В реальных сервисах time to market куда важнее написания собственного сорта.
Не поверите, но я тоже ни разу не писал сортировку по работе. Тем не менее продолжаю утверждать, что для решения определенного класса задач необходимо ЗНАТЬ алгоритмы и структуры данных, а не уметь искать их в интернете. Потому что задача обычно состоит не в том, чтобы написать еще одну реализацию сортировки, а в том, чтобы решить конкретную прикладную задачу, используя базовые алгоритмы и структуры данных как конструктор (или как источник идей).
MTD>Они не стали для меня неожиданностью, просто как-то так вышло, что не пишу быструю сортировку, хотя могу если будет надо. Про сортировку за O(n), да, не знал, но я много чего другого знаю и умею находить информацию, в любом случае это не важно.
С тем же успехом можно сказать "я не знаком с ядерной физикой, но знаю, где библиотека". На мой взгляд, это звучит неубедитьльно.
Почему мы проверяем именно знания алгоритмов, а не умение искать их в интернете, я ответил здесь
.
MTD>А вот что понимается под знаниями С++ я не уловил, может способность писать запутанный код? Ну тогда я точно не подхожу — я пишу так чтобы было очевидно любому.
Под этим понимаются уверенные ответы на простые вопросы. Как я уже сказал, в стенограмме не видно ни Ваших сомнений, ни метаний в поисках истины. Когда в азах сомневается студент — это можно понять, но для разработчика с опытом такое уже недопустимо и, на мой взгляд, говорит о поверхностности.
Здравствуйте, dkotlyarov, Вы писали:
D>С тем же успехом можно сказать "я не знаком с ядерной физикой, но знаю, где библиотека". На мой взгляд, это звучит неубедитьльно.
Дмитрий, я вам ничего не доказываю.
D>Почему мы проверяем именно знания алгоритмов, а не умение искать их в интернете, я ответил здесь
Я допускаю, что у вас ковбой-стайл кодинг без предварительного изучения вопроса — ничего не имею против, полный вперед.
D>Под этим понимаются уверенные ответы на простые вопросы. Как я уже сказал, в стенограмме не видно ни Ваших сомнений, ни метаний в поисках истины. Когда в азах сомневается студент — это можно понять, но для разработчика с опытом такое уже недопустимо и, на мой взгляд, говорит о поверхностности.
Еще раз — вам видней, я ничего вам доказывать не собираюсь.
Это просто собеседование — вы смотрите на меня, я на вас. Вы делаете выводы, я тоже. У меня есть опыт успешно завершенных проектов, которые как вы любите говорить "работают 24 часа в сутки 7 дней в неделю". Я не нуждаюсь в одобрении и не горю сменить работу — она у меня есть и хорошо оплачивается. Поэтому я знаю себе цену и возможно, в отличии от вчерашнего студента у меня от зубов не отскакивают детали быстрой сортировки, но я могу изучить предметную область и написать надежный код, который будет легко поддерживать и развивать. Удачи вам в поиске. Я в свою очередь тоже определенные выводы сделал.
Здравствуйте, dkotlyarov, Вы писали:
D>Под этим понимаются уверенные ответы на простые вопросы. Как я уже сказал, в стенограмме не видно ни Ваших сомнений, ни метаний в поисках истины. Когда в азах сомневается студент — это можно понять, но для разработчика с опытом такое уже недопустимо и, на мой взгляд, говорит о поверхностности.
Здесь есть интересный момент. Базовые вещи со временем уже откладываются на подсознательном уровне. Ты вроде пишешь код правильно, но сходу сформулировать, почему, не всегда удается. Недавно тоже было собеседование, и я поймал себя на этом. Мне дают код, я отвечаю правильно, но когда просят объяснить, сижу и туплю, пытаясь вытянуть информацию из глубин мозга. Конечно, в итоге это удается, но может выглядеть, будто кандидат "плавает". В такие моменты важно чутье интервьюера.
Я еще хотел сказать по поводу Radix Sort. Если первый вопрос действительно прозвучал так, как сказал ТС, не лучше было бы ввести человека в контекст? Например, задать вопрос точнее. "У вас есть массив только положительных целых чисел. Какой бы вы предложили алгоритм, способный максимально быстро отсортировать такой массив?". Мне кажется, указание на приоритет скорости лучше укажет кандидату направление мысли.
D>Не поверите, но я тоже ни разу не писал сортировку по работе. Тем не менее продолжаю утверждать, что для решения определенного класса задач необходимо ЗНАТЬ алгоритмы и структуры данных, а не уметь искать их в интернете. Потому что задача обычно состоит не в том, чтобы написать еще одну реализацию сортировки, а в том, чтобы решить конкретную прикладную задачу, используя базовые алгоритмы и структуры данных как конструктор (или как источник идей).
В общем, чего и требовалось доказать. Сортировка — это способ сортировать кандидатов.
Вот нифига не помню как написать квик сорт или красно-черное дерево. Ни то, ни другое никогда не писал сам.
Более того, постепенно становлюсь противником языков с указателями, ручным управлением памяти и структурами данных основанных на указателях. Парадокс, но портировав низко и средненагруженные проекты с C++ на Node.js получили потерю производительности в 1,5-3 раза при сокращении времени девелопмента в 5-10 раз.
Думаю, в Yandex тенденция сваливания с C/С++ тоже должна иметь место для некритичных проектов
Здравствуйте, dkotlyarov, Вы писали:
D>Если вы хорошо знаете С++ и алгоритмы, обладаете смелостью браться за сложные задачи и желанием постоянно изучать что-то новое, мы ждем вас на собеседовании. При любом исходе вы получите интересный опыт или обнаружите пробелы в знаниях, что тоже полезно.
Привет, Дмитрий!
От себя могу сказать что интервью в яндексе действительно прикольные и я не пожалел что на них сходил. Единственное что для меня немного сгладило впечатление это какая то туманность итоговых ответов мне. Я был на двух очных собеседованиях в двух разных командах (последнее было в вашу в январе), сразу после собеседований мне говорили что все ок, но потом по почте сообщали что то в духе "мы сейчас не можем вам предложить эту работу".
Кстати по поводу radix sort, я бы на вашем месте уже бы начал давать что то другое , например heap sort или хотя бы тот же qsort с условием чтобы не сливал стандартному сильно.
D>Под этим понимаются уверенные ответы на простые вопросы. Как я уже сказал, в стенограмме не видно ни Ваших сомнений, ни метаний в поисках истины. Когда в азах сомневается студент — это можно понять, но для разработчика с опытом такое уже недопустимо и, на мой взгляд, говорит о поверхностности.
Дмитрий, морализаторство совсем не красит руководителя.
Неоднократно был в ситуации когда на вопрос интервьюера я задумывался не о том, как правильно ответить на вопрос, а о том что хочет от меня этот конкретный человек услышать.
Например на вопрос как я отношусь к С++ я могу ответить двумя способами.
1) Это язык который позволяет получить экстремальную производительность кода, является исключительно предсказуемым на этапе исполнения и позволяет создавать высоконагруженные приложения. Это исключительно мощный язык на котором написано огромное количество успешных проектов.
2) Это легаси язык с отсутствием сборки мусора, ручным управлением памятью которое провоцирует утечки памяти, крайне опасными указателями которые позволяют выходит за границы массивов и буферов и приводят к краху программ на этапе исполнения, крайне сложными конструкциями в области шаблонов и слишком бедной стандартной библиотекой которая провоцирует чрезмерно низкоуровневое программирование. Это язык, программирование на котором очень затратно по финансам и времени
Оба ответа — абсолютно правильные. Который из них Вам нравится больше? Не зная Вас персонально я не знаю какой вариант я бы Вам предложил
BNL>От себя могу сказать что интервью в яндексе действительно прикольные и я не пожалел что на них сходил. Единственное что для меня немного сгладило впечатление это какая то туманность итоговых ответов мне. Я был на двух очных собеседованиях в двух разных командах (последнее было в вашу в январе), сразу после собеседований мне говорили что все ок, но потом по почте сообщали что то в духе "мы сейчас не можем вам предложить эту работу".
А у меня собеседование было тупейшим. Шесть-семь человек попеременно задавали вопросы, атмосферка была крайне неприятной. Наверное в Yandex не знают, что собеседование огромной толпой оставляет очень неприятные ощущения.
Здравствуйте, Handie, Вы писали:
H>А у меня собеседование было тупейшим. Шесть-семь человек попеременно задавали вопросы, атмосферка была крайне неприятной. Наверное в Yandex не знают, что собеседование огромной толпой оставляет очень неприятные ощущения.
ИМХО это ещё и очень неэффективная трата времени. Эффективней сделать несколько собеседовний с отдельными людьми и их последующим внутренним обсуждением.
MTD>Это просто собеседование — вы смотрите на меня, я на вас. Вы делаете выводы, я тоже. У меня есть опыт успешно завершенных проектов, которые как вы любите говорить "работают 24 часа в сутки 7 дней в неделю". Я не нуждаюсь в одобрении и не горю сменить работу — она у меня есть и хорошо оплачивается. Поэтому я знаю себе цену и возможно, в отличии от вчерашнего студента у меня от зубов не отскакивают детали быстрой сортировки, но я могу изучить предметную область и написать надежный код, который будет легко поддерживать и развивать. Удачи вам в поиске. Я в свою очередь тоже определенные выводы сделал.
Примерно то-же самое при устройстве в MS и Google. Там никого не волнует Ваш предыдущий опыт, наличие проектов на GitHub. Там будут задачки про гномиков, написания quick-sort и прочая хрень.
Чтобы пройти собеседования в Yandex нужно натаскиваться на сортировки и поиски — написать каждую сортировку по памяти пару раз. Уважающий себя профи натаскиваться на сортировки вечером после работы не будет.
Мне например работа в Yandex не нужна Я слишком хорошо понимаю что такое большая контора с тысячей программеров и насколько рутинной и неинтересной может быть работа там. При этом есть чуть менее престижные конторы но с похожими направлениями, более высокими зарплатами и меньшим пафосом. Просто в Yandex народ рвется из-за раскрученности расказов о бесплатных печеньках, суперпроектах и элитарности этой суперкомпании.
NBN>ИМХО это ещё и очень неэффективная трата времени. Эффективней сделать несколько собеседовний с отдельными людьми и их последующим внутренним обсуждением.
Ну, типа вся команда сразу мучит человека Кстати, то-же самое было и не только в Yandex
Здравствуйте, dkotlyarov, Вы писали:
MTD>>Они не стали для меня неожиданностью, просто как-то так вышло, что не пишу быструю сортировку, хотя могу если будет надо. Про сортировку за O(n), да, не знал, но я много чего другого знаю и умею находить информацию, в любом случае это не важно.
D>С тем же успехом можно сказать "я не знаком с ядерной физикой, но знаю, где библиотека". На мой взгляд, это звучит неубедитьльно. D>Почему мы проверяем именно знания алгоритмов, а не умение искать их в интернете, я ответил здесь
Здравствуйте, Handie, Вы писали:
NBN>>ИМХО это ещё и очень неэффективная трата времени. Эффективней сделать несколько собеседовний с отдельными людьми и их последующим внутренним обсуждением.
H>Ну, типа вся команда сразу мучит человека Кстати, то-же самое было и не только в Yandex
MM>Я еще хотел сказать по поводу Radix Sort. Если первый вопрос действительно прозвучал так, как сказал ТС, не лучше было бы ввести человека в контекст? Например, задать вопрос точнее. "У вас есть массив только положительных целых чисел. Какой бы вы предложили алгоритм, способный максимально быстро отсортировать такой массив?". Мне кажется, указание на приоритет скорости лучше укажет кандидату направление мысли.
А разве из моего комментария следует, что мы ожидаем услышать именно про radix sort? Более того, из постановки вопроса тоже нельзя заключить, что radix sort в данном случае будет наиболее эффективен. Хотя знание данного алгоритма и является плюсом, его незнание не особо критично. Если кандидат может связно объяснить процесс выбора подходящего алгоритма сортировки "в зависимости от", то этот ответ засчитывается.
