Comments 134
В задаче с числами Фибоначчи, на мой взгляд, стоит еще упомянуть о решении через перемножение матриц, работающее за O(log n).
Вот с этим методом очень интересно. Где бы о нём популярно почитать? Я могу его закодить, но не понимаю как он работает (прочёл в «Началах программирования» Степанова)…
Здесь и на хабре есть немного материала по этому поводу. В принципе, ничего сложного нет, просто доказывается, что каждый элемент можно получить через умножение на матрицу 2*2. А возводить что угодно в степень быстрее всего с помощью логарифмического алгоритма (в квадрат, результат еще в квадрат и т.д.).
Функция перевода строки.
scanf("%s", str);
Строка, напоминаю, заканчивается на '\0'. а такой scanf прочитает до пробела.
P. S. за первую реализацию — убить мало)
scanf("%s", str);
Строка, напоминаю, заканчивается на '\0'. а такой scanf прочитает до пробела.
P. S. за первую реализацию — убить мало)
Да, для общего развития — поменять две переменные без буфера в C можно:
a ^= b ^= a ^= b;
Удивился, что автор не знает.
На фоне строчки из предыдущей статьи:
Вы должны знать как минимум один язык программирования очень хорошо, и лучше если это будет С++ или Java. незнание свойств xor'а как-то чревато, что ли…
На фоне строчки из предыдущей статьи:
Вы должны знать как минимум один язык программирования очень хорошо, и лучше если это будет С++ или Java. незнание свойств xor'а как-то чревато, что ли…
Со школы еще помню вариант для перемены, прокатывает только для численных переменных:
A=A+B;
B=A-B;
A=A-B;
A=A+B;
B=A-B;
A=A-B;
а вообще, английская вики твердит, что не стоит пользоваться этим методом.
Пожалуй это будет самый быстрый и самый короткий код для этой задачи. Т.к. переставить две переменные местами, не прибегая к помощи третей в Си реализовать не возможно. Последний символ строки '\0' не трогается, т.к. при i=0 мы будем менять предпоследний символ с первым, длина строки при перевороте не меняется.
Есть такая фишечка с побитовыми операциями (прошу прощения, в чистом C есть ссылки? Если нет, можно подкорректировать):
void swap (int &a, int &b)
{
return a ^= b ^= a ^= b;
}
Но работает медленнее, чем через переменную, число операций больше.
Не успел :)
А разве не нужно добавить проверку, что a и b — это ссылки на одну и ту же переменную? Иначе xor может просто занулить данные.
return void?
«Но работает медленнее, чем через переменную, число операций больше.»
Решил проверить, и оказалось что наоборот. Вариант без переменой работает быстрее в два раза.
Также решил проверить насколько быстрее (len>>1) от (len/2), но компилятор компилирует этот код совершенно одинаково.
Решил проверить, и оказалось что наоборот. Вариант без переменой работает быстрее в два раза.
% time ./v1
./v1 0.57s user 0.00s system 63% cpu 0.906 total % time ./v3
./v3 0.23s user 0.00s system 59% cpu 0.394 totalТакже решил проверить насколько быстрее (len>>1) от (len/2), но компилятор компилирует этот код совершенно одинаково.
Я проверял это в 2007 году в Visual Studio 2005.
Возможно, компилятор теперь лучше оптимизирует этот код.
Возможно, компилятор теперь лучше оптимизирует этот код.
На современных процессорах при использовании оптимизирующих компиляторов, перестановка через переменную либо быстрее, либо такая же по скорости. А читабельность кода выше.
ЗЫ Реальную разницу в скорости измерить будет весьма не просто. И хуже чем «time» для этой цели что-то придумать трудно (разве что дедушкин секундомер). Не смущает что «63% cpu»?
ЗЫ Реальную разницу в скорости измерить будет весьма не просто. И хуже чем «time» для этой цели что-то придумать трудно (разве что дедушкин секундомер). Не смущает что «63% cpu»?
Обмен двух массивов через xor работает в 1.5 раза медленнее, чем через переменную.
Undefined behavior.
habrahabr.ru/blogs/hr/137653/#comment_4591003
Обертка в функцию была для примера, сначала написал int swap, потом подумал, что можно использовать ссылки для скорости, исправил на void, а return забыл убрать.
Обертка в функцию была для примера, сначала написал int swap, потом подумал, что можно использовать ссылки для скорости, исправил на void, а return забыл убрать.
В данном случае в одном выражении одна и та же переменная изменяется несколько раз. Стандарт говорит нам, что в таком случае поведение неопределено. Подробнее см. «точки следования». Иногда на собеседованиях специально задают подобные задачи, чтобы узнать, разбирается ли кандидат в вопросе, открывал ли стандарт. Как еще один пример неопределенного поведения: i = ++i + ++i;
UB тут потому что есть модификация одной и той же переменной дважды между двумя одними и теми же sequence point, а не по названным вами причинам.
А xor (и прочие битовые операции) для целых чисел, которые могут быть и отрицательными — это не UB?
А xor'у какая разница отрицательные они или нет, он их побитово xor'ит, не учитывая знаковый бит или нет.
А то, что в разных представлениях целых чисел результат (-2)^1 будет разным, это не страшно? Почему же тогда переполнение при сложении это UB? Ситуация совершенно такая же.
При xor же никакого переполнения нет, о чём вы вообще?
Давайте предметно, приведите примеры, когда обмен с помощью xor будет работать неправильно (только нормальный обмен, а не в одну строчку).
Давайте предметно, приведите примеры, когда обмен с помощью xor будет работать неправильно (только нормальный обмен, а не в одну строчку).
А я не про обмен, я про сам термин «Undefined behavior». Я его не понимаю, вот и пытаюсь узнать у понимающих людей, в чем его суть, по какому принципу к нему что-то отнесено, а что-то нет.
Undefined behavior означает, что поведение компилятора в конкретной ситуации не определено и он может делать что угодно. Хоть невалидную инструкцию в этом месте вставить, хоть ребут инициировать. По какому принципу к нему что-то относят или не относят — это вопрос к комитету, но вот, например, изменение одной переменной несколько раз в пределах одной точки следования — это неопределенное поведение. А xor двух целочисленных — вполне определенное.
len = strlen(str); /* \0 symbol в конце строки */
buffer = (char*) malloc(len);
Ну что я могу сказать, садитесь, 2. С удачным Segmentation Fault. Я бы на месте экзаменатора за такую ошибку уже отправил набираться опыта.
Да и передача массива со стека в функцию доставляет, в реальной жизни что-то вообще ни у кого из знакомых и подчиненных этого не встречал, да и в каких-либо открытых проектах.
Опять же далее видно, realloc зло, можно было тупо выполнить метод stat и получить размер файла, либо можно сгонять указатель в конец, узнать позицию, выделить память под все сразу и вернуть указатель обратно. Это если читать целиком, а вот если бы файл был пару гигов, тоже весь в память загонять, а потом считать? Я понимаю, что такой файл можно и память отобразить и еще что-нить, но читать буфер по 1кило, обрабатывать цифры и читать дальше совсем не сложно, если последним символом число, то конвертим во временную переменную, читаем следующий кусок, если пробел, так прибавляем, если число, то смотрим по разрядам, умножаем, прибавляем, а дальше как обычно. Реализация не на много сложнее.
Некоторые моменты откровенно слабы и на месте сотрудника гугла я бы вас забраковал.
buffer = (char*) malloc(len);
Ну что я могу сказать, садитесь, 2. С удачным Segmentation Fault. Я бы на месте экзаменатора за такую ошибку уже отправил набираться опыта.
Да и передача массива со стека в функцию доставляет, в реальной жизни что-то вообще ни у кого из знакомых и подчиненных этого не встречал, да и в каких-либо открытых проектах.
Опять же далее видно, realloc зло, можно было тупо выполнить метод stat и получить размер файла, либо можно сгонять указатель в конец, узнать позицию, выделить память под все сразу и вернуть указатель обратно. Это если читать целиком, а вот если бы файл был пару гигов, тоже весь в память загонять, а потом считать? Я понимаю, что такой файл можно и память отобразить и еще что-нить, но читать буфер по 1кило, обрабатывать цифры и читать дальше совсем не сложно, если последним символом число, то конвертим во временную переменную, читаем следующий кусок, если пробел, так прибавляем, если число, то смотрим по разрядам, умножаем, прибавляем, а дальше как обычно. Реализация не на много сложнее.
Некоторые моменты откровенно слабы и на месте сотрудника гугла я бы вас забраковал.
Минусы есть, но в чем я не прав? Жду нормальный коммент.
да вобщем-то ты прав. скорей всего кто-то не осилил.
Наверное, от людей, которые желают автору удачи :)
Потому что замечания по делу — и про segfault и про realloc. Сейчас, сишники проснутся и добавят плюсы :)
Потому что замечания по делу — и про segfault и про realloc. Сейчас, сишники проснутся и добавят плюсы :)
Выделил len байтов, а обращаешься в строке buffer[len] = '\0'; к len+1 байту. В 99% все будет работать нормально, тк алокатор обычно выделяет слегка больше памяти чем запрашивается. Но это баг.
Написание кода в незнакомой среде с телефоном у уха с необходимостью комментировать вслух — не самые лучшие друзья качественного кода, поэтому на месте сотрудника гугла я бы сделал скидку на непринципиальные недочеты. Врядли это единственная проверка, через которую пропустят кандидата, скорее так, крупноячеистое сито, что отсеять шлак.
Увы len+1 и отсутствие этого +1 это очень принципиальный баг, если программист этого подсознательно не чувствует, это плохо. А вот на realloc я бы закрыл глаза, если важно просто показать сам алгоритм.
Такие ошибки исправляются при первом же тестировании программы. Меня, например, всегда нервирует, если требуют в блокноте (или на бумаге) написать точную нетривиальную программу, без ошибок и прочих недочетов. Наличие этой ошибки (на единицу меньше байт, чем нужно) не является признаком того, что программист не знает что нужно сделать +1, это говорит лишь о том, что он не подумал об этом сразу.
На этапе тестирования не всегда может быть выявлена, учитывая факт выравнивания, выделение блоками, опять же все зависит от реализации в библиотеке реализующей методы работы с памятью, изменения от версии к версии. Если где-то что-то неправильно посчитал это одно, но +1, если zero ended строка, то +1, даже не думая. По сути это плавающий баг, который может всплыть через длительное время.
На счет кода
''.join([x for x in reversed(st)])
Скобки можно упускать:
''.join(x for x in reversed(st))
Кроме того, 'reversed' — итерабельный объект, так что такое тоже пройдет:
''.join(reversed(st))
''.join([x for x in reversed(st)])
Скобки можно упускать:
''.join(x for x in reversed(st))
Кроме того, 'reversed' — итерабельный объект, так что такое тоже пройдет:
''.join(reversed(st))
Жуть какая. Надо очень сильно хотеть где-то работать, чтоб на столько напрягаться с собеседованием. Удивлюсь, если к ним кто-то кроме студентов попадает&
Мне, кстати, понравилось, что у них (Гугля) в интервью проверяют умения программировать а не знания конкретного языка. Например интервьюеры предлагали самому выбрать язык для решения задачи (кроме псевдокода). А места, которые сажали на собеседовании решать какой-нибудь экзамен по С++ сразу сильно падали в моих глазах, хоть я эти экзамены щелкал не напрягаясь даже.
да-да-да, умение развернуть строку очень хорошо показывает умение программировать. т.е. с одной стороны, то что человек не может такого написать, говорит о том, что он скорей всего плохой разработчик. с другой стороны, если человек такое может написать, это ни говорит ровным счетом ни о чем. Тоже самое и с тестами по языку.
Верно говорите. Именно по этому, такие задачки только на первых телефонных собеседованиях спрашивают, чтобы отсеять совсем уж шлак. А на на дальнейших уже настоящие задачки идет, и что мне понравилась не абстрактные алгоритмические задачки про всякие весы с монетками, а вполне конкретные программистские проблемы. Например, из сложных меня спрашивали про маппирование больших объемов памяти с эффективных доступом, намекая на то, чтоб я имплементировал radix tree, или, из задач попроще, написать свой семафор используя мьютексы.
Кстати, предварительное отсеивание — оно ой какое полезное. Я сам достаточно много собеседований проводил, и вы наверное не представляете, какое количество людей, заявляющих об огромном опыте и гнущих пальцы направо и налево, «сдуваются» на элементарных задачках вроде переворота строки. Вы знаете, мне по началу было реально жутко неудобно спрашивать какого-нибудь супер-специалиста с Ph.D и 15-ю годами опыта задачку, которая решается одним циклом «for», но потом понял, что именно на таких тестах сразу отсеиваются процентов 30% полностью профнепригодных кандидатов, при том, что на более сложных задачах, им иногда удается запудрить неопытному интервьюиру голову баззвордами. Например, в одном стартапе, где я работал, ухитрились взять чувака на должность начальника разработки, которым умел отличного заговаривать зубы о том, какой он невь*бенный специалист и програмист мирового уровня, и при этом не имея понятия о complexity и не понимая разницы между байткодом и машинным кодом, и рассказывал всем, как копирование массивов в C# намного быстрее, чем в C, так как делается «одной инструкцией».
Кстати, предварительное отсеивание — оно ой какое полезное. Я сам достаточно много собеседований проводил, и вы наверное не представляете, какое количество людей, заявляющих об огромном опыте и гнущих пальцы направо и налево, «сдуваются» на элементарных задачках вроде переворота строки. Вы знаете, мне по началу было реально жутко неудобно спрашивать какого-нибудь супер-специалиста с Ph.D и 15-ю годами опыта задачку, которая решается одним циклом «for», но потом понял, что именно на таких тестах сразу отсеиваются процентов 30% полностью профнепригодных кандидатов, при том, что на более сложных задачах, им иногда удается запудрить неопытному интервьюиру голову баззвордами. Например, в одном стартапе, где я работал, ухитрились взять чувака на должность начальника разработки, которым умел отличного заговаривать зубы о том, какой он невь*бенный специалист и програмист мирового уровня, и при этом не имея понятия о complexity и не понимая разницы между байткодом и машинным кодом, и рассказывал всем, как копирование массивов в C# намного быстрее, чем в C, так как делается «одной инструкцией».
на мой взгляд, задачи гугла решают только один вопрос — они позволяют отсеить тех, кто не согласен потратить довольно большое количество времени на подготовку к собеседованию. большинство их задач — это задачи «на поиск гуглом» и инженер с опытом, с большой вероятность, их не помнит и не решит, т.к. он работает, а не к собеседованиям готовится.
Готовится никогда не мешает (они сами советуют на topcoder тренироваться перед собеседованием), но, простите, про какие такие задачи «на поиск гуглем» вы говорите? То, что я видел — были нормальные задачи по практике и теории программирования (алгоритмы, структуры данных, классы сложности, и т.д.) причем без шелухи в виде абстрактных задач не имеющих отношения к программированию, как иногда любят спрашивать.
Вот бесят меня эти формулировки типа «инженер с опытом». Звучат для меня как «математик с опытом может не знать, сколько будет дважды два» или «хирург с опытом может не суметь помазать ссадину йодом».
Зря тебя это бесит. Инженер с опытом может тебе точно ответить на кучу вопросов по своей текущей предметной области. В то же время, он с большой вероятностью не ответит на вопросы из областей, с которыми давно не имел дела. Это просто свойство памяти — откладывать на дальнюю полку то, что давно не использовалось.
UFO just landed and posted this here
А зачем Ph.D b 15-ю годами опыта помнить про for-ы? На какую должность такой интервьюируется? Если писать задачки, то отсеиваться такой будет еще до интервью :).
Потому, что пусть он дважды доктор, но если он проходит собеседование на должность программиста (другие ко мне и не попадали) то он обязан знать как писать на каком-нибудь настоящем языке программирования. Понятное дело, что если берут, скажем, чистого алгоритмика, то на знание прикладного программирования его проверять нечего, хотя и ему нужно владеть каким-нибудь матлабом, что бы уметь записать и протестировать свой алгоритм.
Не, это я понимаю. Просто выразил удивление, что человек с таким опытом устраивается на должность программиста. Бывает, кончено, но явление не очень распространенное.
Не у всех же есть администраторские способности. А жить на что-то надо.
Всякое бывает. Я условно написал, имея в виду, что расписанные в резюме качества, даже если они формально правдивы, далеко не всегда выявляются на практике. Был у меня когда-то кадр на собеседовании один, весь из себя надутый «Senior Software Developer», который на поверку даже не говнокодера не тянул, правда там совсем клиника была, там уже по CV было ясно.
Кстати, по какой причине он будет отсеиваться? Дискриминация по возрасту, да?
По возрасту HR тоже будет кривить губы, конечно. Но в основном из-за over-qualification.
Хм. Надо будет узнать, что это такое и как с ним бороться. Просто на всякий случай, вдруг придется работу искать.
Бороться — это только искать должность соответствующую квалификации. Я только технические собеседования проводил, но на месте мененджера/HR я бы дважды подумал, стоит ли брать доктора или просто крутого специалиста на не слишком квалифицированную и не слишком высоко оплачиваемую должность. В жизни, конечно, разное у людей бывает, но вполне логично, что вовлеченность и мотивация у такого сотрудника будет близкой к нулю.
Не совсем согласен, а я в все же проверяю знания языка, ибо нужен программист на конкретном языке, а не просто программист, который будет как в данных примерах на С косячить с выделением памяти, да и в том же C++ часто доставляет то, что программисты «знают stl», но как оказывается, знает, что есть контейнеры, но не знают какой и когда использовать, не знают алгоритмы, не умеют работать с потоками и так далее и тому подобное. Даже зная std::map не знают std::make_pair и кругом суют конструктор, хорошо если новый тип объявят, а то ведь пишут всю конструкцию целиком.
Да, человек, который умеет программировать, который изучает быстро языки, это хорошо, но на это требуется время, а если взять к примеру тот же С++, то времени может уйти очень много, а в это время производительность труда отдела только упадет, за счет того, что его работу придется досконально проверять.
И если гугл имеет такие ресурсы, может позволить научить сотрудника и посадить его пожизненно на рутину, то мелкие компании не могут себе этого позволить, поэтому стараются искать готовых специалистов.
И проверяю как работает голова на алгоритмах, тут если программисту проще на каком-нить языке написать, пусть на языке напишет, проще словами, пусть словами.
Да, человек, который умеет программировать, который изучает быстро языки, это хорошо, но на это требуется время, а если взять к примеру тот же С++, то времени может уйти очень много, а в это время производительность труда отдела только упадет, за счет того, что его работу придется досконально проверять.
И если гугл имеет такие ресурсы, может позволить научить сотрудника и посадить его пожизненно на рутину, то мелкие компании не могут себе этого позволить, поэтому стараются искать готовых специалистов.
И проверяю как работает голова на алгоритмах, тут если программисту проще на каком-нить языке написать, пусть на языке напишет, проще словами, пусть словами.
Я согласен, что в С++ огромное количество темных мест, которые берет время выучить. Но и приличный специалист (я не говорю про середнячок) с этим сможет разобраться. Мне что кажется: если ищут толкового человека, а не просто кодераплюс, то во первых ему все равно придется достаточно долго разбираться с новой предметной частью (логично предположить, что для простых задач ищут и кадры попроще) а обучение новому языку это только немного замедлит этот процесс, во вторых и просто найти хорошего специалиста бывает трудно, а хорошего специалиста со знанием языка и предметной области — часто вообще невозможно. Приходиться идти на компромиссы, а единственная часть, которую нельзя восполнить уже «на месте» — это голова на плечах. К тому-же С++ это действительно один из самых сложных языков. А наоборот, человека хорошо знакомого с С++ и еще чем нибудь (чтоб совсем голова не была забита в одном направление) ну совсем не проблема посадить писать как каком-нибудь Питоне/Джаве/С#/etc.
А насчет псевдокода — я не согласен. Мне кажется, что на собеседовании обязательно хотя бы одну задачку дать написать на настоящем языке. Почему-то есть куча людей, особенно с академическим бекграундом, которым без особых проблем могут объяснить на словах алгоритм, но когда доходит до деталей реализации, делают совершенно «детские» ошибки.
А насчет псевдокода — я не согласен. Мне кажется, что на собеседовании обязательно хотя бы одну задачку дать написать на настоящем языке. Почему-то есть куча людей, особенно с академическим бекграундом, которым без особых проблем могут объяснить на словах алгоритм, но когда доходит до деталей реализации, делают совершенно «детские» ошибки.
Толковый может выучить, поэтому я в итоге проверяю только определенные и довольно простые темные места. Если с ними справился, подходит.
Ну я прошу 1-2 задачки на С++ (тут совсем простые алгоритмы, требуется по сути решение в лоб), прошу найти ошибки в хитром коде с кучей темных мест и 1-2 задачки алгоритмических (алгоритмы подбираю такие, что есть решение в лоб с порядочной сложностью и если немного подумать, сильно можно упростить), тут только описать требуется, а дальше испытательный срок покажет.
Ну я прошу 1-2 задачки на С++ (тут совсем простые алгоритмы, требуется по сути решение в лоб), прошу найти ошибки в хитром коде с кучей темных мест и 1-2 задачки алгоритмических (алгоритмы подбираю такие, что есть решение в лоб с порядочной сложностью и если немного подумать, сильно можно упростить), тут только описать требуется, а дальше испытательный срок покажет.
Нафиг нафиг, сделали из себя элиту, а сервисы элементарно тормозят.
Чота как-то не впечатлил топик. Я не стану использовать его как руководство, когда пойду в гугл.
Ссылка на первую часть топика в начале была бы совсем не лишней :)
Это доллары в год или рубли в месяц?
Ну не такая уж и большая зарплата.
Да, 8 с лишним тысяч в месяц, да, копейки.
Даже если взять фейсбуковскую ЗП, 100500 и, например, 36% налога, то сколько остается? почти 6к баков? При стоимости дома кредит 1,5к, + еда 1,5к + машина кредит 1к + связь, быт 500 = 4500
Остается 1500, эти деньги на развлекаловку, одежду, болезни, садики, курсы, гаджеты, игрушки для детей и пр.
При этом это самая высокая (средняя-) зп в отрасли.
Остается 1500, эти деньги на развлекаловку, одежду, болезни, садики, курсы, гаджеты, игрушки для детей и пр.
При этом это самая высокая (средняя-) зп в отрасли.
Забыл про премии еще, может все и не так плохо тогда)
Вопрос про зарплаты конечно интересный и в каком-то смысле философский.
Есть есть где жить, что кушать, машина и всё такое — то чего ещё желать?
Пенсию, кстати тоже надо откладывать (частную, в дополнением к государственной) — 6% от зарплаты считается разумным. Пенсия откладывается ДО налогов, то есть не облагается налогом.
Но хотел бы уточнить несколько вещей:
1. Машина 1к — это же не постоянно — выплатили кредит и дальше ездить раз в полгода на техобслуживание, порядка $50.
2. Связь сотруднику Гугла оплачивается — и мобильник и очень хороший интернет.
3. Гугл даёт очень хорошую медицинскую страховку. Я лично плачу только $10 за визит к любому врачу. Когда видел сколько платит за это страховая компания — глаза на лоб вылезали :-)
4. У меня выходит немного меньше 1к на еду для трёх человек. Сюда же входит и всякая химия, хоз. товары — покупается всё в одном супермаркете.
5. Садик, точнее pre-K стоит $25/неделя.
Есть есть где жить, что кушать, машина и всё такое — то чего ещё желать?
Пенсию, кстати тоже надо откладывать (частную, в дополнением к государственной) — 6% от зарплаты считается разумным. Пенсия откладывается ДО налогов, то есть не облагается налогом.
Но хотел бы уточнить несколько вещей:
1. Машина 1к — это же не постоянно — выплатили кредит и дальше ездить раз в полгода на техобслуживание, порядка $50.
2. Связь сотруднику Гугла оплачивается — и мобильник и очень хороший интернет.
3. Гугл даёт очень хорошую медицинскую страховку. Я лично плачу только $10 за визит к любому врачу. Когда видел сколько платит за это страховая компания — глаза на лоб вылезали :-)
4. У меня выходит немного меньше 1к на еду для трёх человек. Сюда же входит и всякая химия, хоз. товары — покупается всё в одном супермаркете.
5. Садик, точнее pre-K стоит $25/неделя.
Честно говоря, не ожидал, что зарплаты в Yahoo такие высокие. Выше чем в Google и Oracle.
UFO just landed and posted this here
Читать файл посимвольно (fgetc) — зло.
Можно же было читать фрагментами и уже фрагмент разделять на строки.
Можно же было читать фрагментами и уже фрагмент разделять на строки.
Зачем проводить лишние расчеты в условии выхода из цикла?
Можно же считать один раз:
Или это уже не важно, т.к. компилятор оптимизирует код?
len = strlen(str);
for(i=0; i < len>>1;i++){
ch = str[i];
str[i] = str[len-1-i];
str[len-1-i] = ch;
};
Можно же считать один раз:
len = strlen(str);
halfOfLen = len>>1;
for(i=0; i < halfOfLen;i++){
ch = str[i];
str[i] = str[len-1-i];
str[len-1-i] = ch;
};
Или это уже не важно, т.к. компилятор оптимизирует код?
Необязательно использовать readlines() в open, даже можно сказать противопоказано, т.к. readlines возвращает список строк, попробуйте сделать это с большими файлами.
Стоит использовать итератор, что выглядит проще и работает на порядок лучше, не загружая в память лишние строки
for line in FIN.readlines():
Стоит использовать итератор, что выглядит проще и работает на порядок лучше, не загружая в память лишние строки
for line in FIN:
Несколько вопросов для знающих:
1.
Неужели современные компиляторы сами не заменяют деление на 2 побитовым сдвигом?
2. Не в курсе как реализована стандартная strrev в C?
Функция переворота строки из книги Керниган Ритчи по С(без промежуточного буфера):
1.
len>>1
Неужели современные компиляторы сами не заменяют деление на 2 побитовым сдвигом?
2. Не в курсе как реализована стандартная strrev в C?
Функция переворота строки из книги Керниган Ритчи по С(без промежуточного буфера):
for (i = 0, j = strlen(s)-1; i < j; i++, j--) {
c = s[i];
s[i] = s[j];
s[j] = c;
}
Ой, извините
#include <string.h>
void reverse(char s[])
{
int c, i, j;
for (i = 0, j = strlen(s)-1; i < j; i++, j--) {
c = s[i];
s[i] = s[j];
s[j] = c;
}
}
C++ может быть и оптимизирует, а вот Java точно нет. Выполнение арифметических действий и аналогичных им битовых операций существенно отличается по времени. И никакой оптимизации!
Я лично был в шоке, когда узнал, что стандартный перевод из String в BigInteger в случае, когда String содержит двоичную или шестнадцатиричную запись числа, происходит за O(n^2)
Я лично был в шоке, когда узнал, что стандартный перевод из String в BigInteger в случае, когда String содержит двоичную или шестнадцатиричную запись числа, происходит за O(n^2)
Делить на 2 сдвигом вправо бессмысленно (это тривиальная оптимизация и любой компилятор деление соптимизирует сам), а тип bool присутствует в стандарте C99.
Не бессмысленно, потому что так вы сразу получаете целое число, а если вы делите на 2, то вам округлять надо (не помню как там в C с этим)
Си — строго типизированный язык, поэтому в инте нецелого числа лежать не может. :)
Немного нелогично получилось. :)
В int — всегда целое, это понятно. А результат деления записывается в переменную типа int, поэтому нецелого результата ожидать не приходится.
В int — всегда целое, это понятно. А результат деления записывается в переменную типа int, поэтому нецелого результата ожидать не приходится.
Да хоть во float записывать, всё равно целое число будет.
Правильнее было бы сказать, что если оба операнда оператора деления целые, то и деление происходит нацело. Если хотя бы один вещественный, то и результат будет соответствующий.
Правильнее было бы сказать, что если оба операнда оператора деления целые, то и деление происходит нацело. Если хотя бы один вещественный, то и результат будет соответствующий.
Преобразование типов же.
Вообще-то, деление целого числа на 2 и сдвиг — это разные операции. Например, (-3)/2==-1, а (-3)>>1==-2. Так что если компилятор и оптимизирует это, ему приходится повозиться: для отрицательных чисел после сдвига выполнять adc, а для неотрицательных оставлять результат, как есть. Лучше бы ему немного помочь.
sumOfFile = lambda filename: sum([int(line) for line in open(filename, 'r').readlines()])
Здесь надо заменить квадратные скобки на круглые (или просто их убрать):
sumOfFile = lambda filename: sum(int(line) for line in open(filename, 'r').readlines())
В этом случае не придётся беспокоится о создании большого списка. Читайте про generator expressions.
> С лямбдой проблема может быть в том, что сначала мы создадим лист, и только потом просуммируем все его элементы. Если файл огромный — мы зря потратим память на создание этого листа.
Если файл огромный мы зря потратим память на «open().readlines()» (для обоих случаев), лучше использовать просто «open()»
try… except можно пренебречь если «не цифры» пропустить «string.isdigit()»
в итоге «однострочник» мог-бы выглядеть например так:
sumOfFile = lambda filename:sum( imap(lambda x:int(x), ifilter(lambda x:x.isdigit(), imap(lambda x:x.strip(), open(filename,'rb')))) )
Если файл огромный мы зря потратим память на «open().readlines()» (для обоих случаев), лучше использовать просто «open()»
try… except можно пренебречь если «не цифры» пропустить «string.isdigit()»
в итоге «однострочник» мог-бы выглядеть например так:
sumOfFile = lambda filename:sum( imap(lambda x:int(x), ifilter(lambda x:x.isdigit(), imap(lambda x:x.strip(), open(filename,'rb')))) )
C нетерпением ждём продолжения)
> int reverse(char *str); /* возвращаем 1(True), если выполнились удачно */
Обычно если функция возвращает код выхода, то это 0, если все успешно. Причина логична: успешный исход обычно один, а разных ошибок может быть несколько (и в таких случаях код выхода обычно указывает на ошибку, которая произошла во время выполнения).
Обычно если функция возвращает код выхода, то это 0, если все успешно. Причина логична: успешный исход обычно один, а разных ошибок может быть несколько (и в таких случаях код выхода обычно указывает на ошибку, которая произошла во время выполнения).
Мне кажется варианты переворота строки приведенные здесь весьма дурны.
По этой причине я решил показать вам свой.
Он красив, изящен и лишен недостатков.
void reverse(char *_str, int _len)
{
(_len < 2)? 0: reverse((*_str ^= _str[--_len] ^= *_str ^= _str[_len], ++_str), --_len);
}
_len это просто strlen(_str);
По посту. Если бы я отвечал за набор персонала, то никогда бы не взял на работу человека, пишущего на Си как автор.
По этой причине я решил показать вам свой.
Он красив, изящен и лишен недостатков.
void reverse(char *_str, int _len)
{
(_len < 2)? 0: reverse((*_str ^= _str[--_len] ^= *_str ^= _str[_len], ++_str), --_len);
}
_len это просто strlen(_str);
По посту. Если бы я отвечал за набор персонала, то никогда бы не взял на работу человека, пишущего на Си как автор.
То что вы написали, плохо читаемый мусор, а не изящный код.
Недостатки:
1 — lеn как второй параметр.
2 — рекурсия там где её быть не должно
3 — примесь [] и * для одного и того же массива char
Может не стоит вам заниматься набором персонала?
Недостатки:
1 — lеn как второй параметр.
2 — рекурсия там где её быть не должно
3 — примесь [] и * для одного и того же массива char
Может не стоит вам заниматься набором персонала?
Таким кодом надо маленьких программистов пугать. %)
Выпендриваться — так до конца. Вы для полной нечитабельности дол.ны были ещё написать _len[_str] вместо _str[_len].
Вообще-то, ряд Фибоначии всегда начинается с 0, 1.
Я проходил собеседование на интернатуру в Google. C++ и Java. Помню, задавали написать какие-то очень простые алгоритмы, наподобие тех, что в посте. Что запомнил:
1) Сделать random shuffle массива
2) Написать итератор итераторов на Java (3 метода)
Похожие простенькие задачи были на собеседовании на интернатуру в facebook. Написать функию, возвращающее случайное целое число в отрезке [a; b]
В общем, это сильно отличается от тех сложных структур данных в их рекомендуемой литературе. Моя главная проблема по-видимому была в недостатке коммуникации на заданные задачи и в неправильной стратегии. Необходимая стратегия в этом посте абсолютно правильно описана
1) Сделать random shuffle массива
2) Написать итератор итераторов на Java (3 метода)
Похожие простенькие задачи были на собеседовании на интернатуру в facebook. Написать функию, возвращающее случайное целое число в отрезке [a; b]
В общем, это сильно отличается от тех сложных структур данных в их рекомендуемой литературе. Моя главная проблема по-видимому была в недостатке коммуникации на заданные задачи и в неправильной стратегии. Необходимая стратегия в этом посте абсолютно правильно описана
А еще оценить размер Google Maps в байтах. Почему то на этом вопросе не смог вспомнить ни радиус Земли, ни площадь сферы, ни размер пикселя в байтах. Всегда помню, на нем забыл.
Радиус Земли вспомнить не проблема. А уровень разрешения, который они держат для океанов (или для прерий США) — значительно труднее. Тем более, что время быстро идет вперед.
Это они мне сообщили. Количество пикселей на один квадратный метр мне было дано
а разве нельзя было посмотреть в поисковике формулу для площади и величину радиуса?
Несмотря на то, что собеседование происходит по телефону и через интернет, необходимо постоянно поддерживать живую беседу, и в этих условиях сложно отвлечься на поиск чего-нибудь в интернете, так как скорее это все-таки будет замечено интервьюером (отвлечение от разговора, звуки работы на клавиатуре). У меня едва получалось скопировать в студию для проверки на ошибки компилятором, и то, я подозреваю, это было замечено
По-моему в последней задаче на Ц все можно сделать значительно проще.
int sum=0, input=0;
FILE * pFile;
pFile = fopen ("myfile.txt","r");
while(fscaf( pFile ,"%d", &input) != EOF)
sum+=input;
ptintf("sum = %d\n", sum);
Сразу вспомнился каноничный эзотерический метод нахождения чисел Фибоначчи
for (a1=a2=1; i>2; a1=(a2+=a1)-a1) i--;
for (a1=a2=1; i>2; a1=(a2+=a1)-a1) i--;
Sign up to leave a comment.
Я хочу работать в Google! Телефонное интервью (часть 2)