Здравствуйте, мыщъх, Вы писали:

M>>Большее как-то так?
M>>((x ^ (x-1)) + 1) | (x & (x-1))
М>поставил 3 получил 2. как-то не так.

Начал проверять за компом, вышло так. То просто неправильный алгоритм был, сейчас вроде верно
[сcode]
#include <stdio.h>

int main(int argc, char* argv[])
{
unsigned int x;
scanf("%u", &x);
unsigned int y = (x|((x|(x-1))+1))^((((x|(x-1))^((x|(x-1))+1))+1)>>2);
printf("%u\n", y);
return 0;
}
[/сcode]

M>>Меньшее с условием получается, примерно так
М>могу показать свое решение если интересно.

Идея примерно понятна

Здравствуйте, мыщъх, Вы писали:

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

M>>Здравствуйте, мыщъх, Вы писали:

M>>Как такой вопрос: быстрая реализация BSF для uint64_t на C, без ассемблера?
М>встречный вопрос -- а накуя? вы можете назвать хоть один компилятор где нет таких расширений? в ms, gcc, intel'е они есть и libc есть.

(1) Для разминки мозгов
(2) Вопрос скорее в платформах. Есть спарки, есть ARM-ы. Какой там синтаксис соответствующей ассемблерной команды я сказать не могу, да и проверить не могу. Но могу прописать в configure, что если у нас на x86 и не x86_64, то включить общий вариант функции. А там энтузазисты поправят.

М>быстрая реализация на си? гм... без профайлера не скажу. табличная реализация vs калькуляция. трудно сказать, что будет быстрее на современных процессорах, тем более без указания типа процессора.

Одними и самых быстрых считается эти, по сути 4-5 ассемблерных команд без всяких условий.

int trailingZeroCount(U64 bb) {
   static const int lookup67[67+1] = {
      64,  0,  1, 39,  2, 15, 40, 23,
       3, 12, 16, 59, 41, 19, 24, 54,
       4, -1, 13, 10, 17, 62, 60, 28,
      42, 30, 20, 51, 25, 44, 55, 47,
       5, 32, -1, 38, 14, 22, 11, 58,
      18, 53, 63,  9, 61, 27, 29, 50,
      43, 46, 31, 37, 21, 57, 52,  8,
      26, 49, 45, 36, 56,  7, 48, 35,
       6, 34, 33, -1 };
   return lookup67[(bb & -bb) % 67];
}

const int index64[64] = {
   63,  0, 58,  1, 59, 47, 53,  2,
   60, 39, 48, 27, 54, 33, 42,  3,
   61, 51, 37, 40, 49, 18, 28, 20,
   55, 30, 34, 11, 43, 14, 22,  4,
   62, 57, 46, 52, 38, 26, 32, 41,
   50, 36, 17, 19, 29, 10, 13, 21,
   56, 45, 25, 31, 35, 16,  9, 12,
   44, 24, 15,  8, 23,  7,  6,  5
};
 
int bitScanForward(U64 bb) {
   const U64 debruijn64 = C64(0x07EDD5E59A4E28C2);
   assert (bb != 0);
   return index64[((bb & -bb) * debruijn64) >> 58];
}

Некоторые другие быстрые алгоритмы можно найти тут.

Здравствуйте, мыщъх, Вы писали:

M>>Как такой вопрос: быстрая реализация BSF для uint64_t на C, без ассемблера?
М>быстрая -- это на собеседовании?
Нет, не на собеседование. Имхо, это надо запомнить, потому что понять это нивазможно! Но тоже с битами.

Здравствуйте, Паблик Морозов, Вы писали:

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

ПМ>Я не совсем понимаю "once in a lifetime opportunity". Это типа стартап с презентацией в power-point-е?

И ты берешься проводить собеседования, не зная таких элементарных вещей? Стыдно должно быть

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

M>Здравствуйте, мыщъх, Вы писали:

М>>быстрая реализация на си? гм... без профайлера не скажу. табличная реализация vs калькуляция. трудно сказать, что будет быстрее на современных процессорах, тем более без указания типа процессора.

M>Одними и самых быстрых считается эти, по сути 4-5 ассемблерных команд без всяких условий.
1) надеюсь, вы не ожидаете, что этот код напишут прямо на собеседовании?
2) тормозную реализацию можно написать и на питоне (на глаз должно хватить дюжины строк);
3) даже для системщиков это очень узкий вопрос и не уверен, что показательный;
4) в качестве тестового задания -- ИМХО слишком просто (ответ быстро находится в иннете);
5) а почему вы против вычислительных алгосов? на x86 с LEA получается довольно шустро, даже если писать на си -- есть шанс, что оптимизатор это заоптимизирует как надо

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

хотя вы меня натолкнули на интересный вопрос для собеседования -- "в каком порядке искать ответ на вопрос". гугл? гугл не всемогущ. поиск по патентным базам зачастую сокращает ваш путь в десятки и сотни раз. как-то был случай в жизни. попросили реконструировать проприетарный протокол. протокол закрытый, но запатентованный. причем, протокол сношения с микроконтроллером, которому передается микропрграмма. для страховки заказчик дал задачу мне и еще одному парню. я быстро нашел патент и убедился, что опкоды совпадают на 90% (со времен подачи патента протокол претерпел несколько ревизий), в результате послал заказчику полную реконструкцию. мой коллега убил гораздо больше времени и реконстрировал лишь 30% опкодов (т.е. остальные не юзались в конкретной версии клиента, которую он реверсил).

в патентнах находится по меньше мере 60% ответов на мои вопросы, 30% находит гугл, 10% твиттер и потому когда человек говоит "що тут думать -- тут гуглить надо" с ним все ясно.

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

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

Здравствуйте, мыщъх, Вы писали:

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

G>>Здравствуйте, Паблик Морозов, Вы писали:

G>>Каким образом переворачивание списков или еще какие-то тупые задачи, не имеющие отношения к реальной работе что-то показывают?
М>разворот списка решается как на си (и других языках, активно работающих с указателями) так и на питоне с java-script и всяких прочих руби, где указателей вообще нет. более того, реверс списка вполне повседневная задача. вывести список в обратном порядке на печать -- это экзотика?

Во Всех языках есть готовые библиотеки для этого.

G>> Не говоря уже шапках и гномах.
М>а чем вы так недовольны? свои первые собеседования я заваливал и жутко волновался, впрочем, оффера все-таки получал (т.к. собеседование это не экзамен и не бинарная логика, мой ответ был неправильным, но ход мыслей — зачотным). очень быстро я насобачился на этих задачах до такой степени, что проходил телефонные интевью, прижимая плечом трубку к уху и решая текущие дела без отрыва от производства. только мое торжество длилось недолго. меня просто перестали собеседовать. совпадене или нет -- не знаю. а может у HR'ов глобальная база есть -- не в курсе.
Ну вот я и говорю, что решение задач про гномиков это скилл, к работе не имеющий отношения. И недоволен тем что некоторые считают такие задачи хорошим фильтром на собеседованиях.

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

М>могу показать свое решение если интересно.

да, давай свое, интересно

М>лично я обработки ошибок возложил на вызывающую функцию. типа:

я бы тоже так сделал; это выдает доп. требование к алгоритму -- ошибаться только в правильную сторону

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

А я как раз давал без подвохов и без необходимости думать. Просто на базовые программерские навыки: решить что и как сделать публичным, какие стандартные интерфейсы поддержать, написать простую функцию и самому ее протестировать.
Кстати, задачки на простейший дизайн классов вообще полезная вещь. Помню как лет 10 назад один чувак, преподававший ООП в одном из питерских технических ВУЗов на вопрос о пользе множественного наследования привел пример объекта "окно и в нем кнопка", который предлагалось унаследовать от обоих

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

G>Здравствуйте, мыщъх, Вы писали:

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

G> Ну вот я и говорю, что решение задач про гномиков это скилл, к работе не имеющий отношения.
не спрашивали меня за гномиков (это за тех гномиков, из которых уши кодов коррекции ошибок торчат?). у нас вообще интересные интервью были с жаркими спорами, в которые постепенно втягивался весь отдел. интерью ведь не экзамен, а беседа двух умных людей и тут намного важнее позитивное впечатление произвести, чем дать правильный ответ на вопрос.

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

G> Мне и факты предоставлять не надо, каждый второй кто тут пишет подтверждает мои слова.
вы меня извините, но обращение списка я считаю вообще задачей недостойной моей квалификации (хотя я и не программист), но что-то подобное мы еще в школе проходили (как смутно припоминаю). а, нет. вру. мы массив на бейсике обращали.

не, я вообще в упор не вижу проблемы. вот за сорок секунд написал на питоне не самую дебильную реализацию:

my_list = [1, 2, 3, 4, 5, 6, 7, 8, 9];

my_list_len = len(my_list);

print my_list

while my_list_len > 0:
    my_list_len -= 1;
    x = my_list.pop(0);
    my_list.insert(my_list_len,x);

print my_list

[1, 2, 3, 4, 5, 6, 7, 8, 9]
[9, 8, 7, 6, 5, 4, 3, 2, 1]

как видим работает. эффективность программы напрямую зависит от эффективности insert'а и, поскольку, вставка элементов идет в середину списка, реализация рискует соснуть. как вариант -- можно сделать:

x = my_list.pop(my_list_len); my_list.append(x);

или:

x = my_list.pop();
my_list_tmp.append(x);

последнее не уже зависит от реализаций pop и append (т.к. удаляется последний элемент списка и добавляется в конец tmp'а, то мы не только список, но и стек развернем, но тут мы окажемся в зависимости от качества сборщика мусора).

еще можно реализовать swap на питоне, но это зависит от качества реализации enumerate...

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

так что не фиг гнать на задачу. задача простая, но требует понимания как оно работает. конкретно в питоне все же выгоднее реализовывать swap через enumerate, т.к. это позволяет задейстовать map, что в свою очередь позволяет задействовать все ядра ЦП (в теории). на практике большие списки (500 метров данных) выгоднее обращать через импромизированный "кэш", исходя из представлениий об аллоканции памяти в питоне (особенно, если элементы списка -- строки) -- как раз в этом случае очень важно не создавать копию элементов списка, а тассовать указатели на них, но это уже дебри...

М>как видим работает. эффективность программы напрямую зависит от эффективности insert'а и, поскольку, вставка элементов идет в середину списка, реализация рискует соснуть. как вариант -- можно сделать:

очень даже рискует; я бы предположил, что тут будет квадратичная сложность, если, конечно, insert по собственной инициативе не кэширует указатель на позицию прошлой вставки для списка

а в питоне вообще есть способ написать *свой* inplace reverse? че-то опять сомневаюсь -- видимо только list.reverse и юзать

Здравствуйте, мыщъх, Вы писали:

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

G>>Здравствуйте, мыщъх, Вы писали:

G>>Во Всех языках есть готовые библиотеки для этого.
М>а все программы уже написаны задого до нас.

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

G>> Ну вот я и говорю, что решение задач про гномиков это скилл, к работе не имеющий отношения.
М>не спрашивали меня за гномиков (это за тех гномиков, из которых уши кодов коррекции ошибок торчат?). у нас вообще интересные интервью были с жаркими спорами, в которые постепенно втягивался весь отдел. интерью ведь не экзамен, а беседа двух умных людей и тут намного важнее позитивное впечатление произвести, чем дать правильный ответ на вопрос.
Я с тобой солидарен, но топикстартер поставил вопрос по-другому.

G>> И недоволен тем что некоторые считают такие задачи хорошим фильтром на собеседованиях.
М>фильтр отбирает кандидатов еще до собеседования. и если кандидат не может обратить список, то это очень плохой фильтр и собеседовать такого кандидата -- это профукивать деньги на ветер. программистам приходится сталкиваться с нетривальными задачами, которые требуют не только знаний SDK, но и умения мыслить.
Еще раз повторю что разворачивание списка и "гномики" это скилл, не имеющий отношение к работе. В работе другие задачи, и даже если они похожи на "гномиков" люди об этом не знают.

Вот тот же морозов не увидел что из обращения иммутабельного списка тривиально выводится обращение мутабельного.

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


М>>как видим работает. эффективность программы напрямую зависит от эффективности insert'а и, поскольку, вставка элементов идет в середину списка, реализация рискует соснуть. как вариант -- можно сделать:

ME>очень даже рискует; я бы предположил, что тут будет квадратичная сложность, если, конечно, insert по собственной инициативе не кэширует указатель на позицию прошлой вставки для списка

извините за выражение, но в питоне все через жопу. нормальным спискам по фиг куда делать вставку в конец или в начало. во всяком случае в начало уж точно не медленнее, чем в конец. в питоне -- вставка в конец существенно быстрее вставки в начало. потому pop (а точнее даже del для облечения участи сборщика мусора) с append во временный список здорово выиграет по времени.

ME>а в питоне вообще есть способ написать *свой* inplace reverse? че-то опять сомневаюсь -- видимо только list.reverse и юзать
если очень-очень хочется, то можно реализовать свой итератор, который будет помнить позицию для вставки, которую сможет использовать своя же реализация insert'а (или кастомный pop). при этом мы имеем линейную сложность. поскольку, в обоих решениях (insert и pop) позиция вставки/удаления с каждой итерацией меняется ровно на один элемент, скользящий вдоль списка? -- нам достаточно "захачить" итератор next для сохранения этой позиции внутри списка.

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

вообще сюрприз питона в другом. my_list[idx] = val тормозит сильнее, чем del my_list[idx]; insert(idx, val); (при условии, что val -- строка и len(val) > len(my_list[idx]) -- я как бы обратного ожидал. хотя почему тормозит -- понятно.

Задача 2. (Специфическая для С++. )

"Попробуйде сформулировать правила по которым можно выбрать способ абстрагирования для объекта. Предлагаю рассмотреть 3 способа

1. Использование typedef
2. Использование типа как шаблонного параметра
3. использование типа как абстрактного класса (с известным интерефейсом).

Прокоментируйте мотивацию по правилам и приеимущества и недостатки всех 3х способов."

Задача 3.


"Есть несколько альтернативных дизайнов раббиения функционала на модили и их взаимодействия. По каким критериям вы будете сравнивать между собой разные дизайны?"

M>"Попробуйде сформулировать правила по которым можно выбрать способ абстрагирования для объекта. Предлагаю рассмотреть 3 способа

M>1. Использование typedef
M>2. Использование типа как шаблонного параметра
M>3. использование типа как абстрактного класса (с известным интерефейсом).

M>Прокоментируйте мотивацию по правилам и приеимущества и недостатки всех 3х способов."

хм.

мне было бы интересно прочитать твой ответ, но сначала я выдам свой

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

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

а когда и если сможем -- то это будет очень стандартная ситуация, и там не нужна теория, мотивация и прочее, а нужно следование традициям

итак, ответ -- следовать традициям, ну или выражаясь высоким стилям -- паттернам

2. твой вопрос мне чем-то напоминает вопрос "Есть девушка; прокоментируйте мотивацию по выбора способа, которым вы будете ее... ну в общем понятно что"; ответ тоже понятен -- как сочту нужным, так и буду

по преимуществам и недостаткам трех способов уже можно говорить осмысленно

M>"Попробуйде сформулировать правила по которым можно выбрать способ абстрагирования для объекта. Предлагаю рассмотреть 3 способа

M>1. Использование typedef
M>2. Использование типа как шаблонного параметра
M>3. использование типа как абстрактного класса (с известным интерефейсом).

M>Прокоментируйте мотивацию по правилам и приеимущества и недостатки всех 3х способов."

1 (typedef) понятно самый слабый (т.е. дает протечку абстракции), но его юзают довольно часто в сочетании с 2, т.к. не хочется городить совсем уж монстров

3 подтормаживает (затраты на вызов виртуальной функции), зачастую не дает гарантий (т.е. не всегда возможно заставить компилятор уследить за тем, что вместо абстрактного окажется конкретный тип, и получить pure virtual method call в рантайме), и кроме того, бывает что является разновидностью динамической типизации (ммм... вот я сходу не вспомню щас подобный случай, хотя надо -- речь идет о том, что даункасты, хотя и с проверкой, там неизбежны); однако чаще всего это самый надежный вариант... если его удается применить

2 весьма неплох; из недостатков -- структурная эквивалентность (хотя надо это обозвать поточнее) и отсутствие полноценного параметрического полиморфизма, т.е. случаев, когда один и тот же код (шаблон) должен в рантайме принимать аргументы реально разных типов, и мы почему-то не можем провернуть трюк с обертыванием этих типов в объекты одной иерархии

кстати, не указан еще один способ --

4. это void* , обернутый для некоторой безопасности шаблонами

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

а вообще все это конечно интересно

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


ME>мне было бы интересно прочитать твой ответ, но сначала я выдам свой
Мне бы не хотелось свою точку зрения навязывать , тем более , что вопросы мои не пердполагают единого четкого ответа.

ME>попытки разводить теорию на тему "Прокоментируйте мотивацию по правилам", хотя и интересны, но мне кажутся бесполезны по двум причинам:

ME>1. с++, в первом приближении -- лучшее, но все же из говна, которое мы имеем в языках программирования; так что ответ, в общем, сводится к тому -- чтобы результат получился не слишком мимо того, что умеет с++, и не слишком неожидан для остальных разработчиков -- ведь это именно им придется выполнять те соглашения, которые мы, к сожалению, не сможем выразить так, чтобы их мог проверить компилятор

ME>а когда и если сможем -- то это будет очень стандартная ситуация, и там не нужна теория, мотивация и прочее, а нужно следование традициям

ME>итак, ответ -- следовать традициям, ну или выражаясь высоким стилям -- паттернам

Мне сложно согласиться с такой посылкой.

Например класс log_destination который направляет (готовый) поток вывода конкретному потребителю (файл, сеть, экран...). А теперь представьте себе что этот объект мы абстрагируем с помощью шаблоного агрумента по ВСЕМУ коду программы. Разве вы не увидите недостатков такого решения , разве на основе преимуществ и недостатков нельзя попытаться сформировать правила выбора?

ME>2. твой вопрос мне чем-то напоминает вопрос "Есть девушка; прокоментируйте мотивацию по выбора способа, которым вы будете ее... ну в общем понятно что"; ответ тоже понятен -- как сочту нужным, так и буду

Мне не кажется такой ответ зрелым, к контексте моего вопроса.

ME>по преимуществам и недостаткам трех способов уже можно говорить осмысленно

И по ним же можно составить правила (которые не обязаны быть строгими , но легко понятными)

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

M>"Попробуйде сформулировать правила по которым можно выбрать способ абстрагирования для объекта. Предлагаю рассмотреть 3 способа

M>1. Использование typedef
M>2. Использование типа как шаблонного параметра
M>3. использование типа как абстрактного класса (с известным интерефейсом).

M>Прокоментируйте мотивацию по правилам и приеимущества и недостатки всех 3х способов."

возможно, что тут надо добавить еще и

5. вместо самого типа Т передавать Boxed<T>, где

 template<class T> class Boxed: public Object {

можно это рассматривать как комбинацию приемов 2 и 3, а можно как отдельный прием