Аморально ли требовать алгоритмы на архитектора - О работе

Тё>>Аморально ли проверять знание алгоритмов, если на рассматриваемую позицию человек не будет их писать? Ведь задача архитектора- иметь высокоуровневое видение продукта, каким он будет и выбор, какие фреймворки использовать.

KP>Аморально не знать основных алгоритмов и структур данных если ты позиционируешь себя как архитектор

Ну-ка, ну-ка, давай без понтов, а? Напиши-ка, никуда не заглядывая, обычный Quick Sort. А заодно расскажи все о его run-time complexity!

Что? Не знаешь?

Аморально, однако.

Здравствуйте, Олег К., Вы писали:

ОК>Ну-ка, ну-ка, давай без понтов, а? Напиши-ка, никуда не заглядывая, обычный Quick Sort. А заодно расскажи все о его run-time complexity!
ОК>Что? Не знаешь?

Аморально, однако.

По твоему это сложная задача?

Ну я теперь понимаю почему ты так факелом полыхаешь когда речь заходит о вопросах отличных от "расскажите о ваших предыдущих проектах".

Здравствуйте, Олег К., Вы писали:

Тё>>>Аморально ли проверять знание алгоритмов, если на рассматриваемую позицию человек не будет их писать? Ведь задача архитектора- иметь высокоуровневое видение продукта, каким он будет и выбор, какие фреймворки использовать.

KP>>Аморально не знать основных алгоритмов и структур данных если ты позиционируешь себя как архитектор

ОК>Ну-ка, ну-ка, давай без понтов, а? Напиши-ка, никуда не заглядывая, обычный Quick Sort. А заодно расскажи все о его run-time complexity!

А чего в этом сложного?
Псевдокод алгоритма:

1. Выбрать опорный элемент
2. Поделить массив на два -  в одном все элементы больше опорного, во втором меньше
3. Рекурсивно запустить алгоритм для двух половин, полученных на шаге два

Теперь пишем:

void qsort(int[] m, int l, int h)
{
    if(l == h) return;      // выход из рекурсии
    var y = split(m,l,h);   // опорный элемент и деление массива 
    qsort(m,l,y);           // рекурсия
    qsort(m,y,h);
}

самая нетривиальная часть — деление массива пополам
идея простая — идем с начал и кона по массиву и меняем элементы местами если надо

int split(int[] m, int l, int h)
{
    var i = l;
    var j = h;
    var x = m[(l+m)/2];     // опорный элемент

    while(i<j)  // идем с двух сторон массива
    {
        while(i<j && m[i]<x) i++;  //находим слава элемент больше опорного
        while(i<j && m[j]>=x) j--; // находим справа элемент меньше опорного
        if(i<j) // обмениваем найденные
        {
           var t = m[i];
           m[i] = m[j];
           m[j] = t;
           i++;
           j--;
        }
    }
    return i;
}

Надо потестить немного.

Что касается асимптотической сложности, то тоже ничего сложного.
Количество сравнений на каждом шаге в среднем и лучшем случае равно n/2.
o(n) = n/2 + 2*o(n/2).
Рекурсивно подставляя получаем o(n) = n + n + ... + n/2. Причем количество слагаемых равно log2(n)
Итого o(n) = n*log(n)

ОК>Что? Не знаешь?

Аморально, однако.
Знание алгоритмов это не запоминание, а умение комбинировать несколько базовых подходов.
Незнание базовых подходов и неумение комбинировать — аморально, да.

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

Смотря каких алгоритмов. Имхо можно простую задачку дать минут на 5-20 (при этом если нужно оставлять собеседумоего одного, чтобы он спокойно порешал) чисто проверить что мозги не затекли.

ОК>>Ну-ка, ну-ка, давай без понтов, а? Напиши-ка, никуда не заглядывая, обычный Quick Sort. А заодно расскажи все о его run-time complexity!
ОК>>Что? Не знаешь?

Аморально, однако.

KP>По твоему это сложная задача?

Ну я теперь понимаю почему ты так факелом полыхаешь когда речь заходит о вопросах отличных от "расскажите о ваших предыдущих проектах".

Где код?

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

Это ты сейчас в википедию заглянул?

Здравствуйте, Олег К., Вы писали:

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

ОК>Это ты сейчас в википедию заглянул?

Нет

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

G>Здравствуйте, Олег К., Вы писали:

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

ОК>>Это ты сейчас в википедию заглянул?

G>Нет

Я не верю тебе но допустим ты хранишь столько хлама у себя в голове. Если ты такой вундеркинд, напиши еще и shell sort заодно. Для тебя это не должно составить труда.

Здравствуйте, Олег К., Вы писали:

ОК>Где код?

А зачем мне приводить код такому трололо как ты? Ниже тебе дали код и ты сходу обвинил в использовании Википедии, что было ожидаемо. Если тебе человек напишет "и shell sort заодно", ты найдешь еще к чему придраться. Ты очень предсказуемый

Здравствуйте, Олег К., Вы писали:

ОК>>>Это ты сейчас в википедию заглянул?

G>>Нет

ОК>Я не верю тебе

Аргумент!

ОК>но допустим ты хранишь столько хлама у себя в голове.
Сколько хлама? Три строки псевдокода?

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

ОК>>Где код?

KP>А зачем мне приводить код такому трололо как ты?

Ну ясно. Звиздеть не мешки ворочать.

KP>Ниже тебе дали код и ты сходу обвинил в использовании Википедии, что было ожидаемо. Если тебе человек напишет "и shell sort заодно", ты найдешь еще к чему придраться. Ты очень предсказуемый

Первое. Я не верю что ты помнишь как работает Quick sort внутри после 15 лет работы если ты только недавно не перечитал книжку по алгоритмам. Второе. Я продемонстрировал что много ума не надо опустить кандидата. Именно такой подход и практикуют экзаменаторы вроде тебя. Достаточно делать линейный поиск, но если хочешь, я могу выбрать алгоритм посложнее специально ради тебя. Чтобы опустить тебя наверняка. Для этого тоже много ума не надо. Третье. Перечитай фразу выше.

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

G>А чего в этом сложного?
G>Псевдокод алгоритма:
G>

G>1. Выбрать опорный элемент
G>2. Поделить массив на два -  в одном все элементы больше опорного, во втором меньше
G>3. Рекурсивно запустить алгоритм для двух половин, полученных на шаге два
G>

В случае quick sort ты можешь получить вырожденный случай и глубину рекурсии N. Не проверил граничных условий — провалил задание.

G>самая нетривиальная часть — деление массива пополам
G>идея простая — идем с начал и кона по массиву и меняем элементы местами если надо
G>

G>int split(int[] m, int l, int h)
G>{
G>    var i = l;
G>    var j = h;
G>    var x = m[(l+m)/2];     // опорный элемент

G>    while(i<j)  // идем с двух сторон массива
G>    {
G>        while(i<j && m[i]<x) i++;  //находим слава элемент больше опорного
G>        while(i<j && m[j]>=x) j--; // находим справа элемент меньше опорного
G>        if(i<j) // обмениваем найденные
G>        {
G>           var t = m[i];
G>           m[i] = m[j];
G>           m[j] = t;
G>           i++;
G>           j--;
G>        }
G>    }
G>    return i;
G>}
G>

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

G>Надо потестить немного.
Ага.

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

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

Здравствуйте, Олег К., Вы писали:

ОК>Первое. Я не верю что ты помнишь как работает Quick sort внутри после 15 лет работы если ты только недавно не перечитал книжку по алгоритмам. Второе. Я продемонстрировал что много ума не надо опустить кандидата. Именно такой подход и практикуют экзаменаторы вроде тебя. Достаточно делать линейный поиск, но если хочешь, я могу выбрать алгоритм посложнее специально ради тебя. Чтобы опустить тебя наверняка. Для этого тоже много ума не надо. Третье. Перечитай фразу выше.

Ну, раз уж алгоритмические вопросы заставляют таким факелом полыхать кандидатов вроде тебя, такие вопросы просто необходимо задавать для грамотного отбора!

ОК>>>>Это ты сейчас в википедию заглянул?

G>>>Нет

ОК>>Я не верю тебе
G>

Аргумент!

Это не аргумент а опыт. К сожалению здесь невозможно проверить так ли ты силен без литературы.

ОК>>но допустим ты хранишь столько хлама у себя в голове.
G>Сколько хлама? Три строки псевдокода?

Поболее чем три.

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

Ха! То есть, получается, что ты не знаешь стандартные алгоритмы?

Ну это согласно питону.

.Здравствуйте, Тёмчик, Вы писали:

Тё>В случае quick sort ты можешь получить вырожденный случай и глубину рекурсии N. Не проверил граничных условий — провалил задание.
Если что ты всегда можешь его получить, независимо от того, как ты напишешь Быстрая сортировка в худшем случае имеет O(n^2)

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

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

ОК>>Первое. Я не верю что ты помнишь как работает Quick sort внутри после 15 лет работы если ты только недавно не перечитал книжку по алгоритмам. Второе. Я продемонстрировал что много ума не надо опустить кандидата. Именно такой подход и практикуют экзаменаторы вроде тебя. Достаточно делать линейный поиск, но если хочешь, я могу выбрать алгоритм посложнее специально ради тебя. Чтобы опустить тебя наверняка. Для этого тоже много ума не надо. Третье. Перечитай фразу выше.

KP>Ну, раз уж алгоритмические вопросы заставляют таким факелом полыхать кандидатов вроде тебя, такие вопросы просто необходимо задавать для грамотного отбора!

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

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

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

Более того, кажется Сэджвик на нем PhD диссертацию защитил.

Здравствуйте, Олег К., Вы писали:

ОК>Это не аргумент а опыт.
Не суди всех по себе

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

ОК>>>Если ты такой вундеркинд, напиши еще и shell sort заодно. Для тебя это не должно составить труда.
G>>К сожалению не помню в чем идея shell sort. первый и последний раз я читал про него лет 15 назад.
ОК>Ха! То есть, получается, что ты не знаешь стандартные алгоритмы?

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

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

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

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

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

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

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

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

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

Первое. Я не считаю правильным просить реализовать стандартные алгоритмы. Достаточно знать что быстрая сортировка есть и в STL и в сишной библиотеке. И второе. Это зависит на кого нарвешься.

Здравствуйте, Тёмчик, Вы писали:

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

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

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

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

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

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

Еще один...
Я не открывал википедию если что.

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

ОК>>Это не аргумент а опыт.
G>Не суди всех по себе

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

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

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

ОК>>>>Если ты такой вундеркинд, напиши еще и shell sort заодно. Для тебя это не должно составить труда.
G>>>К сожалению не помню в чем идея shell sort. первый и последний раз я читал про него лет 15 назад.
ОК>>Ха! То есть, получается, что ты не знаешь стандартные алгоритмы?

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

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

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

Еще раз ха! Почитай чем она примечательна и где может использоваться. Если этого нет в вики, то открой книгу.

Тё>>Пока что ты показал умение копипасты

Еще один...
G>Я не открывал википедию если что.

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

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

Здравствуйте, Олег К., Вы писали:

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

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

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

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

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

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

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

У меня был случай — надо было написать функцию, которая превращает IEnumerable<T> в IEnumerable<IEnumerable<T>>, нарезая входную последовательность на блоки по определенному условию, зависящему от нескольких предыдущих элементов.
Я потом эту задачу на собеседовании давал. Код менее чем на 20 строк. Из 10 кандидатов справилось два. При этом все прекрасно знали linq, yield, как устроен IEnumerable и то, что енумератор — value type.

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

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

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

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

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

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

Здравствуйте, Олег К., Вы писали:

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

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

Здравствуйте, Олег К., Вы писали:

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

ОК>>>>>Если ты такой вундеркинд, напиши еще и shell sort заодно. Для тебя это не должно составить труда.
G>>>>К сожалению не помню в чем идея shell sort. первый и последний раз я читал про него лет 15 назад.
ОК>>>Ха! То есть, получается, что ты не знаешь стандартные алгоритмы?

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

ОК>Тем не менее его проходят в университетском курсе.
В унверситетском курсе проходят то, что есть у кнута. В издании 2007 года есть timsort

ОК>То что ты его не считаешь стандартным это другой вопрос.
Я ничего не считаю "стандартным" я говорю о том что важно и полезно по моему мнению, а что — не очень.

ОК>В зависимости на кого ты нарвешься, твой интервьюер может иметь совсем иное мнение.
Мне абсолютно пофиг на мнение интервьювера в вакууме.

G>>Быстрая сортировка полезна, так как демонстрирует применение рекурсии и подхода "разделяй и властвуй", а чем так примечательна сортировка шелла?
ОК>Еще раз ха! Почитай чем она примечательна и где может использоваться. Если этого нет в вики, то открой книгу.
Почитал, и чем она так примечательна?
Преимущества, описанные в вики, невнятные. Сделать так, чтобы быстрая сортировка, по описанному мной алгоритму, скатилась до o(n^2) — надо еще очень постараться.
Где еще можно применить этот rocket science с подбором d?

Здравствуйте, Олег К., Вы писали:

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

Забывается то, что ты не понял. В универе, как и в школе, часто пытаются вбить в голову факты, вместо объяснения принципов.
Чтобы понять принципы построения алгоритмов на основе рекурсии я прочитал немало книг, поэтому для меня не проблема написать быстрою сортировку.

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 — совсем другое дело. Элементарная реализация, в которой очень сложно ошибиться.

Здравствуйте, Тёмчик, Вы писали:

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.

Так что твои знания в области алгоритмов совсем не достаточны для архитектора.

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

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

Пока что ты сам показал неспособность заимплементировать алгоритм.

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. Итог — ничего ни с чем не обменяется. А это, очевидно, некорректно.

G>Потому что qsort это не столько про сортировку, сколько про рекурсию и "разделяй и властвуй". очень важный пример для навыка построения алгоритмов.

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

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

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

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

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

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

Значит не прочитал. Читай у Сэджвика.

Здравствуйте, De-Bill, Вы писали:

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

Тем не менее ты первый кто заметил.

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>

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

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

G>Забывается то, что ты не понял. В универе, как и в школе, часто пытаются вбить в голову факты, вместо объяснения принципов.
G>Чтобы понять принципы построения алгоритмов на основе рекурсии я прочитал немало книг, поэтому для меня не проблема написать быстрою сортировку.

Забывается то с чем дела не имеешь напостоянку.

ОК>>Что значит не силен в алгоритмах?
G>Если челоек считает что алгоритмы не надо спрашивать на собеседовании значит что он и ни не силен. Был бы силен — не писал бы на форуме.

Ты, чувак, видишь разницу между знать что есть такие-то структуры данных и такие-то алгоритмы версус того чтобы требовать их имплементацию?

G>У меня был случай — надо было написать функцию, которая превращает IEnumerable<T> в IEnumerable<IEnumerable<T>>, нарезая входную последовательность на блоки по определенному условию, зависящему от нескольких предыдущих элементов.
G>Я потом эту задачу на собеседовании давал. Код менее чем на 20 строк. Из 10 кандидатов справилось два. При этом все прекрасно знали linq, yield, как устроен IEnumerable и то, что енумератор — value type.

Что-то ты переусложняешь все.

N>А поставлю я тебе минус за незнание стандартной библиотеки. Никто тебе не гарантирует, что в STL есть быстрая сортировка. Про std::sort все знают, что там быстрая сортировка внутри может или вызываться всегда, или в частном случае, или вообще не быть реализованной. Но и функция std::qsort ведёт себя совершенно аналогично, цитирую оттуда:
N>

N>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.

Да хоть десять, чувак! Пойнт который ты не понял это то, что ты будешь использоваться сишный qsort() или std::sort<>() как бы ты тут не рассуждал об алгоритмах сортировки.

То чем занимаешься ты называется буквоедство. В реальном коде нужно использовать стандартную библиотеку и понимать, что автор в них сделал разумные вещи (а не какую-нибудь пузырьковую сортировку). Все!

N>Так что твои знания в области алгоритмов совсем не достаточны для архитектора.

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

Знания-то надо применить!

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

Да это мелочи. Разумеется, дай ему время, спокойную обстановку, компьютер и литературу, и он сделает все правильно.

Тут вопрос в другом. Помнит он этот квиксорт как он говорит или все-таки полез в википедию?

Ну и еще тут один момент. Сэджвик защитил диссертацию по квиксорту, а тут некоторые товарищи утверждают что напишут код слету да еще и на интервью. Поражаюсь ихней самоуверенности.

Здравствуйте, Олег К., Вы писали:

ОК>Да хоть десять, чувак! Пойнт который ты не понял это то, что ты будешь использоваться сишный qsort() или std::sort<>() как бы ты тут не рассуждал об алгоритмах сортировки.
ОК>То чем занимаешься ты называется буквоедство. В реальном коде нужно использовать стандартную библиотеку и понимать, что автор в них сделал разумные вещи (а не какую-нибудь пузырьковую сортировку). Все!

Не буквоедство. Я буду использовать именно то, что мне лучше подходит в данный момент.

N>>Так что твои знания в области алгоритмов совсем не достаточны для архитектора.
ОК>Ну ясно, в общем. Ты, как я понял, будешь городить свою сортировку вместо библиотечной.

Знания-то надо применить!

Ничего тебе не ясно. Я буду использовать подходящий алгоритм. А знать, что скрывается за стандартными сортам всё равно надо, ведь всегда могут попасться данные, которые могут сильно замедлить ту же быструю сортировку. Вот невежда и не будет использовать тот же qsort. Если же он будет знать, что за ним скрывается, то и проблем не будет. Так что в архитекторы ты точно не годишься.
Простому кодеру пофиг — использует то, что есть.

Здравствуйте, Nuzhny, Вы писали:

N>Ничего тебе не ясно. Я буду использовать подходящий алгоритм. А знать, что скрывается за стандартными сортам всё равно надо, ведь всегда могут попасться данные, которые могут сильно замедлить ту же быструю сортировку. Вот невежда и не будет использовать тот же qsort. Если же он будет знать, что за ним скрывается, то и проблем не будет. Так что в архитекторы ты точно не годишься.
N>Простому кодеру пофиг — использует то, что есть.
И будешь ты его использовать, разумеется, сразу, а не потом, когда выяснишь, что твой qsort узкое место в производительности...

ОК>>Да хоть десять, чувак! Пойнт который ты не понял это то, что ты будешь использоваться сишный qsort() или std::sort<>() как бы ты тут не рассуждал об алгоритмах сортировки.
ОК>>То чем занимаешься ты называется буквоедство. В реальном коде нужно использовать стандартную библиотеку и понимать, что автор в них сделал разумные вещи (а не какую-нибудь пузырьковую сортировку). Все!

N>Не буквоедство. Я буду использовать именно то, что мне лучше подходит в данный момент.

То есть ты все-таки пишешь свою версию сортировки, ака изобретение велосипеда, вместо того чтобы использовать стандартную функцию?

N>>>Так что твои знания в области алгоритмов совсем не достаточны для архитектора.
ОК>>Ну ясно, в общем. Ты, как я понял, будешь городить свою сортировку вместо библиотечной.

Знания-то надо применить!

N>Ничего тебе не ясно. Я буду использовать подходящий алгоритм. А знать, что скрывается за стандартными сортам всё равно надо, ведь всегда могут попасться данные, которые могут сильно замедлить ту же быструю сортировку. Вот невежда и не будет использовать тот же qsort. Если же он будет знать, что за ним скрывается, то и проблем не будет. Так что в архитекторы ты точно не годишься.
N>Простому кодеру пофиг — использует то, что есть.

Ты, чувак, теоретизируешь или ты уже писал свои функции сортировки вместо того чтобы использовать в коде стандартную функцию в нужный момент?

В общем, как ни крути тут, либо ты фантазер либо ты мега-архитектор.

N>Ничего тебе не ясно. Я буду использовать подходящий алгоритм. А знать, что скрывается за стандартными сортам всё равно надо, ведь всегда могут попасться данные, которые могут сильно замедлить ту же быструю сортировку.

Могут и попасться. Наверняка, это случается один раз в триллион лет. Естественно, несмотря на то, что стандарт библиотеки не гарантирует хорошую реализацию quick-sort, все часто используемые реализации библиотеки имеют хорошую реализацию. И не использовать этот библиотечный метод — это самого себя перемудрить.

N>>Ничего тебе не ясно. Я буду использовать подходящий алгоритм. А знать, что скрывается за стандартными сортам всё равно надо, ведь всегда могут попасться данные, которые могут сильно замедлить ту же быструю сортировку.

DB>Могут и попасться. Наверняка, это случается один раз в триллион лет. Естественно, несмотря на то, что стандарт библиотеки не гарантирует хорошую реализацию quick-sort, все часто используемые реализации библиотеки имеют хорошую реализацию. И не использовать этот библиотечный метод — это самого себя перемудрить.

Да он фантазирует тут. Разумеется он будет использовать стандартную функцию.

ОК>Да он фантазирует тут. Разумеется он будет использовать стандартную функцию.

Здесь скорее проблема в том, что плохое знание зачастую хуже незнания. Та же быстрая сортировка. Кто не знает ничего, будет использовать библиотечную реализацию и никогда не будет иметь никаких проблем. Тот, кто знает тему плохо, будет считать, что существую данные, на которых библиотечная реализация qSort работает медленно и для критичных моментов будет реализовывать какой-то велосипед, который наверняка окажется ещё медленнее и ещё багованнее.

Здравствуйте, Олег К., Вы писали:

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

Да однозначно! Вне всяких сомнений! Еще пальнешь факелом?

Здравствуйте, Олег К., Вы писали:

ОК>То есть ты все-таки пишешь свою версию сортировки, ака изобретение велосипеда, вместо того чтобы использовать стандартную функцию?

Я не буду использовать свою, практически 100%, что найду уже существующую реализацию необходимого. Также как с аллокаторами, например.

ОК>Ты, чувак, теоретизируешь или ты уже писал свои функции сортировки вместо того чтобы использовать в коде стандартную функцию в нужный момент?

ОК>В общем, как ни крути тут, либо ты фантазер либо ты мега-архитектор.

Не писал, но сторонние использовал. Как раз потому, что знал, что внутри стандартной сортировки была не быстрая. Ты хоть в исходники той же std::sort заглядывал?

Здравствуйте, De-Bill, Вы писали:

DB>Могут и попасться. Наверняка, это случается один раз в триллион лет. Естественно, несмотря на то, что стандарт библиотеки не гарантирует хорошую реализацию quick-sort, все часто используемые реализации библиотеки имеют хорошую реализацию. И не использовать этот библиотечный метод — это самого себя перемудрить.

Я как раз говорю, что для твоих данных при вызове std::sort может вызываться не быстрая сортировка, а другая. НИКТО не говорит, что в stl используется быстрая сортировка, по факту так ЧАСТО и происходит. Это просто функция-диспетчер, которая вызывает один из алгоритмов, в зависимости от своих внутренних соображений. Но для конкретных данных может быть больше пригоден другой. Вот об этом я и говорю, что надо знать устройство stl и то, как работают сортировки.
С другой стороны, всегда можно выбирать между вариантами: std::list + std::list::sort, std::vector + std::sort, std::map, std::unordered_map. И этот выбор можно и нужно делать до того, как писать код.

Здравствуйте, UVV, Вы писали:

UVV>И будешь ты его использовать, разумеется, сразу, а не потом, когда выяснишь, что твой qsort узкое место в производительности...

Может быть и да в том момент, когда делаю выбор между, например std::map и отсортированным вектором с поиском по нему. Почему нет?

ОК>>То есть ты все-таки пишешь свою версию сортировки, ака изобретение велосипеда, вместо того чтобы использовать стандартную функцию?

N>Я не буду использовать свою, практически 100%, что найду уже существующую реализацию необходимого. Также как с аллокаторами, например.

Ты заканчивай предложения точками. Непонятно порой читать что к чему.

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

ОК>>Ты, чувак, теоретизируешь или ты уже писал свои функции сортировки вместо того чтобы использовать в коде стандартную функцию в нужный момент?

ОК>>В общем, как ни крути тут, либо ты фантазер либо ты мега-архитектор.

N>Не писал, но сторонние использовал. Как раз потому, что знал, что внутри стандартной сортировки была не быстрая. Ты хоть в исходники той же std::sort заглядывал?

Заглядывал и что? Сколько ты процентов сэкономил используя нестандартную функцию?

Или это все делалось ради одной десятой наносекунды?

UVV>>И будешь ты его использовать, разумеется, сразу, а не потом, когда выяснишь, что твой qsort узкое место в производительности...

N>Может быть и да в том момент, когда делаю выбор между, например std::map и отсортированным вектором с поиском по нему. Почему нет?

Это уже другой сценарий! Сравни: выбор между стандартными контейнарами и алгоритмом версус сказать что стандартный алгоритм плохо реализован и написать свой.

Плохой из тебя архитектор если ты разницу не видишь.

DB>>Могут и попасться. Наверняка, это случается один раз в триллион лет. Естественно, несмотря на то, что стандарт библиотеки не гарантирует хорошую реализацию quick-sort, все часто используемые реализации библиотеки имеют хорошую реализацию. И не использовать этот библиотечный метод — это самого себя перемудрить.

N>Я как раз говорю, что для твоих данных при вызове std::sort может вызываться не быстрая сортировка, а другая. НИКТО не говорит, что в stl используется быстрая сортировка, по факту так ЧАСТО и происходит. Это просто функция-диспетчер, которая вызывает один из алгоритмов, в зависимости от своих внутренних соображений. Но для конкретных данных может быть больше пригоден другой. Вот об этом я и говорю, что надо знать устройство stl и то, как работают сортировки.

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

N>С другой стороны, всегда можно выбирать между вариантами: std::list + std::list::sort, std::vector + std::sort, std::map, std::unordered_map. И этот выбор можно и нужно делать до того, как писать код.

Это другой сценарий! Выбрать один из стандартных контейнеров версус сказать, что медленно работает и реализовать свой велосипед. Ты уже в сторону уходишь, чувак.

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

KP>Да однозначно! Вне всяких сомнений! Еще пальнешь факелом?

Где код, Зин? (с)

Здравствуйте, Олег К., Вы писали:

ОК>Ты заканчивай предложения точками. Непонятно порой читать что к чему.
Заканчиваю. Монитор у тебя заляпан, может?

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

Я ещё boost использую и много чего ещё. Да, оно было написано кем-то другим. Это преступление?!!

N>>Не писал, но сторонние использовал. Как раз потому, что знал, что внутри стандартной сортировки была не быстрая. Ты хоть в исходники той же std::sort заглядывал?
ОК>Заглядывал и что? Сколько ты процентов сэкономил используя нестандартную функцию?

Или это все делалось ради одной десятой наносекунды?

Много. У меня недавно был топик в алгоритмах, где я смог уйти от задачи O(n^3) к O(N^2 * log(M)). И это дало охрененное ускорение. Представь, что может случиться, когда у тебя сортировка, вдруг, вместо O(logN) даёт O(n^2). Для меня это было пиз..ц как медленно. Кстати, зачем, по-твоему, существуют различные алгоритмы сортировки? Почему эту тему не закрыли после диссертации Сэджвика? Подумай над этим на досуге.

Здравствуйте, Олег К., Вы писали:

ОК>Да ты тут опять абстрактно говоришь что может быть.

Не абстрактно, я тебе уже 100 раз сказал, что std::qsort — это не быстрая сортировка и цитату привёл. Зачем, как считаешь, не используют внутри именно быструю сортировку? Зачем это описывают в документации? Зачем вообще занимаются сортировками, когда идеал уже есть в std?

N>>С другой стороны, всегда можно выбирать между вариантами: std::list + std::list::sort, std::vector + std::sort, std::map, std::unordered_map. И этот выбор можно и нужно делать до того, как писать код.
ОК>Это другой сценарий! Выбрать один из стандартных контейнеров версус сказать, что медленно работает и реализовать свой велосипед. Ты уже в сторону уходишь, чувак.

Нет, это часть того же сценария. Зная, как изначально отсортированы данные, что это за данные, подходит ли in-place в конце концов? Нюансов много. Понятно, что все сразу смотрят на std::sort, но мало кто тут же пишет код. Обычно думают сперва.

N>С другой стороны, всегда можно выбирать между вариантами: std::list + std::list::sort

По факту, этого выбора нет. Точнее он сделан ещё до того, как тебе надо что-то отсортировать. Он сделан на уровне выбора структур данных, с которыми ты работаешь. Использовать std::list::sort вместо того, чтобы напрямую использовать std::sort, там, где это возможно и требуется именно сортировка — очень сомнительное действие.
Думаю, единственное место, где может быть разумно использовать не библиотечную сортировку — это тогда, когда можно сделать сортировку за линейное время.

ОК>>Ты заканчивай предложения точками. Непонятно порой читать что к чему.
N>Заканчиваю. Монитор у тебя заляпан, может?

С монитором все в порядке.

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

N>Я ещё boost использую и много чего ещё. Да, оно было написано кем-то другим. Это преступление?!!

Буст это почти что стандарт, но даже из буста не нужно многого для решения большинства задач.

N>>>Не писал, но сторонние использовал. Как раз потому, что знал, что внутри стандартной сортировки была не быстрая. Ты хоть в исходники той же std::sort заглядывал?
ОК>>Заглядывал и что? Сколько ты процентов сэкономил используя нестандартную функцию?

Или это все делалось ради одной десятой наносекунды?

N>Много. У меня недавно был топик в алгоритмах, где я смог уйти от задачи O(n^3) к O(N^2 * log(M)). И это дало охрененное ускорение. Представь, что может случиться, когда у тебя сортировка, вдруг, вместо O(logN) даёт O(n^2). Для меня это было пиз..ц как медленно.

И что же ты такое делал и какие цифры ты выжал? В процентах и в секундах.

N>Кстати, зачем, по-твоему, существуют различные алгоритмы сортировки? Почему эту тему не закрыли после диссертации Сэджвика? Подумай над этим на досуге.

Разумеется чтобы такие как питон, ты и еще несколько товарищей устраивали по ним экзамены вместо интервью. А ты че думал?

N>Зачем вообще занимаются сортировками, когда идеал уже есть в std?

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

ОК>>Да ты тут опять абстрактно говоришь что может быть.

N>Не абстрактно, я тебе уже 100 раз сказал, что std::qsort — это не быстрая сортировка и цитату привёл. Зачем, как считаешь, не используют внутри именно быструю сортировку? Зачем это описывают в документации? Зачем вообще занимаются сортировками, когда идеал уже есть в std?

Чувак, это не идеал. Пользуются стандартными и все. Боттлнеки случаются совершенно в других местах.

N>>>С другой стороны, всегда можно выбирать между вариантами: std::list + std::list::sort, std::vector + std::sort, std::map, std::unordered_map. И этот выбор можно и нужно делать до того, как писать код.
ОК>>Это другой сценарий! Выбрать один из стандартных контейнеров версус сказать, что медленно работает и реализовать свой велосипед. Ты уже в сторону уходишь, чувак.

N>Нет, это часть того же сценария. Зная, как изначально отсортированы данные, что это за данные, подходит ли in-place в конце концов? Нюансов много. Понятно, что все сразу смотрят на std::sort, но мало кто тут же пишет код. Обычно думают сперва.

Я прямо вижу как ты посмотрел на данные в их всевозможных комбинациях и решил что стандартный сорт тебе не подходит и сразу же притащил стороннюю библиотеку в проект и все заработало как надо абсолютно на всех данных!

Уж что-что, а подчеркивать как ты умеешь думать ты умеешь.

Здравствуйте, Олег К., Вы писали:

ОК>С монитором все в порядке.
Точки-то не видишь. Значит, заляпан.

ОК>Буст это почти что стандарт, но даже из буста не нужно многого для решения большинства задач.
А мужики-то и не знали! Буст не нужен, оказывается. Зачем же его тогда в стандарт кусками перетягивают? Сразу видно специалиста.

ОК>И что же ты такое делал и какие цифры ты выжал? В процентах и в секундах.
Это было около 8 лет назад, цифры были — десятки миллисекунд на кадр. Это много при 25 fps.

ОК>Разумеется чтобы такие как питон, ты и еще несколько товарищей устраивали по ним экзамены вместо интервью. А ты че думал?

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

Здравствуйте, Олег К., Вы писали:

ОК>Чувак, это не идеал. Пользуются стандартными и все. Боттлнеки случаются совершенно в других местах.
Конечно в других! В головах тех, например, которые не знают о сортировках ничего, кроме того, что они вообще существуют.

ОК>Я прямо вижу как ты посмотрел на данные в их всевозможных комбинациях и решил что стандартный сорт тебе не подходит и сразу же притащил стороннюю библиотеку в проект и все заработало как надо абсолютно на всех данных!

Уж что-что, а подчеркивать как ты умеешь думать ты умеешь.

Мне достаточно было просто вузовского курса по алгоритмам, дружище. Чего и тебе желаю.

Аморально, однако.

KP>По твоему это сложная задача?

Ну я теперь понимаю почему ты так факелом полыхаешь когда речь заходит о вопросах отличных от "расскажите о ваших предыдущих проектах".

Чувак, Сэджвик диссертацию на ней защитил. Еще ганджастас ниже дал реализацию с ошибками и это при том что а) он скорее всего заглянул все-таки в википедию и б) у него не было интервьичного стресса. Посему еще один неутешительный вывод о тебе: ты не можешь оценить сложность задачи. Уж извини.

Да, где код все-таки?

N>Представь, что может случиться, когда у тебя сортировка, вдруг, вместо O(logN) даёт O(n^2).

Если ты реально поймал ситуацию, когда используя стандартные библиотеки на реальных входных данных давали n^2, то ты просто счастливчик. А так, самый главный способ оптимизации сортировки — это вообще обойтись без сортировки, а не заменить один алгоритм сортировки на другой.

ОК>>С монитором все в порядке.
N>Точки-то не видишь. Значит, заляпан.

Перечитай там предложение выше с запятаями. Я не понял что там с чем связывается.

ОК>>Буст это почти что стандарт, но даже из буста не нужно многого для решения большинства задач.
N>А мужики-то и не знали! Буст не нужен, оказывается. Зачем же его тогда в стандарт кусками перетягивают? Сразу видно специалиста.

А сейчас много г-на кругом пихают. И че?

ОК>>И что же ты такое делал и какие цифры ты выжал? В процентах и в секундах.
N>Это было около 8 лет назад, цифры были — десятки миллисекунд на кадр. Это много при 25 fps.

А в процентном отношении сколько? Прямо все тормозило на взгляд?

ОК>>Разумеется чтобы такие как питон, ты и еще несколько товарищей устраивали по ним экзамены вместо интервью. А ты че думал?

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

Ты прикинь, но я тут еще Шелл сорт упоминал. Может ты ответишь ганджастасу о пользе этой сортировки раз такой умный.

Здравствуйте, Олег К., Вы писали:

ОК>Чувак, Сэджвик диссертацию на ней защитил. Еще ганджастас ниже дал реализацию с ошибками и это при том что а) он скорее всего заглянул все-таки в википедию и б) у него не было интервьичного стресса. Посему еще один неутешительный вывод о тебе: ты не можешь оценить сложность задачи. Уж извини.

Таки пыхнул еще раз? Я даже не сомневался! А кода, конечно же не будет, потому как ты толстое и неумелое трололо

Кстати, а куда таких как ты на работу берут? НИИ какие-то?

Здравствуйте, Олег К., Вы писали:

ОК>Перечитай там предложение выше с запятаями. Я не понял что там с чем связывается.
Сочувствую. К твоему сведению, запятые случат в том числе для разделения простых предложений в сложносочинённом. Твоя моя понимать?

ОК>А сейчас много г-на кругом пихают. И че?

Аргументация на уровне. Браво! Кстати, можно ли это так же применять к твоим утверждениям о std::sort? Например так: её не стоит применять, потому что туда много г-на напихали.

ОК>А в процентном отношении сколько? Прямо все тормозило на взгляд?
Кадр при 25 fps надо обработать за 40 млс, значит, десятки млс — это очень медленно. Тебе понятно, как из 25 fps получаются 40 млс? Или это слишком сложно и о таком тоже на собеседовании не надо спрашивать?

ОК>Ты прикинь, но я тут еще Шелл сорт упоминал. Может ты ответишь ганджастасу о пользе этой сортировки раз такой умный.

М, а зачем ты о ней упомянул? Если её нет в std, то она и не нужна, разве нет? Или ты велосипедишь и применяешь её? Мама твоя знает об этом? Или боишься ей сказать?

ОК>>Чувак, Сэджвик диссертацию на ней защитил. Еще ганджастас ниже дал реализацию с ошибками и это при том что а) он скорее всего заглянул все-таки в википедию и б) у него не было интервьичного стресса. Посему еще один неутешительный вывод о тебе: ты не можешь оценить сложность задачи. Уж извини.

KP>Таки пыхнул еще раз? Я даже не сомневался! А кода, конечно же не будет, потому как ты толстое и неумелое трололо

KP>Кстати, а куда таких как ты на работу берут? НИИ какие-то?

Когда нечего сказать, то начинаются оскорбления. Заметь, я тебе доводы даю а ты "трололо," "пыхнул..."

Здравствуйте, Олег К., Вы писали:

ОК>Когда нечего сказать, то начинаются оскорбления. Заметь, я тебе доводы даю а ты "трололо," "пыхнул..."

В этой теме разве у кого-то кроме тебя пригорает? Не находишь некой занятой закономерности в том, когда у тебя начинает пригорать? Я когда на Артёмовский наброс писал ответ, сразу подумал "сейчас Олег понабежит и будет смешно". И ведь вправду, понабежал и смешно.
Так это, колись где работаешь, или совсем стыдно вслух произносить?

ОК>>Перечитай там предложение выше с запятаями. Я не понял что там с чем связывается.
N>Сочувствую. К твоему сведению, запятые случат в том числе для разделения простых предложений в сложносочинённом. Твоя моя понимать?

В том случае запятая использовалась у тебя вместо точки. Это ты сейчас опять с темы уходишь.

ОК>>А сейчас много г-на кругом пихают. И че?

N>Аргументация на уровне. Браво!

А что не так-то? Будешь отрицать что сейчас много г...на развелось?

N>Кстати, можно ли это так же применять к твоим утверждениям о std::sort? Например так: её не стоит применять, потому что туда много г-на напихали.

Не можно.

ОК>>А в процентном отношении сколько? Прямо все тормозило на взгляд?
N>Кадр при 25 fps надо обработать за 40 млс, значит, десятки млс — это очень медленно. Тебе понятно, как из 25 fps получаются 40 млс? Или это слишком сложно и о таком тоже на собеседовании не надо спрашивать?

Не считай других глупее себя.

ОК>>Ты прикинь, но я тут еще Шелл сорт упоминал. Может ты ответишь ганджастасу о пользе этой сортировки раз такой умный.

N>М, а зачем ты о ней упомянул? Если её нет в std, то она и не нужна, разве нет? Или ты велосипедишь и применяешь её? Мама твоя знает об этом? Или боишься ей сказать?

Это ты ответь мне на счет этой сортировки коли ты влез сюда.

ОК>>Когда нечего сказать, то начинаются оскорбления. Заметь, я тебе доводы даю а ты "трололо," "пыхнул..."

KP>В этой теме разве у кого-то кроме тебя пригорает? Не находишь некой занятой закономерности в том, когда у тебя начинает пригорать? Я когда на Артёмовский пост писал ответ, сразу подумал "сейчас Олег понабежит и будет смешно". И ведь вправду, понабежал и смешно.
KP>Так это, колись где работаешь, или совсем стыдно вслух произносить?

Ты прикинь, но я то же самое подумал и о тебе. Глянул тему и оба-на! Ты здесь. Вот я и ответил.

Здравствуйте, Олег К., Вы писали:

ОК>Это ты ответь мне на счет этой сортировки коли ты влез сюда.

Ну, я "влез" с поправкой, что в STL не обязательно быстрая сортировка используется и что это полезно знать. Ты-то чего возмущаешься? Задело за живое?

Здравствуйте, De-Bill, Вы писали:

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

Идея сортировать связанный список уже сама по себе намекает...

ОК>>Это ты ответь мне на счет этой сортировки коли ты влез сюда.

N>Ну, я "влез" с поправкой, что в STL не обязательно быстрая сортировка используется и что это полезно знать. Ты-то чего возмущаешься? Задело за живое?

Ну так может ты просветишь нас какая сортировка используется когда не используется быстрая? Нам это тоже полезно будет знать, но ты почему-то умолчал об этом.

Здравствуйте, Олег К., Вы писали:

ОК>Ты прикинь, но я то же самое подумал и о тебе. Глянул тему и оба-на! Ты здесь. Вот я и ответил.

Ну стыдно сказать где работаешь, так стыдно. Попробуй с базовой теорией разобраться, может в какую-то приличную компанию позовут работать.

Здравствуйте, Олег К., Вы писали:

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

Конкретно в том случае — никакая. Была функция для определения площади пересечения двух прямоугольников, которая вызывалась очень много раз. В этой функции дважды вызывалась std::sort: для x и y координат. И очень часто так получалось, что данные были обратно упорядочены и сортировка тормозила. Но я убрал сортировку совсем и функцию переписал без неё. Вот и все дела.
Вполне допускаю, что сейчас эта функция могла и не оказаться в числе медленных, как раз потому, что для таких небольших массивов быстрая сортировка внутри std::sort не используется вообще.

L>Идея сортировать связанный список уже сама по себе намекает...

Не совсем понял, на что именно намекает? В-принципе, нет ничего плохого в том, чтобы отсортировать список. Асимптотика O(n log n) в худшем случае. Но, скорее всего, будет эффективнее скопировать список в массив, отсортировать массив, и преобразовать обратно в список, если это возможно.

Здравствуйте, De-Bill, Вы писали:

L>>Идея сортировать связанный список уже сама по себе намекает...

DB>Не совсем понял, на что именно намекает?

Намекает на серьезный косяк. Причем, по моим наблюдениям, косяк типа "лечим простуду зеленкой", когда факап отрастает из вкорне неправильного подхода к решению задачи, нежели реализации алгоритмов.

DB>В-принципе, нет ничего плохого в том, чтобы отсортировать список.

Если это нужно один раз за лайфтам процесса и никого это не напрягает, может быть.

DB>Асимптотика O(n log n) в худшем случае. Но, скорее всего, будет эффективнее скопировать список в массив, отсортировать массив, и преобразовать обратно в список, если это возможно.

Или подумать, откуда взялся список, почему именно список и зачем нужно сортировать.

Здравствуйте, landerhigh, Вы писали:

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

L>Идея сортировать связанный список уже сама по себе намекает...

На незнание merge sort?

Здравствуйте, Тёмчик, Вы писали:

Тё>Аморально ли проверять знание алгоритмов, если на рассматриваемую позицию человек не будет их писать? Ведь задача архитектора- иметь высокоуровневое видение продукта, каким он будет и выбор, какие фреймворки использовать.

На лицо явное непонимание обязанностей архитекторов в больших конторах. В маленьких они нафиг не нужны. Код архитекторы не пишут, алгоритмы не применяют, высокоуровневое видение продукта — это как заставить 500+ стратегических приложений работать вместе, а для этого нужно строчить стандарты и со всеми договариваться.

P.S. Умиляют программисты, заявляющие что они "архитекторы" в CV.

Здравствуйте, 0x7be, Вы писали:

Тё>>Аморально ли проверять знание алгоритмов, если на рассматриваемую позицию человек не будет их писать? Ведь задача архитектора- иметь высокоуровневое видение продукта, каким он будет и выбор, какие фреймворки использовать.
Тё>>Дискас.
0>Аморально требовать те знания, которые не будут востребованы на этой позиции.

Да нет там ничего аморального в любом случае, можно спрашивать всё из computer science. Аморально — это когда требуют стоять на одной ноге, или сдать денег на благотворительность, или сиськи показать.

0>Если в данном конкретном месте роль архитектора такая, что ему эти знания нужны — требовать надо.

Ну, это как бы архитектор думает в проекте про структуру данных — как часто будет использоваться, сортироваться, расти/уменьшаться, если он не будет представлять как алгоритмы работают — мне было б страшно с таким архитектором работать.

Правда, по мне как то несколько странно архитектора тестировать задачками — их или лучше самим растить, или переманивать, но в обоих случаях должно уже быть ясно с кем имеем дело и без задачек.

Здравствуйте, Олег К., Вы писали:

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

G>>Забывается то, что ты не понял. В универе, как и в школе, часто пытаются вбить в голову факты, вместо объяснения принципов.
G>>Чтобы понять принципы построения алгоритмов на основе рекурсии я прочитал немало книг, поэтому для меня не проблема написать быстрою сортировку.

ОК>Забывается то с чем дела не имеешь напостоянку.

Я не имею на постоянку дел с быстрой сортировкой, но все равно могу её написать.

Здравствуйте, Тёмчик, Вы писали:

KP>>Аморально не знать основных алгоритмов и структур данных если ты позиционируешь себя как архитектор

Тё>Смотря что считать основными алгоритмами. Задачки про гномиков, или про обход лабиринта- это основные алгоритмы?
Джаззер был прав, если ты программист/архитект, то должен помнить про алгоритмы и раз в 1-2 года пролистывать кормена и/или сэджвика. От себя добавлю, не лишним будет почитывание прикладного матана и изучения чего-то нового из этой сферы. С гномиками можно справится если поддерживаешь мозги в тонусе.

Здравствуйте, Олег К., Вы писали:

ОК>Ты, чувак, видишь разницу между знать что есть такие-то структуры данных и такие-то алгоритмы версус того чтобы требовать их имплементацию?

Ты сам придумал что надо спрашивать имплементацию и продолжаешь с этим героически спорить.

G>>У меня был случай — надо было написать функцию, которая превращает IEnumerable<T> в IEnumerable<IEnumerable<T>>, нарезая входную последовательность на блоки по определенному условию, зависящему от нескольких предыдущих элементов.
G>>Я потом эту задачу на собеседовании давал. Код менее чем на 20 строк. Из 10 кандидатов справилось два. При этом все прекрасно знали linq, yield, как устроен IEnumerable и то, что енумератор — value type.
ОК>Что-то ты переусложняешь все.
Что именно?

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

G>Я не имею на постоянку дел с быстрой сортировкой, но все равно могу её написать.

"могу её написать" и "могу её написать без ошибок" две большие разницы, в данном случае Вам намекают про второй случай, а Вы упорно давите на первое))

Здравствуйте, rumit7, Вы писали:

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

G>>Я не имею на постоянку дел с быстрой сортировкой, но все равно могу её написать.

R>"могу её написать" и "могу её написать без ошибок" две большие разницы, в данном случае Вам намекают про второй случай, а Вы упорно давите на первое))

Написать на бумаге\на форуме и на компьютере — две большие разницы, я говорю про первый случай, а все упорно делают вид, что это второй

Здравствуйте, Олег К., Вы писали:

ОК>Тут вопрос в другом. Помнит он этот квиксорт как он говорит или все-таки полез в википедию?
Не отпускает до сих пор?

ОК>Ну и еще тут один момент. Сэджвик защитил диссертацию по квиксорту, а тут некоторые товарищи утверждают что напишут код слету да еще и на интервью. Поражаюсь ихней самоуверенности.

Ты плохо представляешь суть диссертации по computer science. Диссертация заключается не в написании кода, а в формальном доказательстве свойств кода.
Докажи формально, что выбор срединного элемента в качестве опорного лучше чем выбор первого. А если выбирать случайный элемент в качестве опорного, как это скажется на свойствах квиксорта?

	мат я запипал
	"Ну, раз уж алгоритмические вопросы заставляют таким факелом полыхать кандидатов вроде тебя, такие вопросы просто необходимо задавать для грамотного отбора" Я тебе уже говорил, что ты — ДЕБИЛ? Могу еще раз повторить, то ты — ДЕБИЛ! Нет никакой необходимости помнить многие алгоритмы. Напиши, к примеру, сходу алгоритм push_heap, который добавляет элемент в кучу, не заглядывая в книгу. Кому это надо помнить?! А чтобы ты, ДЕБИЛ, заткнулся, то я тебе скажу, что это именно я предложил комитету стандартизации по C++ внести изменения относительно этого алгоритма так как имеет место неоднозначность вставки нового элемента. Но мне совершенно не нужно помнить этот алгоритм. Когда понадобиться, я смогу освежить свою память. Слушай, шел бы ты ПИИИИИП от обсуждения программирования, так как ты — НИКТО, и зовут тебя — НИКАК. Я посмотрел на Stackoverflow, так там такого kaa.python и в помине нет. Что ты лезешь ЧМОШНИК со своими куриными мозгами в калашный ряд?!

	тут, походу, веселуха продолжается
	"смотрите как Олежка пыхнул в личке" — Слушай, ДЕБИЛ, я к этому "Олежке" никакого отношения не имею. Я вообще не принимаю участие на этом форуме. Я — сторонний читатель.. Просто уже никаких сил нет читать твою ДЕБИЛЬНУЮ ЧУШЬ. О себе. Автор нескольких предложений по изменению стандарта C++, которые были включены в стандарт. Имею золотые знаки отличия по C и C++ на Stackoverflow. Репутация составляет более 100 тысяч баллов. Это все я пишу, чтобы до твоих куриных мозгов хоть что-то дошло, правда, как показывает жизнь, таких ДЕБИЛОВ чему-либо не научишь. Тебе уже сказано было: "Заткнись!" Глядишь, и за умного сойдешь.

Здравствуйте, kaa.python, Вы писали:

KP>Иногда ты очень хорошо накидываешь, смотрите как Олежка пыхнул в личке!!! Я бы сказал что просто взрыв какой-то!!!

Если это личная переписка, то ты как минимум не прав выкладывая её.

Здравствуйте, Kernan, Вы писали:

K>Если это личная переписка, то ты как минимум не прав выкладывая её.

Я имею полное право делать что угодно с сообщением отправленным лично мне. Тебе привести мнение профессионального юриста на этот счет?

Здравствуйте, kaa.python, Вы писали:

KP>Здравствуйте, Kernan, Вы писали:

K>>Если это личная переписка, то ты как минимум не прав выкладывая её.

KP>Я имею полное право делать что угодно с сообщением отправленным лично мне. Тебе привести мнение профессионального юриста на этот счет?
Давай.

Здравствуйте, Kernan, Вы писали:

KP>>Я имею полное право делать что угодно с сообщением отправленным лично мне. Тебе привести мнение профессионального юриста на этот счет?
K>Давай.

Правила форума не запрещают выкладывать личных сообщений, дисклеймера о конфиденциальности в личном сообщении не было, никакого NDA я не подписывал. Итого: мое сообщение – что хочу, то и делаю с ним. Все остальные сообщения от этого одаренного товарища, если они будут, я планирую выложить к первым двум.

Здравствуйте, Олег К., Вы писали:

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

Потому что он — Босс, ясен пень!

Здравствуйте, De-Bill, Вы писали:

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

Почему?
В классике все для массива. Вот краткая запись:

quicksort(A, lo, hi):
p = partition(A, lo, hi)//O(n)
quicksort(A, lo, p)
quicksort(A, p + 1, hi)

Для связанного списка нужно немного модифицировать процедуры.
partition можно реализовать за O(n), соединение двух сортированных частей — O(1).
Асимптотика не поменяется:

quicksort(A):
Aleft, Aright = partition(A)//O(n)

quicksort(Aleft)
quicksort(Aright)

return Aleft.Add(Aright)//O(1)

Гугление даст результат.

Здравствуйте, Олег К., Вы писали:

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

Разделяй и властвуй — это весь хлам, который нужно помнить для решения задачи навроде квиксорта.
Что ты хочешь шеллом проверить, умение писать вложенные циклы на массиве? Это примерно первый месяц первого курса программирования.

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

ОК>>Забывается то с чем дела не имеешь напостоянку.

G>Я не имею на постоянку дел с быстрой сортировкой, но все равно могу её написать.

Я тоже раньше думал как Олег К. Но однажды разобрался хорошенько с сортировками и по прошествии лет все еще помню как их писать. По крайней мере основные вроде quicksort да mergesort. Там же элементарщина, как можно забыть? Это все равно что забыть как работает хэш-таблица. Принцип простой, а там уж логически детали восстановить можно.

KP>"смотрите как Олежка пыхнул в личке" — Слушай, ДЕБИЛ, я к этому "Олежке" никакого отношения не имею. Я вообще не принимаю участие на этом форуме. Я — сторонний читатель.. Просто уже никаких сил нет читать твою ДЕБИЛЬНУЮ ЧУШЬ.

Это не я был, но до тебя не доходит одна простая вещь. Ты можешь считать сколько угодно что ни я ни написавший тебе лично не разбираемся в алгоритмах. Считай. Считай какой ты крутой в программировании. Твое право. Но... Рано или поздно тебя отинтервьюирует такой же, хм, спец как и ты. Либо в силу своей глупости либо просто умышленно. Это сделать проще простого даже на задачке в десять строк кода. Ты этого не понимаешь.

ОК>>>Забывается то с чем дела не имеешь напостоянку.

G>>Я не имею на постоянку дел с быстрой сортировкой, но все равно могу её написать.

K>Я тоже раньше думал как Олег К. Но однажды разобрался хорошенько с сортировками и по прошествии лет все еще помню как их писать. По крайней мере основные вроде quicksort да mergesort. Там же элементарщина, как можно забыть? Это все равно что забыть как работает хэш-таблица. Принцип простой, а там уж логически детали восстановить можно.

Ну так напиши код. Один уже решил понтануться крутизной но предоставил код с ошибками. Звиздеть все горазды. А как до дела дойдет...

Да, алгоритмов много в разных областях. Ты уверен что все знаешь? Следует понимать что сортировка была приведена просто как пример, и на интервью всякое возможно в зависимости от дурости спрашивающего.

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

R>>"могу её написать" и "могу её написать без ошибок" две большие разницы, в данном случае Вам намекают про второй случай, а Вы упорно давите на первое))
+1 пациент не вполне понимает смысл, но выглядит "что-то похожее".

G>Написать на бумаге\на форуме и на компьютере — две большие разницы, я говорю про первый случай, а все упорно делают вид, что это второй

Нет ничего предосудительного спросить про сортировку на собеседовании. Но в случае quick sort там всё очень неоднозначно, это не просто "разделяй и властвуй". Ты сходу накидал решение, которое работать не будет. Даже не подумал о подвохе. Дальше всё зависит от принципиальности собеседующего, например он мог бы намекнуть про граничные условия и дать тебе возможность реабилитироваться. Или промолчать, и отметить "кандидат негоден". Если ты единственный, кто хоть что-то выдал- значит такой рынок труда, тебе повезло. Ну и в любом случае, сортировки это слишком прямолинейно и легко в наше время. У меня даже такое подозрение, что сортировки как фильтр не отсеивают дебилов от слова совсем. Народ тупо зубрит. Потом в реальной ситуации возникают ужасы кода от сна разума.
Обход лабиринта или гномики но с такой загогулиной, чтобы известные в интернете решения под копирку не подходили- интереснее.

Здравствуйте, Тёмчик, Вы писали:

Тё>Нет ничего предосудительного спросить про сортировку на собеседовании. Но в случае quick sort там всё очень неоднозначно, это не просто "разделяй и властвуй". Ты сходу накидал решение, которое работать не будет. Даже не подумал о подвохе.
Кончай фантазировать. Я скопировал код в студию, поправил в трех строках +\-1, граничные условия и все заработало.

Тё>Дальше всё зависит от принципиальности собеседующего, например он мог бы намекнуть про граничные условия и дать тебе возможность реабилитироваться.
Ты и многие другие не смогли без запуска в студии найти все ошибки. Думаешь интервьювер найдет? И надо оно ему? Это же помнить наизусть весь код надо и только для того, чтобы потешить самолюбие.

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

Тё>Если ты единственный, кто хоть что-то выдал- значит такой рынок труда, тебе повезло.
Я единственный кто хоть что-то выдал в этой теме

Тё>Ну и в любом случае, сортировки это слишком прямолинейно и легко в наше время. У меня даже такое подозрение, что сортировки как фильтр не отсеивают дебилов от слова совсем.
Судя по твоему первому посту тебя как раз и отсеяли

K>Там же элементарщина, как можно забыть? Это все равно что забыть как работает хэш-таблица. Принцип простой, а там уж логически детали восстановить можно.

Блин, меня всегда пугали люди, которые говорят о хэш-таблицах, что это элементарщина. Потому что они явно никогда не пытались сделать хорошую хэш-функцию, что является сверх не элементарной задачей.

SL>Гугление даст результат.

Оставьте этот снисходительный тон)) Я прекрасно понимаю, почему qSort нельзя использовать для списков. Проблема в том, что базовая реализация qSort, когда за pivot принимается первый элемент — бессмысленная и беспощадная. Эта реализация хуже, чем её отсутствие. Реализация qSort для реальной жизни должна как минимум использовать рандомизированный выбор pivot. А в реальности и ещё ряд приседаний для оптимизации производительности. А в списке за время O(1) нельзя получить доступ к случайному элементу. Можно получить только доступ к первому элементу. То, что асимптотика в среднем для случайного списка будет O(n log n) не достаточна для реальной жизни, так как в реальной жизни частично упорядоченные массивы в качестве входных данных встречаются гораздо чаще, чем просто случайные массивы.

Здравствуйте, De-Bill, Вы писали:
DB>Блин, меня всегда пугали люди, которые говорят о хэш-таблицах, что это элементарщина. Потому что они явно никогда не пытались сделать хорошую хэш-функцию, что является сверх не элементарной задачей.
кстати, в одном из финалов олимпиад по программированию, может даже ACM, задачей была разработка хэш-фии, способной выдать наиболее равномерное распределение

Здравствуйте, __kot2, Вы писали:

__>кстати, в одном из финалов олимпиад по программированию, может даже ACM, задачей была разработка хэш-фии, способной выдать наиболее равномерное распределение

Imho хэш функция- это из раздела криптографии, там можно зайти очень далеко для удовлетворения каких-то требований. Сама по себе хэш-таблица- тривиальный массив с связными списками. Ну и для строк например, есть простая (good enough) хэш функция из коробки, а указатели уже сами по себе можно использовать как хэш.

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

Тё>>В случае quick sort ты можешь получить вырожденный случай и глубину рекурсии N. Не проверил граничных условий — провалил задание.
G>Если что ты всегда можешь его получить, независимо от того, как ты напишешь Быстрая сортировка в худшем случае имеет O(n^2)

Глубина рекурсии в quick sort минимальными усилиями ограничивается логарифмом, об этом ещё Хоар писал в своей изначальной статье.

Здравствуйте, Kernan, Вы писали:

KP>>Иногда ты очень хорошо накидываешь, смотрите как Олежка пыхнул в личке!!! Я бы сказал что просто взрыв какой-то!!!

K>Если это личная переписка, то ты как минимум не прав выкладывая её.

Сообщение даже с запикаными матами вообще говоря оскорбительное. Фактически — насилие. Ты точно уверен, что kaa.python не имеет права защитится от такого насилия ?

Здравствуйте, Олег К., Вы писали:

ОК>Это не я был, но до тебя не доходит одна простая вещь. Ты можешь считать сколько угодно что ни я ни написавший тебе лично не разбираемся в алгоритмах. Считай. Считай какой ты крутой в программировании. Твое право. Но... Рано или поздно тебя отинтервьюирует такой же, хм, спец как и ты. Либо в силу своей глупости либо просто умышленно. Это сделать проще простого даже на задачке в десять строк кода. Ты этого не понимаешь.

Ты лучше расскажи, как можно писать код, не владея базовыми принципами кодинга ? Тебя ведь не заставляют придумать квиксорт, а реализовать известный алгоритм. Задачи вида "разделяй и властвуй" встречаются в реальности слишком часто, что бы их можно было просто так забыть.

Здравствуйте, Mishka, Вы писали:

M>На лицо явное непонимание обязанностей архитекторов в больших конторах. В маленьких они нафиг не нужны. Код архитекторы не пишут, алгоритмы не применяют, высокоуровневое видение продукта — это как заставить 500+ стратегических приложений работать вместе, а для этого нужно строчить стандарты и со всеми договариваться.

Видишь ли, есть много разных архитектов. Артем, скорее всего, говорит от Software Architect, а ты описываешь что то похожее на Infrastructure Architect.

... << RSDN@Home 1.0.0 alpha 5 rev. 0 on Windows 8 6.2.9200.0>>

Здравствуйте, De-Bill, Вы писали:

DB>Оставьте этот снисходительный тон))

Да не, тон обычный. Ничего такого

Это я не так давно к одному собеседования готовился и освежил алгоритм.

DB>Я прекрасно понимаю, почему qSort нельзя использовать для списков. Проблема в том, что базовая реализация qSort, когда за pivot принимается первый элемент — бессмысленная и беспощадная. Эта реализация хуже, чем её отсутствие. Реализация qSort для реальной жизни должна как минимум использовать рандомизированный выбор pivot. А в реальности и ещё ряд приседаний для оптимизации производительности. А в списке за время O(1) нельзя получить доступ к случайному элементу. Можно получить только доступ к первому элементу. То, что асимптотика в среднем для случайного списка будет O(n log n) не достаточна для реальной жизни, так как в реальной жизни частично упорядоченные массивы в качестве входных данных встречаются гораздо чаще, чем просто случайные массивы.

Тут только один нюанс могу добавить.
Когда готовился, то я посмотрел две реализации:
1. В .Net Framework
2. В STL, идущий с Visual С++

В обоих берется медиана из [First, Mid, Last].

Здравствуйте, De-Bill, Вы писали:

K>>Там же элементарщина, как можно забыть? Это все равно что забыть как работает хэш-таблица. Принцип простой, а там уж логически детали восстановить можно.

DB>Блин, меня всегда пугали люди, которые говорят о хэш-таблицах, что это элементарщина. Потому что они явно никогда не пытались сделать хорошую хэш-функцию, что является сверх не элементарной задачей.

Принцип в самой таблице простой. Про хеш-функцию нужно помнить только её свойства. Никто не просит изобрести идеальную хеш-функцию прямо на собеседовании с доказательством теорем.
Написание хеш-таблицы это примерно экзамен за первый курс унивеситета. У меня именно такой и был, кстати говоря.

I>Принцип в самой таблице простой.

Также как и принцип, например, любого автомобиля. Есть коробка и 4 колеса. Элементарщина.

I>Написание хеш-таблицы это примерно экзамен за первый курс унивеситета.

Написание хеш-таблицы без хеш-функции — абсолютно бессмысленное дело. Это также как делать автомобиль приколотив к бревну 4 колеса. Вся соль хэш-таблиц заключается именно в хеш-функциях. Если у вас у университете на экзамене было задание написать массив списков, то университет очень хиленький.

Здравствуйте, kaa.python, Вы писали:

KP>Иногда ты очень хорошо накидываешь, смотрите как кто-то пыхнул в личке!!! Я бы сказал что просто взрыв какой-то!!!

Выплескивать эмоции полезнее, чем держать в себе

Здравствуйте, Тёмчик, Вы писали:

Тё>Аморально ли проверять знание алгоритмов, если на рассматриваемую позицию человек не будет их писать? Ведь задача архитектора- иметь высокоуровневое видение продукта, каким он будет и выбор, какие фреймворки использовать.

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

И да, я сам хоть уже 10 лет не кодирую, но даже ночью готов рассказать quick/radix и т.п. sort, пересказать алгоритмы построения/нормализации/обхода деревьев, алгоритмы поиска, десяток основных паттернов и прочее что въелось мне в мозг так, что похоже уже никогда не забудется.

Чем может быть полезен архитектор, который нихрена не знает, я не представляю

Здравствуйте, Kernan, Вы писали:

K>Если это личная переписка, то ты как минимум не прав выкладывая её.

А она не личная — личность писателя не установлена.

Здравствуйте, Олег К., Вы писали:

ОК>Чувак, это не идеал. Пользуются стандартными и все. Боттлнеки случаются совершенно в других местах.
Тут я с тобой не согласен. Боттелнеки как раз и случаются из-за неправильно выбранного контейнера, сортировки или поиска, либо криво написаной комбинации этих вещей.

Здравствуйте, Олег К., Вы писали:

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

Хлама много бывает, да. Но quicksort не подпадает

Для программиста в тренде, работающего с функциональщиной это образ мышления. А функциональщины много и будет еще больше. Ибо параллелизация, осутствие побочных эффектов -> безгеморность проекта, стоимость и честкая связь работой именно архитектора.
Не только способного это все понимать, но и ограничивать слишком увлекшихся функциональщиной членов команды в местах, где это не нужно, в ущерб времени и усложнению для juniors.

Алгоритм точный не помнить это нормально но принцип в голове.
Я в 2011-м в Гугл собеседоваться ходил. До сих пор помнится что принцип разделения на 2 части имеет особенности и разные подходы, плюсы и минусы. На память я эту часть не припомню и не перечислю сходу.
А вот сам базовый принцип и сложность не знать это не хорошо. Т.к. в жизни quicksort писать не придется, но в архитектуре сам подход и его понимание необходимы.

Хорошая задачка, чтобы разделить программистов и архитекторов на 2 категории: кексы и зомби.

Жили-были мыши и все их обижали. Как-то пошли они к мудрому филину
и говорят:
— Мудрый филин, помоги советом. Все нас обижают, коты разные, совы.
Что нам делать?
Филин подумал и говорит:
— А вы станьте ёжиками. У ёжиков иголки, их никто не обижает.
Мыши обрадовались и побежали домой. Но по дороге одна мышка сказала:
— Как же мы станем ёжиками? — и все побежали обратно, чтобы задать
этот вопрос мудрому филину.
Прибежав, они спросили:
— Мудрый филин, а как же мы станем ёжиками?
И ответил филин:
— Ребята, вы меня ерундой не грузите. Я стратегией занимаюсь.

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

I>Разделяй и властвуй — это весь хлам, который нужно помнить для решения задачи навроде квиксорта.

Ну а ты напиши код! В теории тут все умельцы, а как до практики дело дойдет, так в кусты все.

I>Что ты хочешь шеллом проверить, умение писать вложенные циклы на массиве? Это примерно первый месяц первого курса программирования.

Ты ни хрена не понял о чем я тут толкую кучу постов.

V_>Хорошая задачка, чтобы разделить программистов и архитекторов на 2 категории: кексы и зомби.

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

ОК>>Ты, чувак, видишь разницу между знать что есть такие-то структуры данных и такие-то алгоритмы версус того чтобы требовать их имплементацию?

G>Ты сам придумал что надо спрашивать имплементацию и продолжаешь с этим героически спорить.

Вообще-то такое спрашивается и ограничено это дуростью интервьюера.

ОК>>Тут вопрос в другом. Помнит он этот квиксорт как он говорит или все-таки полез в википедию?
G>Не отпускает до сих пор?

Тебя за язык никто не тянул. Решил понтануться, а код не рабочий.

ОК>>Ну и еще тут один момент. Сэджвик защитил диссертацию по квиксорту, а тут некоторые товарищи утверждают что напишут код слету да еще и на интервью. Поражаюсь ихней самоуверенности.

G>Ты плохо представляешь суть диссертации по computer science. Диссертация заключается не в написании кода, а в формальном доказательстве свойств кода.

Это ты плохо представляешь что такое диссертация. Код еще как требуют. Рабочий, разумеется.

G>Докажи формально, что выбор срединного элемента в качестве опорного лучше чем выбор первого. А если выбирать случайный элемент в качестве опорного, как это скажется на свойствах квиксорта?

KP>>>Иногда ты очень хорошо накидываешь, смотрите как Олежка пыхнул в личке!!! Я бы сказал что просто взрыв какой-то!!!

K>>Если это личная переписка, то ты как минимум не прав выкладывая её.

I>Сообщение даже с запикаными матами вообще говоря оскорбительное. Фактически — насилие. Ты точно уверен, что kaa.python не имеет права защитится от такого насилия ?

Насилие? Ты еще к психоаналитику ему посоветуй сходить.

K>>Если это личная переписка, то ты как минимум не прав выкладывая её.

aik>А она не личная — личность писателя не установлена.

Личная это означает не публично было ему написано а не "личность писателя не установлена." Как-то народ тут странно мыслит.

ОК>>Это не я был, но до тебя не доходит одна простая вещь. Ты можешь считать сколько угодно что ни я ни написавший тебе лично не разбираемся в алгоритмах. Считай. Считай какой ты крутой в программировании. Твое право. Но... Рано или поздно тебя отинтервьюирует такой же, хм, спец как и ты. Либо в силу своей глупости либо просто умышленно. Это сделать проще простого даже на задачке в десять строк кода. Ты этого не понимаешь.

I>Ты лучше расскажи, как можно писать код, не владея базовыми принципами кодинга ? Тебя ведь не заставляют придумать квиксорт, а реализовать известный алгоритм. Задачи вида "разделяй и властвуй" встречаются в реальности слишком часто, что бы их можно было просто так забыть.

Где код? Ты можешь рассуждать сколько угодно что ты там что-то можешь, помнишь и т.д. но пока что единственное мерило всех этих громких заявлений — работающий код.

З.Ы. Ты вообще ни хрена не понял о чем я тут толкую.

Тё>>Аморально ли проверять знание алгоритмов, если на рассматриваемую позицию человек не будет их писать? Ведь задача архитектора- иметь высокоуровневое видение продукта, каким он будет и выбор, какие фреймворки использовать.

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

S>И да, я сам хоть уже 10 лет не кодирую, но даже ночью готов рассказать quick/radix и т.п. sort, пересказать алгоритмы построения/нормализации/обхода деревьев, алгоритмы поиска, десяток основных паттернов и прочее что въелось мне в мозг так, что похоже уже никогда не забудется.

Звиздеть не мешки ворочать. Пока что единственное мерило умения это работающий код.

S>Чем может быть полезен архитектор, который нихрена не знает, я не представляю

Ты не понял о чем он.

Здравствуйте, sharpcoder, Вы писали:

S>И да, я сам хоть уже 10 лет не кодирую, но даже ночью готов рассказать quick/radix и т.п. sort, пересказать алгоритмы построения/нормализации/обхода деревьев, алгоритмы поиска, десяток основных паттернов и прочее что въелось мне в мозг так, что похоже уже никогда не забудется.

У тебя такая замечательная память! Я тут через пару месяцев после фазы активного поиска и решения тестовых задачек уже притупляется детали радикс сорта например. Слишком много новой информации и старый "контекст" вытесняется. При необходимости, наверное, освежу и вспомню что знал. Но утверждать что и через 10 лет все сортировки помнишь- сильно. Напишешь сходу параллельную сортировку? А тим сорт? А фильтр Блюма? Суффиксное дерево? Наиболее длинный путь без повторов ребер между 2 вершинами?

S>Чем может быть полезен архитектор, который нихрена не знает, я не представляю

Здравствуйте, Олег К., Вы писали:

K>>>Если это личная переписка, то ты как минимум не прав выкладывая её.
aik>>А она не личная — личность писателя не установлена.
ОК>Личная это означает не публично было ему написано а не "личность писателя не установлена." Как-то народ тут странно мыслит.

Я мыслю с практической точки зрения — писатель скрыл имя чтоб не срамиться, т.е. отсылая нечто, он уже готов к публикации. Подписи нет, обращения к адресату по имени нет — ничего личного не заметно, разве что канал доставки 1-1. Но когда "нигерийский принц" хочет "раздать денег" — выглядит всё ровно так же — это что, тоже личная переписка?

Здравствуйте, Олег К., Вы писали:

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

Ты и на собеседованиях так говоришь собеседующему?

Здравствуйте, Олег К., Вы писали:

ОК>Где код? Ты можешь рассуждать сколько угодно что ты там что-то можешь, помнишь и т.д. но пока что единственное мерило всех этих громких заявлений — работающий код.

Похоже у тебя какие-то болезненные воспоминания связаны с кодом на собеседовании.
Разговор вообще начался с того — надо ли на собеседовании проверять знание алгоритмов.
Знание алгоритмов вообще не означает умение написать квиксорт на бумаге без ошибок. Можно знать алгоритмы и не уметь писать квиксорт на бумаге, а можно алгоритмы не знать и тупо вызубрить код.

Если человек может объяснить как работает квиксорт, почему он быстрее пузрьковой сортировки — этого уже более чем достаточно. Если это понимание есть, то имея достаточно времени и компьютер можно квиксорт написать.

Здравствуйте, Олег К., Вы писали:

ОК>Это ты плохо представляешь что такое диссертация. Код еще как требуют.

Остаётся вопрос — защитил ли Сэджвик дисертацию ?

Здравствуйте, Олег К., Вы писали:

ОК>Чувак, это не идеал. Пользуются стандартными и все. Боттлнеки случаются совершенно в других местах.

Но Сэджвик всё равно её защитил! Диссертацию.

Здравствуйте, Олег К., Вы писали:

ОК>Нам это тоже полезно будет знать, но ты почему-то умолчал об этом.

Гораздо полезнее знать про диссертацию Сэджвика.

Здравствуйте, Олег К., Вы писали:

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

И даже диссертация не защищена. Не то что у Седжвика!

Здравствуйте, Олег К., Вы писали:

ОК>Где код, Зин? (с)

Сколько диссертаций ты защитил ?

Здравствуйте, sharpcoder, Вы писали:

S>И да, я сам хоть уже 10 лет не кодирую, но даже ночью готов рассказать quick/radix и т.п. sort, пересказать алгоритмы построения/нормализации/обхода деревьев, алгоритмы поиска, десяток основных паттернов и прочее что въелось мне в мозг так, что похоже уже никогда не забудется.

Все правильно. А 9 из 10 реально работающих, реально зарабатывающих деньги программистов про radix sort вспомнят только, что такое существует и в универе чето такое рассказывали. Им гораздо важнее знать детали конкретного фреймворка, с которым в настоящий момент ведется работа, чтобы в срок и эффективно выполнять свои задачи.
Про общую же эрудицию, без которой видишь ли невозможно, тут разгоняют в основном бездельники и торговцы лицом типа менеджеров продуктов и прочих полусисадминов-разработчиков инсталляторов.

S>Чем может быть полезен архитектор, который нихрена не знает, я не представляю

Это потому что ты — рукамиводитель и торговец.
Ты — не архитектор, и даже не программист, ты не сталкивался и не представляешь, как правильно проектируются сложные системы, и ЧТО может породить какой-нибудь великий знаток квиксортов. Живой пример — Ангуляр 1, который зачинали аутисты-олимпиадники противоестественным способом, в итоге получился мертворожденный кадавр, пожравший миллионы человеко-часов сотен тысяч прикладных разработчиков.
Более того, кадавр вышел настолько ужасен, что даже самому Гуглу пришлось принять меры.

Здравствуйте, Тёмчик, Вы писали:

Тё>а указатели уже сами по себе можно использовать как хэш.

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

Здравствуйте, Олег К., Вы писали:

ОК>З.Ы. Ты вообще ни хрена не понял о чем я тут толкую.

Не находишь странным что тебя никто не понимает?

... << RSDN@Home 1.0.0 alpha 5 rev. 0>>

S>>Чем может быть полезен архитектор, который нихрена не знает, я не представляю

SA>Это потому что ты — рукамиводитель и торговец.
SA>Ты — не архитектор, и даже не программист, ты не сталкивался и не представляешь, как правильно проектируются сложные системы

С чего ты это взял-то?

Здравствуйте, Олег К., Вы писали:

I>>Ты лучше расскажи, как можно писать код, не владея базовыми принципами кодинга ? Тебя ведь не заставляют придумать квиксорт, а реализовать известный алгоритм. Задачи вида "разделяй и властвуй" встречаются в реальности слишком часто, что бы их можно было просто так забыть.

ОК>Где код? Ты можешь рассуждать сколько угодно что ты там что-то можешь, помнишь и т.д. но пока что единственное мерило всех этих громких заявлений — работающий код.

Да хватит плакать. Идеально работающий код на собеседовании никто не просит. Важно продемонстрировать владение принципами.
Ты будешь смеяться, но большинство разработчиков просто не умеют кодить. Внятно владеют техникой кодирования смешное количество людей, у остальных наколеночный подход — написал пол-строчки, полез дебагером смотреть.

Так вот, если ты владеешь техникой кодинга, то определенные задачи ты просто записываешь не глядя. А если не владеешь, то за тобой остаётся куча мелких или трудноуловимых косяков.

ОК>З.Ы. Ты вообще ни хрена не понял о чем я тут толкую.

Разумеется, что ты же о своих болячках говоришь. Кто знает, где там тебя стукнули и как глубоко задели ?

Здравствуйте, Тёмчик, Вы писали:

Тё>Смотря что считать основными алгоритмами. Задачки про гномиков, или про обход лабиринта- это основные алгоритмы?

Гномики это логика, это не алгоритм.
А обход лабиринта — да, это весьма простой алгоритм по обходу графа.

Здравствуйте, Олег К., Вы писали:

ОК>Я не верю что ты помнишь как работает Quick sort внутри после 15 лет работы если ты только недавно не перечитал книжку по алгоритмам.

Я так думаю, книжки по алгоритмам надо бы периодически перечитывать. Профессия у нас такая.

Да и потом, мало кто работает по 15 лет на одном месте, а перед собеседованием на новое место работы книжку лучше бы перечитать.
Я не архитектор, но Скиену частично перечитываю примерно раз в два года. Освежить память. Хорошо помогает в решении повседневных задач. Надо ещё Кормена купить.

Поэтому я написать QuickSort могу. Хотя на собеседовании меня ни разу не просили это сделать. Вчера вот просили написать реализации очереди используя массив и используя стэк.

Здравствуйте, Mishka, Вы писали:

M>На лицо явное непонимание обязанностей архитекторов в ~~больших конторах~~инвестбанках. В маленьких они нафиг не нужны. Код архитекторы не пишут, алгоритмы не применяют, высокоуровневое видение продукта — это как заставить 500+ стратегических приложений работать вместе, а для этого нужно строчить стандарты и со всеми договариваться.
Поправил, вот теперь верно. А ещё в каждой такой говноконторе обязательно есть SVP, который раз в пару лет объявляет на ~~броневичке~~"all hands meeting" очередную итерацию мегапроекта по Data consolidation

После чего такие "ОрхитектОры" начинают имитировать бурную деятельность, просиживая удвоенное количество штанов на митингах по обсуждению погоды в выходные. Правда, через месяц-два тема как-то сама-собой сходит на нет, потому что те, кто реально могут что-то сделать, и так загружены работой на 146%, а трындоболы-ОрхитектОры сами нихрена не могут сделать, т.к. руки у них давно уже атрофировались за ненужностью. Знакомо, не правда ли?

Здравствуйте, sr_dev, Вы писали:

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

Для одинаковых указателей будут одинаковые значения хэша. Ваш К.О.

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

G>Если что ты всегда можешь его получить, независимо от того, как ты напишешь Быстрая сортировка в худшем случае имеет O(n^2)

Не имеет.

Быстрая сортировка с использованием медианы медиан для выбора разделяющего элемента — имеет гарантированное O(N log N) в худшем случае, за счёт константы скорости.

Быстрая сортировка со случайным выбором ведущего элемента имеет O(N^2) с вероятностью, асимптотически стремящейся к нулю с ростом N, а, значит, практически такое не происходит. Если же при этом ставить ограничение на бюджет рекурсии и переходить или на медиану медиан — то получится и быстро, и надёжно по асимптотике. (На практике чаще в этом случае включают heapsort, чтобы уже радикально решить вопрос.)

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

Тут согласен — хоть и с ошибками, но это не пузырёк. Аккуратно написать разделяющий цикл — самая сложная часть.

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

+1.

Здравствуйте, Олег К., Вы писали:

ОК>То чем занимаешься ты называется буквоедство. В реальном коде нужно использовать стандартную библиотеку и понимать, что автор в них сделал разумные вещи (а не какую-нибудь пузырьковую сортировку). Все!

"В реальном коде" надо понимать, что библиотечные средства хороши только "в среднем по больнице" и без учёта конкретных местных факторов. Например, может потребоваться любой ценой сократить количество сравнений элементов, потому что они жутко дороги, а вот переставить два указателя — копейки. И тогда выгоднее будет написать свою.
Это, кстати, свежий реальный пример: в реализации select{} в Go не взята стандартная библиотечная реализация сортировки, а запилена своя. Причём там пузырёк(!), но, так как в select более 5 каналов бывает только в страшном сне, это эффективнее любой библиотечной.

N>>Так что твои знания в области алгоритмов совсем не достаточны для архитектора.
ОК>Ну ясно, в общем. Ты, как я понял, будешь городить свою сортировку вместо библиотечной.

Знания-то надо применить!

Именно. Там, где они нужны, и применяются.

Здравствуйте, Ikemefula, Вы писали:

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

I>Разделяй и властвуй — это весь хлам, который нужно помнить для решения задачи навроде квиксорта.
I>Что ты хочешь шеллом проверить, умение писать вложенные циклы на массиве? Это примерно первый месяц первого курса программирования.

Там специфика — нужно помнить, какие последовательности шагов дают действительно эффективную реализацию. Я вот помню уже очень смутно, но и то потому, что она меня "приколола". Обычный программист, скорее всего, откинет её как нелепую фигню.
А ещё если задача реализовать последовательность шагов как подмножество 3^x * 2^y — задача становится очень нетривиальной. После этого, да, "вложенные циклы на массиве" это 1% сложности всей задачи.

Здравствуйте, De-Bill, Вы писали:

DB>Написание хеш-таблицы без хеш-функции — абсолютно бессмысленное дело. Это также как делать автомобиль приколотив к бревну 4 колеса. Вся соль хэш-таблиц заключается именно в хеш-функциях.

Ой не всегда. Вот тут (перевод) вся соль именно в методе перемещения элементов в таблице с открытой адресацией, а не в хэш-функции, которая для сегодня банальна. И, кажется, его утверждение про самую быструю хэш-таблицу пока никто не опроверг.

Здравствуйте, kaa.python, Вы писали:

KP>>>Я имею полное право делать что угодно с сообщением отправленным лично мне. Тебе привести мнение профессионального юриста на этот счет?
K>>Давай.

KP>Правила форума не запрещают выкладывать личных сообщений, дисклеймера о конфиденциальности в личном сообщении не было, никакого NDA я не подписывал. Итого: мое сообщение – что хочу, то и делаю с ним. Все остальные сообщения от этого одаренного товарища, если они будут, я планирую выложить к первым двум.

Стало интересно: а если бы был "дисклеймер конфиденциальности", но ты на него заранее не соглашался, тогда как? Сомневаюсь, что он имеет силу в таком случае.

KP>О себе. Автор нескольких предложений по изменению стандарта C++, которые были включены в стандарт. Имею золотые знаки отличия по C и C++ на Stackoverflow. Репутация составляет более 100 тысяч баллов.

Очень сомнительное достижение, по-моему, учитывая качество модерирования на SO. (Это если не врёт. В чём у меня сомнения — это ж кем надо быть, чтобы заведомо предположить идентичные ники на SO и RSDN.) Так кто это был-то?

KP> Это все я пишу, чтобы до твоих куриных мозгов хоть что-то дошло, правда, как показывает жизнь, таких ДЕБИЛОВ чему-либо не научишь. Тебе уже сказано было: "Заткнись!" Глядишь, и за умного сойдешь.

А от такого проезда так вообще товарищ сам себя опустил. Одним махом. Достижение-с...

Может, как архитектор они код и не пишут. И то очень сомнительно — задача написать прототип и проверить концептуальную работоспособность — вполне для архитектора.
Но ничто не мешает при этом часть времени отводить на другие виды деятельности.

Или Вы под "большими конторами" имеете в виду монстров старого образца, где архитектору писать самому код — западло, у него от этого испортится внутренняя карма и его перестанут уважать начальники и подчинённые, индус его посчитает относящимся к нижней касте, а в его Porsche испортят тормоза?

M> высокоуровневое видение продукта — это как заставить 500+ стратегических приложений работать вместе, а для этого нужно строчить стандарты и со всеми договариваться.

А ещё не забывать пить со всеми и раздаривать членство в закрытом клубе "только для джентльменов" с элитной порнухой.

M>P.S. Умиляют программисты, заявляющие что они "архитекторы" в CV.

Ну, умиляйтесь дальше. А они будут и дальше работать

Здравствуйте, Nuzhny, Вы писали:

N>Я как раз говорю, что для твоих данных при вызове std::sort может вызываться не быстрая сортировка, а другая. НИКТО не говорит, что в stl используется быстрая сортировка, по факту так ЧАСТО и происходит. Это просто функция-диспетчер, которая вызывает один из алгоритмов, в зависимости от своих внутренних соображений.

Кстати да. В GCC STL std::sort — вариант introsort с рекурсией только вправо (!!), разделяющий элемент = медиана, переход к heapsort по исчерпанию бюджета рекурсии в 2*log2(N), и финальным догоном вставками по всему массиву сразу (quick и heap не лезут в массивы короче 16 элементов).
Я тут всё понимаю, кроме ограничения, что рекурсия безоговорочно вправо.

Здравствуйте, Тёмчик, Вы писали:

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

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

Тё>Для одинаковых указателей будут одинаковые значения хэша. Ваш К.О.

ты не знаешь для чего нужен хеш? указатель в качестве хеша строки не канает, см выше причину

Здравствуйте, netch80, Вы писали:

I>>Разделяй и властвуй — это весь хлам, который нужно помнить для решения задачи навроде квиксорта.
I>>Что ты хочешь шеллом проверить, умение писать вложенные циклы на массиве? Это примерно первый месяц первого курса программирования.

N>Там специфика — нужно помнить, какие последовательности шагов дают действительно эффективную реализацию. Я вот помню уже очень смутно, но и то потому, что она меня "приколола". Обычный программист, скорее всего, откинет её как нелепую фигню.

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

Важный вопрос — понимание последовательностей. Но его как раз проще проверить отдельно, а не кусками кода.

Здравствуйте, sr_dev, Вы писали:

_>ты не знаешь для чего нужен хеш? указатель в качестве хеша строки не канает, см выше причину

Не надо плодить копии строк и будет тебе счастье. Простенький хэш из указателя получается элементарным циклическим сдвигом с последующим XOR по магическому номеру.

Здравствуйте, Artem Korneev, Вы писали:

AK>Я не архитектор, но Скиену частично перечитываю примерно раз в два года. Освежить память. Хорошо помогает в решении повседневных задач. Надо ещё Кормена купить.
Раз в 2 года открываешь сезон хождений по собеседованиям?

AK>Вчера вот просили написать реализации очереди используя массив и используя стэк.
Правда интересно, как (и главное зачем) эффективно зафигачить FIFO через LIFO. Очередь с приоритетом через стек не просили?

Здравствуйте, Олег К., Вы писали:

S>>И да, я сам хоть уже 10 лет не кодирую, но даже ночью готов рассказать quick/radix и т.п. sort, пересказать алгоритмы построения/нормализации/обхода деревьев, алгоритмы поиска, десяток основных паттернов и прочее что въелось мне в мозг так, что похоже уже никогда не забудется.

ОК>Звиздеть не мешки ворочать. Пока что единственное мерило умения это работающий код.

Это слишком дорогая техника, проверять работающим кодом вместо собеседоания.

Здравствуйте, Тёмчик, Вы писали:

Тё>Не надо плодить копии строк и будет тебе счастье. Простенький хэш из указателя получается элементарным циклическим сдвигом с последующим XOR по магическому номеру.

А проверять есть или нет уже у нас копия наверно предложишь с помощью хеш таблицы?)

Здравствуйте, StandAlone, Вы писали:

SA>Ты — не архитектор, и даже не программист, ты не сталкивался и не представляешь, как правильно проектируются сложные системы, и ЧТО может породить какой-нибудь великий знаток квиксортов. Живой пример — Ангуляр 1, который зачинали аутисты-олимпиадники противоестественным способом, в итоге получился мертворожденный кадавр, пожравший миллионы человеко-часов сотен тысяч прикладных разработчиков.
SA>Более того, кадавр вышел настолько ужасен, что даже самому Гуглу пришлось принять меры.

Ангуляр1 очень быстро вытеснил другие фремворки. И писали его ни разу не знатоки алгоритмов.

Здравствуйте, Тёмчик, Вы писали:

AK>>Я не архитектор, но Скиену частично перечитываю примерно раз в два года. Освежить память. Хорошо помогает в решении повседневных задач. Надо ещё Кормена купить.
Тё>Раз в 2 года открываешь сезон хождений по собеседованиям?

AK>>Вчера вот просили написать реализации очереди используя массив и используя стэк.
Тё>Правда интересно, как (и главное зачем) эффективно зафигачить FIFO через LIFO.

Стандартный ход для языков, где односвязный список — главная структура (LISP, Erlang...)

Тё> Очередь с приоритетом через стек не просили?

А в чём проблема? Читайте вот эту книгу, там есть всё и больше

Здравствуйте, Олег К., Вы писали:

ОК>Рано или поздно тебя отинтервьюирует такой же, хм, спец как и ты. Либо в силу своей глупости либо просто умышленно.
И? Что такое ужасное случится, чтобы этим запугивать? Они найдут общий язык и побеседуют к взаимному удовольствию.

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

Здравствуйте, Ikemefula, Вы писали:

I>>>Что ты хочешь шеллом проверить, умение писать вложенные циклы на массиве? Это примерно первый месяц первого курса программирования.

N>>Там специфика — нужно помнить, какие последовательности шагов дают действительно эффективную реализацию. Я вот помню уже очень смутно, но и то потому, что она меня "приколола". Обычный программист, скорее всего, откинет её как нелепую фигню.

I>Когда просят закодить, обычно проверяют технику кодинга. Т.е. умеет ли девелопер комбинировать или пишет каждый раз начисто со всеми приседаниями. Если умеет, то это означает довольно глубокое понимание написаного. Если не умеет, то и код будет соответствующий, мешанина на мешанине, или, что скорее всего, вообще не справится.

I>Важный вопрос — понимание последовательностей. Но его как раз проще проверить отдельно, а не кусками кода.

Ну вот именно. Поэтому или проверяющий должен сразу дать, какую последовательность шагов использовать, или это будет проверка чего угодно, но не умения собственно кодить.
А вот с быстрой сортировкой, пирамидальной и т.п. — таких проблем нет.

Здравствуйте, netch80, Вы писали:

N>Стандартный ход для языков, где односвязный список — главная структура (LISP, Erlang...)
Лисп про возврат функцию как переменную, эрланг про пересылку сообщений между агентами. При чем тут односвязный список?

Тё>> Очередь с приоритетом через стек не просили?

N>А в чём проблема? Читайте вот эту книгу, там есть всё и больше

N>Image: okasaki_chisto_funkcionalnye_struktury_dannyh.jpg
Много букв. Можно вкратце, как и зачем?

Здравствуйте, sr_dev, Вы писали:

_>А проверять есть или нет уже у нас копия наверно предложишь с помощью хеш таблицы?)

Стандартная хэш функция строки- соль, сдвиг, xor по символу.

Здравствуйте, Ikemefula, Вы писали:

I>Ангуляр1 очень быстро вытеснил другие фремворки.

А знаешь, почему? А совсем не благодаря его качеству.
Просто потому что разного рода погонщики кодеров с недостатком кислорода в левом полушарии дружным гуртом ринулись за Гуглом, погоняя перед собой ораву своих подопечных.
И теперь эти сотни тысяч в глубокой, глубочайшей жопе — потому что Гугл выкинул и их, и всю их работу, и весь Ангуляр один, полтора и прочее гугно на помоечку.

I>И писали его ни разу не знатоки алгоритмов.

А кто? Простые аутисты с функциональным недостатком способности к синтезу и анализу? Очень странно. Как правило, такие альтернативно одаренные личности прекрасно знают алгоритмы. Это вершина того, что они способны запомнить и осознать.

Здравствуйте, Тёмчик, Вы писали:

Тё>Стандартная хэш функция строки- соль, сдвиг, xor по символу.

Валяй, сыпь свою соль.
Заодно, раз пошла такая пьянка, расскажи (и по)чему равен оптимальный fill factor.

Здравствуйте, Тёмчик, Вы писали:

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

N>>Стандартный ход для языков, где односвязный список — главная структура (LISP, Erlang...)
Тё>Лисп про возврат функцию как переменную, эрланг про пересылку сообщений между агентами. При чем тут односвязный список?

На это могу только зафейспалмиться и посоветовать изучить матчасть. Потому что твоё знание обоих на уровне "слышал звон".

Тё>>> Очередь с приоритетом через стек не просили?

N>>А в чём проблема? Читайте вот эту книгу, там есть всё и больше

N>>Image: okasaki_chisto_funkcionalnye_struktury_dannyh.jpg
Тё>Много букв. Можно вкратце, как и зачем?

Вкратце — там, где основная структура — список, и изменяемые структуры нежелательны, для хорошей производительности нужно работать с данными особым образом. Как правило, разные мапы / словари / таблицы / etc. строятся из деревьев на списках, с сохранением существенной части этого дерева (пусть и в перетасованном виде) при любом изменении.

Не.. В этом плане у меня как-то по-другому получается. Последнее время интересные предложения поступают по рекоммендациям коллег, а не от рекрутеров. Поэтому собеседование получается одно. А алгоритмы освежаю из чисто практических соображений. Я не перечитываю книгу целиком, я перечитываю несколько глав из того что соприкасается с моими текущими задачами. Помогает привести мысли в порядок.
То же самое и с книгами по архитектуре приложений.

AK>>Вчера вот просили написать реализации очереди используя массив и используя стэк.
Тё>Правда интересно, как (и главное зачем) эффективно зафигачить FIFO через LIFO.

Про "эффективно" тут трудно говорить, а сама по себе задача известная и подробно разобрана в "Cracking the coding interview".
Берём два стэка и при необходимости меняем порядок элементов, перекидывая из одного стэка в другой.

Тё>Очередь с приоритетом через стек не просили?

Не, такого не просили.

Здравствуйте, Тёмчик, Вы писали:

Тё>Аморально ли проверять знание алгоритмов, если на рассматриваемую позицию человек не будет их писать?
Тё>...

Мораль — это традиции принятые в обществе, так сказать, нормы поведения.
Если в обществе принято пожимать руку при приветствии, то, например, китайского архитектора не пустят строить римские соборы и наоборот, несмотря на то, что рукопожатия и поклоны со сложенными ладонями вряд ли будут применяться непосредственно при строительстве.
Хорош или плох (правилен или неправилен) результат тоже будет оцениваться нормами принятыми в обществе.
Прикинь что было бы, если бы твой любимый поисковик написали бы те, кто не умеет сортировать канализационные люки? Думаю у тебя сразу бы отпали бы вопросы про аморальность вопросов на собеседовании.

Здравствуйте, StandAlone, Вы писали:

I>>Ангуляр1 очень быстро вытеснил другие фремворки.
SA>А знаешь, почему? А совсем не благодаря его качеству.
SA>Просто потому что разного рода погонщики кодеров с недостатком кислорода в левом полушарии дружным гуртом ринулись за Гуглом, погоняя перед собой ораву своих подопечных.

Это целая конспирологичесая теория. Ну, может, набор эмоций. Ангуляр это вообще говоря механика древняя как весь UI, простая, как автоматы Мили и Мура

Потому и стала популярной. До Ангуляра в моде было не столько решать проблемы, сколько исправлять JS, бровзер и тд. Всё это давно никому не надо.
Сейчас в вебе вагоны полу-программистов которые на Ангуляре обгоняют функционалистов-реактивщиков, объезжают на кривых. Пока реактивисты хвастаются классным кодом и стройной концепцией, полу-программисты на Ангуляре собирают бюджет и выкатывают продакшн. Как то так

Жизнь такая — уродцы вроде JS и Ангуляр срывают джекпот. Так было всегда.

SA>И теперь эти сотни тысяч в глубокой, глубочайшей жопе — потому что Гугл выкинул и их, и всю их работу, и весь Ангуляр один, полтора и прочее гугно на помоечку.

Те, кто не хочет мигрировать, спокойно пишут на первом — никто их работу не выкидывал. Во втором считай то же самое, только языковые конструкции и честное ООП вместо библиотечных приседаний.

Фронтенд безо всякого гугла устроен так, что его проще переписать независимо от фремворка или его отсутствия. Через год-два появляется новая концепция сайтов, которая напрочь ломает старую. Проще сломать и выбросить или просто пилить новую морду рядом.
Гугл собственно учел эту особенность, и потому пошел на риск с отказом от обратной совместимости.

I>>И писали его ни разу не знатоки алгоритмов.

SA>А кто?

Покажи, где там алгоритмические чудеса ?

Здравствуйте, Олег К., Вы писали:

I>>Сообщение даже с запикаными матами вообще говоря оскорбительное. Фактически — насилие. Ты точно уверен, что kaa.python не имеет права защитится от такого насилия ?

ОК>Насилие? Ты еще к психоаналитику ему посоветуй сходить.

Именно. Оскорбление == насилие.

Здравствуйте, Тёмчик, Вы писали:

Тё>иметь высокоуровневое видение продукта,каким он будет

это задача менеджера

Тё> какие фреймворки использовать.

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

Здравствуйте, Олег К., Вы писали:

ОК>>>Это ты сейчас в википедию заглянул?

G>>Нет
ОК>Я не верю тебе но допустим ты хранишь столько хлама у себя в голове.
Вот потому архитектов и надо драть по алгоритмам, чтобы понять кто реально опыт имеет, а кто просто занимается написанием бумажек с квадратиками и стрелочками.

Здравствуйте, Sharov, Вы писали:

Тё>>иметь высокоуровневое видение продукта,каким он будет

S>это задача менеджера

Не только менеджера, но и архитектора. Без глобального видения продукта архитектор никому не нужен.

S>в любом случае, архитекторы -- бывшие программисты, чего-то помнить и знать должны.

Архитектор не бывший, а действующий программист.

Здравствуйте, Ikemefula, Вы писали:

S>>это задача менеджера

I>Не только менеджера, но и архитектора. Без глобального видения продукта архитектор никому не нужен.

Архитектору глобальное видение ни к чему. Понимать рынок, как позиционировать продукт, как им будут пользоваться люди -- задача менеджера продукта.
Задача архитектора -- решение технических проблем в целом.

S>>в любом случае, архитекторы -- бывшие программисты, чего-то помнить и знать должны.

I>Архитектор не бывший, а действующий программист.

Код, который пишет арх. и кодер должны существенно отличаться. Человек, который рисует диаграммы, пишет тз, ставит задачу и кодер должны довольно сильно отличаться по навыкам.

Здравствуйте, Sharov, Вы писали:

I>>Не только менеджера, но и архитектора. Без глобального видения продукта архитектор никому не нужен.

S>Архитектору глобальное видение ни к чему. Понимать рынок, как позиционировать продукт, как им будут пользоваться люди -- задача менеджера продукта.
S>Задача архитектора -- решение технических проблем в целом.

"в целом" и есть то самое глобальное видение. Как будет позиционироваться продукт очень важно для разработки — фичи выпекаются задолго до того, как ими начнут пользоваться.
И менеджер, и архитект в курсе глобальной картины, только цели разные.

I>>Архитектор не бывший, а действующий программист.
S>Код, который пишет арх. и кодер должны существенно отличаться. Человек, который рисует диаграммы, пишет тз, ставит задачу и кодер должны довольно сильно отличаться по навыкам.

Архитект не пишет тз и задачи может не ставить. У него более другие задачи, вот, например https://www.sei.cmu.edu/architecture/research/previousresearch/duties.cfm

Здравствуйте, Тёмчик, Вы писали:

Если ты не можешь на написать на на С++17 в 2017, в этом есть какой то смысл.

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

G>Здравствуйте, Олег К., Вы писали:

Мне кажется в 2017 достаточно написать

template<class FwdIt, class Compare = std::less<>>
void quickSort(FwdIt first, FwdIt last, Compare cmp = Compare { }) {
auto const N = std::distance(first, last);
if (N <= 1)
return;
auto const pivot = std::next(first, N / 2);
std::nth_element(first, pivot, last, cmp);
quickSort(first, pivot, cmp);
quickSort(pivot, last, cmp);
}

Здравствуйте, andy., Вы писали:

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

A>Если ты не можешь на написать на на С++17 в 2017, в этом есть какой то смысл.

template<class FwdIt, class Compare = std::less<>>
void quickSort(FwdIt first, FwdIt last, Compare cmp = Compare { }) {
auto const N = std::distance(first, last);
if (N <= 1)
return;
auto const pivot = std::next(first, N / 2);
std::nth_element(first, pivot, last, cmp);
quickSort(first, pivot, cmp);
quickSort(pivot, last, cmp);
}

Здравствуйте, andy., Вы писали:

A>Мне кажется в 2017 достаточно написать
Мне кажется достаточно написать std::sort уже лет 20. Но для собеседования не прокатит.

Здравствуйте, andy., Вы писали:

A> auto const pivot = std::next(first, N / 2);

Если использовать nth_element, то pivot это неправильное название.

A> std::nth_element(first, pivot, last, cmp);

Здесь по смыслу и духу quicksort не std::nth_element нужен (который к тому же внутри обычно реализуется как обрезанный quick/intro-sort), а std::partition.

Здравствуйте, Artem Korneev, Вы писали:

AK>Не.. В этом плане у меня как-то по-другому получается. Последнее время интересные предложения поступают по рекоммендациям коллег, а не от рекрутеров. Поэтому собеседование получается одно. А алгоритмы освежаю из чисто практических соображений. Я не перечитываю книгу целиком, я перечитываю несколько глав из того что соприкасается с моими текущими задачами. Помогает привести мысли в порядок.
AK>То же самое и с книгами по архитектуре приложений.
Хорошо вам в США. Я правда не очень понимаю, зачем "освежать алгоритмы из практических соображений"- ты либо практически используешь алгоритмы в работе, ну тогда освежать ничего не надо. Там скорее интересуешься новыми веяниями, читаешь соответсвующие журналы. Либо ты на работе тупеешь, а на интервью везде алгоритмы спрашивают (ну просто так заведено)- тогда практические соображения как раз освежить эти вопросы с собеседований в памяти.

AK>>>Вчера вот просили написать реализации очереди используя массив и используя стэк.
Тё>>Правда интересно, как (и главное зачем) эффективно зафигачить FIFO через LIFO.

AK>Про "эффективно" тут трудно говорить, а сама по себе задача известная и подробно разобрана в "Cracking the coding interview".
AK>Берём два стэка и при необходимости меняем порядок элементов, перекидывая из одного стэка в другой.
Либо рекурсивный вызов. Если эффективность не требуется- значит ничего нового мне эта книжка бы не дала. Книжка наверное для определённой аудитории.

Тё>>Очередь с приоритетом через стек не просили?

AK>Не, такого не просили.
Потому, что про это не было в "Cracking the coding interview"?

Здравствуйте, Тёмчик, Вы писали:

Тё>не очень понимаю, зачем "освежать алгоритмы из практических соображений"- ты либо практически используешь алгоритмы в работе, ну тогда освежать ничего не надо.

Ну так задачи ж всё время разные. Я с одного раза запомнить все алгоритмы не смогу.

Кроме того, отдельная тема — применимость алгоритмов и структур данных. Мне не всегда сходу очевидно, что какую-то часть своей системы я могу соптимизировать, применив ту или иную структуру данных. А тут, бывает, почитаю какую-нибудь историю из жизни у Скиены или Кнута и вдруг осеняет, что у меня схожий случай.

Тё>>>Очередь с приоритетом через стек не просили?

AK>>Не, такого не просили.
Тё>Потому, что про это не было в "Cracking the coding interview"?

При всём желании, в одно интервью нельзя вместить все задания из книги.

А задания, в общем-то, не только по книге попадаются. Например, меня попросили написать реализацию слияния соседствующих/пересекающихся интервалов — задача, сама по себе, вполне простая, единственный нюанс в том, чтобы правильно обрабатывать более двух сливающихся интервалов. Правда, написать попросили на чистом Си, я на нём последний раз писал ровно 5 лет назад — 17 апреля 2012-го был мой последний день работы в РБК, где я писал на C, C++ и Erlang.

Здравствуйте, andy., Вы писали:

A>Мне кажется в 2017 достаточно написать

A>template<class FwdIt, class Compare = std::less<>>
A>void quickSort(FwdIt first, FwdIt last, Compare cmp = Compare { }) {
A>  auto const N = std::distance(first, last);
A>  if (N <= 1)
A>    return;
A>  auto const pivot = std::next(first, N / 2);
A>  std::nth_element(first, pivot, last, cmp);
A>  quickSort(first, pivot, cmp);
A>  quickSort(pivot, last, cmp);
A>}

Мне чисто для интересу — где здесь перестановки?

Здравствуйте, Ikemefula, Вы писали:

I>Мне чисто для интересу — где здесь перестановки?
Внезапно в std::nth_element, очевидно да?

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

I>>Мне чисто для интересу — где здесь перестановки?
G>Внезапно в std::nth_element, очевидно да?

Нет.

Здравствуйте, De-Bill, Вы писали:

I>>Написание хеш-таблицы это примерно экзамен за первый курс унивеситета.

DB>Написание хеш-таблицы без хеш-функции — абсолютно бессмысленное дело. Это также как делать автомобиль приколотив к бревну 4 колеса.

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

DB>>Написание хеш-таблицы без хеш-функции — абсолютно бессмысленное дело. Это также как делать автомобиль приколотив к бревну 4 колеса.
I>Непонятная аналогия. Реализация хеш-таблицы требует самых разных умений, скажем, работа и с массивами, и со списками, кое какой теории и разных других вещей, иначе ничего не выйдет.

Приколачивание колёс к бревну тоже требует разных умений. Умение держать молоток, умение приставлять гвоздь пальцами к месту, в которое этот гвоздь нужно вбить, умение попадать молотком по гвоздю а не по пальцам. Ничуть не менее лёгкие умения, чем умение работать с массивами и связанными списками. Только эти умения не имеют ничего общего с автомбилестроением. Также как и реализация массива списков ничего не имеет общего с построением эффективного контейнера или с оптимизацией использования библиотечного.

Здравствуйте, De-Bill, Вы писали:

DB>>>Написание хеш-таблицы без хеш-функции — абсолютно бессмысленное дело. Это также как делать автомобиль приколотив к бревну 4 колеса.
I>>Непонятная аналогия. Реализация хеш-таблицы требует самых разных умений, скажем, работа и с массивами, и со списками, кое какой теории и разных других вещей, иначе ничего не выйдет.

DB>Приколачивание колёс к бревну тоже требует разных умений. Умение держать молоток, умение приставлять гвоздь пальцами к месту, в которое этот гвоздь нужно вбить, умение попадать молотком по гвоздю а не по пальцам. Ничуть не менее лёгкие умения, чем умение работать с массивами и связанными списками. Только эти умения не имеют ничего общего с автомбилестроением. Также как и реализация массива списков ничего не имеет общего с построением эффективного контейнера или с оптимизацией использования библиотечного.

А почему ты решил, что написание хеш-таблицы это про построение эффективного контейнера или про оптимизацию использования библиотечного ? Ни то, ни другое не требует написания кода. Их можно и нужно проверять _после_ или _вместо_.

Здравствуйте, Олег К., Вы писали:

ОК>>>Это ты сейчас в википедию заглянул?

G>>Нет

ОК>Я не верю тебе

проекции.. по себе судите.

ОК>но допустим ты хранишь столько хлама у себя в голове.

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

Здравствуйте, netch80, Вы писали:

N>Image: okasaki_chisto_funkcionalnye_struktury_dannyh.jpg
Чисто конкретно

Здравствуйте, Cyberax, Вы писали:

C>Вот потому архитектов и надо драть по алгоритмам, чтобы понять кто реально опыт имеет, а кто просто занимается написанием бумажек с квадратиками и стрелочками.
При этом на работе он будет преимущественно как раз писать бумажки с квадратиками да стрелочками

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

G>Думаешь интервьювер найдет? И надо оно ему? Это же помнить наизусть весь код надо и только для того, чтобы потешить самолюбие.
Мне попадались некоторые конторы с настолько обострённым equal opportunities, что там все вопросы интервью заранее согласовывались и утверждались кучей ~~бездельников~~"менеджеров". Так что человеку, который целыми днями задаёт одни и те же вопросы, будет совсем несложно выучить "правильные" ответы с точностью до последней запятой.

Здравствуйте, StandAlone, Вы писали:

SA>Валяй, сыпь свою соль.
SA>Заодно, раз пошла такая пьянка, расскажи (и по)чему равен оптимальный fill factor.
Ты ж с жабником разговариваешь. У них наверняка есть какая-нить абстрактная фабрика абстрактных фабрик, которая родит нужный адаптер для моста, который сам чё-то там посчитает

Здравствуйте, koandrew, Вы писали:

K>Здравствуйте, StandAlone, Вы писали:

SA>>Валяй, сыпь свою соль.
SA>>Заодно, раз пошла такая пьянка, расскажи (и по)чему равен оптимальный fill factor.
K>Ты ж с жабником разговариваешь. У них наверняка есть какая-нить абстрактная фабрика абстрактных фабрик, которая родит нужный адаптер для моста, который сам чё-то там посчитает

По умолчанию fill factor 0.75. Я xz сколько он "оптимальный"- наверное от ограничений зависит. Вообще, когда для кого-то не очевидна связь хэш функции и псевдо-случайного генератора, там сложно найти общий язык.

Здравствуйте, koandrew, Вы писали:

C>>Вот потому архитектов и надо драть по алгоритмам, чтобы понять кто реально опыт имеет, а кто просто занимается написанием бумажек с квадратиками и стрелочками.
K>При этом на работе он будет преимущественно как раз писать бумажки с квадратиками да стрелочками

Ага. Но тут ведь проблема в том, что неправильные квадратики со стрелочками неправильно работают. И без реального опыта сложно будет понять почему.

От:	Тёмчик	жж
Дата:	09.04.17 08:39
Оценка:

	От:	_Raz_
	Дата:	09.04.17 09:59
	Оценка:	-1

От:	kaa.python	РСДН профессионально мёртв и завален ватой.
Дата:	09.04.17 10:08
Оценка:	1 (1) +17 -2

От:	Тёмчик	жж
Дата:	09.04.17 21:38
Оценка:

	От:	Олег К.
	Дата:	09.04.17 21:53
	Оценка:

От:	gandjustas	http://blog.gandjustas.ru/
Дата:	10.04.17 01:46
Оценка:	+1

От:	MozgC	http://nightcoder.livejournal.com
Дата:	10.04.17 01:48
Оценка:

От:	Nuzhny	https://github.com/Nuzhny007
Дата:	10.04.17 04:13
Оценка:

От:	Kernan	https://rsdn.ru/forum/flame.politics/
Дата:	10.04.17 14:01
Оценка:	+1

От:	StatujaLeha	на правах ИМХО
Дата:	10.04.17 18:02
Оценка:

От:	Ikemefula	http://blogs.rsdn.org/ikemefula
Дата:	10.04.17 19:12
Оценка:	+1 -1

	От:	Evgeny.Panasyuk
	Дата:	11.04.17 08:41
	Оценка:

От:	AndrewVK	http://blogs.rsdn.org/avk
Дата:	11.04.17 17:28
Оценка:

	От:	sharpcoder
	Дата:	12.04.17 09:49
	Оценка:	1 (1) +5

От:	Vetal_ca	http://vetal.ca
Дата:	12.04.17 14:57
Оценка:	+1

	От:	StandAlone
	Дата:	13.04.17 15:54
	Оценка:	5 (1)

От:	Dziman	http://github.com/Dziman
Дата:	13.04.17 17:09
Оценка:

От:	Artem Korneev	https://www.linkedin.com/in/artemkorneev/
Дата:	13.04.17 18:10
Оценка:

От:	koandrew	http://thingselectronic.blogspot.ca/
Дата:	13.04.17 18:39
Оценка:

От:	netch80	http://netch80.dreamwidth.org/
Дата:	14.04.17 04:37
Оценка: