Синусы как раз прекрасно сводятся к простым суммам (ряды Тейлора), но не понятно, как это вообще должно быть связано с отображением результата. В sin(1) ни конечной в десятичной записи рациональной дроби, ни даже периодической вы не увидите, поэтому, по сути вопрос в том, на каком знаке после запятой его округлить. А это примерно "как пользователю нужно". Меня бы 0.01745 бы устроило, кроме тех случаев, когда нужно дальше с этим что-то считать.
Дело в том, что хорошие вычислительные методы, дают предсказуемую погрешность, зачастую значительно меньшую, чем погрешность отдельных операций в составе их алгоритмов. "остаточный член на n-ной итерации", такие вот штуки, и, конечно, кому это надо, они это считают. Смутно конечно помню это с курсов в универе. Но суть представляю: зачем на каждую операцию погрешность считать, тратя на это время, если про многие популярные методы вычислений эти погрешности уже аналитически рассчитаны.
А нафига делать паузы, если скроллящийся текст читаем? На смартфоне, например я скроллю чуть ли не постоянно в принципе, если что-то читаю, причём привык так сразу как только на аппарат с 144Гц перешёл. И примерно с тех же пор вовсе перестал пользоваться eink читалкой, где можно было только pageup/pagedown. Убедиться, что я до конца страницы дочитал, перед перелистыванием, вот ещё. На компе конечно сильно от задач зависит, но код тоже скроллить привык а не закладки на каждый нужный (и ненужный) момент ставить.
Сложно не быть скептиком на эту тему. Полагаю у людей со стократным годовым доходом проблем на этот случай может быть меньше, чем у тех, кто и не пытался раньше ничего "отбеливать", потому как это было не нужно и странно вовсе. У меня вон выписка о покупке долларов в банке за 5 лет перестала быть читаемой в принципе, но даже и она, как я понимаю, не является юридически значимым документом.
И вот не понятно как с такой историей будут работать. Потому что если это засчитывается, то смысл вообще от всех этих проверок кроме нервотрепки? А если не засчитывается, то даже сложно представить какому проценту людей будет не объяснить откуда у них деньги...
Ну так сенсорика человека вещь индивидуальная, да и вообще довольно-таки хрупкая. Кто-то реально не может различить 60 и 120 фпс. Кто-то не может различить даже 24 фпс и 60, а поскольку это "не лечится" с одной стороны, а с другой - ну не то что бы сильно меняет качество жизни, то почему бы не убедить сначала себя, а потом попытаться окружающих, что это мол норма.
Нормальное решение минут пять-десять только голосом объяснять, <...> то, которое справится с всеми возможными замкнутыми комнатами, не попадая в ту же клетку более чем дважды для большинства клеток.
Беру свои слова назад :) На чуть более сложных картах, чем тривиальные (= прямоугольные без препятствий) я так и не пришел к такому решению (которое ограничивает количество повторных посещений клеток, не зависящим от размера карты числом), в фоне думая об этом уже вон сколько.
А чему Вы радуетесь в коде из поста
Скрытый текст
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.
Я и по другую сторону стола сидел, и принял бы в идеале аргумениированный ответ "никак" как финальную точку понимания теории алгоритмической сложности.
Ограничить дерево - это один из способов, да.
Конечно, у нас же дерево в память помещается, а памяти в реальной машине конечное количество, так что на самом деле практически выполнимых алгоритмов с потреблением памяти больше O(1) не существует. Как однократная "шутка" от кандидата это определено плюс. Но второй раз уже не смешно.
Второй вариант: амортизация, если подсчёт перенести в построение или изменение дерева, то получение суммы будет вообще константа.
В дереве, где элементы и их сумма фиксированной длинны, да, конечно, вариант. Было бы в условии задачи это ещё отражено :)
Третий вариант: в дереве нужны ссылки на родителя и соседа, тогда можно сделать обход без дополнительной памяти через конечный автомат.
Ну формально мы добавили ссылки на родителя и соседа в каждый элемент дерева и благополучно сожрали на это O(количество узлов) памяти. Если у нас уже такое дерево было, то круто, а если нет, то условие задачи не выполняется. Это примерно про то, что я в комментарии выше написал, про выбор структуры дерева в памяти.
Ещё можно использовать модификацию дерева, тогда не требуется дополнительная память
Тогда, зачастую, можно и дерево не хранить, а просто только сумму :) напоминает загадку "а и б сидели на трубе".
Но окей, не спорю, есть о чем поговорить, так что вопрос хороший.
Как было у Стругацких: любой может решить решаемую задачу, нам надо решить не решаемую :)
Только вот привычно понимаемым целям найма это несколько противоречит.
Мне важно видеть то, как человек решает задачу которую он НЕ знает, то есть, вынужден думать и искать решение, чем проверять его память.
Скручивать опыт я ещё не пробовал, но вот и о том что в топ-100 codingamer'ов в резюме не добавляю. "только не литкод, пожалуйста, только не литкод" :)
Задача интересная для, например, codingames, на недельку, с живой таблицей лидеров (даём "ограниченный заряд", которого точно не хватит на заполнение всех карт и оцениваем сумму закрашенных ячеек). Для собеседования не очень интересная.
С чего Вы взяли, что кандидаты начнут с stateless решений, зачем? Чтобы потратить время?
Нормальное решение минут пять-десять только голосом объяснять, лично я бы честно сказал, что я не буду даже начинать его писать в рамках часового лимита. Причём нормальное это просто то, которое справится с всеми возможными замкнутыми комнатами, не попадая в ту же клетку более чем дважды для большинства клеток. В рамках контеста на codingames оно бы болталось где-то в самом низу золотой лиги. Но в моем понимании, "сеньорство" только с момента оптимизации решения такого уровня и требуется.
Причём опыт gamedev или подобных контестов имеет определяющее значение. С рекурсии могут начинать лишь те кандидаты, которые вообще ни с чем подобным ранее не сталкивались.
а если в геймдев, то А* должен от зубов отлетать, ни в коем случае не пользоваться библиотеками
А чем в этой задаче A* поможет, для начала? :)
Про тестируемость тем более покрытие тестами в такой задаче на час вообще смешно читать.
Моё мнение, хоть это и плохой заведомо вид тестирования, но на час с остальными вашими требованиями подойдёт например задача расстановки n ферзей на доске n x n, чтобы ни один не был под ударом. При этом, 70-90% реальных синьоров и с этим не справится из-за условий стресса.
Не то направление, милорд. Так ведь можно вообще все сделать наказуемым поступком, смотря кто судит. И вообще нет на Вас @vvzvlad, чтобы пояснить, что это мизогиния, что очевдино как горящая свеча при свете луны, как алгебра стука мышиных лапок, как криптография в 2*2=5.
Но без иронии, вопрос в том, чем психологическое насилие выгодно определенным категориям и почему. Вот одна история, которая может сделать разницу. Если допустить, что материальные вложения в отношениях (не очень интересно на самом деле, разрешим спекулировать) и в браке (очень интересно) должны быть в пропорции 50/50 мужчины и женщины, как и дальнейший раздел совместно приобретенного имущества 50/50, с сохранением необходимости платить алименты (РосГосРанжированные) для стороны, отказавшейся от детей, то вся эта фигня с деланием мозгов улетает как экономически бесперспективная. Излишки средств относительно этой пропорции - в личные инвестиции, не подлежащие разделу, и я могу заслуженно получить минусы дальше от этого заведения.
Мне интересно так построить диалог с вами, чтобы симпатия читающих его была на моей стороны. Ровно с тем же интересом и активностью я могу отстаивать противоположную точку зрения, если я бы вдруг увидел, что логика нарушается у комментатора на другой стороне баррикад и за это можно было уцепиться.
Другими словами: наброс ради плюсиков. Однако, сомнительно, что такая позиция, особенно после столь прямолинейного "саморазоблачения" может их заслуживать. А неприкрытые попытки манипуляции аналогиями в доказательстве истинности вопросов, и отсутствие любых попыток предложить решения, - вполне могут заслуживать и обратной оценки. Но, поскольку Вы не сомневаетесь в успешности ваших действий относительно желаемого результата, могу лишь предположить что у Вас есть козырь, есть уже те, кто ждут отмашки эти плюсики Вам поставить по какому-либо договору с Вами. Ваше право/дело, что уж.
Хабр как НЛП полигон, интересно.
Простите что вселил в вас уверенность что вы вышли на след фем-шпиона в дружных мужских рядах.
Пока у меня была уверенность лишь в том, что это account takeover. После этого сообщения она стала близка к 100%.
Но просто в отличии от вас я признаю за любым человеком право на работу и занятия тем, чем он хочет, безотносительно пола/веры/места рождения/етс. А вы не признаете, просто потому что субьект применения этого права — женщина. Это и называется мизогиния. ¯\_(ツ)_/
Я все таки за изначальным контекстом ветки комментарием слежу. Стартер написал что мол у мужчин прав куда меньше. Вы вступили, сказали что ну а "у женщин нет прав на этот список работ". Формально это тейк. Я сказал - не вопрос, лично я готов способствовать снятию этого запрета, но не вижу никакой актуальности в этом. И да, именно так, я общаюсь с женщинами, и ни одной из них именно эта проблема не интересна. Аудитория большая, разнородная во всех смыслах, и это дает мне право на представление о том, что именно эта проблема не интересует вероятно почти никого. Отсутствие отклоненных петиций доказывает это. Так что хоть формально ваш тейк имеет право на существование, но никаких дальнейших выводов из него не сделать. А для вас просто способ наконец-то вставить мизогинию и начнять пояснять что это такое на странных примерах. Именно так вели себя феминистические движения в РФ еще начиная с годов 2010-х. Смысла во всем этом, кроме как привлечь внимание к себе попросту нет. Хабр пожалуй самое странное место, чтобы иметь хоть какие-то бонусы от "быть подстилкой феминисток". Поэтому, честно говоря, ЯННП, кроме того, что серьезных тейков в оппозиции к комментарию avraam-inside у Вас нету.
Понимать, даже аналогии, вы отказываетесь
Да, я берегу свою логику и свое представление о логике. Понимать камень я тоже отказываюсь. Только мы в том месте это обсуждаем, где дальшнейшей дискусси о том что "чтобы жить необходимо понимать камни, потому что они часть природы, а природа Всевышняя" не прокатят. Собственно следующая часть методички как раз об этом, сводить дискуссию в феноменальный бред и пустую полемику. Все кроме фемок замолчали/вышли - значит фемки победили. Ах, ностальгия.
а вам он в лицо смеется и говорит, что ну надо было в семье директора предприятия рождаться, а тебе лезть куда не надо не следует, продолжай дальше свои копейки получать, тоже мне блин нашелся, ценный спец, вас таким за забором очередь. Вам приятно будет? Вот пример как могут дискримировать вас по признаку родства.
Ну будет в лицо смеяться, что ж рискнет потерять низкооплачиваемый высококвалифицированный кадр (и некоторые вполне готовы рискнуть просто ради собственного фана). А после личной встречи, не сомневайтесь, за бокальчиком вина с друзьями еще десять раз эту историю (и того самого персонажа "Вас") обсмеет.
Да, очень интересно было бы решить проблему дискриминации, там где она больнее всего бьет, только решений нет. Запретить смеяться != запретить дискриминировать. А запретить дискриминировать есть буквально другими словами, запрещать те решения, которые Вам нравятся без основания на то. А благодаря именно Вашему примеру-аналогии, отмечу: еще и те решения, которые вам удобны.
Извините, но Вам уже намекнул другой комментатор о стиле вашего мышления, все ровно по фемдом методичке. Сначала обрисовать проблему которая ровно никого не волнует, потом убедить собеседников, что вы ее не понимаете, потом принести ложные аналогии, которые должны якобы затронуть чувства собеседников о наличии некоторой несправедливости. "Предвосхитить" попытку собеседника ответить формально и верно: проблемы не связаны никак через управление дальнейшими моментами размышленя, и не грешить во всем этом процессе использовать самые общие понятия, едва ли кому-то что-то доказывающие, как то мизогиния.
Мы какую проблему решаем? Еще раз, все что от меня зависит в решении конкретных проблем я сделаю, подпишу петицию о снятии запрета "неженских" работ. Я вообще ничего не теряю о этого. И да, ради смеха, потому что смех вроде бы ничем и никак не запрещен, а по факту ничего, абсолютно ничего после подписания этой петиции не изменится.
Вот кстати идея на коммерцию, снять кино, где девочка мечтает быть шахтером, но злые патриархи ей не этого дают, и ближе к концу фильма, через все интриги и хитросплетения жизни, наконец она достигает своей мечты, ура, - она вся в грязи и пыли в глубокой шахте тащит мешок руды, зал плачет.
Синусы как раз прекрасно сводятся к простым суммам (ряды Тейлора), но не понятно, как это вообще должно быть связано с отображением результата. В sin(1) ни конечной в десятичной записи рациональной дроби, ни даже периодической вы не увидите, поэтому, по сути вопрос в том, на каком знаке после запятой его округлить. А это примерно "как пользователю нужно". Меня бы 0.01745 бы устроило, кроме тех случаев, когда нужно дальше с этим что-то считать.
Дело в том, что хорошие вычислительные методы, дают предсказуемую погрешность, зачастую значительно меньшую, чем погрешность отдельных операций в составе их алгоритмов. "остаточный член на n-ной итерации", такие вот штуки, и, конечно, кому это надо, они это считают. Смутно конечно помню это с курсов в универе. Но суть представляю: зачем на каждую операцию погрешность считать, тратя на это время, если про многие популярные методы вычислений эти погрешности уже аналитически рассчитаны.
А нафига делать паузы, если скроллящийся текст читаем? На смартфоне, например я скроллю чуть ли не постоянно в принципе, если что-то читаю, причём привык так сразу как только на аппарат с 144Гц перешёл. И примерно с тех же пор вовсе перестал пользоваться eink читалкой, где можно было только pageup/pagedown. Убедиться, что я до конца страницы дочитал, перед перелистыванием, вот ещё. На компе конечно сильно от задач зависит, но код тоже скроллить привык а не закладки на каждый нужный (и ненужный) момент ставить.
Сложно не быть скептиком на эту тему. Полагаю у людей со стократным годовым доходом проблем на этот случай может быть меньше, чем у тех, кто и не пытался раньше ничего "отбеливать", потому как это было не нужно и странно вовсе. У меня вон выписка о покупке долларов в банке за 5 лет перестала быть читаемой в принципе, но даже и она, как я понимаю, не является юридически значимым документом.
-- Откуда деньги, которыми погасил кредит?
-- Так вот продал доллары
-- Откуда доллары?
-- Так вот купил 5 лет назад
-- А откуда деньги были на покупку этих долларов?
-- 10 лет под подушкой копил
И вот не понятно как с такой историей будут работать. Потому что если это засчитывается, то смысл вообще от всех этих проверок кроме нервотрепки? А если не засчитывается, то даже сложно представить какому проценту людей будет не объяснить откуда у них деньги...
Ну так сенсорика человека вещь индивидуальная, да и вообще довольно-таки хрупкая. Кто-то реально не может различить 60 и 120 фпс. Кто-то не может различить даже 24 фпс и 60, а поскольку это "не лечится" с одной стороны, а с другой - ну не то что бы сильно меняет качество жизни, то почему бы не убедить сначала себя, а потом попытаться окружающих, что это мол норма.
Беру свои слова назад :) На чуть более сложных картах, чем тривиальные (= прямоугольные без препятствий) я так и не пришел к такому решению (которое ограничивает количество повторных посещений клеток, не зависящим от размера карты числом), в фоне думая об этом уже вон сколько.
А чему Вы радуетесь в коде из поста
Скрытый текст
я ума не приложу. Он же даже на тривиальных картах не работает как 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.
В принципе, это весело.
Я и по другую сторону стола сидел, и принял бы в идеале аргумениированный ответ "никак" как финальную точку понимания теории алгоритмической сложности.
Конечно, у нас же дерево в память помещается, а памяти в реальной машине конечное количество, так что на самом деле практически выполнимых алгоритмов с потреблением памяти больше O(1) не существует. Как однократная "шутка" от кандидата это определено плюс. Но второй раз уже не смешно.
В дереве, где элементы и их сумма фиксированной длинны, да, конечно, вариант. Было бы в условии задачи это ещё отражено :)
Ну формально мы добавили ссылки на родителя и соседа в каждый элемент дерева и благополучно сожрали на это O(количество узлов) памяти. Если у нас уже такое дерево было, то круто, а если нет, то условие задачи не выполняется. Это примерно про то, что я в комментарии выше написал, про выбор структуры дерева в памяти.
Тогда, зачастую, можно и дерево не хранить, а просто только сумму :) напоминает загадку "а и б сидели на трубе".
Но окей, не спорю, есть о чем поговорить, так что вопрос хороший.
Только вот привычно понимаемым целям найма это несколько противоречит.
Скручивать опыт я ещё не пробовал, но вот и о том что в топ-100 codingamer'ов в резюме не добавляю. "только не литкод, пожалуйста, только не литкод" :)
Впрочем, если структуру представления дерева в памяти выбираю я сам, то конечно есть решение :)
Ну если считать ограниченной высоту дерева, то, думаю и больше трех найдётся. А если нет, увы, это какая-то революция в CS.
Хотя и дальше странное...
Никак, полагаю?
Задача интересная для, например, codingames, на недельку, с живой таблицей лидеров (даём "ограниченный заряд", которого точно не хватит на заполнение всех карт и оцениваем сумму закрашенных ячеек). Для собеседования не очень интересная.
С чего Вы взяли, что кандидаты начнут с stateless решений, зачем? Чтобы потратить время?
Нормальное решение минут пять-десять только голосом объяснять, лично я бы честно сказал, что я не буду даже начинать его писать в рамках часового лимита. Причём нормальное это просто то, которое справится с всеми возможными замкнутыми комнатами, не попадая в ту же клетку более чем дважды для большинства клеток. В рамках контеста на codingames оно бы болталось где-то в самом низу золотой лиги. Но в моем понимании, "сеньорство" только с момента оптимизации решения такого уровня и требуется.
Причём опыт gamedev или подобных контестов имеет определяющее значение. С рекурсии могут начинать лишь те кандидаты, которые вообще ни с чем подобным ранее не сталкивались.
А чем в этой задаче A* поможет, для начала? :)
Про тестируемость тем более покрытие тестами в такой задаче на час вообще смешно читать.
Моё мнение, хоть это и плохой заведомо вид тестирования, но на час с остальными вашими требованиями подойдёт например задача расстановки n ферзей на доске n x n, чтобы ни один не был под ударом. При этом, 70-90% реальных синьоров и с этим не справится из-за условий стресса.
Не то направление, милорд. Так ведь можно вообще все сделать наказуемым поступком, смотря кто судит. И вообще нет на Вас @vvzvlad, чтобы пояснить, что это мизогиния, что очевдино как горящая свеча при свете луны, как алгебра стука мышиных лапок, как криптография в 2*2=5.
Но без иронии, вопрос в том, чем психологическое насилие выгодно определенным категориям и почему. Вот одна история, которая может сделать разницу. Если допустить, что материальные вложения в отношениях (не очень интересно на самом деле, разрешим спекулировать) и в браке (очень интересно) должны быть в пропорции 50/50 мужчины и женщины, как и дальнейший раздел совместно приобретенного имущества 50/50, с сохранением необходимости платить алименты (РосГосРанжированные) для стороны, отказавшейся от детей, то вся эта фигня с деланием мозгов улетает как экономически бесперспективная. Излишки средств относительно этой пропорции - в личные инвестиции, не подлежащие разделу, и я могу заслуженно получить минусы дальше от этого заведения.
Да, действительно. У самой подписываемой, как пока смог найти, вижу 2387 подписей.
Другими словами: наброс ради плюсиков. Однако, сомнительно, что такая позиция, особенно после столь прямолинейного "саморазоблачения" может их заслуживать. А неприкрытые попытки манипуляции аналогиями в доказательстве истинности вопросов, и отсутствие любых попыток предложить решения, - вполне могут заслуживать и обратной оценки. Но, поскольку Вы не сомневаетесь в успешности ваших действий относительно желаемого результата, могу лишь предположить что у Вас есть козырь, есть уже те, кто ждут отмашки эти плюсики Вам поставить по какому-либо договору с Вами. Ваше право/дело, что уж.
Хабр как НЛП полигон, интересно.
Пока у меня была уверенность лишь в том, что это account takeover. После этого сообщения она стала близка к 100%.
Чтобы мне не повторяться третий раз, "давайте" сразу суммаризируем.
Мизогиния существует, спору нет. Наверное это плохо, - просто соглашусь. Есть проблема, значит надо как-то решать.
Какие предложения по решению проблемы у Вас есть?
Скрытый текст
По методичке дальше так: огласка проблемы - уже половина ее решения.
Я все таки за изначальным контекстом ветки комментарием слежу. Стартер написал что мол у мужчин прав куда меньше. Вы вступили, сказали что ну а "у женщин нет прав на этот список работ". Формально это тейк. Я сказал - не вопрос, лично я готов способствовать снятию этого запрета, но не вижу никакой актуальности в этом. И да, именно так, я общаюсь с женщинами, и ни одной из них именно эта проблема не интересна. Аудитория большая, разнородная во всех смыслах, и это дает мне право на представление о том, что именно эта проблема не интересует вероятно почти никого. Отсутствие отклоненных петиций доказывает это. Так что хоть формально ваш тейк имеет право на существование, но никаких дальнейших выводов из него не сделать. А для вас просто способ наконец-то вставить мизогинию и начнять пояснять что это такое на странных примерах. Именно так вели себя феминистические движения в РФ еще начиная с годов 2010-х. Смысла во всем этом, кроме как привлечь внимание к себе попросту нет. Хабр пожалуй самое странное место, чтобы иметь хоть какие-то бонусы от "быть подстилкой феминисток". Поэтому, честно говоря, ЯННП, кроме того, что серьезных тейков в оппозиции к комментарию avraam-inside у Вас нету.
Да, я берегу свою логику и свое представление о логике. Понимать камень я тоже отказываюсь. Только мы в том месте это обсуждаем, где дальшнейшей дискусси о том что "чтобы жить необходимо понимать камни, потому что они часть природы, а природа Всевышняя" не прокатят. Собственно следующая часть методички как раз об этом, сводить дискуссию в феноменальный бред и пустую полемику. Все кроме фемок замолчали/вышли - значит фемки победили. Ах, ностальгия.
Ну будет в лицо смеяться, что ж рискнет потерять низкооплачиваемый высококвалифицированный кадр (и некоторые вполне готовы рискнуть просто ради собственного фана). А после личной встречи, не сомневайтесь, за бокальчиком вина с друзьями еще десять раз эту историю (и того самого персонажа "Вас") обсмеет.
Да, очень интересно было бы решить проблему дискриминации, там где она больнее всего бьет, только решений нет. Запретить смеяться != запретить дискриминировать. А запретить дискриминировать есть буквально другими словами, запрещать те решения, которые Вам нравятся без основания на то. А благодаря именно Вашему примеру-аналогии, отмечу: еще и те решения, которые вам удобны.
Извините, но Вам уже намекнул другой комментатор о стиле вашего мышления, все ровно по
фемдомметодичке. Сначала обрисовать проблему которая ровно никого не волнует, потом убедить собеседников, что вы ее не понимаете, потом принести ложные аналогии, которые должны якобы затронуть чувства собеседников о наличии некоторой несправедливости. "Предвосхитить" попытку собеседника ответить формально и верно: проблемы не связаны никак через управление дальнейшими моментами размышленя, и не грешить во всем этом процессе использовать самые общие понятия, едва ли кому-то что-то доказывающие, как то мизогиния.Мы какую проблему решаем? Еще раз, все что от меня зависит в решении конкретных проблем я сделаю, подпишу петицию о снятии запрета "неженских" работ. Я вообще ничего не теряю о этого. И да, ради смеха, потому что смех вроде бы ничем и никак не запрещен, а по факту ничего, абсолютно ничего после подписания этой петиции не изменится.
Вот кстати идея на коммерцию, снять кино, где девочка мечтает быть шахтером, но злые патриархи ей не этого дают, и ближе к концу фильма, через все интриги и хитросплетения жизни, наконец она достигает своей мечты, ура, - она вся в грязи и пыли в глубокой шахте тащит мешок руды, зал плачет.