Здравствуйте, maxkar, Вы писали:
M>What? Решать дискретную задачу о рюкзаке минимаксом или оптимизационным solver'ом? Удачи
Тут не совсем рюкзак, хотя что-то близкое. Ну и, приличные солверы умеют рюкзаки паковать.
M>Если не понятно, откуда там рюкзак: Даем на вход все станции wind. Они fixed cost, fixed energy (после умножения на 10 — вся энергия в выводе — целые числа). Нужно их напаковать на суммарную энергию за минимум денег.
Ветряки упаковывать не проблема, конечно. Вопрос, как остальные типы станций упаковывать, ибо они совсем не fixed cost/fixed energy.
В>>https://github.com/gem-spaas/powerplant-coding-challenge
В>>Мне сказали, что "обычно" выполняют за 40 минут. В>>Ну, и риторический вопрос — стали бы вы это делать?
_>Ну, сколько денег то корячится там?
За задание? Бесплатно.
Здравствуйте, Lexey, Вы писали:
L>Там явно написано в условии, что готовые солверы не использовать. Если ты под солвером понимаешь какой-нибудь градиентный спуск из общедоступных библиотек, то такое, по идее, можно использовать. Вот только, как ты будешь целочисленность отдельных переменных обеспечивать?
Я не верю в "за 40 минут придумать новый solver" и задача жизненная, значит всё уже придумали учёные до нас. Значит нужно найти алгоритм и закодить, а не просто вызвать этот алгоритм из готового пакета.
L>$>За 24 часа можно уложиться- это часа 2-3 на почитать википедию, реализовать алгоритм и отладить еще 2-3 часа.
L>24 часа — это и есть 3-4 дня, внезапно. Ибо рвать жопу круглыми сутками никто в здравом уме не будет.
Нет, 24 часа- это жёсткий лимит. Решается задачка уровня hard за 6 часов для чела, который не "вот прямо в этой предметной области сейчас".
L>необходимости в поиске новой работы у меня сейчас нет (в последние несколько лет она меня находит).
Рынок работника, отсюда и уровень программистов в среднем как в Индии — там точно так же находит.
Здравствуйте, $$, Вы писали:
L>>необходимости в поиске новой работы у меня сейчас нет (в последние несколько лет она меня находит).
$>Рынок работника, отсюда и уровень программистов в среднем как в Индии — там точно так же находит.
Задания как раз практикуют в странах где избыток разработчиков из Индии, так как они любят немного преувеличить в своих резюме
Здравствуйте, kaa.python, Вы писали:
KP>Задания как раз практикуют в странах где избыток разработчиков из Индии, так как они любят немного преувеличить в своих резюме
Как будто русские разработчики ничего не преувеличивают. Апликанты на позицию синьёра, с 3 годами опыта, начавшегося ещё во время института (тут это нонсенс)- из России.
$>Как будто русские разработчики ничего не преувеличивают. Апликанты на позицию синьёра, с 3 годами опыта, начавшегося ещё во время института (тут это нонсенс)- из России.
Там это нонсенс исключительно из-за тараканов в голове у австралов. У меня коллега в ЛК где-то за 3,5 года от стажёра до тимлида дошёл, на 100% заслуженно.
Я так понял что там симплекс-метод + рест-апи.
В>Ну, и риторический вопрос — стали бы вы это делать?
С ходу — наверно нет.
Но я на трудоустройство в их компанию и не рассчитываю.
Вероятно кто-то кто в предметную область погружен и имеер скилы, доки, наработки...
$>Автор задачки прямо написал, что они сами используют
А мне кажется, что они очень прозрачно попросили не забивать шурупы микроскопом. И что не надо усложнять решение и искать в заведомо неверных направлениях.
Мне вот казалось, что я очень прозрачно намекнул на простой факт. Видимо — нет. Задача о рюкзаке — частный случай задачи о ветряках. Задача о рюкзаке — NP-полная. Типичный линейный solver (тот же симплекс-метод) — полиномиальный. Вывод — взять "линейный солвер" и прикрутить его напрямую к (NP-полной) задаче — пусть безнадежный. Нужно будет усложнять. Но многие разработчики не видят классов сложности, поэтому авторы пытались облегчить задачу и закрыть заведомо бесперспективные направления.
$>Уровень "что нельзя использовать" тут непонятен- например, numpy можно использовать?
Можно. Она ну никак не поможет побороть сложность (complexity class) исходной задачи. Более того, чтобы выбрать правильную библиотеку нужно хорошо понимать ее ограничения и особенности (например, псевдополиномиальные решения или осбоенности экспоненциального перебора). Обычно люди, имеющие такое знание, неплохо знают и основы (базовые блоки). Написать реализацию частного случая (простого!) для них будет легко.
Здравствуйте, Lexey, Вы писали:
L>Ветряки упаковывать не проблема, конечно. Вопрос, как остальные типы станций упаковывать, ибо они совсем не fixed cost/fixed energy.
Собственно, отсутствие граничных условий (количество станций и т.п.) — одна из проблем задачи. Всегда можно сказать, что "решение не верное, потому что мы предлагали другой контекст". Например, что ветряных станций не больше 10 (тогда перебор по подмножествам + жадный алгоритм будет самым оптимальным решением). Или наоборот, что ветряков будет очень много.
Реальность может давать еще больше разнообразия. Например, может оказаться, что производительность ветряков заметно меньше производительности других станций. Это может открыть дорогу к быстрым приближенным решениям. Т.е. считать секунду вместо 10 минут но давать ответ на 1-3% дороже в худшем случае.
$>Я не верю в "за 40 минут придумать новый solver" и задача жизненная, значит всё уже придумали учёные до нас. Значит нужно найти алгоритм и закодить, а не просто вызвать этот алгоритм из готового пакета.
Почему нельзя? Я же придумал Обычно из готовых алгоритмов можно легко собрать, особенно зная, что есть решение.
Я бы не был очень оптимистичен по поводу поиска с учетом их "do not use". Вполне может оказаться, что "массовые" решалки плохо ведут себя на их задаче. А чтобы найти хороший solver, нужно быть в теме (читать статьи, иметь специализированное образование и т.п.). Кто вообще сказал, что рядовой программист должен быть способен решить эту задачу? Может, они раньше нанимали и поняли, что ничего хорошего не получается. И теперь ищут людей, для которых придумать новый специализированный solver за 40 минут — совсем не проблема.
Здравствуйте, 3V,
3V>Я так понял что там симплекс-метод + рест-апи.
Симплекс метод за 40 минут? 99% программистов его не напишут вообще.
Я может невнимательно читал, но на вид это «непрерывная задача о рюкзаке», которая решается простым жадным алгоритмом.
3V>Вероятно кто-то кто в предметную область погружен и имеер скилы, доки, наработки...
Вы переоцениваете необходимость погружения в предметную область для разработки программ.
Какой жесткий лимит? Сумасошол? Это тестовое задание, а не олимпиада. Тут никаких жестких лимитов быть не может, если работодателю нужны инженеры, а не студенты-олимпиадники.
$>Решается задачка уровня hard за 6 часов для чела, который не "вот прямо в этой предметной области сейчас".
Уровня hard чего? Хакерранка? Сколько задач такого уровня ты там решил?
$>Рынок работника, отсюда и уровень программистов в среднем как в Индии — там точно так же находит.
Не вижу никакой связи между "средней по больнице" и "своей температурой".
Здравствуйте, Lazytech, Вы писали:
L>Согласен. Вообще, насколько я понял, дело не в багах. Просто человек отлично разбирается в картах и в целом умеет ориентироваться на местности.
В первую очередь, именно баги. В частности, чтобы проходить сквозь стены.
Здравствуйте, Codealot, Вы писали:
C>В первую очередь, именно баги. В частности, чтобы проходить сквозь стены.
Он вроде не проходил сквозь стены. Человек просто наловчился делать ступеньки выстрелами из клеевой пушки и взбираться по этим ступенькам на расположенный выше этаж.
Здравствуйте, Lazytech, Вы писали:
L>Он вроде не проходил сквозь стены. Человек просто наловчился делать ступеньки выстрелами из клеевой пушки и взбираться по этим ступенькам на расположенный выше этаж.
Как минимум один раз на 00:06, дальше я внимательно не смотрел.
Ну и пусть продолжают искать тех, кто выполнит за 40 минут.
Это похоже на развод, когда искал первую работу, тоже было:
— "Ты типа молодец, тестовое задание выполнил, но "обычно" его делают за 1 час, а ты выполнил за 2,3,4,...N часов".
— "Так... Ты хочешь ЗП — N... Но понимаешь, ты же сделал задание за большее время, поэтому ты недостоен ЗП — N, мы можем предложить только M, где M < N".
Если не секрет, то какую ЗП предлагают? По названию компании искать — влом.
Обычно из готовых алгоритмов можно легко собрать, особенно зная, что есть решение.
