Здравствуйте, Тёмчик, Вы писали:
Тё>Здравствуйте, VVV, Вы писали:
VVV>>>>Знаю как не рекурсивно (и очень элегантно) : http://rsdn.org/forum/other/124244.1
Тё>>>Там в коде ошибка. VVV>>Там не код, а псевдокод. Но всё же, где там ошибка? Тё>В индексах.
Покажи где в индексах? https://ideone.com/ckJDhV
VVV>>Речь всё ещё о циклическом сдвиге строки? Тё>«псевдокод» использует reverse строки. Речь об имплементации reverse без for-loop.
В этой подветке речь идёт о _циклическом_сдвиге_строки. Начато ЛаптевымВВ:
LVV>>И приводится удивительно элегантное рекурсивное решение.
Тё>Зачем там рекурсия?
Прошу пардону.
Там реверс строки используется для реализации циклического сдвига строки на n позиций за О(n).
К сожалению, я понял так, что всё же речь идёт про рекурсивный алгоритм сдвига строки, а т.к. я про него много раз слышал, но ни разу не видел (и сам не пытался, т.к. знаю нерекурсивный), то и спросил показать. Сейчас уже понял, что идёт речь как раз о том алгоритме, что я и привёл. Как-то так.
Re[8]: Зачем просят перевернуть строку на интервью?
Здравствуйте, Lexey, Вы писали:
L>Здравствуйте, VVV, Вы писали:
VVV>>Там не код, а псевдокод. Но всё же, где там ошибка?
L>У тебя там, по факту, сдвиг на m влево, а не вправо.
Это ж был ответ на:
Там реверс строки используется для реализации циклического сдвига строки на n позиций за О(n).
и тут не оговаривалось в какую сторону.. (хотя, спасибо за прочтение исходного сообщения и внимательность!)
а если брать исходное сообщение 2002, то там был _псевдокод_, который только демонстрировал _идею_, не реализацию. Ну и при _циклическом_ сдвиге можно двигать хоть вправо, хоть влево.
Re[9]: Зачем просят перевернуть строку на интервью?
Здравствуйте, Lexey, Вы писали:
Тё>>Ну разве про swap без временной переменной
L>Што?
Тё>>и вообще без индексов.
L>Што? L>Маразм крепчал?
Мало того, что у тебя ограниченный кругозор что даже сишные фишки не знаешь (не говоря про математику), — ты ещё и гордишься этим.
А потом приходят такие "с опытом" и впадают в meltdown на школьной задачке.
Re[9]: Зачем просят перевернуть строку на интервью?
Тё>>>>Там в коде ошибка. VVV>>>Там не код, а псевдокод. Но всё же, где там ошибка? Тё>>В индексах.
VVV>Покажи где в индексах? https://ideone.com/ckJDhV
IK>Для массива 1 2 3 4 5 6 7 при сдвиге на 3 позиции должно получиться
IK>5 6 7 1 2 3 4.
Здравствуйте, Тёмчик, Вы писали:
Тё>Ну разве про swap без временной переменной
А нафига? Это прикольный трюк но какой либо значимой практической пользы не несёт.
... << RSDN@Home 1.0.0 alpha 5 rev. 0>>
Re[9]: Зачем просят перевернуть строку на интервью?
Здравствуйте, CreatorCray, Вы писали:
Тё>>Ну разве про swap без временной переменной CC>А нафига? Это прикольный трюк но какой либо значимой практической пользы не несёт.
Это тест на понимание битовых операций. Если у чела опыт C или C++ — должен понимать. Ибо говнокодеры нам не нужны.
Re[10]: Зачем просят перевернуть строку на интервью?
Здравствуйте, Тёмчик, Вы писали:
Тё>Это тест на понимание битовых операций. Если у чела опыт C или C++ — должен понимать. Ибо говнокодеры нам не нужны.
Не, Тёма, это не на понимание, а на проверку, читал ли "Hacker's Delight" (в нашем переводе "Алгоритмические трюки").
Т.е. очков кандидату может добавить, но определяющим не является.
_____________________
С уважением,
Stanislav V. Zudin
Re[3]: Зачем просят перевернуть строку на интервью?
Здравствуйте, Michael7, Вы писали:
M>Здравствуйте, RussianFellow, Вы писали:
RF>>Так, что ли?
M>Все бы ничего, но на utf-8 и даже на utf-16 в общем случае этот алгоритм сработает неправильно из-за переменной длины символов.
А как правильно тогда будет?
1613 г. = 2024 г.
Re[10]: Зачем просят перевернуть строку на интервью?
Здравствуйте, Тёмчик, Вы писали:
Тё>Это тест на понимание битовых операций.
На понимание битовых есть другие, нормальные тесты, которые именно на понимание что как и почему.
Этот же просто бесполезный трик.
... << RSDN@Home 1.0.0 alpha 5 rev. 0>>
Re[4]: Зачем просят перевернуть строку на интервью?
Здравствуйте, RussianFellow, Вы писали:
M>>Все бы ничего, но на utf-8 и даже на utf-16 в общем случае этот алгоритм сработает неправильно из-за переменной длины символов.
RF>А как правильно тогда будет?
Правильно будет уточнять условие задачи до начала решения. Может и не потребуется решать замороченный вариант. И произведешь хорошее впечатление на интервьюера.
_____________________
С уважением,
Stanislav V. Zudin
Re[18]: Зачем просят перевернуть строку на интервью?
Здравствуйте, CreatorCray, Вы писали:
CC>Здравствуйте, 0xCAFEDEAD, Вы писали:
CAF>>Я не очень понимаю, о чем ты. CC>Это не тебе. CC>Тут есть анонимная кукушка, которая ходит и подкладывает своё "ценное мнение" приватными мессагами от анонима.
А что пишет то?
Re[19]: Зачем просят перевернуть строку на интервью?
Здравствуйте, 0xCAFEDEAD, Вы писали:
CC>>Тут есть анонимная кукушка, которая ходит и подкладывает своё "ценное мнение" приватными мессагами от анонима. CAF>А что пишет то?
Я давно уже их не читаю, удаляю сразу как вижу что от анонима с rsdn.
Некоторые тут постили, им тоже приходило.
... << RSDN@Home 1.0.0 alpha 5 rev. 0>>
Re[19]: Зачем просят перевернуть строку на интервью?
Здравствуйте, 0xCAFEDEAD, Вы писали:
CC>>Тут есть анонимная кукушка, которая ходит и подкладывает своё "ценное мнение" приватными мессагами от анонима. CAF>А что пишет то?
Иногда скромно присылает свое решение
Как раз сегодня прочитал данную тему и написал на своем персональном форуме соответствующее решение. за 15 минут
Правда, я не заморачивался кодировкой и использовал базовую кодировку.
Здравствуйте, Stanislav V. Zudin, Вы писали:
Тё>>Это тест на понимание битовых операций. Если у чела опыт C или C++ — должен понимать. Ибо говнокодеры нам не нужны.
SVZ>Не, Тёма, это не на понимание, а на проверку, читал ли "Hacker's Delight" (в нашем переводе "Алгоритмические трюки"). SVZ>Т.е. очков кандидату может добавить, но определяющим не является.
Если не может придумать, значит не понимает битовые операции. Пусть складывает свои лего (и дрочит на указатели) в более других компаниях .
Re[12]: Зачем просят перевернуть строку на интервью?
Здравствуйте, Тёмчик, Вы писали:
Тё>>>Это тест на понимание битовых операций. Если у чела опыт C или C++ — должен понимать. Ибо говнокодеры нам не нужны.
SVZ>>Не, Тёма, это не на понимание, а на проверку, читал ли "Hacker's Delight" (в нашем переводе "Алгоритмические трюки"). SVZ>>Т.е. очков кандидату может добавить, но определяющим не является.
Тё>Если не может придумать, значит не понимает битовые операции. Пусть складывает свои лего (и дрочит на указатели) в более других компаниях .
Категорически не согласен.
Есть знания, которые можно вывести, а есть те, которые надо просто знать (или знать, где подсмотреть).
Вот слабо сходу,не подглядывая в первоисточник, написать функцию реверса битов?
Тыж типа не говнокодер, в "лего" не играешь
_____________________
С уважением,
Stanislav V. Zudin
Re[8]: Зачем просят перевернуть строку на интервью?
Здравствуйте, Тёмчик, Вы писали:
Тё>Здравствуйте, AleksandrN, Вы писали:
Тё>Там нечего оптимизировать- всё правильно сделано. Ну разве про swap без временной переменной и вообще без индексов.
Иногда встречал собеседующих, которые любят позанудствовать. В этом случае можно докопаться до двукратного вычисления n-1-i, хотя современный компилятор это, наверняка, хорошо оптимизирует.
А если делать без индексов и перестановку без временных элементов
void reverse( char *s )
{
if ( !s )
return;
char *e = s + strlen( s ) - 1;
while ( s < e )
{
*e ^= *s;
*s ^= *e;
*e-- ^= *s++;
}
}
Здравствуйте, Тёмчик, Вы писали:
Тё>Там нечего оптимизировать- всё правильно сделано. Ну разве про swap без временной переменной и вообще без индексов.
1. Ты просто не в курсе, чем могут быть временные переменные на стеке после компиляции. В релизе их просто не будет на стеке — значение сразу кладётся в регистр.
2. Аналогично и с индексами: если компилятор не догадается от них избавиться, то у тебя опять же будут проблемы с быстродействием.
3. Если вдруг так получится, что строка будет представлена двусвязным списком, то индексов либо не будут, либо они будут O(n).
4. Про utf-8 тебе уже написали: над такой строкой итератор будет логичной абстракцией, проходящей по строке посимвольно. Индекс же будет ходить либо по символам, либо по байтам, в зависимости от реализации.
Поэтому, если говорить о С++, вариант с итераторами будет одновременно и достаточно общим, и быстрым.
Re[9]: Зачем просят перевернуть строку на интервью?
Здравствуйте, AleksandrN, Вы писали:
AN>А если делать без индексов и перестановку без временных элементов AN>
AN>void reverse( char *s )
AN>{
AN> if ( !s )
AN> return;
AN> char *e = s + strlen( s ) - 1;
AN> while ( s < e )
AN> {
AN> *e ^= *s;
AN> *s ^= *e;
AN> *e-- ^= *s++;
AN> }
AN>}
AN>
Те же яйца (индекс), вид в профиль. Последняя строчка некрасивая- лучше всё запихнуть в for. Что ж вы всё на указатели мастурбируете типа это прибавляет значимости?
