Comments 51
Изюююмительный текст - 87% сгенерирован. И без анализа видно "кучу маркеров", что сгенерирован
Неправильный у вас робот, правильный должен уметь на любой угол поворачивать. Это с завода 90, а по факту будет вправо 87, влево 92. А через пол года вправо 80, влево 85.
И что даёт такое собеседование, кроме чувства глубокого собственного превосходства для интервьюера?
Какой-то бред.
Разработка api для нех и как просуммировать листья произвольного дерева рядом в одном собеседовании на одну вакансию - вы серьезно?
задача какая-то наркомания
если это оторванное от реальности то слишком много каких-то заморочек и фокусировки на ненужных мелочах
если это реальный кейс для фирмы что роботов таких делает то у робота куча периферии и его позиционируешь от док-станции и вообще пофиг на геометрию или размеры, лишь бы хватило заряда и пол был ровным.
и даже если надо чистить "оптимально" все равно проще в первый раз прогнать черепашку что бы карту построила а потом уже по ней "оптимизировать" а не пытаться рожать сферических коней в ввакуме
а сколько времени дается на эту задачу с учетом дополнительных вопросов про LRU кэш и обхода деревьев?
Я развлекаюсь интервьюингом больше десяти лет, лет пять вёл SRE Interview Club
как просуммировать листья произвольного дерева за O(1) по памяти;
как найти узел в дереве по произвольному условию;
как сделать LRU-кеш;
Почему то, мне кажется, что автор чешет свое ЧСВ на таких вопросах...
Например, аббревиатура LRU. С ходу я не помню что это. Но вот глянул как расшифровывает и что подразумевается, и понял, что я уже делал реализацию (кэш активных переводов с вытеснением по времени последнего входящего/исходящего сообщения в "холодный кэш" для СБП переводов).
И, скорее всего, с точки зрения автора, ели "не знаешь что я спросил (LRU) без подскзаки Интрернета" - фуу лох.
Может и ошибаюсь, но вот фраза "или блокнотики, начинаем кодить на доске!" как бы намекает исходный "промпт" вида "ты в постапокалиптическом мире и у тебя нет возможность найти информацию. только помнить".
Например, аббревиатура LRU. С ходу я не помню что это
Посмотрите еще раз как задаётся задача. Суть вопроса -- "напишите проход по матрице".
Так же и дальше, не надо спрашивать "напишите обход дерева" или "Напишите LRU кеш". Это тупо. Есть псевдо-задача, решение для неё органично через обход дерева или через кеш. Я ожидаю что сеньёр знает кеши и деревья и может продемонстрировать это знание, ничего больше.
"начинаем кодить на доске"
отсылка на интервью когда почему-то нельзя пользоваться ничем кроме доски. я как не понимал этого подхода -- так и не понимаю... :D хорошо, что сейчас чаще это удалённо, поэтому как минимум редактор с подсветкой...
Я ожидаю что сеньёр знает кеши
Кстати, а что Вы подразумеваете по "кэш"? Кэш конвеера выполнения команд в CPU, прикладной кэш name+value параметров в памяти программы, кэш HTTP сервера (GET запросов), кэш планов запросов DB.. и и.д. и т.п.
Слово одно, важные нюансы - разные.
Когда мне задают "простой вопрос" я долго и нужно выясняю, а что спрашиваешь то. Потому что, как показывает опыт, в половине случаев "то что подразумевал вопрошающий != как понял вопрос отвечающий".
На встрече с заказчиками (особнено общение с менаджерами, желанющими кнопку "счастье"), приходится долго выяснять "а что он имел в виду". А для него "это же очевидно что я имел в виду". Да нихрена не очевидно в 90%.
Кстати, достают задачи в школных учебниках (иногда приходится помогать) в которых решение состоит из "угадай что имел в виду под вопросом автор учебника".
На собеседовании (да и просто в работе), если человек не задают уточняющие вопросы по поставленной задаче - это "что то не так". Либо вообще не понял что, либо понял не правильно "это очевидно" и будет делать не то.
Суть вопроса -- "напишите проход по матрице"
Я общие принципы матричного исчисления помню (проходил когда то). Но в практической работе мне приходилось это применять очень давно (программа раскладки выкроек и управление раскроечным столом). Если меня вот прям сейчас спросят "быстро быстро на время напиши функцию умножения матриц" - пошлю нахер. Общие принципы и зачем это надо я помню. Вывезти из этого формулу - на это нужно время.
Как то сдавал дип курс (PADI). На 40м нужно было решить какую ни будь задачку (тест на склонность к азотному наркозу). И тут мне инструктор подосовывает деление в столбик двух числе (5 и 3 разряда где то). Я его послал (жестом). Да я блин минут 5 на боте/на поверхности вспоминал (а точнее выводил из общего принципа) метод деления.
Так что, задавать какую то узкую задачу (которую знаешь сам, повторил недавно) и считать, что если человек с ней быстро быстро не справился, то все - это чесать свое ЧСВ.
Именно к этому я и веду: нет, нельзя спрашивать "напишите обход дерева". Какого? Зачем? Чтобы что?
Нельзя спрашивать "напишите A* поиск пути".
Есть практическая ситуация: вот робот, надо почистить весь дом.
Уже пришёл к тому, что надо строить карту, на карте надо помечать где был, через какую сторону не смог пройти между ячейками.
Пришёл к тому, что надо найти ближайшую не чищенную клетку, и надо найти дорогу туда.
Все, пишем заголовок функции, и продолжаем основную логику.
Есть время? Можно подумать и написать её тоже.
Не хватило? Неважно, взяли библиотечную.
Если человек умеет думать и декомпозировать задачу - задача решается на ту степень детальности, на которую было времени.
Вопросы уровня "назовите пять протоколов когерентности кеша процессора" оставьте шарашкам, именующим себя универами... Это там проверяют кеш студента, "что из лекций он ещё не забыл со вчера"
Есть практическая ситуация: вот робот, надо почистить весь дом.
Уже пришёл к тому, что надо строить карту, на карте надо помечать где был, через какую сторону не смог пройти между ячейками.
В принципе, ответов должно хватить для того, чтобы стало понятно, что же надо.
Если говорить про эту контретную задачу, что при входных условия "нужно накатить на прод хотя бы как то работающее решенеи и быстро".
Все эти рассуждения про карту, "где был" и пр. это разновидность мозгового _а_нанизма.
Потому что, как минимум, не прозвучало ни одного вопроса "а какими датчиками" оснащен робот (какие входные данные доступны для алгоритма)
А без ЭТИХ входных условий дальнейшие рассуждения просто вредны. Потому что решается на фактическая задача, а что то придуманное при иллюзии что решаем проблему.
Да и решение для прода в условиях "нужно решение и быстро и тестировать некогда" должно быть минимально сложным и желательно шаблонным, что бы уменьшить риски на период до "сделали нормальное тщательно оттестированное решение".
Например, шаблонная классика из самых первых вариантов работы роботов уборщиков: смена направления движения на произвольный угол после срабатывания датчика удара/касания (как минимум такой датчик должен быть в любой подобной платформе робота). И пофиг что он промусолит несколько раз по одному и тому же месту и не будет "карты комнат". Потому задача не составить карту комнат, а "что бы работал и езди и убирал". Пусть и кажется (умозрительно, а не фактически ибо это тоже нужно оценивать на тестах) что это не оптимально.
Как показывает лично мой опыт, попытка по быстрому сделать что то сложное, что бы закрыть проблему быстро быстро и выкатить на прод кончается еще большими проблемами.
(кстати, минусы не я ставлю)
Потому что, как минимум, не прозвучало ни одного вопроса "а какими датчиками" оснащен робот (какие входные данные доступны для алгоритма)
Строго говоря, в задаче четко описано: либо шагает либо не шагает вперёд на 1 шаг, и гарантированно поворачивается влево либо вправо на месте на строго 90 градусов.
Это -- входные данные для алгоритма.
смена направления движения на произвольный угол после срабатывания датчика удара/касания
https://habr.com/ru/articles/948784/comments/#comment_28863822
Хз чего тут заминусовали. норм задача, на чуть-чуть подумать, причем не сильный-то и алгоритмодроч.
Вопросы, которые так или иначе влияют на решение,
я бы задал и такой вопрос, а что такое чисто в комнатах? Если пока нет конкретного сигнала\понятия, то и алгоритм с random поворот\движения когда-нибудь позволит пройтись по всей площади.
"Чисто" для MVP - робот хотя бы один раз бывал на клетке.
Да, интересный подход, и однажды его приводили.
А есть доказательство, что рандомный поворот и движение приведёт к обходу всей доступной площади? 😁
Есть, это следствие теоремы о возвращении, если комната конечна, связана (т.е. достижимы все её точки) и нет никаких циклов при выборе пути, то рано или поздно вы побываете везде, если точнее - она утверждает что при таких условиях вероятность посетить любую точку стремится к 1
Согласен. На бесконечности.
Вот только батарея не может быть бесконечной, даже если она на миллион шагов, и то не всегда достаточно: https://pythononline.net/#80Qwbf
У нас еще осталось 40 минут до лонча, давайте попробуем сделать какой-либо детерминированный алгоритм, чтобы пользователи меньше жаловались? :)
Мы всегда можем ехать до половины заряда, потом возвращаться по тому же пути на зарядку, чтобы нам не мешали препятствия по среди, потом запускать случайные блуждания снова, дело не в заряде, а во времени, но тут эстетически пользователь будет наслаждаться что постоянно происходит какая-то работа и возможно ничего не заподозрит... А мы к тому моменту выпустим патч
Если серьезно самое простое что мне приходит в голову вот с ходу, это как в лабиринте идти всегда прижавшись к стене и делая только правые повороты, пока не замкнется многоугольник, определить внутри или снаружи многоугольника, если внутри - применить любой алгоритм закраски многоугольника, если снаружи, то ехать от него в произвольную сторону и повторять пока не найдем внешнюю границу комнаты
Но если есть 40 минут, можно придумать что то лучше, наверное, сейчас возьму пивка, подумаю
Очень прикольная задача! Есть место для вопросов, для оптимизации, для алгоритмов, для кодинга, для общения, для проактивности... Короче, куча качеств сразу проявляется у кандидата (или их отсутствие)
Задача интересная для, например, codingames, на недельку, с живой таблицей лидеров (даём "ограниченный заряд", которого точно не хватит на заполнение всех карт и оцениваем сумму закрашенных ячеек). Для собеседования не очень интересная.
С чего Вы взяли, что кандидаты начнут с stateless решений, зачем? Чтобы потратить время?
Нормальное решение минут пять-десять только голосом объяснять, лично я бы честно сказал, что я не буду даже начинать его писать в рамках часового лимита. Причём нормальное это просто то, которое справится с всеми возможными замкнутыми комнатами, не попадая в ту же клетку более чем дважды для большинства клеток. В рамках контеста на codingames оно бы болталось где-то в самом низу золотой лиги. Но в моем понимании, "сеньорство" только с момента оптимизации решения такого уровня и требуется.
Причём опыт gamedev или подобных контестов имеет определяющее значение. С рекурсии могут начинать лишь те кандидаты, которые вообще ни с чем подобным ранее не сталкивались.
а если в геймдев, то А* должен от зубов отлетать, ни в коем случае не пользоваться библиотеками
А чем в этой задаче A* поможет, для начала? :)
Про тестируемость тем более покрытие тестами в такой задаче на час вообще смешно читать.
Моё мнение, хоть это и плохой заведомо вид тестирования, но на час с остальными вашими требованиями подойдёт например задача расстановки n ферзей на доске n x n, чтобы ни один не был под ударом. При этом, 70-90% реальных синьоров и с этим не справится из-за условий стресса.
Навык решить задачу не идеально, а в заданном ограничении по времени для минимального решения - очень важный навык.
С чего Вы взяли, что кандидаты начнут с stateless решений, зачем?
Я наблюдал это в подавлящем большинстве случаев, когда я задавал этот вопрос. Я могу вспомнить только 3 или 4 случая, когда человек сразу начинал с рекурсивного решения, и, вроде, только один кто сразу начал строить карту и строить очередь на посещение.
Нормальное решение минут пять-десять только голосом объяснять
А что вы понимаете под нормальным решением? 🤔
Я в таких случаях прошу написать основной алгоритм, а детали заполним уж как успеем.
Причём опыт gamedev или подобных контестов имеет определяющее значение
Если человек с таким опытом, я скорее задам другой вопрос. Мне важно видеть то, как человек решает задачу которую он НЕ знает, то есть, вынужден думать и искать решение, чем проверять его память.
Как было у Стругацких: любой может решить решаемую задачу, нам надо решить не решаемую :)
Как было у Стругацких: любой может решить решаемую задачу, нам надо решить не решаемую :)
Только вот привычно понимаемым целям найма это несколько противоречит.
Мне важно видеть то, как человек решает задачу которую он НЕ знает, то есть, вынужден думать и искать решение, чем проверять его память.
Скручивать опыт я ещё не пробовал, но вот и о том что в топ-100 codingamer'ов в резюме не добавляю. "только не литкод, пожалуйста, только не литкод" :)
но вот и о том что в топ-100 codingamer'ов в резюме не добавляю
тогда понятно, откуда такое искажение :)) завидую настойчивости.
Да, искажение, Вы абсолютно правы. Мне интересно решать задачки, не потому, что их вообще можно решить, а потому, что их можно решить лучше других. Говорили, что это должно пройти, но нет, время не лечит, и теперь просто это стало хобби. Иногда, конечно искажающим другие процессы, но кто в сущности то без этого :) На CG особого усердия, кстати в топ попасть много не надо, это надо не все подряд хорошо решать, а просто в паре-тройке челленжей абсолютно выиграть.
Нормальное решение минут пять-десять только голосом объяснять, <...> то, которое справится с всеми возможными замкнутыми комнатами, не попадая в ту же клетку более чем дважды для большинства клеток.
Беру свои слова назад :) На чуть более сложных картах, чем тривиальные (= прямоугольные без препятствий) я так и не пришел к такому решению (которое ограничивает количество повторных посещений клеток, не зависящим от размера карты числом), в фоне думая об этом уже вон сколько.
А чему Вы радуетесь в коде из поста
Скрытый текст
def Clean(robot: Robot, x=0, y=0):
state.add((x,y))
if (x,y-1) not in state and robot.Up():
Clean(robot, x, y-1)
if (x,y+1) not in state and robot.Down():
Clean(robot, x, y+1)
if (x-1,y) not in state and robot.Left():
Clean(robot, x-1, y)
if (x+1,y) not in state and robot.Right():
Clean(robot, x+1, y)я ума не приложу. Он же даже на тривиальных картах не работает как MVP (не обходит каждую клетку). Упретесь в угол, соседи все были посещены, идти дальше некуда. Единственное, где он работает верно, если на тривиальной карте (ну это не совсем правда, некоторые препятствия он все же обходит) запускать из одного из углов карты :)
Самый простой MVP это как-то так: строим карту препятствий. Идем в ближайшую клетку которую мы еще не сканировали (scanned(x,y)==false), оттуда пробуем Left-назад, Right-назад, Up-назад, Down-назад [сноска1] (если клетки в соответствующем направлении не были посещены И не были проверены на препятствие) и проставляем scanned(x,y)=true, затем идем (можно по кратчайшему пути) в ближайшую клетку, где мы еще не производили сканирование препятствий, и которая не является препятствием сама. Три мапы: visited, blocked и scanned. Visited имеет тот же смысл, что not blocked, это клетки в которых мы были (потому что в них можно побывать). То есть для каждой клетки (x,y) ее !scanned превращается в заполненную информацию blocked/visited ее соседей.
Сноска1: если в Left-назад не удался left, назад идти не надо, а левой клетке проставляем blocked=true. Аналогично для оставшихся трех направлений.
Так мы хотя бы гарантированно обойдем все доступые клетки, только это драматически неэффективно.
На картах с небольшим количеством препятствий можно оптимизировать: Scanned делаем не bool а битовой маской уже проверенных направлений из этой клетки. 0x1 left, 0x2 right, 0x4 up, 0x8 down. Полностью просканированная клетка, соответственно имеет значение 15 (1+2+4+8), и туда мы идем только, если через нее проходит кратчайший маршрут в следующую нужную нам точку. Во всех остальных клетках мы обязаны побывать, и проверить те направления из четырех, которые еще не проверяли (тут напрашивается оптимизация1, о ней ниже). Теперь мы можем идти, по возможности, не меняя предыдущее направление, дальше: допустим мы в клетке (x,y), идем влево, получается: тогда scanned(x,y)+=0x1 (left), visited(x-1,y)=true и из клетки (x-1,y) идем влево тем же способом. Если уперлись в препятствие, возвращаемся к ближайшей клетке, где scanned != 15 и проверяем оставшиеся направления. Оптимизация2 будет заключаться в оптимальном выборе "следующего" направления для проверки для заданной клетки.
Оптимизация1: если мы попали в точку (x,y), то для всех 4 ее соседей можно сразу проставить соответствующие направления scanned. scanned(x,y-1)+=0x8 (для точки (x,y-1) точка (x,y) является нижним соседом, в нее очевидно можно попать, если сама точка (x,y-1) не является препятствием), scanned(x-1,y)+=0x2, и еще 2 кейса.
Оптимизация2: приоритетное направление стоит выбирать как то, в котором можно пройти потенциально бОльшее число клеток. Держим для карты XMin, XMax, YMin, YMax, которые просто значения минимумов и максимумов из координат тех клеток, где мы уже были (visited, напомню, что это тоже самое что known as not blocked). Соответственно, направление это то, где X-XMin, XMax-X и еще два соответствующих варианта - даст максимальное значение.
Здесь нужно еще не запутаться в лапше кода. Потому что blocked это клетки в которые точно нельзя попасть, но при этом из-за оптимизации1 для них вполне могут быть частично проставлены флаги scanned. Ничего страшного, просто имеем в виду. А еще, по большому счету, после введения битовых масок в scanned нам не нужна больше даже мапа visited, она тривиально получается из разворачивания scanned для ее соседей.
Ах да, кратчайший путь ищем обычным BFS, из текущей клетки заполняем динамический массив расстояний до каждой другой точки карты, выбираем там минимум, и сам путь. Никакого смысла что-то усложнять для карт менее, чем из миллиона элементов особо не вижу, но и не в этом сложность. Это минут за 10 пишется, если "рука набита".
Подытожу:
В принципе, это лучшее, что я придумал, не затачивая под конкретные частные случаи возможных карт, и есть интуитивное представление, что под общие случаи ничего сильно лучше не придумать
Это ни разу не 5 минут объяснять.
Это точно не написать за час, если не писал в точности ровно тоже самое раньше
Я не сдержал изначальную "обещания": никакой гарантии о посещении клеток не более чем по два раза здесь нет. Но на около-тривиальных картах (прямоугольные, препятствия все изолированные друг от друга), так и будет конечно. Но так же я могу нарисовать карту, где некоторые клетки будут посещены вплоть до O(общее количество клеток) раз. У робота нет вообще никакой информации о карте изначально, потому так и сложно.
Насколько сложная задача - каждый сам сделает выводы, но лично я, если бы не решал несколько подобную задачу о "слепом пакмэне" отнес бы ее к very hard.
В принципе, это весело.
А чему Вы радуетесь в коде из поста
Правильному направлению мыслей:
задача разбита на кусаемые части -- трекинг направления убран с глаз, логика ужата
в решении есть маленький баг, который исправляется добавлением одной строчки в каждый бранч
человек думает в правильном направлении и почти решил проблему.
Упретесь в угол, соседи все были посещены, идти дальше некуда.
О том, что в этом коде есть ошибка и её надо исправить -- я же написал :)
Минимальный исправленный код выглядит так: 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 раза.
Да, каюсь, все же не такая уж и сложная задача. Вот уж теперь не знаю, что меня заставило проглядеть идею о том, что код из поста нужно немного исправить, чтобы он заработал. Наверное стойкое ощущение, что в том направлении он все равно был бы безобразно неэффективен (ну это некоторая деформация, да).
Но, оказалось, что это не правда. Я все же написал, как и обозначил идею, решение с битовыми масками для оптимизации обхода. На самом деле тоже не очень много времени заняло, если бы не отладка, то меньше получаса, ну оно работает, хорошо работает, только вот на том небольшом количестве карт для тестирования, которые вручную нарисовал, едва ли более чем в 2 раза более эффективно (в количестве Move()) в среднем, чем предложенный Вами код.
А значит, то решение, направление которого Вы предлагаете вполне решает поставленную задачу. И действительно вполне укладывается и в обозначенное время, и не надо было ничего переусложнять :)
В принципе я и так счел задачу интересной, теперь соглашусь, что пусть и не ультимативно, но в заданном формате собеседований это может быть хорошим выбором.
Да-да, я примеры тоже уже успел посочинять немного, на них все становится сразу более-менее понятно. Мне кажется, именно этого посту и не хватало, чтобы получить более положительную реакцию; привычка читать "по диагонали" уже скорее ближе к норме, чем исключениям, а тут и люди и кони, и странный пылесос, и какие-то движущиеся объекты, и карты со странной геометрией, а нет, все банально об "обойди такую штуку
Скрытый текст
###############
# O # #
# ### # ### #
# # # # # # #
# # # # #
# #############
# #
# ########### #
# # # #
# # ####### # #
# # # # # #
# # # ### # # #
# # # #
### ###########
# #
###############более-менее эффективно через точно заданный API".
едва ли более чем в 2 раза более эффективно (в количестве Move()) в среднем
Хм. На рандомных картах с вертикальными стенками я видел до 10 раз разницу, но я искал худшие случаи, а не среднее.
Возвращаясь к вопросу тестируемости... :)
Про тестируемость тем более покрытие тестами в такой задаче на час вообще смешно читать.
Есть три подхода: TDD, тесты постфактум и "метод пристального взгляда". Я не против ни одного из них -- я против только подхода "вот, всё хорошо".
Если человек с деформацией TDD и начинает с написания тестов -- хорошо, конечно, но в конкретной задаче я через 3-4 теста попрошу уже переключиться на задачу. (Однажды видел как человек почти 20 минут потратил на обсуждение условий и тестов, а вот код был не способен написать потом вообще, я не знаю, почему. Может, устал от тестов). Как правило, код получается хорошо структурирован сразу, и чаще всего решение идёт снизу вверх. Не знаю почему, возможно, выборка искаженная.
Структурирование кода для того, чтобы потом его можно было протестировать -- неважно как, через DI, через манкипатчи, или через наследование -- показывает, что человек уже обжигался, и стелит соломку где надо. Как правило, это хороший знак. И, по наблюдениям, как правило код пишется сверху вниз -- сперва алгоритм, потом требуемые помошники.
Если человек пытается написать код-спагетти и потом правит его по 10 раз в ответ на каждый вопрос, по дороге пропуская ветки и оставляя те же ошибки в разных местах -- это очень плохой звонок, потому что в продакшене будет то же самое. Код пишется как на выброс (в принципе, ожидаемо от интервью), но он при этом редко доходит до состояния когда даже можно понять идею.
А вот про "покрытие тестами" я ничего не говорил -- на это времени не хватает, факт. Но как минимум представить пару комнат и "пройтись" по ним алгоритмом -- мастхэф.
Соответственно, если о тестировании вообще мысли есть -- адаптация кода для тестов упакована в код и почти не требует времени отдельно. Если же нет, и тестирование исключительно повинность на "как вы меня уже задостали", то добавление тестов выливается в боль и требует иногда времени больше, чем написание кода -- и это еще без составления самих тестов. Хорошо это или плохо -- решает для себя менеджер нанимающей команды, я передаю сигнал, а что им нужно -- они оценивают сами. Я далёк от бытия образцом тут :D
до 10 раз разницу, но я искал худшие случаи, а не среднее.
Пропорция увеличивается в зависимости от размера карты, и да именно:
Возвращаясь к вопросу тестируемости... :)
Конечно я "просрал весь бюджет времени" в рамках Вашей идеи задачи для собеседования. 10 минут потратил на то что бы критиковать. 20 минут на описание того, что сделал бы. 30 минут на реализацию этого. 10 минут на придумывание первых тестов в формате input.txt output.txt, карты которые рисовал вручную и так же вручную считал сколько полей останутся неочищенными. Знаете, тоже труд. Никакого генератора у меня не было, потому что алгоритма, который по входу построит мне правильный выход у меня не было. Поэтому рисовал поля от 5х5 до 15х15. И, конечно тут же тесты сфейлились, и пришлось ещё потратить 30 минут на отладку. Правда в этот же момент я заметил, что оптимизация2 это полная ерунда на реальных картах. Следующим шагом я бы с удовольствием нагенерил бы карт побольше (и побольше размером) и стал бы думать не только над корректностью ответа, но и конкретными оптимизациями вызова move(). Не беда, выходные будут - думаю ещё займусь.
Вернувшись к тому, что Вы говорите о вопросе тестируемости, конечно в общих словах я всецело согласен. Удивляет вообще сам факт наличия людей, которым хватает временного бюджета и на MVP решение задачи и на хотя бы ограниченное тестирование. Поэтому прямой вопрос, а они правда были? Вопрос провокационный, но без подвоха.
Согласен, задача вовсе не верихард, а ближе к медиум на литкоде, и требует должной сообразительности, но напрашивается ещё один вопрос, в чем смысл нанимать людей, которые справляются именно с этим, то есть, ну почему Вам нужны именно такие люди.
По моему опыту почти все знакомые сеньоры знатные слоупоки. Такое вот вынужденое искажение происходит.
Конечно я "просрал весь бюджет времени"
Для этого и есть интервьюер, чтобы следить за временем и не давать застрять в той или иной фазе.
рисовал вручную и так же вручную считал сколько полей останутся неочищенными
Да, одна из причин зачем сперва делать неэффективный но дуболомный MVP -- это даёт эталон для сравнения и снимает кучу рутины при подготовке тестов для оптимизаций :)
Берём тупую рекурсию с одной стороны, оптимальный с другой и всё тестирование сводится к QuickCheck/Hypothesis на равенство.
Удивляет вообще сам факт наличия людей, которым хватает временного бюджета и на MVP решение задачи и на хотя бы ограниченное тестирование. Поэтому прямой вопрос, а они правда были?
Из телефонных скринингов -- процентов 15.
Из on-site / основных интервью -- больше половины.
Это буквально вопрос привычки -- кто так или иначе по работе вынужден писать с тестами -- пишут с тестами на автопилоте.
требует должной сообразительности, ... то есть, ну почему Вам нужны именно такие люди
Так или иначе постоянно нужны люди с должной сообразительностью и не боящиеся грызть задачи, которые могут казаться неподъёмными или нерешаемыми или неадекватным бюджетом по времени -- но таки находящие достаточное решение. Если они еще при этом знают, как жить дальше и делать лучше если будет достаточный бюджет по времени -- еще лучше.
И ещё такая мысль. Если в задачу входит управление роем робопылесосов на одной и той же карте с соперником в равных условиях с сохранением всех остальных условий, то это настоящая котлета :)
Хотя и дальше странное...
как просуммировать листья произвольного дерева за O(1) по памяти
Никак, полагаю?
Есть как минимум 3 решения.
Ну если считать ограниченной высоту дерева, то, думаю и больше трех найдётся. А если нет, увы, это какая-то революция в CS.
Впрочем, если структуру представления дерева в памяти выбираю я сам, то конечно есть решение :)
Ограничить дерево - это один из способов, да.
Второй вариант: амортизация, если подсчёт перенести в построение или изменение дерева, то получение суммы будет вообще константа.
Третий вариант: в дереве нужны ссылки на родителя и соседа, тогда можно сделать обход без дополнительной памяти через конечный автомат.
Ещё можно использовать модификацию дерева, тогда не требуется дополнительная память.
Я и по другую сторону стола сидел, и принял бы в идеале аргумениированный ответ "никак" как финальную точку понимания теории алгоритмической сложности.
Ограничить дерево - это один из способов, да.
Конечно, у нас же дерево в память помещается, а памяти в реальной машине конечное количество, так что на самом деле практически выполнимых алгоритмов с потреблением памяти больше O(1) не существует. Как однократная "шутка" от кандидата это определено плюс. Но второй раз уже не смешно.
Второй вариант: амортизация, если подсчёт перенести в построение или изменение дерева, то получение суммы будет вообще константа.
В дереве, где элементы и их сумма фиксированной длинны, да, конечно, вариант. Было бы в условии задачи это ещё отражено :)
Третий вариант: в дереве нужны ссылки на родителя и соседа, тогда можно сделать обход без дополнительной памяти через конечный автомат.
Ну формально мы добавили ссылки на родителя и соседа в каждый элемент дерева и благополучно сожрали на это O(количество узлов) памяти. Если у нас уже такое дерево было, то круто, а если нет, то условие задачи не выполняется. Это примерно про то, что я в комментарии выше написал, про выбор структуры дерева в памяти.
Ещё можно использовать модификацию дерева, тогда не требуется дополнительная память
Тогда, зачастую, можно и дерево не хранить, а просто только сумму :) напоминает загадку "а и б сидели на трубе".
Но окей, не спорю, есть о чем поговорить, так что вопрос хороший.
Или хранить дерево в виде списков смежности. Тогда по размеру списка сразу видно лист или нет без доп памяти
Кодинг-интервью: без боли и литкода