Аморально ли требовать алгоритмы на архитектора
От: Тёмчик Австралия жж
Дата: 09.04.17 08:39
Оценка: :)
Аморально ли проверять знание алгоритмов, если на рассматриваемую позицию человек не будет их писать? Ведь задача архитектора- иметь высокоуровневое видение продукта, каким он будет и выбор, какие фреймворки использовать.

Дискас.
Re: Аморально ли требовать алгоритмы на архитектора
От: _Raz_  
Дата: 09.04.17 09:59
Оценка: -1
Здравствуйте, Тёмчик, Вы писали:

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


Аморально считать что должность говорит о предметной области.
... << RSDN@Home 1.0.0 alpha 5 rev. 0>>
Re: Аморально ли требовать алгоритмы на архитектора
От: kaa.python Ниоткуда РСДН профессионально мёртв и завален ватой.
Дата: 09.04.17 10:08
Оценка: 1 (1) +17 -2
Здравствуйте, Тёмчик, Вы писали:

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


Аморально не знать основных алгоритмов и структур данных если ты позиционируешь себя как архитектор
Re[2]: Аморально ли требовать алгоритмы на архитектора
От: Тёмчик Австралия жж
Дата: 09.04.17 21:38
Оценка:
Здравствуйте, kaa.python, Вы писали:

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


Смотря что считать основными алгоритмами. Задачки про гномиков, или про обход лабиринта- это основные алгоритмы?
Re[2]: Аморально ли требовать алгоритмы на архитектора
От: Олег К.  
Дата: 09.04.17 21:53
Оценка:
Тё>>Аморально ли проверять знание алгоритмов, если на рассматриваемую позицию человек не будет их писать? Ведь задача архитектора- иметь высокоуровневое видение продукта, каким он будет и выбор, какие фреймворки использовать.

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


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

Что? Не знаешь? Аморально, однако.
Re[3]: Аморально ли требовать алгоритмы на архитектора
От: kaa.python Ниоткуда РСДН профессионально мёртв и завален ватой.
Дата: 09.04.17 23:52
Оценка: +4 -2
Здравствуйте, Олег К., Вы писали:

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

ОК>Что? Не знаешь? Аморально, однако.

По твоему это сложная задача? Ну я теперь понимаю почему ты так факелом полыхаешь когда речь заходит о вопросах отличных от "расскажите о ваших предыдущих проектах".
Re[3]: Аморально ли требовать алгоритмы на архитектора
От: gandjustas Россия http://blog.gandjustas.ru/
Дата: 10.04.17 01:46
Оценка: +1 :)
Здравствуйте, Олег К., Вы писали:

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


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, да и вообще программирую крайне редко.
Re: Аморально ли требовать алгоритмы на архитектора
От: MozgC США http://nightcoder.livejournal.com
Дата: 10.04.17 01:48
Оценка:
Смотря каких алгоритмов. Имхо можно простую задачку дать минут на 5-20 (при этом если нужно оставлять собеседумоего одного, чтобы он спокойно порешал) чисто проверить что мозги не затекли.
Re[4]: Аморально ли требовать алгоритмы на архитектора
От: Олег К.  
Дата: 10.04.17 01:52
Оценка:
ОК>>Ну-ка, ну-ка, давай без понтов, а? Напиши-ка, никуда не заглядывая, обычный Quick Sort. А заодно расскажи все о его run-time complexity!
ОК>>Что? Не знаешь? Аморально, однако.

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


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

Это ты сейчас в википедию заглянул?
Re[5]: Аморально ли требовать алгоритмы на архитектора
От: gandjustas Россия http://blog.gandjustas.ru/
Дата: 10.04.17 01:54
Оценка:
Здравствуйте, Олег К., Вы писали:

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


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

Нет
Re[6]: Аморально ли требовать алгоритмы на архитектора
От: Олег К.  
Дата: 10.04.17 02:08
Оценка:
Здравствуйте, gandjustas, Вы писали:

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


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


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

G>Нет

Я не верю тебе но допустим ты хранишь столько хлама у себя в голове. Если ты такой вундеркинд, напиши еще и shell sort заодно. Для тебя это не должно составить труда.
Re[5]: Аморально ли требовать алгоритмы на архитектора
От: kaa.python Ниоткуда РСДН профессионально мёртв и завален ватой.
Дата: 10.04.17 02:13
Оценка: +4 -2
Здравствуйте, Олег К., Вы писали:

ОК>Где код?


А зачем мне приводить код такому трололо как ты? Ниже тебе дали код и ты сходу обвинил в использовании Википедии, что было ожидаемо. Если тебе человек напишет "и shell sort заодно", ты найдешь еще к чему придраться. Ты очень предсказуемый
Re[7]: Аморально ли требовать алгоритмы на архитектора
От: gandjustas Россия http://blog.gandjustas.ru/
Дата: 10.04.17 02:16
Оценка:
Здравствуйте, Олег К., Вы писали:

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

G>>Нет

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

Аргумент!

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

Сколько хлама? Три строки псевдокода?

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

К сожалению не помню в чем идея shell sort. первый и последний раз я читал про него лет 15 назад.
Re[6]: Аморально ли требовать алгоритмы на архитектора
От: Олег К.  
Дата: 10.04.17 02:32
Оценка: 1 (1) +2 -2
ОК>>Где код?

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


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

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


Первое. Я не верю что ты помнишь как работает Quick sort внутри после 15 лет работы если ты только недавно не перечитал книжку по алгоритмам. Второе. Я продемонстрировал что много ума не надо опустить кандидата. Именно такой подход и практикуют экзаменаторы вроде тебя. Достаточно делать линейный поиск, но если хочешь, я могу выбрать алгоритм посложнее специально ради тебя. Чтобы опустить тебя наверняка. Для этого тоже много ума не надо. Третье. Перечитай фразу выше.
Re[4]: Аморально ли требовать алгоритмы на архитектора
От: Тёмчик Австралия жж
Дата: 10.04.17 02:33
Оценка: +2 -1
Здравствуйте, 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 грамотно реализовать- нетривиальная задача.
Re[7]: Аморально ли требовать алгоритмы на архитектора
От: kaa.python Ниоткуда РСДН профессионально мёртв и завален ватой.
Дата: 10.04.17 02:36
Оценка: +2 -3
Здравствуйте, Олег К., Вы писали:

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


Ну, раз уж алгоритмические вопросы заставляют таким факелом полыхать кандидатов вроде тебя, такие вопросы просто необходимо задавать для грамотного отбора!
Отредактировано 10.04.2017 2:37 kaa.python . Предыдущая версия .
Re[8]: Аморально ли требовать алгоритмы на архитектора
От: Олег К.  
Дата: 10.04.17 02:40
Оценка:
ОК>>>>Это ты сейчас в википедию заглянул?
G>>>Нет

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

G> Аргумент!

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

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

G>Сколько хлама? Три строки псевдокода?

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

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

G>К сожалению не помню в чем идея shell sort. первый и последний раз я читал про него лет 15 назад.

Ха! То есть, получается, что ты не знаешь стандартные алгоритмы? Ну это согласно питону.
Re[5]: Аморально ли требовать алгоритмы на архитектора
От: gandjustas Россия http://blog.gandjustas.ru/
Дата: 10.04.17 02:41
Оценка:
.Здравствуйте, Тёмчик, Вы писали:

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

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

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

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

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

Тё>qsort грамотно реализовать- нетривиальная задача.
Это не надо делать. надо уметь показать на собеседовании что ты знаешь как это сделать.
Re[8]: Аморально ли требовать алгоритмы на архитектора
От: Олег К.  
Дата: 10.04.17 02:44
Оценка:
ОК>>Первое. Я не верю что ты помнишь как работает Quick sort внутри после 15 лет работы если ты только недавно не перечитал книжку по алгоритмам. Второе. Я продемонстрировал что много ума не надо опустить кандидата. Именно такой подход и практикуют экзаменаторы вроде тебя. Достаточно делать линейный поиск, но если хочешь, я могу выбрать алгоритм посложнее специально ради тебя. Чтобы опустить тебя наверняка. Для этого тоже много ума не надо. Третье. Перечитай фразу выше.

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


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