Нехитрый вопрос на собеседовании или как не попадают в стартапы
Алексей КолупаевОпубликовано 12.06.2008 в Статьи
Всем привет, меня зовут Алексей Колупаев, и мне посчастливилось познакомиться с людьми, которые изменили мою профессиональную жизнь: я делаю новый стартап. Именно от меня будет зависеть вся техническая часть нового народного финансового портала. И, на данном этапе, это означает, что мне нужно собрать убийственную команду и так построить процесс, чтобы добиться суперэффективности. Есть мнение, что собрать классную команду очень нелегко. Мне довелось поработать в интересных местах, со многими интересными людьми и провести, наверное, около сотни собеседований, в основном, PHP-программистов. Пользуясь случаем, хочу поблагодарить всех, кто приходил ко мне на собеседования – вы многому меня научили. И я хочу поделиться со всеми одной из своих самых любимых задачек для собеседования.
Придумал ее, разумеется, не я, а прочитал, кажется, у Джоела Спольски. Слышал, что ее дают на собеседовании в Microsoft. В коротком варианте она звучит так: «как повернуть строку задом наперед?». Подозреваю, что в Microsoft не ожидают ее решения на PHP, а вероятно, на С или С++. Прелесть задачи состоит в том, что она мало говорит о языке и много – о программисте. В моем варианте она звучит так:
<?php
$a = 'abcdefgh';
// Напишите здесь недостающий код, чтобы результатом работы скрипта была строка $a, повернутая наоборот
echo $a;
?>То есть, этот скрипт должен выдавать
hgfedcbaВот в этом месте предлагаю всем читателям, владеющим PHP, решить эту несложную задачку. А я поделюсь с вами тем спектром решений, которые я получал во время проведения собеседований.
Нет, правда, попробуйте.
Итак, буду оглашать и комментировать варианты ответа в порядке моего личного, субъективного, наверняка в чем-то ошибочного понимания правильности решения.
5. Номер пять в моем хит-параде занимает ответ «я не знаю, и не буду это писать». Иногда с вариантом «что за дурацкая задача, в жизни такого не бывает». Слив, как говорится, засчитывается сразу.
4. Номер четыре занимает вариант «В PHP вроде должна быть такая функция…». Что ж, справедливости ради, должен сказать, что в PHP действительно есть такая функция. Названия ее, конечно же, никто не помнит. Это нормально. Но неужели вы думаете, что я задавал эту задачку, чтобы услышать такой ответ? Следом за таким ответом предлагаю реализовать эту функцию самостоятельно. То есть, как отмазка не канает, надо писать.
3. Место номер три уходит семейству решений под девизом «ну, как-то через массивы». Код при этом, разумеется, выглядит по-разному, и до победного конца (работающего и выполняющего задачу скрипта) добираются не все адепты массивных решений. Функции explode() и, соответственно, implode() приходят в голову далеко не всем, а уж что пытаются делать между ними – прямо стыдно рассказывать. Даже сортировку. Решение с массивами формально годится, задача должна быть в первую очередь решена, а потом уже можно и заняться оптимизацией, и поговорить о производительности, и так далее. Нюанс в том, что решить задачу через массивы не так уж легко, потому что массивы тут не нужны. Есть у меня подозрение, что такое решение говорит о том, что человек недостаточно работал с примитивными типами данных, а был в детстве ранен в мозг простотой и легкостью динамических массивов в PHP. Но человека, более-менее писавшего, например, на С, таким не обмануть. Так что в целом – подходу незачот.
2. Следующее решение – минимально адекватное для того, чтобы я рассматривал человека всерьез:
$b = '';
for ($i = strlen($a)-1; $i>=0; $i--)
$b .= $a[$i];
$a = $b;Возможны, понятно, некоторые вариации.
Такое решение встречается в большинстве случаев, не всегда с первого раза, правда. В этом решении есть нескольно важных мест:
strlen()вынесен из тела цикла и выполняется один раз (есть ли понимание того, что это зло?)- минус один от длины строки (сколько шишек об это уже набито?)
- как там с ноликом – больше или больше-равно? (те же, в принципе, шишки)
Так как часто это задание я предлагаю решить на бумажке, сразу видно, что человек учитывает сходу, а что «подтачивал» бы по результату.
1. Джедайские техники. Чемпионов видно по джедайским техникам решения задач, хочется верить, что такие люди хотя бы листали Кнута. Мне известно только две, на собеседовании я встретил их буквально один или два раза. Первая, которую я таки встречал (Вадим, привет) заключается в том, чтобы использовать цикл вдвое меньшей длины и менять местами соответствующие символы:
$b = '';
$l = strlen($a)-1;
for ($i = 0; $i < $l/2; $i++) {
$b = $a[$i];
$a[$i] = $a[$l-$i];
$a[$l-$i] = $b;
}
Вторая джедайская хитрость состоит в том, чтобы поменять местами символы в строке без использования третьей переменной. Очень сильно удивлен, что многие не знают, как это сделать даже для чисел. А тут – символы. А так хотелось бы, что-то кто-то написал что-то вроде
$a[$i] = $a[$l-$i]^$a[$i];
$a[$l-$i] = $a[$l-$i]^$a[$i];
$a[$i] = $a[$l-$i]^$a[$i];Задачка, конечно, «плюшевая». Я сам могу придумать десяток причин, по которым она плоха – не отражает знание PHP, не соответствует реальной жизни, что вообще она показывает, бла, бла, бла. Как, например, понять, догадался человек о таком решении или просто читал о нем где-то еще? Неважно. Уверяю вас – пользуясь этой задачкой (и, конечно, еще многими другими) я еще ни разу серьезно не ошибся с кандидатом. Ведь формальное знание PHP в кандидате – поверьте, далеко не главное. Значительно важнее – отношение к своему занятию, стремление к развитию, способность играть в команде, видение мира, если угодно. Мне гораздо интереснее, как человек решает задачу, чем ее фактическое решение. Грань между этими вещами довольно тонка, но мне кажется – она есть, и понять, что за ней, не так уж просто.
А всем, кто дочитал до этого драматического места, я напоминаю, что наш проект ищет людей, которые обладают талантами PHP-программистов, которые в начале этой статьи все-таки решили эту задачку и ответ находится в первой или второй группе решений. Таким программистам мы хотим рассказать о прелестях работы в стартапе, о чудесах, на которые способна маленькая но мощная команда, вооруженная разносторонними знаниями, оснащенная лучшими средствами производства гениальных проектов и мотивированная нашими, украинскими, реальными рыночными целями. Если вы хороши, действительно хороши в PHP, и это не единственный ваш язык программирования, если у вас есть свое мнение относительно модели MVC и пара серьезных проектов за спиной, если вам не все равно как происходит развитие проекта, и вы болеете душой за agile, scrum и xp, если вы еще недостаточно закостенели и готовы броситься с головой в проект, где надо будет реально показать то лучшее, на что вы способны – то у нас есть к вам предложение мечты. Но задачка на собеседовании будет другая 
Алексей Колупаев,
kolupaev@gmail.com
(40 голосов, средний: 3.33 из 5)
Загрузка ...Понравилась статья? Подпишись на обновления по RSS/E-mail
Прикольно, если бы мне такие задачи давали при поступлении на работу
Кстати, по задаче, я бы тоже сделал вариант с половиной строки, вот как я это прокоментировал
(не силен в PHP, балдею по С++)
$b = ”;
$l = strlen($a); //Не будем вычитать 1
//посколькьу деление на 2 четного числа дает правильные результат, например если
//строка состоит из 8 символов, 8/2=4, в условии можно поставить так:
//for ($i = 0; $i < $l/2; $i++)
//это даст обращение ко всем 4 символам с начала, и
//тоже самое для нечетного числа, например 9, 9/2=4
//тоже даст обращение к 4-рем символам, что надо, а обращение к 5-тому символу некчему,
//т.к. одно центральное и менять местами его не к чему
for ($i = 0; $i < $l/2; $i++) {
$b=$a[$i];
$a[$i]=$a[$l-(i+1)];
$a[$l(i+1)]=$b;
}
О, блин..
И что, люди, которые не решали эту задачу не получали работу?
А я вот думаю, неужели в Microsoft дают ТАКИЕ задачи при поступлении на работу??? |)
да, особенно важно сделать это через XOR, очень повышает читаемость.
Задачу надо было ставить как
// Напишите здесь недостающий код, с наибольшим кол-вом выебонов, чтобы результатом работы скрипта была строка $a, повернутая наоборот
сначало вспомнил что в пхп есть функция для реверта строки, потом конечно подумал о втором варианте, но когда увидел пункт “джедайские техники” задумался как можно оптимизировать, вот мой ответ:
$a = '1234567';
$i=strlen($a);
for($z=$i/2; $z>=0; --$z) $a .= ($a[$z+$z] . $a[$z+$z-1]);
echo substr($a, $i) . "\n";
for($z=$i/2; $z>=0; –$z) $a .= ($a[$z<<1] . $a[($z<<1)-1]);
))
чтобы повысить читаемость
$a = ‘abcdefgh’;
$a = ‘hgfedcba’;
echo $a;
Строки в php состоят из байтов или символов? Как эти прекрасные решения будут работать с мультибайтными кодировками?
Устроили конкурс на джедайкие приколы
Да все всем понятно
побитово оно даже красивей выглядит 
ЗЫ: Кто знает смысл этого вопроса ? Сколько будет 3 + 6
Это просто такая MAPTCHA
+1 за вариант $a = ‘hgfedcba’;
$a = 'abcdefghi';
$l = strlen($a);
$b = '';
for($i=0;$i<$l;$i++) {
$b = $a[$i].$b;
}
$a=$b;
а вот так сильно калично?
Много слов ни о чем – 1/5
<?php
$a = 'abcdefgh';
# First
$a1 = strrev($a);
# Second
$a2 = $a;
$len = strlen($a);
for($i=0;$i<$len/2;$i++) {
$tmp = $a2[$i];
$a2[$i] = $a2[$len-$i - 1];
$a2[$len-$i - 1] = $tmp;
}
#Third
$a3 = join("",array_reverse(preg_split("//",$a,-1,PREG_SPLIT_NO_EMPTY)));
#Fourth
$a4 = "";
$len = strlen($a);
for($i=0;$i
кто больше ?
а я как раз бы таких джидаев и не брал.
он накалякает эту галиматью, тест конечно же не напишет – потом как таких бойцов всегда услышишь – “я тесты не пишу у меня код изначально правильный”, а потом покинет проект – и ты сойдёшь с ума пока найдёшь почему вдруг такой код перестал работать к примеру на ютф-ной кирилице
Ну, я не безнадёжен, наверное. Сначала подумал про «половинный» цикл, потом решил, что по сравнению с прямым (2) он всё равно особого выигрыша не даст, а прямой понимать проще.
Но. До всего этого у меня возник вопрос — в сколькобайтной кодировке у нас строки? Последние несколько лет работаю исключительно с utf-8, а тут в условиях даже намёка нет. Подозрительно. В жизни бы спросил обязательно.
А вот то, что при оглашении вариантов решений Вы про мультибайты даже не упомянули — вот это уже как-то странгно смотрится. Понятно, что ни один прдложенный код без доработки напильником с мультибайтом не прокатит.
Хм, а спрашивали другое. А вообще люблю интересные задачи на собеседовании, только мало кто пердлагает
А вот и я.
Отвечаю по порядку:
> Прикольно, если бы мне такие задачи давали при поступлении на работу
А какие задают?
Смотри, зачем минус один: ты делишь количество символов (например, 9) пополам, получаешь 4.5. Условие цикла выполнится для 0, 1, 2, 3, 4, и для значения 4, получается, будешь менять символ [4] (то есть пятый в строке) на символ $l-(i+1), то естть 9-(4+1)=4, то есть на тот же самый.
>И что, люди, которые не решали эту задачу не получали работу?
Ну я же писал – задач много, это не единственная. А решение принимается по итогу. Но вообще, если человек не в силах обернуть строку задом наперед, то он и с остальными задачами справляется не очень, как показывает практика. Как-то так получается.
Ребята, я поделился только одной задачей, потому что мне кажется, что она интересная. Это не единственная задача, и ни одна задача не покажет ничего, кроме умения решать эту задачу. Поэтому задач много, а знания и умения – это и есть то, что проверяется на собеседовании.
> Напишите здесь недостающий код, с наибольшим кол-вом выебонов
Я еще часто слышу аргумент “я не силен в теории, дайте мне реальную задачу – я ее решу, а вот такое вот непонятно что, программирование ради программирования – это все выебоны. А я – суровый и серьезный практик”. Мое мнение по этому поводу – есть теоретическая подготовка, есть ее применение на практике. Это не взаимозаменяемые категории. Данная задача в большей степени академическая, естественно.
> echo substr($a, $i) . “\n”;
Да, вариант с подстрокой тоже интересный, и мне в собеседованиях попадался несколько раз, редко.
> $a = ‘hgfedcba’;
5!
> Строки в php состоят из байтов или символов? Как эти прекрасные решения будут работать с мультибайтными кодировками?
Я подозреваю, что хреново будут работать.
> а вот так сильно калично?
Вполне, вариация решения группы №2
> кто больше ?
Кто сможет придумать больше решений – тот и более крутой программист. Вполне, кстати. Во всяком случае, с фантазией, что немаловажно.
Кстати, вариант
> а я как раз бы таких джидаев и не брал.
шлите к нам, может, они как раз те люди, которые нам нужны
Я такой вопрос уточнил бы.
Какая кодировка входящей строки?
Нужно ли *написать алгоритм* переворачивания?
Если кодировка однобайтовая, тогда, например, так:
$b = ”;
for ($i = strlen($a)-1; $i >= 0; $b .= $a[$i]);
$a = $b;
Джедайские техники — только при жесткой необходимости оптимизации, иначе предпочту более читабельный вариант.
Если нужно просто решить поставленную задачу средствами предоставленного языка, тогда strrev.
А если кодировка мультибайтная (например, UTF-8), тогда без таких библиотек как mb_string не оботись «малой кровью».
В моём примере опечочка закралась. Вместо $b .= $a[$i] нужно написать $b .= $a[$i--]
Автор явно не понял Джоела Спольски. Джедайские варианты действительно на самом деле уменьшают читабельность кода. Джоел принципиально требовал написать код на С, потому что это давало гарантию, что человек понимает, насколько опасны строковые операции (в плане производительности).
Сам Джоел Спольски писал, что С++ знать надо, но он вам врядли пригодится…
> а вот так сильно калично?
Вполне, вариация решения группы №2
вполне калично?
)) и немного пугает то что у вас номерация идёт начиная с пятой группы и вниз – в данном случае №2 – это вторая по-порядку или реальный номер 2 (т.е. минимально адекватное для того, чтобы я рассматривал человека всерьез) ?
У Спольски, понятно, другой оттенок у задачи, но задача тем не менее интересная, и я реально вижу как по-разному ее решают разные программисты. Мне нравится.
А про читабельность – я вам так скажу, что это приемы и способы написания кода, приняте в команде. Приемы, которые знакомы всей команде называют читабельными и понятными, ведь из все “читают”, понимают. Это фактическии означает, что у более профессиональной команды код будет менее “читабельным”, чем у менее опытной. То есть, его смогут прочитать и понять меньше программистов. А что – это действительно очень нужно, чтобы код могли читать непрофессиональные программисты в больших количествах? Это реально преимущество кода? Это лишь увеличивает количество и снижает средний профессионализм программистов, которые потом смогут работать с этим кодом.
Я, кстати, тоже считаю, что С/С++ знать надо.
>Steward
Я имею в виду группу номер 2, приемлемое решение, я считаю.
Так как поступаем с программистом из 19-го и 20-го комментариев?
>1mdm
Я тебе в почту написал. Давай беседовать предметно
Евгений, вопрос не только в читаемости. Из двух “джедайских” вариант с временной переменной будет быстрее и “займет” под неё аж целый регистр. Писать приведенный код с XOR и в низкоуровневых языка — дебилизм, а в PHP так вообще без комментариев.
$b = $a;
$a = ”;
for ($i = strlen($b)-1; $i>=0; $i–) echo $b[$i];
“В джедаи б я пошел, пусть меня научат!”
)
5 баллов
А мне понравился пост – и наши реалии описаны, и код есть, и философия, и авторский стиль изложения мне нравится.
Да ну тут вопрос стоит не в том, какое решение быстрее по факту – это же просто повод поговорить, и обсудить взгляды на этот вопрос, понять, как программист решает задачу, о чем думает.
Джедайские варианты говорят об искушенности ума.
2 Родион Быков
не очень понятно чем это отличается от уже написанного (причём совсем не джедайского) варианта, и при чём тут echo $b[$i]; – задача не вывести символы строки в обратном порядке.. а перевернуть значение самой переменной.
Вообще эта переменная $b тут зачем?
for ($i = strlen($а)-1; $i>=0; $i–) echo $а[$i];работает аналогично вашему коду. только делает не то что надо
Алексей, а не говорит ли о искушенности ума «что за дурацкая задача, в жизни такого не бывает» или например “цикл, и в нем менять символы местами. давайте лучше общаться по делу”? По-моему тот кого такие детские забавы уже утомили — лучший программист.
Возможно, и так, Евгений. Я поэтому сразу сказал – это мой личный, субъективный подход, наверняка в чем-то слишком субъективный. Но я, тем не менее, в него верю, и поэтому делюсь опытом. Брать ли себе его на вооружение – дело ваше.
>$a[$i] = $a[$l-$i]^$a[$i];
>$a[$l-$i] = $a[$l-$i]^$a[$i];
>$a[$i] = $a[$l-$i]^$a[$i];
Полный дебилизм. Кстати не задумывалисьл что будет если в строке на одинаковых позиция от начала и от конца будут одинаковые символы?
Steward, где Ваше чувство юмора ? Могу пояснить – единственной целью задачи является вывести перевернутую строку. Мой код это делает
Переменная b нужна потому что внизу авторской задачи стоит echo $a — если выводить $a[i], выведется hgfedcbaabcdefgh
Мне этот пост понравился намного больше чем пустопорожние переливания про гномов и шапки.
Меня что удивило в этой истории: на собеседование в стартап (планка заранее поднята выше обычного) приходят люди, знания которых не доходят и до 2й позиции хитпарада. Правду говорят на западе – “русского программиста” легко отличить по завышенному самомнению.
>что будет если в строке на одинаковых позиция от начала и от конца будут одинаковые символы?
И что же будет, Игорь?
Алексей Колупаев – всякий подход субьективен, Вы набираете человеков себе в команду, в стартап – кроме Вас лично никто не может сказать брать кандидата или нет. Успех не сводится к знанию PHP, и поэтому я “за” такие субъективные методы. Спасибо за интересный опыт.
судя по приведенному хит-параду ответов, функцию strrev не угадал никто из претендентов ???
вот жеж разошлись))))
Этот, как и многие другие — афигенный пример того, как ловят людей по глазам.
Первые две секунды после вопроса решают все. просто загляните в глаза собеседуемого.
Интересно, какое решение предлагает сам автор?
А, кстати, мне реально интересно, в какой кодировке будет работать Ваш стартап:)
вероятнее всего, в UTF-8
Помоему стартап обречен на провал…
Объяснять не буду, все и так понятно
На джедайском варианте сломал глаза. Лучший вариант:
a = a[::-1](Python)44: собеседование на питониста ты прошел. Берем.
Урра! Я джедай! =)
Фраза – жесть! А вообще этого говорит о том, что в университете/школе программировать человек не учился, следовательно недостаток фундаментального образования.
alexs:
Тебя ещё твой тим-лид за такое не пристрелил? Это дело времени.
alexsun:
+1
… и громкий призыв ПРИЙДИТЕ К НАМ РАБОТАТЬ! МЫ ГА%%НА НЕ ДЕРЖИМ
to Vadim Voituk
как видишь жив
Что тебе не понравилось в этом коде ?
Вот как-то решал я такую задачку, кажется решил.. э.. с ошибками, которые тут же на бумажке и подправил. И еще решал на том же собеседовании другую задачку из тех что так любит Спольски.
В общем, то собеседование я прошел, но по итогам нескольких месяцев работы в той конторе я сделал вывод – от тех, кто задает такие задачи на собеседованиях, надо держаться подальше.
Но это все сугубое имхо.
Небольшое уточнение, чтоб исключить кривотолки. “Та” контора никакого отношения к автору поста, Алексею Колупаеву то бишь, не имеет
А то мало ли кто чего подумает еще…
а как же рекурсия? оно ж как минимум красиво ^-^
самое верное решение.
Рекурсию, увы, никто по своей инициативе не сделал (я иногда ставлю это в условие). А это действительно красивое решение.
Откровенно говоря php, C++ и C не одно и то же
for ($i = 0, $j = strlen($s) - 1; $i < $j; ++$i, --$j) {
$tmp = $s[i];
$s[i] = $s[j];
$s[j] = $tmp;
}
for (std::string::iterator i = s.begin(), j = s.end() - 1; i < j; ++i, --j)
std::swap(*i, *j);
char* i = s;
char* j = s;
while (*j != '')
j++;
j--;
while (i < j) {
char tmp = *i;
*i = *j;
*j = tmp;
}
//Джедайи маст дай
)
//ИМХО ответ в стиле “в PHP есть\должна быть такая функция reverse, stringreverse и тд” вполне приемлимо для поиска в гугле (если уж и подзабыл такую “часто используемую” функцию
$a = ‘abcdefgh’;
$a = strrev($a);
echo $a;
Блин, ну нефигась… вчера сдесь небыло ниодного коментария, стоило мне что то ляпнуть..
ОФТОП: Народ, кто подскажет где можна заработать на програмировании через интернет, или вообще для начинающих программистов в Москве к примеру.
Человек, раненый в мозг курсом функционального программирования (lisp!lisp!) в институте, мог бы решить задачу примерно так:
function rev($str) {
return strlen($str) ? array_merge( array(rev(substr($str,1))), array($str[0]) ) : array();
}
print join(”,rev(’bla’));
Вам таких не попадалось ? %)
Или вот еще странный (джедайский ?
вариант:
$ol = $l = strlen($a); while ($l) $a .= $a[--$l]; $a = substr($a,$ol);
Ну и напоследок: Perl рулит даже когда он всего-лишь “P” в “PCRE” в PHP:
$a = preg_replace(’/^(.)(.*)?(.)$/’,'$3$2$1′,$a);
fix: array() вокруг rev(substr…) не нужно
а про вывод на рекурсивном возврате никто из джедаев не вспомнил?
но ИМХО лучшее решение для PHP это strrev()
Если напишете более быстрый код – отошлите в Zend, и вам все скажут спасибо
Писать весь код в одну строку – это не истинное джедайство
Регэкспы как подход интересны, но в контексте “еще одного решения”.
Хотел бы обратить внимание на количество операторов, которое выполняется в цикле. В варианте 2 в цикле расположен один оператор, следовательно, количество операторов, которые выполняются в цикле равно количеству символов в строке. В варианте 1а в цикл выполняется для половины символов строки, но в цикле находится три оператора, следовательно, 3*0.5 = 1.5, количество операторов которые выполняются в цикле в полтора раза больше. Также хочу напомнить, что РНР не полноценный компилятор, как С. Так что, утверждение, что код в решении 1а, эффективней кода в решении 2, можно поставить под сомнение.
Что касается стиля программирования, то решение 2 несомненно лучше, чем 1а.
Что касается техники подбора кандидатов для обучения, то техника не плохая, и имеет ряд преимуществ перед тестами.
Я бы сказал, что количество операций интересное приближение, но вообще, я бы не стал так наивно сравнивать создание новой динамической строки и добавление к ней элементов в тремя бинарными операциями, соответствующими одному (!) такту процессора.
Решение на Java совсем не простое )
import java.util.*;
public class ReverseString {
public String reverse(String string) {
assert string != null;
Deque stack = new ArrayDeque();
for (String str : string.split(”")) {
stack.push(str);
}
StringBuffer result = new StringBuffer();
for (String str : stack) {
result.append(str);
}
return result.toString();
}
public static void main(String[] args) {
String a = “abcdefgh”;
ReverseString rs = new ReverseString();
System.out.println(rs.reverse(a));
}
}
@javadev:
new StringBuffer('1234567890').reverse()Леша, забудь! В современных языках (тем более интерпретируемых) больше нет операций соответствующих одному такту процессора.
IMHO мерять сложность оепраций тактами процессора стало неактуально.
P.S.
Первая, которую я таки встречал (Вадим, привет) заключается в томНадеюсь это не я такое сморозил?
>В современных языках (тем более интерпретируемых) больше нет операций соответствующих одному такту процессора.
Да, бытует такое мнение.
Я с ним полусогласен. В том смыле, что, конечно, это далеко не тоже самое, что и xor ax bx, однако тем не менее мы не используем наследные PDP-шные / С-шные строки с нулем в конце, и не перебираем их, каждый раз увеличивая длину, как в случае со второй строкой. Я даже не поленился и сделал тест – xor работает, как и ожидалось, быстрее.
> Надеюсь это не я такое сморозил?
Алексей Колупаев: Дык я же не утверждал что способ с поиском подстроки будеь быстрее. Это было к фразе про такты процессора.
Знаешь, я думаю, что PHP будут некоторые “накладные” расходы по адресации переменных, но в итоге, где-то там все равно будет стоять аппаратная команда xor. Ну не эмулируют же они ее, ей-богу.
то есть, все не так просто, но и не слишком-то сложно.
Чуваки, вы суровы!
Кроме strrev() вижу адекватным решение только через массивы:
$a=’asdfgh’;
$b=str_split($a);
krsort($b);
$a=implode($b);
мне 11 числа на собеседовании по С/С++ такую же задавали. Написал за минуту без предварительного обдумывания, потом понял свою ошибку и расстроился – я не изобразил напряженную работу моска, они наверняка решили, что видел эту задачу и зазубрил правильный ответ:
char* strrev(char* s){
int l=0, r=strlen(s)-1;
while(l<r){
char x=s[l];
s[l]=s[r];
s[r]=x;
r--;
l++;
}
return s;
}
Вопрос к залу – такие загадки для младших школьников только РНР программистов должны пугать, или я сильно недооцениваю свой уровень?
pako, им мог не понравится Ваш стиль написания. Я бы написал так:
for(;l<r;r–,l++)
{
char x=s[l];
s[l]=s[r];
s[r]=x;
}
Потому что в случае усложнения задачи, Вы можете незадумываясь вставить внутрь цикла continue. В Вашем же случае, необхдимо проверить, не получители Вы бесконечный цикл.
Все это конечно мелочи, но они должны выскакивать на автомате и тогда программист огородит себя от большинства ошибок, а следовательно подымет свою производительность.
Однако, хочу заметить, что стиль программирования – вещч субъективная и в одной команде тим лидер требует один стиль, в другой будет требовать такой как у Вас.
Кстати, если бы Вы таки понапрягали свой моск, то могли бы оптимизировать свой алгоритм, уменьшив кво переменных на одну. Правда, я в этом не вижу смысла, так как в современном программировании преждевременная оптимизация не приветствуется.
Ещё, хочу добавить поводу оценки производительности: С++ отличает от РНР тем что в нем более точно регламентировано способ хранения данных. Это с одной стороны дает большую свободу разработчикам РНР. С другой стороны, если разработчики изменят способ хранения или обработки строк, то алгоритм работающий эффективно на РНР4 может начать работать медленее на РНР5…
ИМХО пижонство это – в такой задаче думать о супер-стиле или супер-оптимизации.
Какие последствия того, что ты не учел возможные доп. требования? Придется при их появлении в худшем случае переписать с нуля всю функцию – а это аж целых 5-7строчек, которые заняли у тебя 2 минуты.
Не надо путать одну функцию с диаграммой классов, которая лечится неделей рефакторинга или рестартом проекта:)
Примерно то же и с оптимизацией.
Думаю что статья вовсе не о том, что успешный кандидат должен в ответ на вопрос “напишите нам хелловорлд на жаве” нарисовать на бумажке тех.задание, календарный план разработки, UML-диаграммаму, юниттесты, код, описать протоколирование ошибок, администрирование доступа к приложению и т.п.
Я не говорил о том что в “в такой задаче думать о супер-стиле или супер-оптимизации”. Я говорил, что хороший стиль должен вылетать с под пера автора на автомате.
Может случится так что ты сначало напишешь маленькую функцию, а потом в следствие изменившихся требований она вырастет в очень большую и если придерживаться хорошего стиля изначально, то можно избежать мноих ошибок, а следовательно и увеличить производительность.
Джоел Спольски писал, что программист подобен жанглеру с туевой хучей шариков. Только программист жонглирует не шариками, а мелкими деталями в краткосрочной памяти. Использование хорошего стиля уменьшает количество этих деталей, а значит и меньше вероятность, что какой-нибудь шар останется незамеченным и он упадет.
Однако опять повторюсь, что хороший стиль – вещь субъективная и я не претендую на эталон хорошего стиля.
Если бы кандидат начал писать “тех.задание, календарный план разработки, UML-диаграммаму, юниттесты, код, описать протоколирование ошибок, администрирование доступа к приложению и т.п.”, я бы его взял незадумываясь, потому что как раз это обычно некому делать.
А тебя я бы не взял, потому что ты не принимаешь критику. В комманде это может стать ступором.
хм .. а Паша и Веталик отказываються проводить собеседования?))
Отвечал бы через strrev. Ну а если бы уже нужно было написать свою реализацию – то писал бы через цикл.
Но в целом – по одной этой задаче еще мало чего можно судить. Алексей, давайте еще задачи в студию из своего арсенала, посмотрим и на них.
Помилуйте, господа, а что же я буду задавать на собеседовании?
Их не так-то легко генерировать, как может показаться.
возможно. но я высказал одно возражение по одному твоему посту – помоему слишком рано судить, воспринимаю ли я критику. так что могу обвинить тебя в аналогичном недостатке
“но я высказал одно возражение по одному твоему посту – помоему слишком рано судить, воспринимаю ли я критику.” Вот в этом то и корень зла собеседований – слишком мало всего чтобы поставить оценку. Поэтому Джоел Спольски и пытается затащить студентов к себе на летнюю практику, чтобы когда они закончат учиться и будут устраиваться, он имел намноги большее представление, что они из себя представляют.
“Помилуйте, господа, а что же я буду задавать на собеседовании?” А вы не оглашайте здесь свою реакцию на посты и тогда кандидатам тяжело будет играть из себя хорошего.
Гыы
ну чем не вариант
$a = ‘abcdefgh’;
$b = str_split($a);
$a=”;
while($z = array_pop($b))
{
$a .=$z;
}
echo $a;
Задача в исходном виде слишком простая. В задаче нужно повышать уровни сложности:
1 уровень. хоть как-нибудь перевернуть строку
2. перевернуть строку, которая занимает всю оперативную память
3. перевернуть как можно быстрее на многопроцессорной системе
4. перевернуть в файле на диске, файл в память не влезает, memory mapping-а нету.
5. файлы – в utf8
6. как можно меньше использовать CPU, выполнять основную работу на GPU
думаю найбільш ефективним рішенням буде внутрішня ф-ція, а ті всі хитрості будуть повільними – інтерпретатор всетаки
)
Ну а это чем не вариант
$len = strlen($str)-1;
for ($i = 0; $i < $len/2; ++$i) {
list($str[$i], $str[$len-$i]) = array($str[$len-$i], $str[$i]);
}
ну или это
function rev ($str, $len) {
if ($len == 0) return $str;
$len–;
return $str[$len].rev(substr($str,0, $len), $len);
}
strrev нашел за 5 сек в гугле, и чего вы добиваетесь вот этими заморочками, неужели думаете, что напишите что то лучше чем функцию из стандартной библиотеки?
2 Андрей
Люди перевіряють, чи кандидат в змозі написати два рядки тривіального коду без помилок. Цей тест відсіює набагато більший відсоток кандидатів, ніж здається на перший погляд.
Ти не пройшов
Представьте на секунду, что вы не программист (если вы программист), а сами проводите собеседование с программистом. Взгляните на собеседование с другой стороны. Самое главное, что надо понять – подходит ли вам этот человек. Не гениален ли он, не знает ли он PHP, не сколько у него лет опыта, хотя все это и интересно. А только – подходит ли ОН ВАМ. Лично он лично вам.
Поскольку мне с этим человеком, возможно, вместе делать проект, мне хочется понять: как он относится к разработке, к инструментам, к своей роли в проекте, как решает задачи, какими абстрактными категориями оперирует. И самое главное – совпадает ли это с моим видением идеальной команды. Сможем ли мы тянуть в одном направлении. Заметьте, в первую очередь – в одном направлении.
Нет объективных критериев оценки. Поэтому мне на самом деле вообще не важно, как повернуть строку задом наперед. Но мне интересно, как человек делает то, что мне хотелось бы чтобы он делал в моей команде: эффективно решал проблемы сообща. Вот тут все четыре слова важны: эффективно, решал, проблемы, сообща.
Программирование – это больше, чем поиск подходящих функций в мануале. Это больше, чем построение правильной архитектуры. Это командная работа группы людей, и очень важно, чтобы это была дружная и сплоченная команда. И когда в проекте появится необходимость повернуть строку задом наперед я буду уверен, что это будет сделано именно так, как требует того именно этот проект в именно этом состоянии.
автору низачёт за побитовые операции
низя работать со строками побитово в мультибайте
а так прикольная статейка
15:08:59 XXX
http://www.developers.org.ua/archives/kolupaev/2008/06/12/startup-interview/
15:10:57 YYY
я видел
ты предлагаешь асилить каменты?
15:11:13 XXX
хз, я сам не асилил
15:11:23 YYY
решил на мне проверить?
15:11:24 XXX
потому что не увидел там ничего умного
если бы в первых 10 каментах автору сказали, что он идиот, то был бы смысл читать
а комментаторы такие же. видимо считают круто для экономии одного байта делать 3 шаманских XOR’а
15:13:25 YYY
ага, типа нестандартно мыслишь
15:13:56 ХХХ
“нестандартно” – это выражаясь политкоректно.
как на западе инвалидов называют- человек с нестандартными потребностями.
вот так и эти программисты.
15:17:36 ХХХ
On modern (desktop) CPUs, the XOR technique is considerably slower than using a temporary variable to do swapping. One reason is that modern CPUs strive to execute commands in parallel; see Instruction pipeline . In the XOR technique, the inputs to each operation depend on the results of the previous operation, so they must be executed in strictly sequential order.
+ они не асилят эти вырезки из вики на английском
и еще надо отметить, что этот алгоритм не работает в случае, если мы пытаемся одну и ту же ячейку памяти засвапать.aliasing problem
Без буфера можно еще так менять значения
a = a – b
b = a + b
a = b – a
Статейка супер. Абсолютно согласен с автором – именно на таких задачках и проверяется, подходит селовек или нет.
Инициативность, что-ли… Готовность думать…
А то в последнее время уж слишком обленились многие. Да Гугл – хорошо, но, как и сказал уважаемый Алексей, главное – не знание библиотеки стандартных функций, а чувствование.
$a = ‘hgfedcba’;
Более короткое решение. И вполне отвечает условию поставленной задачи.
2 92.илья – очень умнО… просто уписяться… любой нормальный понимает что исходная строка может быть произвольного вида…
Не понимаю смысла вообще в вашем комментарии – блеснуть?
Да вы блеснули – только боюсь в стартап вас не возьмут.
Удачи.
вообщето задачка решаемая для любого студента(IT), котрый хотя бы чуток проявлял интерес к программированию..
сор..забыл нико поставить..))
наверное не джедай :-\ сходу в голову пришло:
$a = ‘abcdefgh’;
$b = ”;
foreach(str_split($a) as $c) {
$b = $c . $b;
}
echo $b;
или, если не забывать что длина строки всегда на 1 меньше самого старшего индекса
foreach(range(strlen($a)-1, 0) as $i) {
$b .= $a[$i];
}
echo $b;
джедаизм
echo join(array_reverse(explode(’ ‘, chunk_split($a, 1, ‘ ‘))));
еще один:
array_walk(str_split($a), create_function(’$c’,'global $b; $b = $c . $b;’));
echo $b;
(недостатки очевидны)
2 93: Steward, разве ответ Ильи не гениальный? супер ИМХО
сколько людей хотят на работу )))))
aRt, по-моему не на работу хотят, а “повыпендриться” и “покичиться”.
Станислав Малкин, ну а как же без этого ? ))) надо ж бляснуть ))
> сколько людей хотят на работу )))))
да и если на собеседовании предлагают решать задачки, сразу разворачиваюсь и ухожу. зачем? возьми с флешки примеры моего кода и пялься скока влезет 
да и есть же испытательный срок в конце-концов 
неее, вот где бы не хотел работать, так это в стартапе в свежесозданной конторе
Ну, Васья, тут есть два аспекта. Первый – твой код на флешке (твой ли?) – это результат. А мне интересен процесс. Как кандидат решает задачу. Готовый код и я на сурсфордже могу скачать, что за интерес? Второй – нам же не нужно, чтобы ты писал код. Нам интересно, чтобы ты создавал проект, в команде с нами. Есть разница?
Код из предыдущих проектов интереснее потому что ближе к тому что получится в рабочей обстановке при реальных задачах. Решение под присмотром, на бумажке, да еще и задачи высосанной из пальца может только показать что человек вообще не понимает о чем речь, для фильтрации хорошо, но решенная задача не говорит ни о чем. В готовом коде можно увидеть есть ли документация, нормальные ли API, думает ли человек о том куда бы всунуть XOR или о том чтобы код работал корректно итд. Даже если код подсунут чужой можно сделать выводы о том какой код этот товарищ считает эталоном, хотя если есть подозрения, то зачем вообще собеседование продолжать?
решенная-то задача, может, и не говорит ни о чем. А вот нерешенная – говорит
Нормальная задача, как для собеседования, только сильно простая, ИМхО. Отсеивает только самых тупых.
Но вообще, всяческих успехов вам, ребята! Даёшь второй Гугль! 
А что до таких понтовых, которые “не решают задачи на собеседованиях” и “ходют с флешками”, то у меня б они и дальше пошли со своими флешками. Если я прошу человека сделать элементарную вещь, а он начинает сразу пальцы гнуть про то, что он “лоховские задачи” не решает, то я не вижу как я с этим человеком буду дальше работать.
Что до ксоров или не ксоров, то автор вроде как сказал, что он оба варианта рассматривает как правильные и смотрит затем по другим задачам. Так что идиот не автор, а кое-кто другой. К сожалению, я не пхпшник, да и деньги мне сейчас приблизительно поровну нужны со свободным временем (очень много других увлечений), так что в стартапы к вам не пойду.
Всегда интересно видеть как даже из комментария к статье делают рассказ о себе любимом. бгг
Алексей Колупаев.
Задача на самом деле бредовая. Я не знаю пхп и никогда на нем не писал, но если там есть стандартная функция, то ваша задача автоматом превращается в разряд маразма. Я бы у вас не работал. Попробуйте задать чтонить пооригинальнее.
Если вы считаете что программист должен беспрекословно(не задумываясь) выполнять задачу, которую ему ставит какойто манагер, а не подумав, выяснить – может задача уже решена?.. То мне вас жалко. Вы ищите быдлокодеров, а не программистов. Программисты думают, а быдлокодеры пишут то, что им скажут.
ЗЫ Моя девушка к вам ходила на собеседование, и хорошо что не устроилась на работу к вам…
Кстати почему-то не увидел варианта с использованием ob_start и ob_get_contents которым собрать результат echo в цикле. А кстати почем 3+6….
Излишне простая задачка.
Задавай что-нибуть посложнее
Не хочется обижать автора – но “Ваш вариант” дико некорректен. Я не знаю ПХП и не программировал со средней школы, но
И боюсь для человека подбирающего сотрудников неумение ставить задачу правильно – проблема.
Не хочется обижать комментаторов.
зацепила эта тема. решил попробывать различные варианты. вы уж извините, за мой кривой C#
вопрос и зачем все эти выпендрежи с XOR, если стандартный способ гораздо быстрее? или я слишком криво написал…
А какой способ “стандартный”?
походу если бы я такое на собеседовании по C# меня наверное бы не взяли… методы RevStr3() и public string RevStr5() эт я загнул… такое количество упаковок и распаковок это я зря. признаю не прав. если к примеру переписать так
то по скорости сопоставим с тем методом, который в стандартной библиотеке
и StringBuilder медленный. массив чаров гораздо быстрее
Ну правильно, хорошая джедайская техника. Зачот.
После комментария №44 писать на C# как-то…
Шарп еще и тормозней в несколько раз. Красота.
WP кавычки расставляет просто феерически. Еще и переносы строк размножились.
А как Вам такой вариант? Вроде такого не было.
Вы, кстати, сделали одну из типичных ошибок, которые я видел на собеседованиях. Я о ней еще не говорил, но вообще-то формально ваш код не решает поставленную задачу. Посмотрите внимательно на условие.
Я к тому, что функционал, который только выводит результат не так универсален, как код, возвращающий результат. Условия задачи косвенно требуют возврата результата, а не вывода, обратите внимание.
А за рекурсию, конечно, зачот. Хотя это и ужасное решение в плане производительности, но владение инструментом рекурсии я склонен оценивать как одну из джедайских техник.
С использованием буферизации вывода
прозрачность против сложности
$a = ‘abcdefgh’;
$l = strlen($a);
do {
$b .= $a[strlen($a)-(++$i)];
} while ($l != strlen($b));
echo $a = $b;
только вместо строки $b .= $a[strlen($a)-(++$i)];
строка $b .= $a[$l-(++$i)]; конечно
> Ravanger
Решение формально правильное, но не зачотное.
Буратино дали пять яблок. Три яблока он съел. Сколько яблок осталось у Буратино?
> Roman
Вынести strlen за цикл – это правильно. Внести еще два, причем один вообще непонятно за каким – неправильно.
Интересно, это кагбе прозрачный вариант или кагбе сложный?
Все равно еще один strlen остался. А ведь есть $i.
Что выгоднее использовать?
да, сплоховал) честно говоря сходу написал и засабмитил. мой вариант с твоими поправками
$a = ‘abcdefgh’;
$l = strlen($a);
do {
$b .= $a[strlen($a)-(++$i)];
} while ($l != $i);
echo $a = $b;
торопишься
>Алексей Колупаев
просто вариант в общую кучу
ну на зачет или оригинальность оно и не претендовало
вообщем небольшей ресерч, код походу невлез
SIMPLE
a – hgfedcba
time – 0.0069670677185059
BUFFER
a – hgfedcba
time – 0.009005069732666
HALF_LOOP
a – hgfedcba
time – 0.026051998138428
XOR
a – hgfedcba
time – 0.011031866073608
Все примеры взяты отсюда
Первое, что пришло в голову – какой вопрос такой ответ.
$a = ‘abcdefgh’;
$a = ‘hgfedcba’;
echo $a;
Ну а если извращатся – то лучше написать на регулярных выражения.
PHP не знаю. Прочитав задачу, в голову сразу пришёл такой код на java:
String input = “abcdefgh”;
System.out.println(new String( new StringBuilder(input).reverse() ));
Конечно по скорости и доп. памяти он уступает варианту автора
$a[$i] = $a[$l-$i]^$a[$i];
$a[$l-$i] = $a[$l-$i]^$a[$i];
$a[$i] = $a[$l-$i]^$a[$i];
, но читается легче, поэтому я бы предпочёл его, если не стоит задача оборачивать строку “abcdefgh” в миллионе параллельных потоков.
А если цель — именно принтнуть текст в поток вывода, то можно даже без new String(..):
System.out.println( new StringBuilder(input).reverse() );
Конечно, перевод String в StringBuilder, а потом принтлн-ом назад в String — зло, но маленькое. Нечитаемый код — зло побольше.
Статья – фуфел по сути, но как повод к обсуждению оказалась полезной. Комментарии – отличные.
Демонстрируют, что програмирование в ВУЗах пропадает впустую для 90% “девеловперов”, и они снова и снова изобретают тот велосипед, который наверняка был одной из тем лабораторок. Впрочем, и за это они достойны огромного уважения, если сравнить с теми лентяями (по опыту, во всех слуячаях еще и безмозглыми), которые называют “быдлокодерами” тех, кто ищет решение всеми доступными способами, если существует готовая функция, но они о ней не помнят.
Дети, пожалуйста, учитесь писать программы, и изучите хотя бы простейшие алгоритмы, прежде чем требовать за свою некомпетентность реальные деньги. http://algolist.ru/
Автору и участникам – успехов!
Правильное решение:
$a= “hgfedcba”;
к какой категории?
$a = ‘abcdefgh’;
for ($i=strlen($a)-1; $i>=0; $i–)
$a .= $a{$i};
$a =substr($a,strlen($a)/2);
echo $a;
стрелял бы таких умников прям на собеседовании. Написав задачу в том последнем НАВОРОЧЕННОМ варианте читаемость понизил до максимума. Скорость написания такого кода ДАЛЕКО не самая низкая. Увидел бы такой код у кого-нить в тиме – минимум заставил бы переписать.
все-равно что сказать: докажите теорему Ферма или покажите вывод Теории относительности Эйнштейна. Результат будет один – сходу нихрена никто не напишет – но если посидеть и поставить целью – сделает ЛЮБОЙ
А че, в РНР берут только студентов-недоумков?
Тут сидишь голову ламаешь как бы человеческое лицо распознать в разных ракурсах, а народ оказывается верхом мастерства считает вывод строки задом наперед.
Тоже мне джедаи …
Спасибо, теперь я понял откуда на этом сайте появилась строка “Минимальная ЗП” с зарплатой 100 у.е.
Хотя мне до сих пор не понятно зачем даже 100 у.е. платить таким? Ведь всё равно пока объяснишь такому джедаю что ты от него хочешь, то времени потратишь больше.
А ты прикинь, как его потом просить лицо распознать в разных ракурсах, да еще и чтобы не тормозило, если он даже строчку перевернуть не может?
public static void Main(){
Stopwatch sw = new Stopwatch();
string result;
string s = "Hello world!";
int width = s.Length;
sw.Start();
unsafe
{
char* ca = stackalloc char[width];
for (int i = 0; i < width; i++)
ca[width - 1 - i] = s[i];
result = new string(ca, 0, width);
}
sw.Stop();
Console.WriteLine(result);
Console.WriteLine(sw.ElapsedTicks);
Console.ReadLine();
}
Бідний Джоел! Він, всього-навсього, хотів послухати, як людина мислить при вирішенні задачі, а не отримати правильну відповідь
В голову приходили и вариации оперировать непосредственно с массивом, и половинный цикл, но отобразил бы на бумаге этот вариант. К какой категории?
+1 за вариант $a = ‘hgfedcba’;
С точки зрения производительности и потребления памяти равных ему нет.
С точки зрения решения в рамках “процесса” равных ему тоже нет так как – собеседование это частная задача которая выполняется однократно и поэтому не требует документирования, длительного сопровождения и, соответственно, решения в общем виде. Здача не стояла в виде “напишите функцию которая…”.
А я решил так, только на сишарпе:
char[] slovo = “abcdefg”.ToCharArray();
char[] tmp = new char[slovo.Length];
for (int i = slovo.Length – 1, j =0 ; i >= 0; i–, j++)
{
tmp[j] = slovo[i];
}
Предлагаю еще решение на С++, используя мощ указателей
char str[] = “abcdfg”;
int size = strlen(str);
char *start, *end;
start = str;
end = &str[size-1];
char tmp;
cout<<”Before: ” << str <<”\n”;
while(start<end)
{
tmp = *start;
*start = *end;
*end = tmp;
start++;
end–;
}
Coder: вот именно что “мощ”
ну-ка, кто больше горбов в коде найдет?
а код то рабочий))
Ох, вот уж выросло поколение идиотиков… Вместо ожидания встроенной в язык функции на собеседовании хотят увидеть чертов бред, рекурсия у них – “джедайская техника”… “Действительно хороши в РНР”… Кроме того, “душой болеют за аджаэл”…. Как это все уныло…
Автор – гм, не скажу кто.
Прежде чем изучать Кнута, почитали бы RTFM.
Оптимизация – вопрос последней стадии проекта, а не первой.
Для этого есть profiler (если он вообще понадобится).
Правильнее (но нереально) не брать того, кто strlen за скобки выносит.
У него мозги в неправильной последовательности работают.
А по поводу пыхпыха и джедаев – кто сказал, что нельзя добавить
в php библиотеку на C/C++? Там strlen какую хошь можно слабать.
Нафига фигней страдать?
>>strlen() вынесен из тела цикла и выполняется один раз (есть ли понимание того, что это зло?)
вот тут не пойняв