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

X>Конечно. Удивительно то, как много матёрых перцев на этом буксуют.

Они не ожидают такого разгула дебилизма от интервьюера.

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



PM>Или оставаться в 1D, но двигаться дальше — циклический сдвиг массива на k N позиций влево или вправо, само собой, тоже inplace.

эту задачку давали в google на разминке в 15 году

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

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

A>>Это не работает. Потому что хороший специалист не станет тренироваться решать задачки на собеседованиях, а тот человек, который работать не умеет и ничего из себя не представляет — будет смотреться замечательно на фоне всех остальных. Поскольку у него выбора иного нету.

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

Вопрос же не в том можешь или нет. А тех обстоятельствах, в которых тебя вынуждают этим заниматься.
Мне жаловались разные люди, что обстановка на собеседованиях не располагает ни разу, к такого рода занятиям. Грубо говоря пыхтеть на листочке бумаги ручкой, когда рядом восседает откровенно зевающий собеседователь.
Т.е. задачка дерьмо, потому что есть лишь один годный вариант решения, но есть ряд вариантов облажаться при этом. Проверить мышление-рассуждение кандидата задачка не позволяет. Даётся задачка в таких обстоятельствах, что почти наверняка нетренированный человек в чём-нибудь да ошибётся. И в этом ожидании ошибки от кандидата и весь смысл, весь сок давания данной задачи. Чтобы у собеседующего появилась возможность ткнуть кандидата в некую ошибку в некой очень простетской задачке.

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

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

A>>На данный момент, выявлено две жуткие дурости, т.е. придётся осознать две вещи:
A>>1. на собеседовании квалификацию не показывают, это не испытание кандидатов
A>>2. собеседование проводят не для того, чтобы кандидатов между собой сравнивать

I>Для чего проводят собеседование?

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

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

PM>>Или оставаться в 1D, но двигаться дальше — циклический сдвиг массива на k N позиций влево или вправо, само собой, тоже inplace.

S>эту задачку давали в google на разминке в 15 году

Ну-ну, кто бы в этом сомневался. Во что пишет про алгоритм block swap Дж. Бентли в "Жемчужинах программирования"

Б. Керниган и П. Дж. Плоджер пользовались именно этим методом для перемещения строк в текстовом редакторе в своей книге (В. Kernighan, P. J. Plauger, Software Tools in Pascal, 1981). Керниган пишет, что эта функция заработала правильно с первого же запуска, тогда как их предыдущая версия, использовавшая связный список, содержала несколько ошибок. Этот же код используется в некоторых текстовых редакторах, включая тот, в котором я впервые набрал настоящую главу. Кен Томпсон (Ken Thompson) написал этот редактор с функцией reverse в 1971 году, и он утверждает, что она уже тогда была легендарной.

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

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

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

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

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

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

I>>Для чего проводят собеседование?

A>Для того чтобы людей подбирать?

Подбирать по какому принципу?

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

S>несколько хороших задачь которымиможно заменить разоворот списка

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

struct linked_list
{
    struct node
    {
        int data;
        node* next;
        node* prev;
    };
    node* head;
    node* tail;
};

linked_list list;

void traverse(linked_list list, ...);

traverse(list, ???); // forward
traverse(list, ???); // backward

Дополнительный бонус за решение без if, штраф за читерство с шаблонами С++ или макросами С. В реализуемости на управляемых языках не уверен.

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

I>>Более того, не все ведь к С++ сводится. Часто это джыт, который, вобщем, сильно дохлый супротив обычного компилятора.
S>Джытами не пользуюсь, но вот что мне гугл дает:
S>

S>There’s effectively zero difference between using division versus a shift with numbers this small. Those are nanoseconds, after all. Using a negative number shows no difference in the result.

S>With this we can now definitely say that replacing value / 2 with value >> 1 offers no benefit. Stop doing it for arithmetic operations and reserve it only for strictly bitwise things!

Это написано чтобы люди перестали в С коде фигачить shifts везде где ни попадя. Компилятор же вполне может поменять div на shr.

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

N>>А почему не перспективное? А почему матриц, а не матрицу на вектор? А нужна ли там вообще матрица?
Тё>Представить каждый пиксел как вектор координатами (x,y) и умножать на матрицу афинного преобразования, по аналогии с 3d.

Это ты щас ядрёной боНбой по таракану собрался бить.

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

X>Тут то и нюанс. Многие начинают обходить source буфер. И всё — приплыли.
Ага, у таких появляются "дырки" в результате.
Знал людей которые упирались и ни в какую не хотели "перевернуть" логику и ходить таки по destination, ибо "так будет дольше!" и упорно изобретали велосипед по предотвращению tears.

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

IID>tearing то откуда возьмётся ?
Не тот tearing который VSync, а когда результат получается с прорехами, когда итерацию делают не по dest а по src.

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

PM>Дополнительный бонус за решение без if
Да банальный pointer arithmetic, использование bool параметра для выбора который из двух указателей в парах next/prev head/tail брать через "pointerPtr[param]"

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

Pzz>P.S. Я даже умудрился в повседневной работе использовать функцию, которая переставляет местами две "половины" массива разного размера, используя O(1) дополнительной памяти и за время O(n):

Pzz>[AAAAA][BBBBBBBBBBBBBB] -> [BBBBBBBBBBBBBB][AAAAA]

Так это разворот строки

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

Pzz>>[AAAAA][BBBBBBBBBBBBBB] -> [BBBBBBBBBBBBBB][AAAAA]

Тё>Так это разворот строки

Нет.

[0123456][ABCDEFGHIJKLMNOPQR] -> [ABCDEFGHIJKLMNOPQR][0123456]

Так понятнее?

И да, это эквиавалентно упомянутому здесь циклическому сдвигу массива in place.

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


CC> результат получается с прорехами, когда итерацию делают не по dest а по src.

Логичный результат. Если из src считать dst- будут "прорехи", но если из dst считать src- будут "складки". Очевидно, можно проецирующую координату оставить в double без округления, и копировать субпиксельно, т.е. раскидывать на "пятно" из покрытых координатой пикселов. Либо если reverse- брать значение пиксела с покрытого пятна из нескольких пикселов, в пропорциях покрытия. Либо почитать про билинейную фильтрацию.

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

Тё>>Так это разворот строки

Pzz>Нет.

Pzz>[0123456][ABCDEFGHIJKLMNOPQR] -> [ABCDEFGHIJKLMNOPQR][0123456]

Pzz>Так понятнее?

Pzz>И да, это эквиавалентно упомянутому здесь циклическому сдвигу массива in place.

Ты так и не понял? ел кашу->кашу ел. Разворот строки, как он есть.

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

Тё>Очевидно, можно проецирующую координату оставить в double без округления, и копировать субпиксельно, т.е. раскидывать на "пятно" из покрытых координатой пикселов. Либо если reverse- брать значение пиксела с покрытого пятна из нескольких пикселов, в пропорциях покрытия. Либо почитать про билинейную фильтрацию.

Ты уже "не сдал", ещё с матрицами, чего уж теперь суетиться?

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

Тё>>Очевидно, можно проецирующую координату оставить в double без округления, и копировать субпиксельно, т.е. раскидывать на "пятно" из покрытых координатой пикселов. Либо если reverse- брать значение пиксела с покрытого пятна из нескольких пикселов, в пропорциях покрытия. Либо почитать про билинейную фильтрацию.

CC>Ты уже "не сдал", ещё с матрицами, чего уж теперь суетиться?

Формула с синусами-косинусами- это продукт матрица вращения на вектор. Матрица вращения- частный случай аффинной матрицы.

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

Тё>Ты так и не понял? ел кашу->кашу ел. Разворот строки, как он есть.

Разворот, это ел кашу->ушак ле