Мы все знаем, что работа программиста зачастую заключается в модификации уже существующих программ (исходного кода) для исправления какого-то их некорректного поведения в некоторых ситуациях или для реализации новой функциональности для пользователей. В любом случае тот, кто считает себя хорошим программистом, должен быть готов что-то изменить или дополнить в своей или даже в чужой программе самым эффективным способом.
Мне кажется, у меня получилось придумать интересную задачу для проверки такой способности у программистов. Мне кажется, ничего подобного я никогда не видел, или, по крайней мере прямо сейчас не помню, может кто-то напомнит.
А еще мне кажется, что описанная далее задача была бы хорошей проверкой даже для искусственного интеллекта, чтобы проверить насколько он, собственно, интеллект в области способностей к программированию. Интересно возьмется ли кто-нибудь сформулировать такую задачу для ИИ. Возможно ли это?
Задание для программирования
Задача состоит из двух элементарных частей, и вся загвоздка, естественно, отнесена ко второй части.
Итак, первая часть задачи. Нужно написать программу, которая будет проверять знание таблицы умножения второклассником,
для этого должны случайным образом генерироваться два числа от 2 до 9 (фактически цифры);
выводить такой случайный пример на умножение для решения второклассником;
ждать ответа, или команды на завершение программы, если решили зациклить программу (пускай по нажатию клавиш "Enter" и "Esc" соответственно, суть совершенно не в этом);
похвалить в случае правильного ответа или сообщить правильный результат в случае ошибки.
Можно вывести статистику по завершении программы, но это не обязательное требование, это так сказать на пять с плюсом, в статистику можно включить среднее время на ответ, например, но это уже на 6+ (на шесть с плюсом по пятибалльной системе, но это все еще не суть, это не имеет отношения к заковырке запланированной во второй части задачи :).
Часть вторая, заковыристая
Тут мы подходим, неожиданно(!), к возможности расширения программы. А ведь, казалось бы, что же можно расширить в программе, которая уже может быть написана на "Шесть с плюсом" по пятибалльной системе?
И тут следует вот такое задание для второй части задачи:
необходимо расширить пункт 2 первой части задания разбивкой на подпункты, следующим образом:
2. выводить пример для решения второклассником
a. на умножение
b. на деление (целочисленное, по той же таблице умножения, все также для второклассника)
Но в таком виде разбор задания и его решения было бы через чур сложным для данной статьи. Разбор такого расширения требований к программе вместе с требованиями на оценку выше 5 баллов потребует еще одной статьи. Здесь я предлагаю разобрать простую замену пункта 2 на пункт 2 в виде:
2. выводить пример на деление для решения второклассником
Было бы очень интересно узнать какой процент людей, считающих себя программистами или даже опытными программистами, сможет сформулировать адекватное решение для такой в общем то элементарной задачи. К сожалению, мы вряд ли получим объективный результат из опроса поскольку не все согласятся объективно отнести себя к группе не справившихся даже анонимно, более того с тем решением, которое я ниже распишу, не все согласятся как с лучшим.
Но надо, конечно, описать проблему, которая возникает при таком, в общем то тривиальном, изменении требования к программе. Рассмотрим, как работает программа для примера с умножением и что не так с этим алгоритмом при переходе к примеру с делением.
Итак, по заданию из первой части,
1. программа генерирует два случайных числа Х и У в заданных пределах, в любом языке есть соответствующая библиотечная функция генерации случайных чисел, с этим нет проблем!
2. Запоминаем произведение (Х * У) в переменную Res;
3. Программа выводит на экран переменные Х и У с помощью форматированной строки, например как-то так:
«7 * 3 = введите ответ ниже»
4. Введенный ответ сохраняется в переменную Z и сравнивается с Res,
5. По результатам сравнения выводим либо поздравление, либо правильный результат из Res.
При попытке замены операции умножения на операцию деления там, где мы запоминаем произведение чисел, теперь это будет(?) частное от деления – то есть вместо
Res = (Х * У)
Кажется, нам просто нужно сделать
Res = (Х / У),
но, оказывается, так это работать не будет (неожиданно?), потому что дроби второклассник знать совершенно не обязан! К тому же нам все равно придется изменить то, что называется гордо «интерфейс взаимодействия с пользователем» - заменить знак умножения на знак деления в строке, отображающей задание. Оказывается, программу (функцию) надо как-то переписывать, нельзя просто поменять умножение на деление! В этот момент начинающий программист (или некомпетентный?) понимает, что он пока еще (по крайней мере!) не совсем программист и начинает барахтаться в поисках подходящего варианта. В этой необходимости изменить программу и заключается заковырка, которая позволяет оценить компетентность программиста.
Я припоминаю попытки что-то изобретать с процедурой генерации случайных чисел у студентов, которым я задавал такую задачку и это было абсолютно ложное направление решения проблемы, которое я вынужден был пресечь как неконструктивное, когда вы знаете правильное решение (то есть не то, чтобы знаете – это решение, само собой разумеется).
Правильное решение
Очевидным является то, что не надо особо придумывать, как известно. Если не менять формулу:
Res = (Х * У)
А просто вывести на экран вместо переменных Х и У, переменные Res и У (например, можно использовать Х) с помощью чуть измененной форматированной строки (заметим еще раз форматированную строку все равно придется менять!), например это будет выглядеть как-то так:
21 / 3 = введите ответ ниже
То далее еще придется изменить переменную для сравнения, вместо:
4. Введенный ответ сохраняется в переменную Z и сравнивается с Res,
Надо переписать (заменить переменную Res на Х)
4. Введенный ответ сохраняется в переменную Z и сравнивается с Х,
И все опять будет работать, но уже для примеров с делением.
Далее, если вы знакомы с указателями или со ссылками вы можете поупражняться с соответствующим способом параметризации алгоритма, но, как я уже заметил ранее, это могло бы быть темой для еще одной статьи, так же, как и необходимость дополнительных потоков для измерения времени или тайм-аута, за которое второклассник вводит ответ.
Интересно было бы прочитать описания чего-то подобного (условно заковыристых задач и их решений) из чужой практики.
Комментарии (123)
Spaceoddity
02.07.2023 07:12+20У вас талант давать вводные задачи настолько заковыристо и непонятно...
Я что-то никак в толк до сих пор не возьму - а в чём собственно проблема (это если мы оставим в стороне фактическую примитивность самой задачи в посте)? В замене знака деления? Или в концептуальном отделении логики от представления (вас же никто не обязывает показывать пользователю "внутреннюю кухню логики" - можете нарисовать ему двоеточие хоть картинкой между двумя "полями" для вывода сгенерированных чисел)?
Wesha
02.07.2023 07:12+8У вас талант давать вводные задачи настолько заковыристо и непонятно...
Добро пожаловать в реальный мир! Примерно так ставят задачи чуть менее чем все клиенты. И нередко основная трудность не в написании программы, а в том, чтобы клещами вытянуть из заказчика, что он, собственно говоря, хочет.
а в чём собственно проблема
Насколько я понимаю, аффтар человек весьма неопытный, и по умолчанию считает, что программист сначала выберет случайное число 1...100, скажет, что "это произведение", а потом долго будет думать "а каких двух чисел это произведение". Потом его осенило — "надо сделать наоборот: сгенерить множители, показать произведение ученику, и проверить, что он введет те же множители, что были сегенерены". Ну что ж, поздравим аффтара, он только что переизобрёл один из приёмов ТРИЗ.
Spaceoddity
02.07.2023 07:12+2Нет-нет. Я возбудился как раз на то, что из контекста поста следует что ТС далеко не случайный человек в этой отрасли. Вон, об алгоритмах же рассуждает...
Так-то я тёртый калач)) И по возможности всегда иду навстречу заказчику, сразу указывая на косяки в бизнес-логике. Но в "клинических случаях" ведь всегда есть финт с "всё строго по ТЗ"))
Ну и на самом деле так ведут себя далеко не все заказчики - многие вполне себе умеют в строгую формализацию ТЗ.
SiGGthror
02.07.2023 07:12+4С генерацией случайного числа и потом поиска его множителей есть проблема, которая состоит в том, что для начала было бы неплохо понять, а не простое ли это число. Конечно от 1 до 100 их не так много и можно захардкодить их и пытаться перегенирировать, но уже на этом этапе понятно, что генерация сразу произведения сопряжена с некоторыми сложностями и стоит поискать путь попроще
rukhi7 Автор
02.07.2023 07:12-14но уже на этом этапе понятно, что генерация сразу произведения сопряжена с некоторыми сложностями и стоит поискать путь попроще
вот это не фига себе! Я то думал что ничего проще нет, но в дно постучали.
SiGGthror
02.07.2023 07:12+9Ничего проще нет чем что, позвольте уточнить
rukhi7 Автор
02.07.2023 07:12-11С генерацией случайного числа и потом поиска его множителей есть проблема
не надо искать множители случайного числа, надо сгенерировать два случайных числа и перемножить их и вы получите случайное число с известными множителями.
Читайте статью внимательно.
SiGGthror
02.07.2023 07:12+16Я ее прочел. Она мне не нравится.
Во-первых, в ней ни слова о том, что в некоторых случаях (1,26%, если я верно посчитал) мы можем получить одинаковые задания, следующие друг за другом, а еще в части случае мы просто поменяем множители местами. Это редкие случаи, но на мой взгляд важные.
Во-вторых, мой комментарий лишь показывает возможный путь размышления над задачей и что при решении "в лоб" есть некоторые дополнительные расходы и любому разработчику стоит задуматься о поиске более простого пути.rukhi7 Автор
02.07.2023 07:12-19Я ее прочел. Она мне не нравится.
Ну вот это хотя бы человеческий язык, СПАСИБО!
Ну не нравится так не нравится, закрыли бы и все, зачем же тогда мозахизмом заниматься и садизмом заодно?
Я не понимаю.
Wan-Derer
02.07.2023 07:12+1Я прочитал ещё раз и вот что я увидел:
1. для этого должны случайным образом генерироваться два числа от 2 до 9 (фактически цифры);
2. выводить пример на деление для решения второклассником
Из этого ТЗ для меня очевидно что программа проверяет только деление одной цифры на другую. Всё, больше тут ничего нет. Если задание заключается в чём-то ином - значит ТЗ должно быть сформулировано иначе. Например:
Напишите программу для проверки знания таблицы умножения на примере операций умножения и/или деления.
И всё, без каких-либо пунктов.
Или:
1. для этого должны случайным образом генерироваться два числа от 2 до 9 (фактически цифры), которые являются множителями для формируемого примера;
2. выводить пример на деление для решения второклассником
Тогда да, претензии обоснованы, а так - нет :)
Hardcoin
02.07.2023 07:12+3не надо искать множители случайного числа, надо сгенерировать два случайных числа
Разумеется. Ваш собеседник именно это и имел ввиду, когда сказал, "надо искать путь по-проще". А вы ему в ответ про дно.
dgoncharov
02.07.2023 07:12а потом долго будет думать "а каких двух чисел это произведение".
Ну и пусть подумает. Для толкового студента тут широкий простор для того, чтобы проявить свои таланты. Проверка на простоту, разложение на множители и пр. Для учебной программы, оперирующей числами, не большими сотни, нет в этом ничего сложного.
Hardcoin
02.07.2023 07:12+1Это если вы работаете напрямую с клиентом. Если работаете с аналитиком или архитектором, тогда основная трудность именно написать программу, т.к. требования описаны, иногда вплоть до формата ответа сервисов.
rukhi7 Автор
02.07.2023 07:12-6вы противоречите сами себе, если вы не видите проблемы, то в чем заковыристость и непонятность?
Spaceoddity
02.07.2023 07:12+8очевидно в тезисе автора о том, что проблема наличествует
rukhi7 Автор
02.07.2023 07:12-7но я точно видел эту проблему на лице будущих(на самом деле) студентов, школьников 8-го класса!
Я не вру! Меня это вот так впечатлило, что я решил поделиться этими наблюдениями.
funca
02.07.2023 07:12+1Ваши наблюдения выстроены в таком ключе, что давят на самооценку. Для школьников такой прием звучит на грани фола. Для людей постарше - как минимум странным. Поэтому в качестве провокации статья конечно удалась, не оставив никого равнодушным и собрав кучу комментариев.
rukhi7 Автор
02.07.2023 07:12-20не очень красиво разговаривать с человеком в третьем лице, кстати.
Вы хотите подчеркнуть свою исключительность?
GospodinKolhoznik
02.07.2023 07:12+15Если я правильно понял, его студенты не сообразили, что после того, как сгенерировано два случайных числа a и b, надо посчитать их произведение x=a*b и вывести на экран вопрос x/a=? и сравнить результат с b. А они же выводили a/b=? и потом не знали, что с этим делать.
На настоящем собеседовании, где их попросят решить действительно сложную задачу, их ждёт серьёзное потрясение.
rukhi7 Автор
02.07.2023 07:12-26Ничё, ничё,
Мать дура, Мать плохая!
А как в городе то хвост, тебе прижало...
Цитата из монолога главной героини из фильма "Любовь и голуби"
Spaceoddity
02.07.2023 07:12+10ну значит я всё правильно понял. просто это как бы уровень даже не студентов, а школьников (причём не особо умных)...
BobovorTheCommentBeast
02.07.2023 07:12Мне кажется, это вообще проблема не в программировании. Так можно и прорабу дать, самосвал, экскаватор и рабочих, а он погрузит экскаватор в самосвал и рабочих закопает.
Leetc0deMonkey
02.07.2023 07:12+20Человек, который легко экстраполирует умение решить некую задачку на опыт и компетентность, априори расписывается в своей некомпетентности. Настоящий инженер очень осторожен в гипотезах "если A, то B" и потому очень тщательно их проверяет прежде чем создавать на этих гипотезах решение поставленной задачи.
rukhi7 Автор
02.07.2023 07:12-21Настоящий инженер очень осторожен в гипотезах "если A, то B" и потому очень тщательно их проверяет прежде чем создавать на этих гипотезах решение поставленной задачи.
видимо, особенно, когда этот инженер решает задачи для второкласников,
Похоже на то что вы палитесь :)
Leetc0deMonkey
02.07.2023 07:12+16Ещё раз. У вас нет никаких доказательств корреляции между умением решать подобные задачки и опытом и компетентностью. Никаких. Только интуитивные домыслы. А интуитивным домыслам в инженерном деле не место. Всё должно проверяться и доказываться. Проведите широкое статистическое исследование и возвращайтесь. С превеликим удовольствием изучим этот материал.
rukhi7 Автор
02.07.2023 07:12-16Так я вроде как и провожу, и я так понимаю вам это исследование очень не нравится.
Боитесь увидеть неприемлемые для вас результаты?
Leetc0deMonkey
02.07.2023 07:12+15Я не вижу никакого статистического исследования а-ля "собрали две группы по 100 человек опытных и начинающих, дали им задачку, обнаружили с P=0.05 что профи её решают, а чайники не могут".
Впрочем, подозреваю, вы не очень представляете о чём вообще идёт речь и как всё это работает.
Hardcoin
02.07.2023 07:12Идея хорошая, но как сотрудников нанимать с таким подходом? Десяток статистических исследований не проведёшь, слишком дорого. Приходится ориентироваться на пяток вопросов, надеясь, что ответы дадут тебе релевантную информацию.
sergeaunt
02.07.2023 07:12Простейшие задачи на собеседованиях даются не для того, чтобы выявить гениев, а для того, чтобы отсеять тупиц.
Вы начинаете собеседование с FizzBuzz, дальше варианты:
Кандидат не решает за 15 минут. Тогда о чем разговаривать дальше?
Кандидат решает. Переходим к более сложным вопросам.
Это нужно просто для того, чтобы позволить себе роскошь собеседовать компетентных людей, не тратя много времени на самозванцев.
Farongy
02.07.2023 07:12+9Во-первых. гуглим "Принцип открытости/закрытости".
Во-вторых, если речь идёт о коде, который будет поддерживаться, этот код должен быть максимально очевидным. Если для деления нужна формула a / b = c, значит эта формула должна быть записана именно так, самым наглядным образом.
Решение квизов и реальная разработка - это две большие разницы. Не надо, пожалуйста, учить этому студентов.
rukhi7 Автор
02.07.2023 07:12-19Вы хотите сказать что такую НЕ обычную задачу которая раскрывает во всей красе
"Принцип открытости/закрытости".
вы видите в первый раз? - Спасибо!
Spaceoddity
02.07.2023 07:12+1Если для деления нужна формула a / b = c, значит эта формула должна быть записана именно так, самым наглядным образом.
Вы ходите по очень тонкому льду... Вроде бы вполне себе элементарная замена операции умножения на концептуально более понятную операцию деления, именно в программировании может повлечь за собой кучу проблем на ровном месте.
Для затравки - как вы собрались писать "более поддерживаемый код" с "движком" в виде "a / b = c "? Брать два случайных натуральных числа, делить их и проверять ответ на "целое число больше 1"? Если не удовлетворяет, то повторить?
Phantom91x
02.07.2023 07:12+21Сегодня какой-то день гениальных статей на хабре) В начале один описывал как он сделал git pull и коммит.. в этой статье уровень программиста предлагают проверять задачей на уровне начальных классов)
shasoftX
02.07.2023 07:12+3Следующая статья будет как включать компьютер. А потом статья для профи - как его правильно выключать.
Arris
02.07.2023 07:12+2И задача на 6 с плюсом - как это делать правильно, не просто выдёргивая вилку из розетки...
BobovorTheCommentBeast
02.07.2023 07:12А кроме шуток интересная была бы статья, если in-depth. Почему так можно, а так нельзя, а что может быть если вот так, а когда не может и т.п.
Ее без тонны глубоких знаний не напишешь.
PavelMos
02.07.2023 07:12Ещё генерация случайных чисел-множителей в такой программе должна быть без повторений, в том числе без повторений в парах, например 4 * 7 и 7 * 4
rukhi7 Автор
02.07.2023 07:12-11еще много чего должно быть, но я не собирался писать "Войну и мир"
aelaa
02.07.2023 07:12Что как раз таки нужно делать на собеседовании.
Не то чтобы дословно писать, но оглавление накидать точно было бы полезнее. Какие подходы, какие подводные камни в каких местах на простейшем примере кода.
askharitonov
02.07.2023 07:12+2Мне кажется, подавляющее большинство программистов (с уровнем чуть выше начального) примерно так и сделают, вариант взять два числа и перемножить (вместо того, чтобы подбирать числа, одно из которых можно без остатка разделить на второе) — он же просто напрашивается.
Leetc0deMonkey
02.07.2023 07:12В условиях стресса могут и начать делить и проверять остатки. Всё что проверяет типичное собеседование - это может ли человек пройти это собеседование.
askharitonov
02.07.2023 07:12Вот кстати да. То решение пришло в голову как бы само, я лениво читал статью, параллельно представляя в памяти, каким должно быть решение, и ответ был очевиден. Если же рядом со мной был другой человек, на которого нужно было бы произвести хорошее впечатление, который чего-то от меня ждал и требовал, то тут наверное и на простой задаче можно начать тупить.
Wan-Derer
02.07.2023 07:12+1Этсамое... А тут должно быть решение от шестиклассника или у нас тут серьёзный бизнес с большой нагрузкой и стойкостью от падучей в четыре девятки? :)
jishi
02.07.2023 07:12+3Надо устроить конкурс на самое энтерпрайз-решение! Итак, поскольку у нас в штате нет русского гения, который может летмишоую формулу, то нам потребуется база данных, в которые мы занесём множители и результат. База данных, само собой, не в Oracle, а то вдруг санкции, а в православном Postgres Pro. На неё нужна одна виртуалка. Сервер приложений будет на второй виртуалке. Резервирование оставим на Stage2 проекта, заказчик как раз ещё бизнес-фич принесёт: либо сложение с вычитанием, либо таблицы Брадиса, либо фазы Меркурия, с такими заказчиками сложно предугадать. Раз у нас энтерпрайз, писать будем на Java. У меня сегодня генератор дичи барахлит, какие ещё будут предложения, коллеги?
warlock66613
02.07.2023 07:12+2А с помощью самой такой программы можно проверять на компетентность учёного-физика: решил 10 примеров без ошибок (из них минимум три на деление), значит компетентный учёный. /с
rukhi7 Автор
02.07.2023 07:12-15вы наверно не в курсе что заголовки выбирают в том числе с целью привлечь внимание.
Ну вот я вам рассказал по секрету.
lesskop
02.07.2023 07:12+3В Вашем случае привлечение внимания играет против Вас самих. Компетентность программиста не может быть определена одной задачкой, да еще и такой простой.
markoni
02.07.2023 07:12+7А я еще умею apt install и git pull. Оцените мои навыки программиста? Цирк с конями какой-то :)
wehaud
02.07.2023 07:12+11. Для этого должны случайным образом генерироваться два числа от 2 до 9 (фактически цифры);
2. Выводить такой случайный пример на умножение для решения второклассником
Меня совершенно запутало условие задачи, а потому ее "очевидное" решение стало для меня открытием
Что значит "такой случайный пример"?
Если 2 и 9:
Пример множителями, которого будут два сгенерированных числа?
2 * 9
9 * 2
18 / 2
18 / 9
Пример входными данными будут два сгенерированных числа?
2 * 9
9 * 2
2 / 9
9 / 2
Я подумала, что это второй вариант и мне показалось очень интересной задача, придумать как учесть деление не нацело, возможно проверки, чтобы первое число было больше второго иначе поменять и так далее, а оказалось, что это задачка не на логику, а на изворотливость.
Можно конечно оценивать компетентность бухгалтера по тому, как он уклоняется от налогов, а не по умению их правильно рассчитывать, но как будто это неправильно.
Лучше заменить "компетентность" на "находчивость"
aragaer
02.07.2023 07:12+16Когда-то много лет назад я собеседовался в CCP (ту самую исландскую) и мне дали задание (домашнее) -- написать "игру", в которой человек и компьютер бросают по два d6. Победитель определяется следующим образом:
если у одного дубль, а у другого нет, побеждает дубль
если у обоих дубль, побеждает больший, если оба равны, то ничья
если нет дубля, побеждает бОльшая сумма
при равной сумме побеждает тот, у кого больше бОльшая цифра
иначе опять же ничья
Но при этом было требование -- соотношение выигрышей/проигрышей должно быть 55%/45% в пользу компьютера.
Соответственно решения в стиле "добавить +1 к результату броска" или "перебрасывать плохой результат" не могут дать нужного соотношения (ну или надо как-то очень сильно упороться и все считать). А значительно более простое решение это сначала выполнить два броска, определить "победивший бросок", а потом с вероятностью 55% назначить его компьютеру, а 45% -- человеку.
IkaR49
02.07.2023 07:12Так как со "статьёй" всё понятно, начну оффтопик: и как оно там в ССР? Ещё будучи школьником мечтал пойти к ним работать, но не сложилось, а потом ещё и выяснил, что непосредственно делать игры мне не интересно :)
aragaer
02.07.2023 07:12+3Понятия не имею -- я прошел домашнее задание и собственно поговорил с ними по скайпу, но мы так и не договорились, чем бы именно я бы у них хотел заниматься -- я-то думал сидеть у них на зарплате и патчить wine, чтобы ева на нем нормально шла, но им такой вариант как-то не понравился.
nivorbud
02.07.2023 07:12+1Я дочь сейчас учу основам Питона, и задал ей простую задачку: написать функцию, которая принимает на вход спискок чисел и возвращает медианное значение. Она тут же выслала мне решение, которое меня заинтересовало. Сразу спрашиваю ее: "Где взяла код?". Призналась, что нагуглила и выбрала самый простой на ее взгляд. А в реале это оказалось выпендрёжное решение, которое требует знаний о том, как хранятся числа внутри компа в двоичном виде (конкретно - отрицательные числа - в дополнительном коде), а также знание того факта, что вычислительные системы в глубине своих глубин ничего не умеют кроме сложения.
Короче, вот этот код:def get_median_num(nums): sorted_nums = sotred(nums) mid = len(sorted_nums) // 2 return (sorted_nums[mid] + sorted_nums[~mid]) / 2
nronnie
02.07.2023 07:12Задача хорошая, потому что на решение "в лоб" сразу вопрос "а если чисел миллиард?" Потому что тут уже требуется знать, например, про алгоритмы Манро-Паттерсона или Канна-Гринвальда (и про тот и про другой здесь когда-то писали), и про их особенности (например, что один из них вероятностный, а второй приближенный).
nivorbud
02.07.2023 07:12потому что на решение "в лоб" сразу вопрос "а если чисел миллиард?"
О, этого я насмотрелся. Из-за непонимания этого обычно следуют возгласы неофитов: "Да я такое за неделю сделаю...". Да без проблем! И это возможно будет работать на... десятке тысяч единиц информации. А если их миллион? А если триллион? То оказывается, что ни одно готовое решение не подходит. Более того известные алгоритмы не подходят, и приходится искать оригинальные компромиссные решения.
В общем... гладко было на бумаге...
Wesha
02.07.2023 07:12на решение "в лоб" сразу вопрос "а если чисел миллиард?"
...а на такой вопрос сразу ответ "все условия, явно не оговорённые в задании, кандидат имеет право выбирать на своё усмотрение!"
Alexandroppolus
02.07.2023 07:12Я может чего не понимаю, но почему не просто
return sorted_nums[mid]? (и есть, кстати, "quick select" за O(n))
Cerberuser
02.07.2023 07:12почему не просто
return sorted_nums[mid]?Не работает для чётного числа элементов.
michael_v89
02.07.2023 07:12+3Насколько я вижу, тут не используется особенность хранения отрицательных чисел.
Python это не C++, в нем отрицательный индекс массива имеет специальную обработку, это сокращенная записьlen - index.nivorbud
02.07.2023 07:12+2Чтобы так решить эту задачку, надо было мыслить примерно так:
Цель: получить два соседних средних элемента (если кол-во элементов четное) или средний элемент два раза (если кол-во элементов нечетное). И всё это сделать без дополнительных условий.
Для этого автор решения хочет взять второй элемент, отсчитывая с начала списка, а первый - с конца списка.
Если получить индекс среднего элемента путем целочисленного деления длины списка на 2 (mid = len(nums) // 2), то мы получим индекс второго элемента (для четной длины). Но как получить индекс первого элемента? -mid будет на 1 больше, чем надо.
Например (в скобках пишу значения переменных):
nums = [1,2,3,4,5,6]
mid = 6 // 2 (в mid индекс 3)
nums[3] (вынимаем число 4) - ок, это правильно
nums[-3] (вынимаем число 4) - это неправильно, промахнулись на один элемент, нужен индекс -4.Что делать? Вспоминаем, что отрицательные числа хранятся в памяти в двоичном дополнительном коде. Как получается дополнительный код? Инверсией битов и прибавлением 1 (на этом уровне нет отрицательных чисел, просто старший бит установлен в 1).
Например число -3 в дополнительном коде (считаем для простоты слово размером в 4 бита, старший бит означает знак):
0011 - это 3
1100 - это ~3 (инверсия битов)
+
0001 - дополняем единицей
1101 - это -3 в дополнительном кодеЗамечаем, что инвертированная побитно 3 отличается от допополнительного кода (т.е. -3) на 1, а это то, что нам нужно: ~3 == -4
Всё! Поэтому вынимаем два средних элемента:
nums[mid], nums[~mid]
т.е. nums[3], nums[~3],что соответствует элементам: 4 и 3. Это то, что надо - побитовая инверсия дает отрицательное исходное число с коррекцией на 1.
Для нечетной длины списка это решение также работает без изменений.
Так что и для питона полезно знание архитектуры компьютеров, схемотехники и пр.
Но в продакшене так извращаться, конечно, не надо.
michael_v89
02.07.2023 07:12Не, про инверсию битов я знаю. Просто на моем компьютере тильда в этом коде отображается почти как минус, а вы написали про отрицательные числа, вот я искал их и нашел)
nivorbud
02.07.2023 07:12Это кстати еще один минус такого решения. Мало того, что оно выпендрёжное и неочевидное, так еще и, действительно, легко тильду с минусом спутать.
Дочь мне преподнесла это найденное решение как самое простое на ее взгляд :). Но это был хороший повод устроить разбор полетов с разъяснением, что там находится под капотом такого решения.
sophist
02.07.2023 07:12
То есть, получается, выпендрёжность здесь сводится к использованию
~nвместо-n-1nivorbud
02.07.2023 07:12То есть, получается, выпендрёжность здесь сводится к использованию
~nвместо-n-1Не только. Еще условие с двумя ветками убирается (для четной и нечетной длины списка). Но лучше конечно без выпендрежа условие поставить и обработать два случая. Понятность важнее краткости.
sophist
02.07.2023 07:12Согласен, с явными ветками лучше. (FizzBuzz, кстати, на мой взгляд, для этого и нужен: проверка на склонность к избыточной оптимизации).
Но всё-таки, без бинарных операций было бы, пожалуй, в рамках приемлемости.
michael_v89
02.07.2023 07:12+71. Если бы вы назвали статью "Простая проверка на компетентность студента-программиста", то критики было бы меньше.
Проверка на компетентность обычно упоминается в контексте приема на работу. В реальных собеседованиях проверяются немного другие навыки, и если человек не догадался во время собеседования, то это не значит, что он будет плохо решать рабочие задачи, как и наоборот. Как один из вопросов собеседования подойдет на позиции начинающих, но не в качестве определяющего критерия, как вы это хотите показать.2. Вы слишком многословно описали проблему, и это вызывает непонимание. Именно проблему, а не статью. Статья довольно короткая, и поэтому непонятно, почему вы говорите, что нужна еще одна статья.
Вместо постоянного упоминания "для второклассника" и "по таблице умножения" можно было сразу написать "целочисленное". После этого слова я понял, какое решение вы подразумеваете. Сформулировали задачу на умножение, сформулировали модификацию про деление, описали в паре предложений в чем особенность, дальше можно было разобрать, как их скомбинировать в одной программе (если я правильно вас понял).
nightlord189
02.07.2023 07:12-1На самом деле подход в лоб вида «сгенерили два числа, если результат их деления - целый, то выдали пример, если нет - повторили генерацию» тоже вполне себе работать будет, не сказал бы что это не решение.
Spaceoddity
02.07.2023 07:12нет. не будет работать. есть ненулевая вероятность того, что программа не сможет вам сгенерировать даже одну корректную пару чисел))
как бы понятно, что утрирование (шансы сгенерировать простое число = 1/ln(x)), но вот что-то мне подсказывает, что изначально закладывать такое фундаментальное ограничение (работоспособность программы зависит от генератора случайных чисел) не совсем правильный архитектурный подход...
upd: нет, можно надеть штаны и через голову и применить условное "обратное решето Эратосфена" к массиву натуральных чисел, затем дёрнуть случайный элемент массива, разложить его на множители и дёрнув случайный найденный множитель, наконец сгенерировать пару чисел, но как бы сами понимаете...))
nightlord189
02.07.2023 07:12Генерация работать будет быстро, так что за секунду можно нагенерить много вариантов. Подход может и не совсем правильный архитектурно, но если это учебная/тестовая задача - не вижу проблем.
Spaceoddity
02.07.2023 07:12+1Уже ошибка насчёт вывода о "быстроработающей генерации". У вас есть какие-то вводные о мощности аппаратных ресурсов, на которых будет запускаться эта программа (это может быть и условная "виртуальная реализация процессора на редстоуне в Minecraft")? Если таких вводных нет, логично ориентироваться на минимально необходимые аппаратные ресурсы, не?
Раз это учебная задача - так и надо сразу учить правильно. Чтобы потом не переучивать.
nightlord189
02.07.2023 07:12есть какие-то вводные о мощности аппаратных ресурсов, на которых будет запускаться эта программа
Если не указано иное - то обычный десктопный комп, который тянет браузер. А значит - потянет и эту задачу.
nronnie
02.07.2023 07:12Насколько я знаю, существующий алгоритм генерации ключей RSA (а точнее, генерации простых чисел большого размера, который в него входит) тоже вероятностный и есть хоть и малая, но все равно ненулевая вероятность, что он даст неправильный результат.
Spaceoddity
02.07.2023 07:12Ну зачем вы тёплое с мягким путаете?)) C RSA и прочими эллиптическими кривыми - это вынужденная и продуманная мера. А тут с ходу напрашивается элементарное и вполне очевидное решение, но мы вот ринемся в "hindy style", аргументируя это тем что в криптографии тоже мат.статистика используется))
Source
02.07.2023 07:12Если добавить к условиям требование, чтобы задания не повторялись в рамках одного прогона программы (что весьма логичное требование для программы, которая тестирует знание таблицы умножения), то вариант иметь заранее сгенерированную структуру данных становится очень даже уместен. Это может быть хеш-таблица, где ключ - произведение, а значение - массив из множителей. В языках с поддержкой метапрограммирования, такое можно на этапе компиляции нагенерить. В остальных - захардкодить.
Сравните:
вариант 1: выбираете одно рандомный ключ, показываете пример и затем убираете это этот ключ из хеш-таблицы (повторяете нужное кол-во раз)вариант 2: генерируете множители, и начинаете сохранять их произведения в массив и на каждой итерации проверяете, что псевдослучайное произведение не входит в массив, а если входит - перегенерируете пока не сгенерируете нужное.
Второй вариант явно сложнее.
Spaceoddity
02.07.2023 07:12Прекратите оправдывать сомнительные варианты решения задачи всякой отсебятиной))
Если добавить требование... С чего вдруг? У вас разве были вводные с таким требованием? Кто-то логичным посчитает наоборот - переспросить один и тот же вопрос, чтобы бы удостовериться, что пользователь честен на продолжении всего сеанса.
На самом деле, закинуть таблицу умножения в какую-либо структуру данных (массивы, объекты, хэш-таблицы) - это первое что пришло в голову. И первое же, что было откинуто. Поскольку входит в противоречие с "дальнейшей поддержкой и расширяемостью". Вот первое что вам приходит на ум, если вам предложить расширить функционал этой программы? Разумеется, снять ограничение для множителей < 10. И после этого вам придётся переделывать всю логику.
и на каждой итерации проверяете, что псевдослучайное произведение не входит в массив, а если входит - перегенерируете пока не сгенерируете нужное.
Не произведение, а пару множителей. Множители можно поменять местами - и это как раз актуальный вопрос на знание таблицы умножения (точнее переместительного закона умножения).
Source
02.07.2023 07:12Не нервничайте вы так. Тот вариант, который вы в статье описываете как правильный, мне первым пришёл в голову. Но он слишком наивный и не production-ready. Чтобы это понять, достаточно хотя бы минуту подумать над потенциальной бизнес-постановкой.
Просто вам, как учителю информатики, такое направление мыслей недоступно, т.к. вы не являетесь профессиональным программистом.
Разумеется, снять ограничение для множителей < 10. И после этого вам придётся переделывать всю логику.
Во-первых, это не разумеется, т.к. таблица умножения имеет строго фиксированный размер. А во-вторых, в самом снятии этого ограничения нет проблемы. Там появляются другие вопросы:
Будет ли вообще какое-то ограничение, или мы будем тестировать сверхлюдей, которые могут двадцатизначные числа в уме перемножать?
Числа должны быть произвольными или обязательно простыми и больше какого-то минимума? Уж если мы сверхлюдей собрались проверять, то задания должны быть сложными, так ведь?
Spaceoddity
02.07.2023 07:12а зачем вы это делаете? зачем вы пальцы на пустом месте гнёте?))
для начала - вы меня перепутали с автором статьи. я не учитель информатики, а как раз тот самый "практикующий программист"
затем, очень интересно, что вы подразумеваете под "production-ready"? чем больше непонятных терминов вплетем - тем весомее аргументация будет казаться?)) или что, в проде запрещена операция умножения?
а что значит "слишком наивный"? это что ещё за практики?))
т.е. в итоге вы прям настаиваете на создании "хэш-таблицы умножения", в некоторых случаях, видимо, с самым натуральным "hindy code" (if a = 2...)?
Source
02.07.2023 07:12Упс, действительно перепутал. У вас просто такой же агрессивный стиль комментариев.
очень интересно, что вы подразумеваете под "production-ready"?
В данном случае, я имею в виду насколько реализация справляется с тем, что нужно на практике. Хоть постановка задачи и конченая, но в ней всё же указано, что мы пишем программу, которая должна тестировать школьников на знание таблицы умножения. Т.е., условно говоря, выдавать 20 примеров и считать сколько из них решено правильно. Очевидно, что для целей такого тестирования необходимо избегать дублирующих примеров, чтобы охватить более существенную часть таблицы.
Решение описанное автором как правильное является наивным, потому что оно примерно в 25% случаев будет генерировать дубликаты примеров. В итоге у вас будет всего 15 из 20 уникальных вопросов. Что ни в какие ворота не годится для объективной проверки знаний.
а что значит "слишком наивный"? это что ещё за практики?))
Странно, что вы как практикующий программист не слышали этот термин. Загуглите "naive algorithm". Оно означает наиболее очевидный способ сделать что-либо, который не учитывает подводных камней.
в некоторых случаях, видимо, с самым натуральным "hindy code" (if a = 2...)?
Это про что вообще? Единственный if, который на всю эту программу нужен - это сравнение введенного ответа с правильным результатом.
Spaceoddity
02.07.2023 07:12Очевидно, что для целей такого тестирования необходимо избегать дублирующих примеров, чтобы охватить более существенную часть таблицы.
Вот вообще не очевидно)) Вот именно с позиции практикующего программиста, это вредная методология - додумывать ТЗ. Бывают действительно совершенно однозначные ситуации, которые ты продумываешь наперёд, а заказчик тебе "нет, не надо! делайте как сказано в ТЗ".
Вот вы уже вангуете насчёт целей тестирования... Таблица умножения, а проверяют почему-то скилл деления)) А может быть это тестирование на "умение строго следовать ТЗ"?))
Решение описанное автором как правильное является наивным, потому что оно примерно в 25% случаев будет генерировать дубликаты примеров.
Ну во-первых, и что с того что оно будет генерировать дубликаты? Мы это уже обсудили выше, но ещё вернёмся.
Во-вторых, решение автора отнюдь не наивное. Понимание того, что здесь уместнее использовать операцию умножения, а не деления - не самое очевидное. А самое главное, именно такой "логический движок" будет самым поддерживаемым - он легко модифицируется и под отсутствие дублей, и под снятие любых ограничений на значения данных. Потому что в основе логики лежит мат.аппарат, а не манипуляции с данными, которые ещё надо сгенерировать.
Source
02.07.2023 07:12Вот вы уже вангуете насчёт целей тестирования...
Я не вангую. Я просто внимательно прочитал постановку. Цитата: "Нужно написать программу, которая будет проверять знание таблицы умножения второклассником".
Кстати, исходя из этого, ваше предложение про числа >= 10 как раз противоречит постановке.Бывают действительно совершенно однозначные ситуации, которые ты продумываешь наперёд, а заказчик тебе "нет, не надо! делайте как сказано в ТЗ".
Ну, с заказчиком это всё надо обсуждать конечно. Эта стадия разработки называется бизнес-анализ.
Ну во-первых, и что с того что оно будет генерировать дубликаты?
Вы проверите за N итераций меньше примеров. А значит точность итоговой оценки знаний будет ниже. Можно, конечно, заставить бедных второклассников отрешать больше итераций, но это как-то негуманно. Зачем детям лишний стресс создавать из-за того, что кто-то поленился на программном уровне убрать дубли?
Во-вторых, решение автора отнюдь не наивное. Понимание того, что здесь уместнее использовать операцию умножения, а не деления - не самое очевидное.
Ну хз, всё конечно субъективно. На мой взгляд, это первое что приходит в голову и это супер очевидное решение. Плюс, как уже в комментариях писали, помимо дублей, это решение имеет ещё и проблемы с равномерностью распределения. Т.е. да, решение условно рабочее (т.к. формально удовлетворяет ТЗ), но оно халтурное с точки зрения профессиональной разработки.
Хотя допускаю, что для школьников это всё не столь очевидно. Но на то они и школьники, а не программисты.
warlock66613
02.07.2023 07:12Это называется "преждевременная пессимизация" и является существенным минусом.
brakerkir
02.07.2023 07:12+6Тест скорее не на компетентность программиста, а на то, своим ли делом он занимается. Если, конечно, говорить о настоящем программисте, как заявлено в заголовке, а не о школьниках 8 класса, как оказалось в комментариях.
А еще статья и особенно комментарии оказались хорошим тестом на умение излагать свои мысли людям. Кажется, что человек, преподающий детям, уже по профессии должен быть значительно более терпим и сдержан при обсуждении альтернативных точек зрения.
sophist
02.07.2023 07:12+4На самом деле, сама идея правильная. Напомнило "Притчу" Дейкстры. Но, конечно, в такой подаче это не уровень Хабра. (Я, признаться, в начале статьи подумал, что очевидное решение – это как раз взять произведение и один из множителей, а подвох кроется где-то в неравномерности распределения произведений).
yea
02.07.2023 07:12А мне вот не понравилось, что если брать случайные X и Y и перемножать для генерации делимого, то распределение полученных таким образом делимых на множестве составных чисел, по идее, не будет равномерным :) Вы этого не учли и, кажется, даже не заметили. Формально-то задача всё ещё решена, потому что к распределениям никаких требований нет, но получается не очень красиво.
sophist
02.07.2023 07:12Я тоже про это подумал, но ведь если произведение можно получить несколькими способами, то отработать надо их все. (То есть нас должно интересовать распределение не произведения, а пары множителей).
yea
02.07.2023 07:12С точки зрения здравого смысла и пользы для сугубо гипотетического юзера "обучающей программы" — соглашусь, конечно так.
С точки зрения программиста-буквоеда на интервью — вопросы неизбежны :)
Andruh
02.07.2023 07:12+1Равномерное распределение по всем примерам таблицы умножения, тут незачем усложнять.
lair
02.07.2023 07:12+2Если бы это была простая проверка на компетентность, она бы позволяла показать, что программист... компетентен. Однако совершенно не обязательно, что программист, решивший вашу задачу, компетентен.
Так что ваша задача отсекает некое множество людей, которые не могут решить такую задачу (наверное, они и правда не очень хорошие программисты, но это не обязательно, кстати), но не более того.
remendado
02.07.2023 07:12+1Давняя программистская байка
- Вася, нужно поместить в холодильник жирафа. Твои действия?
- Подойти к холодильнику, открыть дверь, засунуть жирафа, закрыть дверь.
- Молодец, Вася. А теперь нужно поместить в холодильник бегемота. Твои действия?
- Подойти к холодильнику, открыть дверь, засунуть бегемота, закрыть дверь.
- Садись, Вася, двойка. Ты должен был сначала вытащить жирафа.
Thetafelius
02.07.2023 07:12В условиях задачи не указано что холодильник недостаточно вместительный чтобы вместить оба экземпляра животных.)) На крайняк можно расчленить для более плотной упаковки.
Andruh
02.07.2023 07:12+7Обожаю такие задачки имени боли. Задачки психологической травмы, задаваемые собеседователем на собеседовании. Про неё он знает каждый уголок, все твои движения мысли, он демиург и хозяин в такие моменты. Все твои потуги кажутся никчёмными, а любое движение взгляда уже класифицировано и диагностировано. Этой задаче отведено огромное пространство в мозге собеседователя. Конечно же, она того стоит. Потому что это одновременно и дань уважения и психологическая защита. Просто потому что когда-то сам собеседователь не решил её оперативно и правильно.
Andruh
02.07.2023 07:12Если человек отталкивается от требований, он может не понять и начать искать сложных решений.
Если от простоты и красоты, а также понимает, что ружьё на стену должно было быть повешено не зря, ещё на первом слове про деление предполагают тот самый ответ.
Тут скорее даже опыт решения, в том числе искусственных задач из учебников, где часто всё сворачивается и даёт простой изящный ответ. В жизни такое бывает тоже, но не у всех и не всегда. И далеко не каждое расширение/изменение требований так красиво вписывается в код.
Helldar
02.07.2023 07:12+1На техническом собесе такая задача не даст понять о человеке как специалисте абсолютно ничего. Кроме того, подобные калькуляторы нас в универе на паре по информатике учили писать и то лишь с целью понимания как происходит взаимодействие между числами. И выстраивали не только простейшие решения, а ещё и от пользователя просили нажать кнопку что он хочет сделать - сложить, вычесть, умножить или удалить, и, в соответствии с выбранными действиями, выполнить их. Самый обычный калькулятор ¯\_(ツ)_/¯
funca
02.07.2023 07:12-1Есть такой тип учителей, что-то типа снаряда в спортзале. Ну скажем, турника. Его вопросы не оставляют ни кого равнодушными и ученики готовы перерыть полбиблиотеки в поисках аргументов, чтобы показать своё превосходство. Он справляется со своей работой когда ученик выходит с ощущением, что смог превзойти своего учителя, доказав неправоту и разгромив того в пух и прах. Количество минусов с одной стороны, и комментариев к статье с другой, думаю, хороший тому пример).
jishi
Это чтоб отсеивать тех, кто даже трёхмесячные курсы программирования не осилил?
rukhi7 Автор
и для тех кто имеет диплом.
А как конкретно вы проверяете осилил ли человек трехмесячные курсы, поделитесь?
novoselov
А у вас диплом или курсы?
rukhi7 Автор
А у вас?
Вы решили что только вы можете хамить отвечая вопросом на вопрос?
Animegravitation
после прочтения комментарииев хочу заметить
Вы вообще очень страннор и резко реагируете на критику считая исключительно свою точку зрения верной на 100% ))) при этом почему то дискутирующих с вами считаете глупее вас
Хотя я много читаю текстов, ваша статья увы по больше части невнятна и написана трудночитаемым текстом, начиная о постановки второй части задачи и до самого описания решения данной задачи
Боюсь даже представить чему и как и каким образом вы учите 8класников )))
И да к критикующим обоснованно вас людям надо быть терпимее , может тогда вас и не будут под КАЖДЫМ комментарием минусить
sergeaunt
По моим наблюдениям, это вообще типично для хабраюзеров с отрицательной кармой. А именно: неумение/нежелание прислушиваться к конструктивной критике, отсюда - человек не учится и при этом считает несогласных с ним идиотами, а карму - тоталитарным средством угнетения непризнанных гениев со стороны тупого большинства.
cat_chi
Впрочем, ничего нового. Очередной несчастный хабраюзер, заминусованный токсичным сообществом за мнение, отличное от мнения толпы.
/s
nronnie
Просто подобных пассажиров с достаточной кармой вы не слышите — они в таком случае молча поставят минус в карму вам, да еще и с меткой "Личная неприязнь" :)
nronnie
То, что мне сразу же в карму прилетело это хорошо подтверждает. Да и похер — чем бы дети не тешились… :))
sergeaunt
Вот всегда удивляло, откуда люди знают, за что им прилетело в карму. Мне вот Хабр не показывает, минуснули меня за последний коммент или за статью, написанную 2 года назад.
aegoroff
Значит не показалось - в предыдущей статье автора про COM (https://habr.com/ru/articles/738350/) я поучаствовал в дискуссии и тоже позиция автора показалась в стиле - вы все дураки и не лечитесь, один я умный, стою в белом пальто красивый :)
Animegravitation
Новодворская ксати во много оказалась права с учетом реалий 2023 года )))
Так что иногда люди в белом пальто делают верные прогнозы )))