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

[grigori]

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

 

[Adelf]

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

Им нужен какой-нибудь фильтр чтобы оправдать свои маркетинговые 3%

 

[grigori]

да понятно
я их немного троллю теперь

 

[mz]

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

зачем что-то подбирать?

-4 / -2 =  2 rem  0 => 0
 2 / -2 = -1 rem  0 => 0
-1 / -2 =  0 rem -1 => 1
 1 / -2 = -0 rem  1 => 1
=> -4 = 1100


 4 / -2 = -2 rem  0 => 0
-2 / -2 =  1 rem  0 => 0
 1 / -2 = -0 rem 1 => 1
=> 4 = 0100

 

[fixxxer]

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

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

с черепашкой я часа два решал) решение очень простое на самом деле

 

[Adelf]

@fixxxer, у меня ушло минут 50. Но баллов я там набрал видимо очень мало. Сейчас нарою точные условия - попробую решить

 

[fixxxer]

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

 

[fixxxer]

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

В топтале следующий после кодилити этап такой же. Кодилити там для автоматического отсева, у них просто не хватит ресурсов проводить скайп-интервью с каждым, кто эпплаится, перед этим прочитав книжку "джаваскрипт за 24 часа".
Я от необходимости решать кодилити-задачки был не в восторге, но я понимаю, почему они это делают. Ну и само по себе, если забыть о том, что это критерий отбора, оно мне даже понравилось

 

[Redjik]

только потом удалите =)

 

[Redjik]

я кстати набрал много, мне так и сказали, хотя хз сколько
но решил только 2 задачи, 3юю вообще не успел, тупо с гитхаба не гляда скопипастил =)))))
причем на собеседовании честно признался... и вроде даже в комментах к коду это написал

 

[fixxxer]

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

 

[grigori]

@Redjik, раслабься
думаю, не потроллить ли их на reddit, что они выбирают не лучших, а ушлых
ну, потеряют несколько клиентов

 

[Redjik]

пфф, зачем?
они же тебя не тролят =) результаты теста не публикуют, ошибки не разбирают =))

 

[grigori]

@Redjik, это на днях у русских в Берлине спрашивают - хрена вы тут митингуете с плакатами за немецкие ценности? отвечают - а кто кроме нас?!
там все голову поднять, слово сказать не смеют

 

[fixxxer]

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

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

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

Нашел скриншот. Есть там про индекс size в условии.

 

[fixxxer]

А вот свежачок, мне понравилось.

 

[Adelf]

@fixxxer, ага... в голове нарисовался вариант с простым проходом по массиву держа в памяти стек текущих групп, и по необходимости схлопывая его. вроде должно работать но проверить бы где-нить на кейсах

 

[fixxxer]

Ну, тут вопрос в том как определить группу.
У меня получилось с построением массива, производного от входного, его сортировкой, и потом проходом по нему. Под условия complexity подходит, но не уверен, что это лучшее решение.
Кроме как про сортировку даже и не думал, если в условии O(N logN) - очевидно, в решени сортировка

 

[Adelf]

@fixxxer, а ты где пробовал? На кодилити? Есть линк?

 

[fixxxer]

Не, просто решить пробовал. Я, конечно, не могу быть абсолютно уверен, что решил правильно.