Для этого и есть интервьюер, чтобы следить за временем и не давать застрять в той или иной фазе.
рисовал вручную и так же вручную считал сколько полей останутся неочищенными
Да, одна из причин зачем сперва делать неэффективный но дуболомный 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 или подобных контестов имеет определяющее значение
Если человек с таким опытом, я скорее задам другой вопрос. Мне важно видеть то, как человек решает задачу которую он НЕ знает, то есть, вынужден думать и искать решение, чем проверять его память.
Как было у Стругацких: любой может решить решаемую задачу, нам надо решить не решаемую :)
Именно к этому я и веду: нет, нельзя спрашивать "напишите обход дерева". Какого? Зачем? Чтобы что? Нельзя спрашивать "напишите A* поиск пути". Есть практическая ситуация: вот робот, надо почистить весь дом. Уже пришёл к тому, что надо строить карту, на карте надо помечать где был, через какую сторону не смог пройти между ячейками. Пришёл к тому, что надо найти ближайшую не чищенную клетку, и надо найти дорогу туда. Все, пишем заголовок функции, и продолжаем основную логику. Есть время? Можно подумать и написать её тоже. Не хватило? Неважно, взяли библиотечную.
Если человек умеет думать и декомпозировать задачу - задача решается на ту степень детальности, на которую было времени.
Вопросы уровня "назовите пять протоколов когерентности кеша процессора" оставьте шарашкам, именующим себя универами... Это там проверяют кеш студента, "что из лекций он ещё не забыл со вчера"
Например, аббревиатура LRU. С ходу я не помню что это
Посмотрите еще раз как задаётся задача. Суть вопроса -- "напишите проход по матрице". Так же и дальше, не надо спрашивать "напишите обход дерева" или "Напишите LRU кеш". Это тупо. Есть псевдо-задача, решение для неё органично через обход дерева или через кеш. Я ожидаю что сеньёр знает кеши и деревья и может продемонстрировать это знание, ничего больше.
"начинаем кодить на доске"
отсылка на интервью когда почему-то нельзя пользоваться ничем кроме доски. я как не понимал этого подхода -- так и не понимаю... :D хорошо, что сейчас чаще это удалённо, поэтому как минимум редактор с подсветкой...
Это вопрос "напишите обход матрицы". Вариант "прогнать черепашку чтобы карту построила" -- идеален для мвп, потому что пока строится карта -- всё еще и почищено.
Это интересный способ проведения интервью через кодбаттл, для компаний, кому нужен такой профиль людей :)
Для этого и есть интервьюер, чтобы следить за временем и не давать застрять в той или иной фазе.
Да, одна из причин зачем сперва делать неэффективный но дуболомный 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 минут до лонча, давайте попробуем сделать какой-либо детерминированный алгоритм, чтобы пользователи меньше жаловались? :)
Именно к этому я и веду: нет, нельзя спрашивать "напишите обход дерева". Какого? Зачем? Чтобы что?
Нельзя спрашивать "напишите A* поиск пути".
Есть практическая ситуация: вот робот, надо почистить весь дом.
Уже пришёл к тому, что надо строить карту, на карте надо помечать где был, через какую сторону не смог пройти между ячейками.
Пришёл к тому, что надо найти ближайшую не чищенную клетку, и надо найти дорогу туда.
Все, пишем заголовок функции, и продолжаем основную логику.
Есть время? Можно подумать и написать её тоже.
Не хватило? Неважно, взяли библиотечную.
Если человек умеет думать и декомпозировать задачу - задача решается на ту степень детальности, на которую было времени.
Вопросы уровня "назовите пять протоколов когерентности кеша процессора" оставьте шарашкам, именующим себя универами... Это там проверяют кеш студента, "что из лекций он ещё не забыл со вчера"
"Чисто" для MVP - робот хотя бы один раз бывал на клетке.
Да, интересный подход, и однажды его приводили.
А есть доказательство, что рандомный поворот и движение приведёт к обходу всей доступной площади? 😁
Посмотрите еще раз как задаётся задача. Суть вопроса -- "напишите проход по матрице".
Так же и дальше, не надо спрашивать "напишите обход дерева" или "Напишите LRU кеш". Это тупо. Есть псевдо-задача, решение для неё органично через обход дерева или через кеш. Я ожидаю что сеньёр знает кеши и деревья и может продемонстрировать это знание, ничего больше.
отсылка на интервью когда почему-то нельзя пользоваться ничем кроме доски. я как не понимал этого подхода -- так и не понимаю... :D хорошо, что сейчас чаще это удалённо, поэтому как минимум редактор с подсветкой...
Неважно -- вопрос всегда заканчивается тогда, когда заканчивается время. Обычно 45 минут на кодинговую часть.
Это вопрос "напишите обход матрицы". Вариант "прогнать черепашку чтобы карту построила" -- идеален для мвп, потому что пока строится карта -- всё еще и почищено.
"Что еще спросить" -- это другие вопросы. Конкретно этот вопрос -- "напишите обход матрицы".
Показывает, умеет ли думать кандидат. Всё остальное можно нагуглить.
Согласен, мы внесём это в бэклог для следующей версии прошивки.