Re[5]: Аморально ли требовать алгоритмы на архитектора
От: Олег К.  
Дата: 10.04.17 02:49
Оценка:
G>>ЗЫ. ни разу не писал qsort, да и вообще программирую крайне редко.

Тё>qsort грамотно реализовать- нетривиальная задача.


Более того, кажется Сэджвик на нем PhD диссертацию защитил.
Re[9]: Аморально ли требовать алгоритмы на архитектора
От: gandjustas Россия http://blog.gandjustas.ru/
Дата: 10.04.17 02:53
Оценка:
Здравствуйте, Олег К., Вы писали:

ОК>Это не аргумент а опыт.

Не суди всех по себе

ОК>Поболее чем три.

Помнить нужно именно три. А остальное надо не помнить, а просто написать. Если для тебя проблема написать функцию split по известным требованиям (эти требования таки надо помнить), то лучше вообще программированием не заниматься.

ОК>>>Если ты такой вундеркинд, напиши еще и shell sort заодно. Для тебя это не должно составить труда.

G>>К сожалению не помню в чем идея shell sort. первый и последний раз я читал про него лет 15 назад.
ОК>Ха! То есть, получается, что ты не знаешь стандартные алгоритмы? Ну это согласно питону.
С каких пор shellsort стал стандартным? Он массово применяется где-то? Реализован в библиотеках множества языков? Имеет среднее время лучше n*log(n)? Имеет какую-то ценность для построения других алгоритмов? Почему например не timsort?

Быстрая сортировка полезна, так как демонстрирует применение рекурсии и подхода "разделяй и властвуй", а чем так примечательна сортировка шелла?
Re[6]: Аморально ли требовать алгоритмы на архитектора
От: Тёмчик Австралия жж
Дата: 10.04.17 02:53
Оценка:
Здравствуйте, gandjustas, Вы писали:

G>Ты не силен в алгоритмах, так что свои слова стоит доказать


Не силен. Но в твоей дословной кальке с Википедии сходу нашел 2 проблемы. На собеседовании потребуешь звонок другу скопировать с Википедии?

G>>>ЗЫ. ни разу не писал qsort, да и вообще программирую крайне редко.

Тё>>qsort грамотно реализовать- нетривиальная задача.
G>Это не надо делать. надо уметь показать на собеседовании что ты знаешь как это сделать.
Пока что ты показал умение копипасты
Re[6]: Аморально ли требовать алгоритмы на архитектора
От: Олег К.  
Дата: 10.04.17 02:56
Оценка: -1
Тё>>Ты вроде qsort предлагал, а код твой сортирует пузырьком.
G>Ты не силен в алгоритмах, так что свои слова стоит доказать

Что значит не силен в алгоритмах? Помнить их все наизусть? Ну так и ты их все не помнишь, о чем ты сам сейчас признался.

G>>>ЗЫ. ни разу не писал qsort, да и вообще программирую крайне редко.

Тё>>qsort грамотно реализовать- нетривиальная задача.
G>Это не надо делать. надо уметь показать на собеседовании что ты знаешь как это сделать.

Первое. Я не считаю правильным просить реализовать стандартные алгоритмы. Достаточно знать что быстрая сортировка есть и в STL и в сишной библиотеке. И второе. Это зависит на кого нарвешься.
Re[7]: Аморально ли требовать алгоритмы на архитектора
От: gandjustas Россия http://blog.gandjustas.ru/
Дата: 10.04.17 02:58
Оценка:
Здравствуйте, Тёмчик, Вы писали:

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


G>>Ты не силен в алгоритмах, так что свои слова стоит доказать


Тё>Не силен. Но в твоей дословной кальке с Википедии сходу нашел 2 проблемы.

Проблемы в студию.

Тё>На собеседовании потребуешь звонок другу скопировать с Википедии?

Для меня на собеседовании важнее будет если человек расскажет почему быстрая сортировка быстрее сортировки выбором или вставками.

G>>>>ЗЫ. ни разу не писал qsort, да и вообще программирую крайне редко.

Тё>>>qsort грамотно реализовать- нетривиальная задача.
G>>Это не надо делать. надо уметь показать на собеседовании что ты знаешь как это сделать.
Тё>Пока что ты показал умение копипасты
Еще один...
Я не открывал википедию если что.

Прикинь, я умею без википедии код на 20 строк написать. Желаю тебе того же.
Re[10]: Аморально ли требовать алгоритмы на архитектора
От: Олег К.  
Дата: 10.04.17 03:05
Оценка:
ОК>>Это не аргумент а опыт.
G>Не суди всех по себе

Не сужу. Я прекрасно осведомлен кто работает и какие задачи решаются в индустрии.

ОК>>Поболее чем три.

G>Помнить нужно именно три. А остальное надо не помнить, а просто написать. Если для тебя проблема написать функцию split по известным требованиям (эти требования таки надо помнить), то лучше вообще программированием не заниматься.


Пардон но почему ты помнишь один алгоритм а не помнишь другой?

ОК>>>>Если ты такой вундеркинд, напиши еще и shell sort заодно. Для тебя это не должно составить труда.

G>>>К сожалению не помню в чем идея shell sort. первый и последний раз я читал про него лет 15 назад.
ОК>>Ха! То есть, получается, что ты не знаешь стандартные алгоритмы? Ну это согласно питону.
G>С каких пор shellsort стал стандартным? Он массово применяется где-то? Реализован в библиотеках множества языков? Имеет среднее время лучше n*log(n)? Имеет какую-то ценность для построения других алгоритмов? Почему например не timsort?

Тем не менее его проходят в университетском курсе. То что ты его не считаешь стандартным это другой вопрос. В зависимости на кого ты нарвешься, твой интервьюер может иметь совсем иное мнение.

G>Быстрая сортировка полезна, так как демонстрирует применение рекурсии и подхода "разделяй и властвуй", а чем так примечательна сортировка шелла?


Еще раз ха! Почитай чем она примечательна и где может использоваться. Если этого нет в вики, то открой книгу.
Re[8]: Аморально ли требовать алгоритмы на архитектора
От: Олег К.  
Дата: 10.04.17 03:12
Оценка:
Тё>>Пока что ты показал умение копипасты
G> Еще один...
G>Я не открывал википедию если что.

G>Прикинь, я умею без википедии код на 20 строк написать. Желаю тебе того же.


Видишь ли, я верю что ты можешь писать код на работе, но в данном случае это был больше вопрос не на написать а на помнишь ли ты как это работает изнутри. Такое быстро забывается после учебы. Поэтому я и отказываюсь верить что ты помнишь быструю сортировку.
Re[7]: Аморально ли требовать алгоритмы на архитектора
От: gandjustas Россия http://blog.gandjustas.ru/
Дата: 10.04.17 03:12
Оценка:
Здравствуйте, Олег К., Вы писали:

Ты отвечаешь на коммент другому человеку.

Тё>>>Ты вроде qsort предлагал, а код твой сортирует пузырьком.

G>>Ты не силен в алгоритмах, так что свои слова стоит доказать

ОК>Что значит не силен в алгоритмах?

Если челоек считает что алгоритмы не надо спрашивать на собеседовании значит что он и ни не силен. Был бы силен — не писал бы на форуме.

ОК>Помнить их все наизусть? Ну так и ты их все не помнишь, о чем ты сам сейчас признался.

Я не говорил что надо помнить, да и вообще речи не шло про то, что надо наизусть помнить все алгоритмы сортировки. Это ты сам придумал.

G>>>>ЗЫ. ни разу не писал qsort, да и вообще программирую крайне редко.

Тё>>>qsort грамотно реализовать- нетривиальная задача.
G>>Это не надо делать. надо уметь показать на собеседовании что ты знаешь как это сделать.

ОК>Первое. Я не считаю правильным просить реализовать стандартные алгоритмы.

Никто не говорил что надо помнить стандартные алгоритмы.

ОК>Достаточно знать что быстрая сортировка есть и в STL и в сишной библиотеке.

Недостаточно. Надо уметь самому конструировать алгоритмы, если в стандартной библиотеке подходящих нет.

У меня был случай — надо было написать функцию, которая превращает IEnumerable<T> в IEnumerable<IEnumerable<T>>, нарезая входную последовательность на блоки по определенному условию, зависящему от нескольких предыдущих элементов.
Я потом эту задачу на собеседовании давал. Код менее чем на 20 строк. Из 10 кандидатов справилось два. При этом все прекрасно знали linq, yield, как устроен IEnumerable и то, что енумератор — value type.
Re[8]: Аморально ли требовать алгоритмы на архитектора
От: Тёмчик Австралия жж
Дата: 10.04.17 03:19
Оценка:
Здравствуйте, gandjustas, Вы писали:

G>>>Ты не силен в алгоритмах, так что свои слова стоит доказать


Тё>>Не силен. Но в твоей дословной кальке с Википедии сходу нашел 2 проблемы.

G>Проблемы в студию.
1) граничные условия. У тебя переполнение стека может случиться
2) переполнения не случится, ибо в твоем варианте это не quick sort ни разу
3) в сортах квадратичных сортировок не разбираюсь.

Тё>>На собеседовании потребуешь звонок другу скопировать с Википедии?

G>Для меня на собеседовании важнее будет если человек расскажет почему быстрая сортировка быстрее сортировки выбором или вставками.
Например, ты показал незнание отличия амортизированной сложности от сложности в худшем случае. О силе рандомтзироыанных алгоритмов тоже ты не в курсах- значит Скиену не читал. О чём вообще с таким архитектом говорить?

G>Прикинь, я умею без википедии код на 20 строк написать. Желаю тебе того же.

Писать бред? Не знаю как там в РФ, но в Австралии дают тест на хакерранке например, и вот бред там просто не засчитается.
Re[9]: Аморально ли требовать алгоритмы на архитектора
От: kaa.python Ниоткуда РСДН профессионально мёртв и завален ватой.
Дата: 10.04.17 03:31
Оценка:
Здравствуйте, Олег К., Вы писали:

ОК>Пока что от тебя я не увидел ни строчки кода. Поэтому возникает вполне резонный вопрос. Почему ты считаешь что стоить давать такие вопросы хотя ты сам не можешь написать этот код?


Потому что от таких вопросов у трололо пригорает. Задал вопрос, заметил дымок – до свидания! Отличный алгоритм!
Re[11]: Аморально ли требовать алгоритмы на архитектора
От: gandjustas Россия http://blog.gandjustas.ru/
Дата: 10.04.17 03:34
Оценка: -2
Здравствуйте, Олег К., Вы писали:

ОК>>>Поболее чем три.

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]: Аморально ли требовать алгоритмы на архитектора
От: gandjustas Россия http://blog.gandjustas.ru/
Дата: 10.04.17 03:43
Оценка: -1
Здравствуйте, Олег К., Вы писали:

ОК>Видишь ли, я верю что ты можешь писать код на работе, но в данном случае это был больше вопрос не на написать а на помнишь ли ты как это работает изнутри. Такое быстро забывается после учебы. Поэтому я и отказываюсь верить что ты помнишь быструю сортировку.


Забывается то, что ты не понял. В универе, как и в школе, часто пытаются вбить в голову факты, вместо объяснения принципов.
Чтобы понять принципы построения алгоритмов на основе рекурсии я прочитал немало книг, поэтому для меня не проблема написать быстрою сортировку.
Отредактировано 10.04.2017 4:22 kaa.python . Предыдущая версия .
Re[4]: Аморально ли требовать алгоритмы на архитектора
От: De-Bill  
Дата: 10.04.17 03:51
Оценка: +3
G>
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]: Аморально ли требовать алгоритмы на архитектора
От: gandjustas Россия http://blog.gandjustas.ru/
Дата: 10.04.17 03:55
Оценка:
Здравствуйте, Тёмчик, Вы писали:

G>>Проблемы в студию.

Тё>1) граничные условия. У тебя переполнение стека может случиться
Тё>2) переполнения не случится, ибо в твоем варианте это не quick sort ни разу
Так может или не может, ты определись уже


Тё>3) в сортах квадратичных сортировок не разбираюсь.

Чего?

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

Прости, но это ты сейчас показываешь нензание

Тё>О силе рандомтзироыанных алгоритмов тоже ты не в курсах- значит Скиену не читал.

Прикинь, в курсе. Только какое это имеет отношение к разговору?

Тё>О чём вообще с таким архитектом говорить?

По сравнению с тем, кто вообще не бум-бум в алгоритмах, есть о чем.


G>>Прикинь, я умею без википедии код на 20 строк написать. Желаю тебе того же.

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


Тё>Не знаю как там в РФ, но в Австралии дают тест на хакерранке например, и вот бред там просто не засчитается.

На хакерранке не пишут на бумаге\форуме. Вообще странно сравнивать код на бумаге и код на компьютере. Он пишется с совершенно разными целями.
Отредактировано 10.04.2017 4:21 kaa.python . Предыдущая версия .
Re[7]: Аморально ли требовать алгоритмы на архитектора
От: Nuzhny Россия https://github.com/Nuzhny007
Дата: 10.04.17 04:13
Оценка:
Здравствуйте, Олег К., Вы писали:

ОК>Первое. Я не считаю правильным просить реализовать стандартные алгоритмы. Достаточно знать что быстрая сортировка есть и в 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]: Аморально ли требовать алгоритмы на архитектора
От: Олег К.  
Дата: 10.04.17 04:13
Оценка:
ОК>>Пока что от тебя я не увидел ни строчки кода. Поэтому возникает вполне резонный вопрос. Почему ты считаешь что стоить давать такие вопросы хотя ты сам не можешь написать этот код?

KP>Потому что от таких вопросов у трололо пригорает. Задал вопрос, заметил дымок – до свидания! Отличный алгоритм!


Пока что ты сам показал неспособность заимплементировать алгоритм.
Re[4]: Аморально ли требовать алгоритмы на архитектора
От: De-Bill  
Дата: 10.04.17 04:13
Оценка:
G>
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]: Аморально ли требовать алгоритмы на архитектора
От: Олег К.  
Дата: 10.04.17 04:18
Оценка:
G>Потому что qsort это не столько про сортировку, сколько про рекурсию и "разделяй и властвуй". очень важный пример для навыка построения алгоритмов.

Это не только "теоритический" алгоритм но и практический.

G>Остальные сортировки мало интересны, так как не дают почти ничего для навыка построения алгоритмов.


Тебе может быть неинтересны. Кому-то другому интересны и он будет ожидать этого же от тебя. Понимаешь к чему я клоню?

G>Мне абсолютно пофиг на мнение интервьювера в вакууме.


На интервью будет не пофиг.

G>Почитал, и чем она так примечательна?


Значит не прочитал. Читай у Сэджвика.
Отредактировано 10.04.2017 4:21 kaa.python . Предыдущая версия . Еще …
Отредактировано 10.04.2017 4:21 kaa.python . Предыдущая версия .
Re[5]: Аморально ли требовать алгоритмы на архитектора
От: gandjustas Россия http://blog.gandjustas.ru/
Дата: 10.04.17 04:19
Оценка:
Здравствуйте, De-Bill, Вы писали:

DB>В указанных строках очевидная ошибка.

Запустил в студии.
Это не единственная ошибка

Тем не менее ты первый кто заметил.
Re[4]: Аморально ли требовать алгоритмы на архитектора
От: De-Bill  
Дата: 10.04.17 04:21
Оценка:
G>
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>


И ещё момент. Когда ты поправишь первую ошибку, начнёт ломаться здесь.
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.