Я тоже однажды столкнулся с таким. Попросили написать код на листке бумаги. Набросал примерное решение опустив проверки крайних ситуаций для краткости. На что начались придирки что мол тут вы на null не проверили, тут блок finally не написали, и т.п.
Вот это уже полный идиотизм, я все это опустил думая что проверяют в принципе понимание ситуации.
Задача простая, но немного нестандартная. Видимо предполагается что собеседуемый вряд-ли сталкивался именно с ней, но если хорошо разбирается в алгоритмах — быстро придумает решение. Мне, например, рекурсивное решение пришло в голову в течении минуты. Но если никогда не писал обработку деревьев — быстро придумать может не получиться.
Возможная цель такой проверки — была ли у человека практика в написании алгоритмов, или только теорию читал.
И разве это стрессовая ситуация? Вот когда после 4 часов собеседования из 4х частей с разными собеседующими просят написать на бумажке решение чего — то подобного, и еще 3 человек сидят над душой…
Очень интересно!
Но вот у меня такая мысль, а нельзя на таком же принципе сделать аналог фильтра Блума с еще меньшими потребностями памяти?
Простейшая идея: если добавление очередного элемента достаточно (на 1?) увеличивает этот счетчик — значит такого элемента, скорее всего, еще не было. Если увеличивает недостаточно — то, скорее всего, уже встечался. Правда ошибка будет очень большой боюсь…
Рано или поздно, с развитием ИИ технологий, большинство профессий исчезнут. Вопрос будет ли профессия программиста в числе первых?
Сомнительно, если программы будут занимать все больше областей деятельности человека, то потребуется все больше программ. Хотя конечно профессия сильно трансформируется, придется решать более сложные задачи и в других областях. Простые задачи, вроде тех что уже сейчас почти решаются разными конструкторами, перестанут быть основной нишей.
Фреймворки появляются и исчезают, а основы(математика, алгоритмы ..) остаются.
Я не отрицаю ТОУ. Просто утверждения вроде «начать можно хотя бы с вариационного исчисления — его проще освоить» подразумевает что собеседник не знает вариационного исчисления, а если бы знал — легко применил. А я утверждаю что применить все это тут с пользой — очень сложно, я пытался — не получилось.
Возможно, мои познания мат. анализа не достаточны, все же около 7 лет назад изучал. Попробуйте сами поучаствовать, если удастся добиться хорошего результата с применением ТОУ — с удовольствием послушаю как Вам это удалось.
Наверно не зря это теория «оптимального» управления. Если вы решаете задачу управления роботом на конвейере на заводе — это одно. Ваши вычислительные ресурсы и время жестко не ограничены, можно попытаться найти оптимальное решение. Тут же за отведенные временные рамки (ограничение процессорного времени) найти оптимальное решение не представляется возможным. Нужно найти хотя бы просто хорошее решение. Преобразование Фурье и подобные вещи не такие уж легкие в этом плане.
По поводу того чтобы искать аналитическое решение от столкновения к столкновению: столкновения очень важная часть оценочной функции, на основании которой выбирается траектория. Если рассматривать участок траектории только между столкновениями — то практически не остается критериев по которым выбирать.
Основная проблема применимости этой математики в подобном соревновании — то что критерии оптимальности не известны. Единственный точно известный критерий — надо набрать больше всего очков в гонке. Какой функционал должен принимать максимальное значение не известно. И какой смысл искать абсолютный максимум некоторого выдуманного функционала — если вы даже не уверены он ли вам нужен?
Подход с перебором траекторий в этом плане очень удобен, можно менять критерии выбора очень легко, ничего не переделывая.
Например, в танках я нашёл аналитическое решение уравнения движения танка. Пытался применить его для нахождения кратчайшего пути к бонусу, но учесть размеры и формы танка и бонуса (подобрать можно чиркнув углом) в уравнении движения практически невозможно. Я уже не говорю про столкновения. И даже если получится, уравнения будут столь сложными, что их численное решение будет намного медленнее симуляции с обработкой столкновений. А ещё точность будет хуже, так как «движок» дискретный.
При свободно движущихся объектах, вроде ракеты и самолета, найти аналитическое решение ещё возможно. Но в данном соревновании действия происходят в узких коридорах. Столкновения с ограждениями, столкновения с шинами, столкновения машин между собой. Каким образом Вы будете писать для них уравнения движениями, тем более, решать их численно быстрее чем простой симуляцией?
Я не вижу способа применить аналитическое решение даже небольшого участка траектории. Как я уже писал, я пытался, в первом соревновании (танках). Я по образованию физик, и это было даже естественнее для меня. Но потом все пришлось выкинуть и переписать на симуляцию.
Не будьте голословны, приведите пример того, как это можно применить.
У меня за последний год была возможность попрактиковаться в выжимании из кода предельной производительности, тут это оказалось не лишним. Хотя «красота» кода из-за этого сильно пострадала, много дублирования кода. Писать быстрый и красивый код одновременно — это, видимо, навык следующего уровня…
Игровой «движок» дискретный, простая симуляция обычно работает гораздо быстрее чем аналитическое решение. Я пытался что-то подобное применить в первом соревновании (танках)- ничего хорошего не получилось.
И на трассе есть противники, которые активно противодействуют — это не очень вписывается в теорию оптимального управления.
Для себя не хотел снижать точность, чтобы машинка максимально долго не сходила с траектории. Для противников, наверно, имело смысл. Но пришлось бы корректировать симулятор чтобы он оба варианта поддерживал, времени на все не хватало.
Вот это уже полный идиотизм, я все это опустил думая что проверяют в принципе понимание ситуации.
Возможная цель такой проверки — была ли у человека практика в написании алгоритмов, или только теорию читал.
И разве это стрессовая ситуация? Вот когда после 4 часов собеседования из 4х частей с разными собеседующими просят написать на бумажке решение чего — то подобного, и еще 3 человек сидят над душой…
Но вот у меня такая мысль, а нельзя на таком же принципе сделать аналог фильтра Блума с еще меньшими потребностями памяти?
Простейшая идея: если добавление очередного элемента достаточно (на 1?) увеличивает этот счетчик — значит такого элемента, скорее всего, еще не было. Если увеличивает недостаточно — то, скорее всего, уже встечался. Правда ошибка будет очень большой боюсь…
Может кто-нибудь уже встречал похожий алгоритм?
А еще дума законы все время меняет…
Сомнительно, если программы будут занимать все больше областей деятельности человека, то потребуется все больше программ. Хотя конечно профессия сильно трансформируется, придется решать более сложные задачи и в других областях. Простые задачи, вроде тех что уже сейчас почти решаются разными конструкторами, перестанут быть основной нишей.
Фреймворки появляются и исчезают, а основы(математика, алгоритмы ..) остаются.
Возможно, мои познания мат. анализа не достаточны, все же около 7 лет назад изучал. Попробуйте сами поучаствовать, если удастся добиться хорошего результата с применением ТОУ — с удовольствием послушаю как Вам это удалось.
По поводу того чтобы искать аналитическое решение от столкновения к столкновению: столкновения очень важная часть оценочной функции, на основании которой выбирается траектория. Если рассматривать участок траектории только между столкновениями — то практически не остается критериев по которым выбирать.
Основная проблема применимости этой математики в подобном соревновании — то что критерии оптимальности не известны. Единственный точно известный критерий — надо набрать больше всего очков в гонке. Какой функционал должен принимать максимальное значение не известно. И какой смысл искать абсолютный максимум некоторого выдуманного функционала — если вы даже не уверены он ли вам нужен?
Подход с перебором траекторий в этом плане очень удобен, можно менять критерии выбора очень легко, ничего не переделывая.
Я не вижу способа применить аналитическое решение даже небольшого участка траектории. Как я уже писал, я пытался, в первом соревновании (танках). Я по образованию физик, и это было даже естественнее для меня. Но потом все пришлось выкинуть и переписать на симуляцию.
Не будьте голословны, приведите пример того, как это можно применить.
И на трассе есть противники, которые активно противодействуют — это не очень вписывается в теорию оптимального управления.
youtu.be/dJ37tF_QwYY