тест-головоломка из toptal

[grigori]

Я тут зашел на toptal, попробовал их тесты, и слегка офигел

Задача:
Входной параметр - число, которое представлено в двоичном виде в системе счисления с базой -2. Отрицательная база. 1001 - это десятичное -9.
Алгоритм преобразования в десятичную систему прост:

$x = [1,0,1,1];
$decimal = 0;
foreach ($x as $k=>$v) {
    $decimal += $v * (-2)**$k;
}
echo $decimal;

Надо вычислить представление числа в результате отрицания. То есть если дано -9, надо вычислить двоичное представление для 9 по базе -2.

base_convert() не подходит потому что ждет базу от 2 до 35.
Алгоритм приведения числа к бинарному виду через остаток от деления не подходит, потому что нужно подобрать сумму из отрицательных и положительных чисел.
Жесткий такой тест для PHP.

 

[grigori]

Кстати, прикол в том, что в php -2 **2 = -4 потому что -2 - это не число, это операция минус к числу 2

 

[Adelf]

Решал именно эту задачу там. Решил -2 во второй степени это 4. Т.е. 1, -2, 4, -8, 16. Именно это дает возможность представить в минусдвоичной системе все натуральные числа

 

[fixxxer]

тут надо провести аналогию с представлением signed int но в рамках двух бит)

а вообще не надо палить - так весь смысл теряется, я хоть и сччитаю это малорелевантным тестом но все же

 

[Redjik]

Это на кодилити, классный тест кстати, на алгоритмическую базу, считаю, что они вполне в своем праве такую муру давать, мне еще с черепахой у них нравится.
ЗЫ. вообще я них 10ок тестов знаю, набрал у "сослуживцев", Гриша, тебе попался один из самых сложных, но и интересных. Сложных именно в рамках лимита по времени.

 

[grigori]

Я спросил их зачем эти ребусы - говорят, с умением работать это не связано, просто мы хотим посмотреть что вы можете бежать в колесе не задумываясь о смысле. Я так понял, "вас много, мы одни".
Думаю, что нормально "палить" их тесты, просто потому что им пофиг на людей. Из Facebook, Skype, Rockets звонили люди и задавали вопросы по профессии, к примеру.

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

@Adelf, за пол-часа решил? ты крут!

 

[Redjik]

Из Facebook, Skype, Rockets звонили люди и задавали вопросы по профессии, к примеру.

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

 

[grigori]

другая задача была попроще, но с неполным описанием:

* Два входных параметра: int X, и массив A [0=>int, ...].
Надо найти ключ в массиве, который указывает на позицию, по которой можно разделить массив на 2 части.
В левой части должно быть столько же значений Х, сколько в правой значений не-Х.
т.е. для [5,5,1,2,3,5] и X=5, результат 4. Получается при разделении 2 значения "5" в левой части, и два значения не 5 в правой.

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

 

[grigori]

@Redjik, это гугл, из фейсбука и всяких rockets таки звонят и общаются голосом по профессии

 

[WMix]

$decimal += $v * (-2)**$k;

прикольно, я не знал что так можно

php -r "echo 3**2;"

 

[Redjik]

@grigori, так и тому парню звонили и позвали на второй этап собеседования, ни в одной крупной компании тебя не возьмут после одного телефонного звонка, будь ты даже сам Фабьен.

 

[grigori]

@Redjik, с чем ты споришь? Я про себя рассказываю, а не про того парня. Как ты мог заметить, я тут много лет уже пишу обо всех любопытных ситуациях в ходе собеседований с разными крупными конторами.
Я и про тесты с выводом звездочек для Rockets писал. У них это было в ходе skype-звонка в режиме расшаривания экрана, человек смотрел как я пишу код, и этого им вполне хватило. Они зажевали на визах для всей семьи, а я не то чтобы горю желанием хоть куклой хоть чучелом.
И про Facebook писал, как они меня спрашивали глубокие вещи из технологий ядра Linux, я не тянул, но это было приятное собеседование.

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

 

[Adelf]

@grigori, ващет за 10-15 минут ) кода там немного. суть алгоритма если вывести. а так, да. у тебя уровень другой, чтобы решать эти задачки(в смысле уровень выше чем обычные претенденты на топтал). как @Redjik, говорил мне, они для того чтобы отделить натягивателей шаблонов от более-менее программистов. там дают 3 задачи на полтора часа. и достаточно решить одну и хотя бы какого-нибудь результата добиться в другой.

@Redjik, а вот с черепашкой - интереснее. я помоему не тот путь выбрал, когда решал. напиши в приват как там решалось если не лень.

 

[Redjik]

@Adelf, если найду, сами задачи в архиве валяются.

@grigori, полностью поддерживаю предыдущего оратора, только уточню, ты очень крутой спец по бизнесу, бизнес-процессам, привязывания всего этого к архитектуре, и у тебя оно очень круто получается без всяких DDD, но ты не кодописатель. А топтелу нужны рабы/рабочие лошадки. Им не нужны особо Лиды и CTO.

 

[grigori]

@Adelf, там 130 баллов из 300 надо, то есть одной задачи будет мало.

Я просто не тяну такое, у меня нет базового математического образования.
И таки да, не кодописатиль я от забора до обеда, за 15 лет пару сотен проектов накодил, уже думаю прежде чем писать, а это несколько противоречит тесту на время

 

[Adelf]

@grigori, ну мы с реджиком бывшие олимпиадники. нам было проще

130 из 300. 100 за одну задачу и 30 баллов за какой-нибудь результат в другой.

 

[Redjik]

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

 

[grigori]

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

@Redjik, да я Кнута читал, но прикол в том, что в реальных проектах ошибка архитектуры стоит месяца работы команды, а ошибка алгоритма - одного дня одного программиста.

 

[Adelf]

@grigori, проектов где надо архитектурить там - единицы.

 

[Redjik]

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

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