Здравствуйте, Олег К., Вы писали:
ОК>Это не аргумент а опыт.
Не суди всех по себе
ОК>Поболее чем три.
Помнить нужно именно три. А остальное надо не помнить, а просто написать. Если для тебя проблема написать функцию split по известным требованиям (эти требования таки надо помнить), то лучше вообще программированием не заниматься.
ОК>>>Если ты такой вундеркинд, напиши еще и shell sort заодно. Для тебя это не должно составить труда. G>>К сожалению не помню в чем идея shell sort. первый и последний раз я читал про него лет 15 назад. ОК>Ха! То есть, получается, что ты не знаешь стандартные алгоритмы? Ну это согласно питону.
С каких пор shellsort стал стандартным? Он массово применяется где-то? Реализован в библиотеках множества языков? Имеет среднее время лучше n*log(n)? Имеет какую-то ценность для построения других алгоритмов? Почему например не timsort?
Быстрая сортировка полезна, так как демонстрирует применение рекурсии и подхода "разделяй и властвуй", а чем так примечательна сортировка шелла?
Re[6]: Аморально ли требовать алгоритмы на архитектора
Здравствуйте, gandjustas, Вы писали:
G>Ты не силен в алгоритмах, так что свои слова стоит доказать
Не силен. Но в твоей дословной кальке с Википедии сходу нашел 2 проблемы. На собеседовании потребуешь звонок другу скопировать с Википедии?
G>>>ЗЫ. ни разу не писал qsort, да и вообще программирую крайне редко. Тё>>qsort грамотно реализовать- нетривиальная задача. G>Это не надо делать. надо уметь показать на собеседовании что ты знаешь как это сделать.
Пока что ты показал умение копипасты
Re[6]: Аморально ли требовать алгоритмы на архитектора
Тё>>Ты вроде qsort предлагал, а код твой сортирует пузырьком. G>Ты не силен в алгоритмах, так что свои слова стоит доказать
Что значит не силен в алгоритмах? Помнить их все наизусть? Ну так и ты их все не помнишь, о чем ты сам сейчас признался.
G>>>ЗЫ. ни разу не писал qsort, да и вообще программирую крайне редко. Тё>>qsort грамотно реализовать- нетривиальная задача. G>Это не надо делать. надо уметь показать на собеседовании что ты знаешь как это сделать.
Первое. Я не считаю правильным просить реализовать стандартные алгоритмы. Достаточно знать что быстрая сортировка есть и в STL и в сишной библиотеке. И второе. Это зависит на кого нарвешься.
Re[7]: Аморально ли требовать алгоритмы на архитектора
Здравствуйте, Тёмчик, Вы писали:
Тё>Здравствуйте, gandjustas, Вы писали:
G>>Ты не силен в алгоритмах, так что свои слова стоит доказать
Тё>Не силен. Но в твоей дословной кальке с Википедии сходу нашел 2 проблемы.
Проблемы в студию.
Тё>На собеседовании потребуешь звонок другу скопировать с Википедии?
Для меня на собеседовании важнее будет если человек расскажет почему быстрая сортировка быстрее сортировки выбором или вставками.
G>>>>ЗЫ. ни разу не писал qsort, да и вообще программирую крайне редко. Тё>>>qsort грамотно реализовать- нетривиальная задача. G>>Это не надо делать. надо уметь показать на собеседовании что ты знаешь как это сделать. Тё>Пока что ты показал умение копипасты
Еще один...
Я не открывал википедию если что.
Прикинь, я умею без википедии код на 20 строк написать. Желаю тебе того же.
Re[10]: Аморально ли требовать алгоритмы на архитектора
ОК>>Это не аргумент а опыт. G>Не суди всех по себе
Не сужу. Я прекрасно осведомлен кто работает и какие задачи решаются в индустрии.
ОК>>Поболее чем три. G>Помнить нужно именно три. А остальное надо не помнить, а просто написать. Если для тебя проблема написать функцию split по известным требованиям (эти требования таки надо помнить), то лучше вообще программированием не заниматься.
Пардон но почему ты помнишь один алгоритм а не помнишь другой?
ОК>>>>Если ты такой вундеркинд, напиши еще и shell sort заодно. Для тебя это не должно составить труда. G>>>К сожалению не помню в чем идея shell sort. первый и последний раз я читал про него лет 15 назад. ОК>>Ха! То есть, получается, что ты не знаешь стандартные алгоритмы? Ну это согласно питону. G>С каких пор shellsort стал стандартным? Он массово применяется где-то? Реализован в библиотеках множества языков? Имеет среднее время лучше n*log(n)? Имеет какую-то ценность для построения других алгоритмов? Почему например не timsort?
Тем не менее его проходят в университетском курсе. То что ты его не считаешь стандартным это другой вопрос. В зависимости на кого ты нарвешься, твой интервьюер может иметь совсем иное мнение.
G>Быстрая сортировка полезна, так как демонстрирует применение рекурсии и подхода "разделяй и властвуй", а чем так примечательна сортировка шелла?
Еще раз ха! Почитай чем она примечательна и где может использоваться. Если этого нет в вики, то открой книгу.
Re[8]: Аморально ли требовать алгоритмы на архитектора
Тё>>Пока что ты показал умение копипасты G> Еще один... G>Я не открывал википедию если что.
G>Прикинь, я умею без википедии код на 20 строк написать. Желаю тебе того же.
Видишь ли, я верю что ты можешь писать код на работе, но в данном случае это был больше вопрос не на написать а на помнишь ли ты как это работает изнутри. Такое быстро забывается после учебы. Поэтому я и отказываюсь верить что ты помнишь быструю сортировку.
Re[7]: Аморально ли требовать алгоритмы на архитектора
Ты отвечаешь на коммент другому человеку.
Тё>>>Ты вроде qsort предлагал, а код твой сортирует пузырьком. G>>Ты не силен в алгоритмах, так что свои слова стоит доказать
ОК>Что значит не силен в алгоритмах?
Если челоек считает что алгоритмы не надо спрашивать на собеседовании значит что он и ни не силен. Был бы силен — не писал бы на форуме.
ОК>Помнить их все наизусть? Ну так и ты их все не помнишь, о чем ты сам сейчас признался.
Я не говорил что надо помнить, да и вообще речи не шло про то, что надо наизусть помнить все алгоритмы сортировки. Это ты сам придумал.
G>>>>ЗЫ. ни разу не писал qsort, да и вообще программирую крайне редко. Тё>>>qsort грамотно реализовать- нетривиальная задача. G>>Это не надо делать. надо уметь показать на собеседовании что ты знаешь как это сделать.
ОК>Первое. Я не считаю правильным просить реализовать стандартные алгоритмы.
Никто не говорил что надо помнить стандартные алгоритмы.
ОК>Достаточно знать что быстрая сортировка есть и в STL и в сишной библиотеке.
Недостаточно. Надо уметь самому конструировать алгоритмы, если в стандартной библиотеке подходящих нет.
У меня был случай — надо было написать функцию, которая превращает IEnumerable<T> в IEnumerable<IEnumerable<T>>, нарезая входную последовательность на блоки по определенному условию, зависящему от нескольких предыдущих элементов.
Я потом эту задачу на собеседовании давал. Код менее чем на 20 строк. Из 10 кандидатов справилось два. При этом все прекрасно знали linq, yield, как устроен IEnumerable и то, что енумератор — value type.
Re[8]: Аморально ли требовать алгоритмы на архитектора
Здравствуйте, gandjustas, Вы писали:
G>>>Ты не силен в алгоритмах, так что свои слова стоит доказать
Тё>>Не силен. Но в твоей дословной кальке с Википедии сходу нашел 2 проблемы. G>Проблемы в студию.
1) граничные условия. У тебя переполнение стека может случиться
2) переполнения не случится, ибо в твоем варианте это не quick sort ни разу
3) в сортах квадратичных сортировок не разбираюсь.
Тё>>На собеседовании потребуешь звонок другу скопировать с Википедии? G>Для меня на собеседовании важнее будет если человек расскажет почему быстрая сортировка быстрее сортировки выбором или вставками.
Например, ты показал незнание отличия амортизированной сложности от сложности в худшем случае. О силе рандомтзироыанных алгоритмов тоже ты не в курсах- значит Скиену не читал. О чём вообще с таким архитектом говорить?
G>Прикинь, я умею без википедии код на 20 строк написать. Желаю тебе того же.
Писать бред? Не знаю как там в РФ, но в Австралии дают тест на хакерранке например, и вот бред там просто не засчитается.
Re[9]: Аморально ли требовать алгоритмы на архитектора
Здравствуйте, Олег К., Вы писали:
ОК>Пока что от тебя я не увидел ни строчки кода. Поэтому возникает вполне резонный вопрос. Почему ты считаешь что стоить давать такие вопросы хотя ты сам не можешь написать этот код?
Потому что от таких вопросов у трололо пригорает. Задал вопрос, заметил дымок – до свидания! Отличный алгоритм!
Re[11]: Аморально ли требовать алгоритмы на архитектора
Здравствуйте, Олег К., Вы писали:
ОК>>>Поболее чем три. G>>Помнить нужно именно три. А остальное надо не помнить, а просто написать. Если для тебя проблема написать функцию split по известным требованиям (эти требования таки надо помнить), то лучше вообще программированием не заниматься. ОК>Пардон но почему ты помнишь один алгоритм а не помнишь другой?
Потому что qsort это не столько про сортировку, сколько про рекурсию и "разделяй и властвуй". очень важный пример для навыка построения алгоритмов.
Остальные сортировки мало интересны, так как не дают почти ничего для навыка построения алгоритмов.
ОК>>>>>Если ты такой вундеркинд, напиши еще и shell sort заодно. Для тебя это не должно составить труда. G>>>>К сожалению не помню в чем идея shell sort. первый и последний раз я читал про него лет 15 назад. ОК>>>Ха! То есть, получается, что ты не знаешь стандартные алгоритмы? Ну это согласно питону. G>>С каких пор shellsort стал стандартным? Он массово применяется где-то? Реализован в библиотеках множества языков? Имеет среднее время лучше n*log(n)? Имеет какую-то ценность для построения других алгоритмов? Почему например не timsort?
ОК>Тем не менее его проходят в университетском курсе.
В унверситетском курсе проходят то, что есть у кнута. В издании 2007 года есть timsort
ОК>То что ты его не считаешь стандартным это другой вопрос.
Я ничего не считаю "стандартным" я говорю о том что важно и полезно по моему мнению, а что — не очень.
ОК>В зависимости на кого ты нарвешься, твой интервьюер может иметь совсем иное мнение.
Мне абсолютно пофиг на мнение интервьювера в вакууме.
G>>Быстрая сортировка полезна, так как демонстрирует применение рекурсии и подхода "разделяй и властвуй", а чем так примечательна сортировка шелла? ОК>Еще раз ха! Почитай чем она примечательна и где может использоваться. Если этого нет в вики, то открой книгу.
Почитал, и чем она так примечательна?
Преимущества, описанные в вики, невнятные. Сделать так, чтобы быстрая сортировка, по описанному мной алгоритму, скатилась до o(n^2) — надо еще очень постараться.
Где еще можно применить этот rocket science с подбором d?
Re[9]: Аморально ли требовать алгоритмы на архитектора
Здравствуйте, Олег К., Вы писали:
ОК>Видишь ли, я верю что ты можешь писать код на работе, но в данном случае это был больше вопрос не на написать а на помнишь ли ты как это работает изнутри. Такое быстро забывается после учебы. Поэтому я и отказываюсь верить что ты помнишь быструю сортировку.
Забывается то, что ты не понял. В универе, как и в школе, часто пытаются вбить в голову факты, вместо объяснения принципов.
Чтобы понять принципы построения алгоритмов на основе рекурсии я прочитал немало книг, поэтому для меня не проблема написать быстрою сортировку.
G>void qsort(int[] m, int l, int h)
G>{
G> if(l == h) return; // выход из рекурсии
G> var y = split(m,l,h); // опорный элемент и деление массива
G> qsort(m,l,y); // рекурсия
G> qsort(m,y,h);
G>}
G>
В указанных строках очевидная ошибка. Вообще, конечно, реализацию quick-sort нельзя спрашивать на собеседовании. Можно обсудить только идею, сложности реализации и подобное. Сама реализация "начального уровня" не только относительно сложная, но и вредная. Она создаёт иллюзию работоспособного алгоритма. Вот merge-sort — совсем другое дело. Элементарная реализация, в которой очень сложно ошибиться.
Re[9]: Аморально ли требовать алгоритмы на архитектора
Здравствуйте, Тёмчик, Вы писали:
G>>Проблемы в студию. Тё>1) граничные условия. У тебя переполнение стека может случиться Тё>2) переполнения не случится, ибо в твоем варианте это не quick sort ни разу
Так может или не может, ты определись уже
Тё>3) в сортах квадратичных сортировок не разбираюсь.
Чего?
Тё>Например, ты показал незнание отличия амортизированной сложности от сложности в худшем случае.
Прости, но это ты сейчас показываешь нензание
Тё>О силе рандомтзироыанных алгоритмов тоже ты не в курсах- значит Скиену не читал.
Прикинь, в курсе. Только какое это имеет отношение к разговору?
Тё>О чём вообще с таким архитектом говорить?
По сравнению с тем, кто вообще не бум-бум в алгоритмах, есть о чем.
G>>Прикинь, я умею без википедии код на 20 строк написать. Желаю тебе того же. Тё>Писать бред?
Прежде чем кидаться словами ты свою позицию обоснуй.
Тё>Не знаю как там в РФ, но в Австралии дают тест на хакерранке например, и вот бред там просто не засчитается.
На хакерранке не пишут на бумаге\форуме. Вообще странно сравнивать код на бумаге и код на компьютере. Он пишется с совершенно разными целями.
Здравствуйте, Олег К., Вы писали:
ОК>Первое. Я не считаю правильным просить реализовать стандартные алгоритмы. Достаточно знать что быстрая сортировка есть и в STL и в сишной библиотеке. И второе. Это зависит на кого нарвешься.
А поставлю я тебе минус за незнание стандартной библиотеки. Никто тебе не гарантирует, что в STL есть быстрая сортировка. Про std::sort все знают, что там быстрая сортировка внутри может или вызываться всегда, или в частном случае, или вообще не быть реализованной. Но и функция std::qsort ведёт себя совершенно аналогично, цитирую оттуда:
Despite the name, C++, C, and POSIX standards do not require this function to be implemented using quicksort or make any complexity or stability guarantees.
Так что твои знания в области алгоритмов совсем не достаточны для архитектора.
Re[10]: Аморально ли требовать алгоритмы на архитектора
ОК>>Пока что от тебя я не увидел ни строчки кода. Поэтому возникает вполне резонный вопрос. Почему ты считаешь что стоить давать такие вопросы хотя ты сам не можешь написать этот код?
KP>Потому что от таких вопросов у трололо пригорает. Задал вопрос, заметил дымок – до свидания! Отличный алгоритм!
Пока что ты сам показал неспособность заимплементировать алгоритм.
Re[4]: Аморально ли требовать алгоритмы на архитектора
G> while(i<j && m[i]<x) i++; //находим слава элемент больше опорного
G> while(i<j && m[j]>=x) j--; // находим справа элемент меньше опорного
G>
И совсем не очевидная ошибка.
Допустим, у тебя есть массив [1,1,0,1,1]. Для него x = 0. После прохождения этих циклов while, у тебя будет такая ситуация: i = 0, j = 0. Итог — ничего ни с чем не обменяется. А это, очевидно, некорректно.
Re[12]: Аморально ли требовать алгоритмы на архитектора
G>Потому что qsort это не столько про сортировку, сколько про рекурсию и "разделяй и властвуй". очень важный пример для навыка построения алгоритмов.
Это не только "теоритический" алгоритм но и практический.
G>Остальные сортировки мало интересны, так как не дают почти ничего для навыка построения алгоритмов.
Тебе может быть неинтересны. Кому-то другому интересны и он будет ожидать этого же от тебя. Понимаешь к чему я клоню?
G>Мне абсолютно пофиг на мнение интервьювера в вакууме.
На интервью будет не пофиг.
G>Почитал, и чем она так примечательна?