Расслабить глаза и размылить картинку - эти стандартный хак для быстрого решения. Так же как "раскосить" (или "свести") а-ля 3Д картинки что быстро найти N отличий.
Для этого и есть интервьюер, чтобы следить за временем и не давать застрять в той или иной фазе.
рисовал вручную и так же вручную считал сколько полей останутся неочищенными
Да, одна из причин зачем сперва делать неэффективный но дуболомный MVP -- это даёт эталон для сравнения и снимает кучу рутины при подготовке тестов для оптимизаций :)
Берём тупую рекурсию с одной стороны, оптимальный с другой и всё тестирование сводится к QuickCheck/Hypothesis на равенство.
Удивляет вообще сам факт наличия людей, которым хватает временного бюджета и на MVP решение задачи и на хотя бы ограниченное тестирование. Поэтому прямой вопрос, а они правда были?
Из телефонных скринингов -- процентов 15. Из on-site / основных интервью -- больше половины. Это буквально вопрос привычки -- кто так или иначе по работе вынужден писать с тестами -- пишут с тестами на автопилоте.
требует должной сообразительности, ... то есть, ну почему Вам нужны именно такие люди
Так или иначе постоянно нужны люди с должной сообразительностью и не боящиеся грызть задачи, которые могут казаться неподъёмными или нерешаемыми или неадекватным бюджетом по времени -- но таки находящие достаточное решение. Если они еще при этом знают, как жить дальше и делать лучше если будет достаточный бюджет по времени -- еще лучше.
едва ли более чем в 2 раза более эффективно (в количестве Move()) в среднем
Хм. На рандомных картах с вертикальными стенками я видел до 10 раз разницу, но я искал худшие случаи, а не среднее.
Возвращаясь к вопросу тестируемости... :)
Про тестируемость тем более покрытие тестами в такой задаче на час вообще смешно читать.
Есть три подхода: TDD, тесты постфактум и "метод пристального взгляда". Я не против ни одного из них -- я против только подхода "вот, всё хорошо".
Если человек с деформацией TDD и начинает с написания тестов -- хорошо, конечно, но в конкретной задаче я через 3-4 теста попрошу уже переключиться на задачу. (Однажды видел как человек почти 20 минут потратил на обсуждение условий и тестов, а вот код был не способен написать потом вообще, я не знаю, почему. Может, устал от тестов). Как правило, код получается хорошо структурирован сразу, и чаще всего решение идёт снизу вверх. Не знаю почему, возможно, выборка искаженная.
Структурирование кода для того, чтобы потом его можно было протестировать -- неважно как, через DI, через манкипатчи, или через наследование -- показывает, что человек уже обжигался, и стелит соломку где надо. Как правило, это хороший знак. И, по наблюдениям, как правило код пишется сверху вниз -- сперва алгоритм, потом требуемые помошники.
Если человек пытается написать код-спагетти и потом правит его по 10 раз в ответ на каждый вопрос, по дороге пропуская ветки и оставляя те же ошибки в разных местах -- это очень плохой звонок, потому что в продакшене будет то же самое. Код пишется как на выброс (в принципе, ожидаемо от интервью), но он при этом редко доходит до состояния когда даже можно понять идею.
А вот про "покрытие тестами" я ничего не говорил -- на это времени не хватает, факт. Но как минимум представить пару комнат и "пройтись" по ним алгоритмом -- мастхэф.
Соответственно, если о тестировании вообще мысли есть -- адаптация кода для тестов упакована в код и почти не требует времени отдельно. Если же нет, и тестирование исключительно повинность на "как вы меня уже задостали", то добавление тестов выливается в боль и требует иногда времени больше, чем написание кода -- и это еще без составления самих тестов. Хорошо это или плохо -- решает для себя менеджер нанимающей команды, я передаю сигнал, а что им нужно -- они оценивают сами. Я далёк от бытия образцом тут :D
задача разбита на кусаемые части -- трекинг направления убран с глаз, логика ужата
в решении есть маленький баг, который исправляется добавлением одной строчки в каждый бранч
человек думает в правильном направлении и почти решил проблему.
Упретесь в угол, соседи все были посещены, идти дальше некуда.
О том, что в этом коде есть ошибка и её надо исправить -- я же написал :) Минимальный исправленный код выглядит так: https://pythononline.net/#cxhTAk (строки 118-136). Вся обёртка -- 85-116, причем TurnTo может иметь тело-однострочник, если без оптимизации поворота.
Нет, это всё ещё не готово в продакшен, но уже точно решает проблему -- и пишется за 5-10 минут, причем неважно восходящим (сначала обёртка потом код) или нисходящим (сперва алгоритм потом требуемые функции в обёртке) подходом.
а левой клетке проставляем blocked=true.
только если препятствия занимают всю клетку, а не представляют собой вертикальную стену между клетками. как я писал в статье -- тупой рекурсивный обход иммуннен к этому варианту, а вот построение карты препятствий требует хранения и обработки известных и неизвестных связей между клетками, например, через храние на карте не только факта очистки, но и битовых масок стен клетки. а, да, не забываем, что при обнаружении стены, обновлять надо стенку у двух клеток -- текущей и целевой.
С остальным направлением мысли согласен -- это и есть правильный вектор мышления. И вы правы, рабочая реализация не вписывается в 40 минут, даже если человек эту задачу недавно решал -- много деталей которые надо не забыть и не запутаться. Но! Если правильно декомпозировать задачу, то основной алгоритм пишется, требуемый код-помошник пишется заглушками NotImplemented + прототипы + комментарий-описание что должно делать.
Всё вместе укладывается в 15-20 минут и еще остаётся 20 минут обсудить их ожидаемую сложность и подумать как это можно адаптировать для работы с двигающимися препятствиями (бегающими по комнате людьми, животными, стульями). Вот тут уже A* и вылезает (точнее, AD* и ище с ними).
Я не сдержал изначальную "обещания": никакой гарантии о посещении клеток не более чем по два раза здесь нет.
А это невозможное обещание. Тривиальный пример:
xxxxx
xx xx
x ^ x
xx xx
xxxxx
робот в центре смотрит вверх: через центральную точку он пройдёт минимум 3 раза.
Потому что, как минимум, не прозвучало ни одного вопроса "а какими датчиками" оснащен робот (какие входные данные доступны для алгоритма)
Строго говоря, в задаче четко описано: либо шагает либо не шагает вперёд на 1 шаг, и гарантированно поворачивается влево либо вправо на месте на строго 90 градусов. Это -- входные данные для алгоритма.
смена направления движения на произвольный угол после срабатывания датчика удара/касания
Ещё раз уточню: вопрос звучит НЕ как "просуммируйте листья дерева за константное время". К дереву и сумме надо придти, и по дороге можно взять и несколько альтернативных решений.
Навык решить задачу не идеально, а в заданном ограничении по времени для минимального решения - очень важный навык.
С чего Вы взяли, что кандидаты начнут с stateless решений, зачем?
Я наблюдал это в подавлящем большинстве случаев, когда я задавал этот вопрос. Я могу вспомнить только 3 или 4 случая, когда человек сразу начинал с рекурсивного решения, и, вроде, только один кто сразу начал строить карту и строить очередь на посещение.
Нормальное решение минут пять-десять только голосом объяснять
А что вы понимаете под нормальным решением? 🤔 Я в таких случаях прошу написать основной алгоритм, а детали заполним уж как успеем.
Причём опыт gamedev или подобных контестов имеет определяющее значение
Если человек с таким опытом, я скорее задам другой вопрос. Мне важно видеть то, как человек решает задачу которую он НЕ знает, то есть, вынужден думать и искать решение, чем проверять его память.
Как было у Стругацких: любой может решить решаемую задачу, нам надо решить не решаемую :)
Не всем же.
Расслабить глаза и размылить картинку - эти стандартный хак для быстрого решения.
Так же как "раскосить" (или "свести") а-ля 3Д картинки что быстро найти N отличий.
Hidden text
5я строка 2й столбец...
🤘🔥 (чет я пропустил, а когда убрали эмоджи под постами?...)
Вообще пропозал с 19го года, я подозреваю, тогда нагугливалась viva64? А то может и еще более старый, лень дальше в архив лезть...
Это не совсем легковесный контейнер.
Да, когда вариант только window приложение, хорошая тема. А возможность достучаться до GUI в контейнре уже есть?
А это всё только для того чтобы
wsl --installне делать, да? :)Это интересный способ проведения интервью через кодбаттл, для компаний, кому нужен такой профиль людей :)
Для этого и есть интервьюер, чтобы следить за временем и не давать застрять в той или иной фазе.
Да, одна из причин зачем сперва делать неэффективный но дуболомный MVP -- это даёт эталон для сравнения и снимает кучу рутины при подготовке тестов для оптимизаций :)
Берём тупую рекурсию с одной стороны, оптимальный с другой и всё тестирование сводится к QuickCheck/Hypothesis на равенство.
Из телефонных скринингов -- процентов 15.
Из on-site / основных интервью -- больше половины.
Это буквально вопрос привычки -- кто так или иначе по работе вынужден писать с тестами -- пишут с тестами на автопилоте.
Так или иначе постоянно нужны люди с должной сообразительностью и не боящиеся грызть задачи, которые могут казаться неподъёмными или нерешаемыми или неадекватным бюджетом по времени -- но таки находящие достаточное решение. Если они еще при этом знают, как жить дальше и делать лучше если будет достаточный бюджет по времени -- еще лучше.
Хм. На рандомных картах с вертикальными стенками я видел до 10 раз разницу, но я искал худшие случаи, а не среднее.
Возвращаясь к вопросу тестируемости... :)
Есть три подхода: TDD, тесты постфактум и "метод пристального взгляда". Я не против ни одного из них -- я против только подхода "вот, всё хорошо".
Если человек с деформацией TDD и начинает с написания тестов -- хорошо, конечно, но в конкретной задаче я через 3-4 теста попрошу уже переключиться на задачу. (Однажды видел как человек почти 20 минут потратил на обсуждение условий и тестов, а вот код был не способен написать потом вообще, я не знаю, почему. Может, устал от тестов). Как правило, код получается хорошо структурирован сразу, и чаще всего решение идёт снизу вверх. Не знаю почему, возможно, выборка искаженная.
Структурирование кода для того, чтобы потом его можно было протестировать -- неважно как, через DI, через манкипатчи, или через наследование -- показывает, что человек уже обжигался, и стелит соломку где надо. Как правило, это хороший знак. И, по наблюдениям, как правило код пишется сверху вниз -- сперва алгоритм, потом требуемые помошники.
Если человек пытается написать код-спагетти и потом правит его по 10 раз в ответ на каждый вопрос, по дороге пропуская ветки и оставляя те же ошибки в разных местах -- это очень плохой звонок, потому что в продакшене будет то же самое. Код пишется как на выброс (в принципе, ожидаемо от интервью), но он при этом редко доходит до состояния когда даже можно понять идею.
А вот про "покрытие тестами" я ничего не говорил -- на это времени не хватает, факт. Но как минимум представить пару комнат и "пройтись" по ним алгоритмом -- мастхэф.
Соответственно, если о тестировании вообще мысли есть -- адаптация кода для тестов упакована в код и почти не требует времени отдельно. Если же нет, и тестирование исключительно повинность на "как вы меня уже задостали", то добавление тестов выливается в боль и требует иногда времени больше, чем написание кода -- и это еще без составления самих тестов. Хорошо это или плохо -- решает для себя менеджер нанимающей команды, я передаю сигнал, а что им нужно -- они оценивают сами. Я далёк от бытия образцом тут :D
Правильному направлению мыслей:
задача разбита на кусаемые части -- трекинг направления убран с глаз, логика ужата
в решении есть маленький баг, который исправляется добавлением одной строчки в каждый бранч
человек думает в правильном направлении и почти решил проблему.
О том, что в этом коде есть ошибка и её надо исправить -- я же написал :)
Минимальный исправленный код выглядит так: https://pythononline.net/#cxhTAk (строки 118-136).
Вся обёртка -- 85-116, причем TurnTo может иметь тело-однострочник, если без оптимизации поворота.
Нет, это всё ещё не готово в продакшен, но уже точно решает проблему -- и пишется за 5-10 минут, причем неважно восходящим (сначала обёртка потом код) или нисходящим (сперва алгоритм потом требуемые функции в обёртке) подходом.
только если препятствия занимают всю клетку, а не представляют собой вертикальную стену между клетками. как я писал в статье -- тупой рекурсивный обход иммуннен к этому варианту, а вот построение карты препятствий требует хранения и обработки известных и неизвестных связей между клетками, например, через храние на карте не только факта очистки, но и битовых масок стен клетки. а, да, не забываем, что при обнаружении стены, обновлять надо стенку у двух клеток -- текущей и целевой.
С остальным направлением мысли согласен -- это и есть правильный вектор мышления. И вы правы, рабочая реализация не вписывается в 40 минут, даже если человек эту задачу недавно решал -- много деталей которые надо не забыть и не запутаться. Но! Если правильно декомпозировать задачу, то основной алгоритм пишется, требуемый код-помошник пишется заглушками NotImplemented + прототипы + комментарий-описание что должно делать.
Всё вместе укладывается в 15-20 минут и еще остаётся 20 минут обсудить их ожидаемую сложность и подумать как это можно адаптировать для работы с двигающимися препятствиями (бегающими по комнате людьми, животными, стульями). Вот тут уже A* и вылезает (точнее, AD* и ище с ними).
А это невозможное обещание. Тривиальный пример:
робот в центре смотрит вверх: через центральную точку он пройдёт минимум 3 раза.
тогда понятно, откуда такое искажение :)) завидую настойчивости.
Строго говоря, в задаче четко описано: либо шагает либо не шагает вперёд на 1 шаг, и гарантированно поворачивается влево либо вправо на месте на строго 90 градусов.
Это -- входные данные для алгоритма.
https://habr.com/ru/articles/948784/comments/#comment_28863822
Ещё раз уточню: вопрос звучит НЕ как "просуммируйте листья дерева за константное время".
К дереву и сумме надо придти, и по дороге можно взять и несколько альтернативных решений.
А, да, есть ещё 2 решения... 😂
Ограничить дерево - это один из способов, да.
Второй вариант: амортизация, если подсчёт перенести в построение или изменение дерева, то получение суммы будет вообще константа.
Третий вариант: в дереве нужны ссылки на родителя и соседа, тогда можно сделать обход без дополнительной памяти через конечный автомат.
Ещё можно использовать модификацию дерева, тогда не требуется дополнительная память.
Навык решить задачу не идеально, а в заданном ограничении по времени для минимального решения - очень важный навык.
Я наблюдал это в подавлящем большинстве случаев, когда я задавал этот вопрос. Я могу вспомнить только 3 или 4 случая, когда человек сразу начинал с рекурсивного решения, и, вроде, только один кто сразу начал строить карту и строить очередь на посещение.
А что вы понимаете под нормальным решением? 🤔
Я в таких случаях прошу написать основной алгоритм, а детали заполним уж как успеем.
Если человек с таким опытом, я скорее задам другой вопрос. Мне важно видеть то, как человек решает задачу которую он НЕ знает, то есть, вынужден думать и искать решение, чем проверять его память.
Как было у Стругацких: любой может решить решаемую задачу, нам надо решить не решаемую :)
Есть как минимум 3 решения.
Согласен. На бесконечности.
Вот только батарея не может быть бесконечной, даже если она на миллион шагов, и то не всегда достаточно: https://pythononline.net/#80Qwbf
У нас еще осталось 40 минут до лонча, давайте попробуем сделать какой-либо детерминированный алгоритм, чтобы пользователи меньше жаловались? :)