Как стать автором
Обновить

Комментарии 260

Ряд пользователей отсеется само, т.к. не навидит выполнять тестовые задания, при том это ни разу не говорит о профессионализме, т.е. отсеятся и профессионалы у которых ведь чётко в резюме указано что они умеют со ссылками на git (Очень часто встречал отказывающихся делать задание, причин море)

Второй эшелон отсеяных — искушенные программисты, которые прочитают и поймут что задание составлено не полно, не явно, не косвенно не решаемо(как обычно и бывает с ТЗ(тех.заданиями)).

Третий эшелон — кто тупо не справился.

Прошедшие задание… снова начнут отсеиваться. Там синтаксис корявый, там задача корявая…

Вывод (ИМХО):
* Не давать задание до встречи, после которой тоже не стоит давать, иногда :)
* Варьировать задания от личности к личности, это если вы градируете соискателей
* Брать иногда без всяких заданий…

PS
Для любителей головоломок, вот такое очень крутое задание в виде квеста от ребят, даже если не ищешь работу интересно.
zoon.ru/job.php
у них опечатка в \u0437\u0430\u0439\u043c\u0451\u0442 и \u043f\u0440\u0438\u0447\u0451\u043c
ах да… задание не по русскому языку :)
Zanuda->Init();
Это понятно. Просто меня, скажем, покоробило.
Автор поста рассуждает же, к примеру, о качестве кода, я сам когда людей собеседую — смотрю как они форматируют отступы и прочее.
Почему с позиции соискателя и исполнителя я должен игнорировать постановку задачи?
Принципиально нету разницы между ТЗ с опечатками (которые, кстати, иногда могут вылиться в несколько дней лишней работы, перепутал «и» с «или»), и ТЗ вроде «Ну типа тут короче надо такую плюху, ты не ниё щелк и она такая пиупиу пошла выгрузке».
Zanuda->__destruct();
«займёт» «причём», а что с этим не так?
clip2net.com/s/5smhzN
или я что-то не понимаю?

(хотя если буква «и» была в json'е прямо русской буквой и, то это конечно кривость)
Ребята, я же просил не обсуждать целесообразность тестовых заданий…
извините, запретный плод сладок :)
ну и это к теме «Что можно узнать о кандидате по тестовому заданию»
ничего полезного из одного тестового задания не узнаешь!
Печально, что вы сделали такой вывод.
Да нет печалиться не стоит «so many men so many minds»
Для любителей головоломок, вот такое очень крутое задание в виде квеста от ребят, даже если не ищешь работу интересно.
zoon.ru/job.php

Крутое задание, спасибо!
Этот квест является отличным завершением трудовой пятницы.
Я не пхпист, а front-end, поэтому начал решать на Javascript, но столкнулся с проблемой:
после первого таска стек оказывается пустой и output = «00420042220462042220402282004604242042042004220422000220464221220482024204204620042048420220026400648222020242000020842042262000202620220820202222020420242422402842024260222062400242002202202662820682410202240201042002044200282020642002022040282002220220802200024620220220602020022400242802240022420402820220022022420042402402062202620288402002 „

У меня вопрос к знатокам: chr($p + 1) в PHP и String.fromCharCode(p + 1) в Javascript отличаются?
Может там подсказка какая-то должна быть вместо толпы цифр?

Алгоритмы проверил, вроде всё ок.
по поводу JS не скажу, но у меня в реализации (delphi XE2) chr работает с ASCII кодировкой, то есть код символа 60(dec) интерпретируется как "<".
PS: у меня всё заработало ^_^
PPS: осмысленный результат выходит только после прогона всех тасков
Если $p+1 не превосходит 127, то разницы не должно быть. С большими значениями уже хуже: в JS везде и всюду юникод, а в php… он отдельно поставляется.

Впрочем, я давно не сталкивался с php, возможно, это уже и не так.
Спасиба за ссыль, прикольный квест.
Вообще, можно было бы на каждом шаге записывать в текущую клетку значение левого, верхнего, или нижнего соседа, если оно отличается от значения текущей клетки. В этом случае, выпадал бы момент перерисовывания клетки в её текущий цвет.
Достаточно левого соседа, если генерировать волну сразу полностью в невидимом «за левым краем»
тогда будет по сути две области, и вся оптимизация к чертям
Я не пишу на AS, но мне кажется у вашего алгоритма есть недостаток — если следующую волну начать с той же точки при следующем тике, она полностью поглотит предыдущую. Хотя в идеале та должна вырываться на один пиксел вперед.

Также, меня смущает «сложность» алгоритма обхода — это ж O(n*m). Если взять за основу нечто типа Breadth-first search было бы, на мой взгляд быстрее и лучше. И заодно появились бы ништяки вроде обхода препятствий.
покажите вашу программу!))
окей, через часок-другой закончу с задачами — сделаю :)
Набросал пример алгоритма на JS, смотреть можно тут
Исходники удобно глянуть на gist

PS. Используйте Chrome, FF или иной браузер умеющий HTML5 с Canvas.
НЛО прилетело и опубликовало эту надпись здесь
С оперой нашел проблему, с зумленной страницей артефакты не удалось воспроизвести. Это под каким браузером так отрисовка страдает?

Начинали с алгоритма волны, закончили особенностями браузеров :)
НЛО прилетело и опубликовало эту надпись здесь
FF 22.0.
Ноль реакции.
Если человек не проходил тест, Вы ему сообщали об этом?
Конечно.
Если он сам не отваливался по пути.
Хорошо, что вы в таких вещах ко всем по-человечески относитесь.

Не так давно я искал работу и проходил тестирование в нескольких организациях.
Самая первая заинтересовавшаяся мною организация отправила мне тестовое задание, которое я выполнил в срок. Ждал ответа 2 недели, отправлял решение повторно несколько раз.
Ответа не было никакого.

Пока я ждал ответа, мне прислали еще одно задание, которое я тоже успешно выполнил, и меня пригласили на собеседование.
На собеседовании мне задавали много вопросов и разных задач, код которых приходилось писать на листе А4.
Руководитель IT, который проводил собеседование, проверял мой код. Почти во всем он был со мной согласен. Обещали позвонить через неделю… В итоге так и не позвонили.

Из-за того, что не было никаких ответов, даже отрицательных (которые я в основном и ожидал услышать), только лишь отбивало желание решать тестовые задания других организаций.
Может быть, это одна из причин, почему соискатель не хочет решать какие-то тесты.

Такое поведение не с тестами связано, а с внутренними правилами HR-отдела компании, которая проводит собеседование. У меня бывало по-всякому, но после тестовых заданий всегда на работу брали =))) Если бы не выполнила, не знаю, как в таких случаях реагировать принято.
Согласен с вами, тесты роль не играют в том, что компания не уважительно относится к соискателю. Но это неуважение подогревает негативное отношение к решению тестов в других компаниях. Так как человек напрягался, тратил время. А ему даже «Извините вы нам не подходите» не прислали по email. По-моему это не уважительно.
По-моему это в любом случае неуважительно, в независимости тесты ли были или только вопросы.
Я бы не принимал такие вещи близко к сердцу на вашем месте и на трактовал это как неуважение. Если у вас при поиске работы 3-4 работодателя, с которыми вы общаетесь, то у работодателя одновременных кандидатов — десятки (иногда — сотни). Он физически не может сказать ни «да», ни «нет» каждому из них в отдельности, пока не отсмотрит всех. Поэтому работодатель (если только он серьезно ищет хорошего сотрудника или же если он не наткнулся случайно на «звезду», которую сразу же заметно) естественным образом тянет время, т.е. молчит. А потом проходит несколько недель, и вот уже неудобно просто писать всем кандидатам, которые «не подошли» (плюс работает еще такой фактор, что если написать кандидату «извините, не договоримся», то некоторые в этом случае начинают забрасывать письмами, выпытывать детали, а иногда и грубить).

Я ни в коей мере не хочу оправдать работодателей, которые «пропадают» (профессиональные рекрутеры, конечно же, структурируют и автоматизируют процессы так, чтобы такого не происходило). Я лишь привожу нечто вроде психоанализа, взгляд с другой стороны, так сказать, чтобы никому не было обидно.
Моя точка зрения такова:
Люди занимающиеся подбором персонала, как не трудно догадаться, работают с людьми. Люди все разные и работа с ними тяжелая. Каждый все понимает по своему и с некоторыми очень трудно найти общий язык.
На счет того, что если кандидат в случае отказа начинает задавать вопросы, грубить и прочее, HR-менеджер должен уметь предотвращать конфликтные ситуации, выходить из них и находить нужные слова чтобы объяснить человеку что он не подходит.
Если даже ответа от потенциального работодателя нет, те люди которых это сильно задело и они хотят нагрубить, они позвонят в компанию сами и сделают это. Более того эти люди могут создать трудности компании в дальнейшем. (может быть перегибаю)
За свою работу рекрутеры как профессиональные так и не профессиональные получают деньги, и свою работу они должны выполнять качественно, чтоб такого не происходило.

На некоторых собеседованиях я слышал такие фразы «Если не позвоним через n-дней, вы нам не подходите», где-то говорили в прямую что у нас еще столько-то кандидатов. В таких ситуациях не возникает ни каких обид от того что не поступило никакого ответа, так как ответ был дан сразу.

Для профессиональных рекрутеров — да, справедливо. Но вот только профессиональные рекрутеры далеко не у всех компаний есть (и часто это оправдано: хорошие рекрутеры — большая редкость), а поиском кандидатов занимаются сами основатели или же руководители отделов/групп. Говорить «если не позвонимичерез N дней, вы нам не подходите» — это означает уже дать понять, что собеседование прошло плоховато (когда собеседование прошло отлично, то часто человека прямо сразу же на нем и хватают, либо в течение одного-двух дней, т.к. боятся, что он уйдет с рынка).
Я на своём месте близко к сердцу такое не принимаю. Тем не менее я считаю, что пособеседовать человека, чтобы впоследствии пропасть — это неправильно.

Несколько недель — это не отговорка. То есть, с одной стороны, кандидат, скорее всего работу уже нашёл, но с другой — приятно же, что человека не за пустое место принимают.
Пара слов о задании. Мне было все равно на чём человек его реализует, но сразу же обговаривались два условия:
я смогу его запустить,

Несколько раз у меня возникли трудности с запуском приложения:

Использовались какие-то библиотеки, которые не понятно где быстро взять.
Нужно было ставить IDE, SDK и всё на свете, чтобы лишь скомпилировать апп.
У меня были явно не все файлы проекта, а с незнакомым языком возиться его настраивать было не много желания.


Какие условия ставите, такое решение и получаете. Напоминает цитату с башорга:

<ssd.meister> Когда я сказал студентам принести лабу по алгоритмизации на любом языке программирования, я не подозревал, что на потоке найдётся мудак, который напишет её на… BRAINFUCK'е!


Вы ожидали, что кандидат пришлёт Вам вместе с исходниками ещё и IDE с SDK? И ещё документацию по языку? И кучу ссылок на библиотеки, которые, к примеру, являются стандартом для этого языка?

Мне кажется, в данном пункте Вы не совсем правы.
Но всё-ж таки, это простое правило хорошего тона и вежливости к проверяющему написать к программе простой readme, о том как её скомпилировать и запустить с ссылками на IDE, библиотеки и т.п. Ведь с самого начала было ясно, что проверяющий скорее всего не умеет работать с языком N и фреймворком M.
Тогда стоило указать, с какими языками проверяющий знаком. Я считаю, что это увеличило бы шансы, что к коду на неизвестном языке добавят readme.
К сожалению, многие уверены, что язык программирования, который они знают, самый распространенный, и его просто нельзя не знать.
Так и думал, что этот пункт нужно переписать. И со мной согласны уже 18 человек.
Да, этот момент неоднозначен, но выводы из него я получаю именно такие.

Что хотел сделать человек, написавший лабу на brainfuck? He wanted to fuck the teacher's brain, obviously. Намерянно. Стоит ли так себя вести при сдаче тестового задания? Не думаю.
> Что хотел сделать человек, написавший лабу на brainfuck?

Показать, что может?
Просто у него есть чувство юмора, вот и все. И он тролль. И то, и другое похвально (в разумных рамках).
Почему Вы решили, что brainfuck студент использовал с целью постебаться над преподом. А если нет? Если он им активно увлекается (а это, как известно, хорошая разминка для мозгов) и поэтому его выбрал? За это его надо отчислить? )

Лично я тоже в универе, если был выбор, писал лабы на C++ вместо Delphi, который требовали в большинстве случаев. Хотя преподаватели на плюсах ничего и не понимали, я получал профит в плане развития и уважение с их стороны.

Выводы, конечно, у всех разные. Мой вывод от общения с Вами (исходя из данной статьи) был бы а-ля «э, да такой всю душу вынет из сотрудника, пойду-ка ещё поищу»…

Ваш подход так же наводит на некоторые выводы. Нечёткая постановка ТЗ + последующая критика по мелочам. Вопрос — а кто-нибудь Вам понравился в итоге? И сколько человек после успешно выполненного задания сами отказались у Вас работать?
Почему Вы решили, что brainfuck студент использовал с целью постебаться над преподом. А если нет? Если он им активно увлекается (а это, как известно, хорошая разминка для мозгов) и поэтому его выбрал?

Вы сами-то в это верите?
Я помню себя в школе/универе — мне только дай какой-нибудь косяк в формулировке задания, я сразу этим воспользуюсь.

Я уже привёл контрпример — я использовал кучу всего нового, писал свои визуализаторы на Qt (когда нам про него даже не рассказывали, а когда я рассказывал — не верили), делал пасхалки в лабах, использовал системные хаки, о которых преподы и не подозревали, и тп. И всё — для саморазвития.

И если бы я в те времена знал о brainfuck, то вполне мог бы на нём лабу попробовать написать. Тем более, если в ней простой алгоритм.
Ну, зная наших преподов по программированию, мне страшно смотреть на получающихся оттуда программистов.

Отлично, если вы развивались, пытались делать что-то новое. Для этого и существует университет и те 4 (6) лет, которые вы там проводите. Сделать лабу на C++ вместо Паскаля — это хорошо, тут всем понятно зачем.

Вообще, в университете оценивается почти всегда бинарно: сделал или не сделал. Сделал 5 заданий — на тебе 5, сделал 2 — вали на пересдачу. За редким исключением кто-то полезет в твой код / в твое решение изучать где же ты там ошибся все-таки. Нет цели узнать студента получше, чтобы взять его на работу.

У меня такая цель есть. Это совсем разные примеры.
Ну, в код залезали очень даже часто. И объясняли, что где не так.

Бинарно оценивают, это бывает, но не всегда. В моём опыте была лаба, выдававшая неправильный ответ, но за оригинальность решения (а как исправить баг можно я на защите объяснил на словах) я получил отл. Всякие преподы бывают ;)

И цели у преподов были — предлагали остаться на кафедре и тп.
Мой вывод от общения с Вами (исходя из данной статьи) был бы а-ля «э, да такой всю душу вынет из сотрудника, пойду-ка ещё поищу»…

При собеседовании на работу я бы вам всю статью показывать не стал (8 Но вы правы, пристальное изучение идет как со стороны работодателя, так и кандидата.
Да, кандидат на работодателя зачастую смотрит даже пристальней, чем тот на него. )
Ваш подход так же наводит на некоторые выводы. Нечёткая постановка ТЗ + последующая критика по мелочам.

Вы как-то толи читали не внимательно, толи надумали себе каких-то странных выводов.

Где вы видели 100% чёткую постановку ТЗ? Всегда есть нюансы, о которых человек либо не знает, либо забывает, либо считает несущественными. Для этого и придумали вербальное общение тысячелетия назад.

Критика по мелочам — это выводы для меня, я никогда не подходил к кандидату и не говорил, мол, слышь чо, вон у тебя там инкапсуляция нарушена — ты лох!
Где вы видели 100% чёткую постановку ТЗ?

Да, такого не бывает. Но для тестового задания понятность ТЗ должна стремиться к 100%, иначе уже будут субъективные оценки типа «я имел в виду это, а он сделал то, вот глупый». А вербальное общение это, конечно, хорошо, но не в данной ситуации. Если человек активно ищет работу да при этом работает на полную ставку, то ему не до общения, такова реальность. Тестовые задания делаются зачастую поздно вечером, когда уже просто неприлично звонить работодателю с дурацкими вопросами.
есть два вида преподавателей. Одни радуются, когда студент чем-то увлекается помимо того, что они дают, другие ненавидят студентов, которые считают себя умнее их. Очевидно вторым лучше потакать, если не хочешь схлопотать неуд за то, что выполнил задание лучше чем другие
Ну, это тоже верно. )
Все люди разные.
А как насчет Lisp`а?
У меня в универе был случай, когда препод заявил, что понимает любой язык. В итоге принесли программу на Lisp`е и продемонстрировали ее работу. Но в коде преподаватель так и не разобрался. Потому как там были явные ошибки и подведение под правильный результат.
Очень странно заявлять такое:
Мне было все равно на чём человек его реализует...

И при этом ставить условие о понятности кода Вами:
я смогу понять код


Кандидат вообще не знает Ваших знаний.
Я обладаю достаточным кругозором, чтобы понять синтаксис любого современного языка. Другое дело, что на любом языке можно написать программу так, что черт без поллитры не разберется. Приведенные вами утверждения не противоречат друг другу.
В таком случае, надо было писать это в задании — на современном, широко используемом языке программирования. А так получается, что я могу вообще на своем языке написать.
Можете. Но, готовьтесь доказывать, почему этот язык был лучшим выбором для данной задачи.
Или вы хотите создать свою группу тех, кто для решения тестового задания написал собственный язык?
Всех то вам надо классифицировать и повесить ярлык :)
Я просто описал наблюдения в нечеткости формулировки задачи. О лучшем выборе языка речи не шло даже в задание.
Нет там никакой неточности в формулировки. Формулировка ровно такая, чтобы проверять кандидата еще и на элементарную адекватность.
Мне кажется, не ознакомившись, хотя бы с основами языка, разобраться не получится. Например, у руби довольно классный синтаксис, но одним кругозором его не понять.

def current_user
  store_location
  false
end

store_location — переменная или результат вызова store_location().
Последняя строчка функции, это значение, которое она вернет.
Спасибо, я знаю Ruby (8
«Теперь знаете», или знали раньше? :)
Простите, не уверен какой вы вложили смысл.
Ваше решение неверно. Нет возможности управлять скоростью, хотя это одно из немногих требований, которые таки были указаны в задании.
Как нет? А кнопка «Turbo» на системнике?
Кстати, в условии задачи не однозначно сказано, скорость волн общая или у каждой волны своя.
У вас есть возможность спросить.

Вывод: при неоднозначностях решения, человек не хочет или боится задавать уточняющие вопросы и выполняет (возможно) не ту задачу.
Я бы, конечно, спросил.

Но вы ей богу, как будто курсовую по психологии/социологии делаете.
Управлять скоростью всего процесса или отдельной волны?
Как нет? Ставишь FPS флэша 100 и разгоняешься. Возможность есть.
Вот, товарищи минусуют… А между тем, бОльшая часть решений выглядела примерно так: уменьшим паузу между тиками / увеличим количество пробегаемых клеток за тик. Что есть ни что иное, как FPS.
Сама задача подразумевает квантованность времени, поэтому все остальные способы изменения скорости — суть изменение ФПС.
Почти во всех решениях скорость была пропорциональна длине дефолтового тика в программе. Полностью самостоятельная скорость заливки была у трех или 4х.
>>хороший структурированный по канонам ООП код — признак опытного разработчика, который может грамотно разбить задачу по модулям и собрать из них приложение.
>>>… с бегающими цветными волнами в вакууме: волны, двигающиеся в любых направлениях, каждая в своем потоке. Человек пытался показать, что может писать многопоточные высоконагруженные системы? На таком тестовом задании?..

А чё не наоборот:

Человек пытался показать, что может писать в ООП стиле? На таком тестовом задании?..
Хороший код с возможностью масштабирования и заделом к изменению требований(волны, двигающиеся в любых направлениях, многопоточность) — признак опытного разработчика.
Это называется overengineering. Как от него отучать программистов, я не знаю. Так что согласен с автором — лучше сразу не брать.
т.е. вы не возьмете разработчика, который не тратя ваших ресурсов, решил задачу?
И при этом заложил мину замедленного действия в виде сложного кода, который потом кто-то будет поддерживать и дорабатывать. Например, вы уверены, что любой джуниор сможет изменить алгоритм и при этом не накосячить с многопоточными блокировками? Или это значит, что код этого разработчика смогут поддерживать только программисты его же уровня? Дорого, блин.
Лет 6 назад я взял одного разработчика который всегда решал задачи, как вы сказали — overengineering.
В данный момент он отличный архитектор, который спроектировал несколько коммерчески успешных решений, именно из-за overengineering.
Т.к. проектировал так, что последующие изменения, даже переворачивающие решение с ног на голову, не валили его (проект) с ног.
Если он заложил лишние абстракции в тех местах, где они понадобились, это хороший архитектор. Если где попало, то плохой. Писать тестовое задание из топика с потоками — это просто программист жонглировал потоками без всякого конкретного смысла.
Всегда думал, что тестовые задания пишутся для того, чтобы исполнитель мог показать себя, что умеет делать.
Как я и написал в конце — у каждого свои задачи. Каждый смотрит сам и оценивает по своим потребностям. В моём случае, overengineering был тревожным знаком, так как под такого специалиста у нас нет вакансии. В вашем же случае, вы увидели бы то, о чем написали в комментарии. Для вас это плюс.

Важно не плюс или минус, а то, что вы смогли этот нюанс вовремя разглядеть.
У автора там противоречие, но вы согласны бгг… С обоими(с).

Вообще я к тому, что «хочешь получать умные ответы — задавай умные вопросы». Хочешь получать мегаООП на ровном месте и жёстко захардкодженые цвета и направление движения — так и скажи.

Это же типичнейшая проблема тестовых заданий. Называется угадай, что хотел сказать автор, каких конвеншнов он придерживается и что считает(а что не считает) вот тем вот вашим умным словом на непонятном языке.
Так точно. По умолчанию, если ничего не сказано, надо делать максимальное простое и понятное решение. Если оно без ООП простое и понятное, значит ок. Если без ООП получается запутанное, а с ООП простое, значит надо было использовать ООП.
Это не типичнейшая проблема заданий. Если в задании сказано «посчитать 2*2», не надо додумывать за автора условия и абстрагироваться, до x*y, до считывания примеров из файлов, до создания грамматик и т.д. Расширять можно бесконечно. Самое простое решение — print 2*2. Всё, что сверху — это overengineering.
Это всего лишь ваше мнение и совсем не факт, что оно совпадает с мнением того, кто составлял ТЗ. Вы сами занимаетесь додумыванием за автора, решая, что, наверное, это так, раз не оговорено иначе. А, как мы видим, из этой статьи все может быть совсем не так.
Вы куда-то в сторону уплыли.

Давая тестовое задание, я не хочу получить ни захардкоженные значения, ни фреймворк для создания тестовых заданий. Я смотрю на код, который присылает человек и пытаюсь понять как он мыслил во время его написания. Если человек сделал все одним способом, я делаю для себя отметку и пытаюсь развить одну линию общения. Сделав все по-другому, я буду с ним разговаривать о другом.
Вы бы об этом написали в статье.

Впечатление-то сложилось, что почти все ваши группы вы сразу браковали т.к. они не оправдывали ваши ожидания.
Мне кажется, overengineering в тестовых заданиях — это попытка показать больше навыков.
Чисто для справки: какой процент задание не прошел и на какую ЗА они шли?
Судя по всему, это было чисто исследование для написания этой статьи.
В начале же написано. Получается, не прошли задание 3/5.
А что такое ЗА я не знаю. ЗАрплата?
НЛО прилетело и опубликовало эту надпись здесь
Код в студию. Особенно интересно посмотреть, сколько будет лишнего кода, если обойтись без инкапсуляции волны.
В статье такой код.

Исходя из задачи, скорее всего будет лишним код с инкапсуляцией волны. Потому как цвет клетки при следующей итерации перерисовки однозначно определяется цветами клеток вокруг. Для такой поставленной задачи экземпляры волн не нужны. Ни хранить их, ни знать количество.

Но если кто-то удумает перерисовывать не все клетки, то объекты волн могут помочь.
Использование клеточного автомата — хорошее решение. В комментах выше есть сомнения, что оно решает задачу полностью, но даже если решает, это алгоритмический трюк. Обычное решение, по моему мнению, чтобы было простым, должно использовать класс волны.
Не думаю, что должно. У каждой строки кода должна быть какая-то необходимость.
Это не алгоритмический трюк. Никто не мешает создать класс клетки и привести код в порядок: разделить отображение от модели, модель будет представляться либо классом «доской», либо клеткой. Каждая клетка будет иметь метод — соседи, опрашивать их и находить цвет. Хотя это тоже может стать оверинженирингом. Но я пишу в том смысле, что представление задачи не заставляет писать не в ООП-стиле. Классы не обязаны моделировать наши представления о мире, если эти представления выходят за рамки задачи.
Даешь класс ячейки с двухсторонними связями к другим ячейкам, чтобы можно было пускать волны на октогональных ячейках без переписывания алгоритма!
Даешь граф ячеек ICell, соединенных связями IRelation, чтобы пускать по ним IWave! :)
И можно пускать волны в пространстве не только произвольной мерности, но и произвольной конфигурации.
НЛО прилетело и опубликовало эту надпись здесь
АХТУНГ! В комментариях представитель второй группы!
Вычислений при обновлении вроде бы можно и меньше делать. Каждый тик сдвигаем всю сцену на клетку вправо (если получится это место векторизовать — совсем круто должно быть), а крайнюю левую колонку вычисляем как максимум из трех (для угловых — двух) соседних клеток из второй колонки.
Есть ли смысл тратить время на оптимизацию, потенциально добавляя багов в реализацию, если для решения задачи достаточно и неоптимального решения? Это называется premature optimization. Она, как известно, the root of all evil.
т.к. в условии задачи не указано какой должна быть скорость, то совершенно непонятно достаточно-ли здесь неоптимального решения. это называется эм..., скажем, нечеткая постановка задачи. root, как мне кажется, гораздо большего количества evil.
Количество минусов у моего коммента наглядно демонстрирует, что вред от оверинжиниринга понимают далеко не все.

Если в спецификации не сказано, что вы должны выжать максимум производительности, не надо этого делать. Если не сказано, что надо использовать минимум памяти, то не выжимать байты. Если не сказано, что вы должны учитывать риск случайной порчи битов памяти, значит не надо этого делать. Требования могут задаваться и неявно. Если вы знаете, что делаете высоконагруженный проект, или что у вас матрица может быть 1000000x1000000, или что решение надо отобразить в Full Screen с 60 FPS, то да — делаете какие-то оптимизации. Пока это не требуется условием задачи, вы пишете самую простую реализацию, достаточную, чтобы решить задачу.

Свободная переменная, по которой необходимо оптимизировать по умолчанию — это читаемость и поддерживаемость кода. Это всегда напрямую влияет на надёжность кода и на качество продукта.
Эффект должен работать при любых значениях M, N, V.

Сразу напрашивается оптимизация перерисовки при больших M и N.
Нет, не напрашивается. Напрашивается аккуратное отношение к граничным условиям. А если понимать условие буквально и заставлять дурака расшибать лоб, то при M=N=1e10 вам надо будет делать большой кластер и запускать какой-нибудь двумерный map-reduce. Очевидно, что задача не про это.
На самом деле, это еще одна вещь о которой нужно спросить.
А вообще, зачем заставлять человека постоянно задавать уточняющие вопросы? Искать какие-то подколы в постановке задачи. Дайте строгое формальное описание задачи и вам сделают то, что вы хотите. Чтобы не было потом обид с обеих сторон.
Человек выполнил задание, а ему говорят, ты его сделал не так, как было нужно. А как было нужно никто ему не сказал. И кто виноват? Составитель ТЗ или человек который не уточних всех нюансов? Я считаю, что составитель ТЗ.
Именно это и есть проблема. Разжевать разработчику все (совсем все) условия очень много времени занимает. Очень — это действительно очень. Быстрее самому всё напрограммить, чем ТЗ писать. Программист должен получать только вводные данные — место его модуля в общей системе, и как он будет использоваться. На выходе должно получиться минимальное решение, которое работает ровно так, как просили. Если чего-то не просили, и программист сам не догадался, что это точно понадобится, то делать этого не надо.
Вот именно, что отвечать на одинаковые вопросы от 20-30 кандидатов, отнимает очень много времени.
Почему бы не включить все граничные условия в задачу и на этом успокоиться и дать разработчкам просто сделать свою работу.
Или вы предлагаете сразу готовить их к суровой реальности с плохими менеджерами и идиотами-заказчиками?
Вы говорите о коне в вакууме.

На практике, мало кто задавал вопросы, мало кому что-то было не понятно. Никто не сделал неправильно.

Люди делали так, что результат не работал — это да. А правильности или неправильности тут не было. Я никого не отсеивал только за то, что человек не использовал ООП. Неиспользование ООП — лишь показатель, повод подумать «почему?». Зачастую, потому что человек был очень зелёный и просто не справился в итоге со своим же алгоритмом.
Да, я немного абстрагировался от реальности, но согласитесь, что в теории, скорее всего, именно так?
А как должны себя вести хорошие менеджеры и хорошие заказчики? Они тоже до конца не знают требования. Это просто жизнь так устроена. Поэтому проблемы советуют решать по мере поступления.
Задача хорошего менеджера — выжать максимум информации из заказчика, структурировать эту информацию и передать ее разработчикам. А не сделай, как на картинке справа.
Не про это немного я говорю. Ни хороший менеджер, ни хороший заказчик не могут знать достоверно, что будет через 5 лет с бизнесом. Они физически не смогут дать точный прогноз, каким образом он может видоизмениться за это время. Делать программное решение, закладываясь на все возможные варианты развития по всем фронтам, это лишняя трата денег.

Условно говоря, если вы не можете с высокой долей уверенности говорить о том, что, например, магазинчик разрастётся до сети супермаркетов, то и не нужно делать ему программу учёта с поддержкой огромного числа рабочих мест кассиров, реализацией сложной внутренней логистики для управления складами, планированием расписаний разгрузки фур на десяти дебаркадерах и т.д. Потенциально любой магазинчик может разрастись до таких масштабов, но это не значит, что надо сразу всё это закладывать в проект, пусть даже «на вырост».

Сделайте то решение, которое нужно клиенту сейчас. Уточните у него реалистичные прогнозы на ближайшее время, с чем он может столкнуться, и заложите в этих местах слои абстракции, чтобы потом проще было доработать. Но не надо закладывать будущие маловероятные расширения и усложнять программу без необходимости.

Сделай, как на картинке справа, учитывая то, что написано слева — нормальное задание. Точнее, я могу предложить ситуации, когда это было бы нормальным заданием. Было ли оно в реальности нормальным — не знаю.
Согласен со всеми абзацами кроме последнего. Он очень спорный.
Тут ещё неясность ожиданий потенциального работодателя: а вдруг от меня именно такой оптимизации и ждут? Что если потом скажут: а запусти-ка мне это для N=100000 и M=1? И наоборот.

Я видел разные тестовые задания, и каждый работодатель вкладывает в них что-то своё. Кто-то придирается к лишним тактам процессора, кто-то — к отрисовке. А кто-то к потенциальному overflow в printf.
Ага, N=1 и M=1 — вполне себе интересные граничные условия. На это посмотрят обязательно. Об этом в задании и говорилось.

Придираться к тактам процессора и отрисовке — это особенности конкретного задания. Я не берусь говорить, прав был работодатель или нет, что придирался в том конкретном задании. Это нужно конкретный случай смотреть.
А напрашиваться должно после замеров и неудовлетворительной работы.

Всё, что напрашивается «до» — и есть предварительная оптимизация.

А вообще, не удивляет Вас самих желание здесь оптимизировать? Какие большие M и N Вы представляете? Вроде ж не программы не для ламповых калькуляторов.
А вы попробуйте отрисовывать в цикле по клеточкам поле хотябы 1000х1000 ячеек(или пусть размер ячейки будет равен 1 пикселю, а размер поля равен размеру экрана), без аппаратного ускорения. Да даже с аппаратным ускорением, без использования специфических вещей OGL или DX, заметите сильное проседание FPS.
В задании не было ничего о плавности движения фигур. Цикл из миллиона проходит быстро.
Даже решение, которое с клетками (без сдвига), где все клетки пересчитывается, легко оптимизируется, не меняя структуры кода. Например, в изолированном участке кода, где цикл по клеткам, меняем цикл, который уже не бегает по всему полю, а бегает только по сохраненным в какой-то структуре клеткам. Очевидно, что при перерисовке в следующий раз будут меняться только клетки справа. Их можно сохранить.
И еще можно оптимизировать. Но это будет потом.

Да и сдвигать тоже можно всю картинку. Если так будет код проще. Заранее же думать об оптимизации вредно.
Вы давно что-нибудь программно рисовали на компьютере? А на телефоне? А с полным ооп во все места? Вам после этого не очень захочется рассказывать про калькуляторы.
да, давно. Помню, рисовал поточечно планеты на паскале в году так 95 на том еще медленном железе. Мгновенно так работало… Видимо что-то изменилось? ))

В любом случае — предварительная оптимизация — это зло. Я не имею ничего против решения со сдвигом в данном случае, т.к. оно может упростить код и дело не в оптимизации.
>поточечно планеты на паскале в году так 95 на том еще медленном железе. Мгновенно так работало… Видимо что-то изменилось? ))

А какое разрешение у экрана было? 240*320 небось :) И цвета 8 бит. Так что изменилось немало ;) Не умаляя зла предварительной оптимизации, я, например, совершенно не разделяю мнение автора, что для такого задания не нужны треды. Хотя бы потому, что за вычисления в UI треде нужно руки отрывать вместе с задницей в любой графической задаче. Или что не нужно закладываться на большое число волн, потому что кликать человек вполне может с частотой 10 раз в секунду (и ни один клик нельзя пропускать).
точно не помню, в районе 800 на 600. 8 бит
Да просто снобизм никому не нравится.
Речь же не идёт о переписывании на asm. Оптимизация, предложенная eyeless_watcher находится в рамках задания (волна движется слева) и может быть внедрена малой кровью, с сохранением наглядности кода.
Каждая хитрость, каждое дополнительное условие — это минус к читаемости кода. За снобизм прошу прощения, слишком уж тема зацепила за больное.
Наоборот, никакого оверинжинеринга. Раз сказано, что волна движется слева — двигаем её слева. Оверинжинеринг как раз — перерисовка всего поля, так как предполагает возможность других направлений волн. :)
Нет. В данном случае, перерисовать всё — это самый первый и самый простой вариант, который приходит в голову.
Это не оптимизация, а приятный бонус. Ибо ваше решение мне в голову бы просто не пришло, а бег волн за счет сдвига сцены и апдейта крайней колонки — лично мне куда понятнее.

А еще у вас сцена по обоим измерениям на два квадратика меньше, чем должна быть.
Тогда не получится управлять скоростью волны. Хотя… ею и в этом решении не управляют.
слева на право со скоростью V пробегает волна
Для того, чтобы управлять скоростью волн, надо иметь не один таймер, а два — один для отрисовки, другой — для апдейта сцены. Скорость у всех волн вроде как одинаковая, от неё и зависит частота апдейта.
А, ок. Я понял так, что у каждой волны может быть своя скорость. А если просто ускорять-замедлять все, то да.
На самом деле даже векторизовать ничего не надо — просто надо счиать нашу матрицу «замкнутой по кругу»(после последнего столбца идёт первый) и хранить в переменной фактическое начало. На каждом шаге пересчитывать столбец который является фактическим началом по предложенному алгоритму и смещать указатель. То есть в исходниках надо сделать так():
var startPosition:uint
function frameHandler(e:Event):void {
    for (var j:uint = 1; j < Height-1; j++) {
        buffer.setPixel(startPosition, j, Math.max(bmp.getPixel(startPosition, j), bmp.getPixel(startPosition-1, j), bmp.getPixel(startPosition, j-1), bmp.getPixel(startPosition, j+1)));
    }
    startPosition = (startPosition -1) % Width;
    bmp.copyPixels(buffer, buffer.rect, zeroPoint);
    
    var rect:Rectangle = new Rectangle(0, 0, Size, Size);
    for (i = 0; i < Width; i++) {
        for (j = 0; j < Height; j++) {
            rect.x = i*Size;
            rect.y = j*Size;
            display.fillRect(rect, colors[bmp.getPixel((i-startPosition)%Width,j)]);
        }

    }
}
Если никто так и не показал вам того что вы ожидали стоит задуматься а правильно вы выбрали тестовое задание
Я ожидал правильный ответ.

Свой ответ я придумал уже ближе к концу использования этого задания. И огорчился, что так никто даже не пытался решить.
Вот в этом то и есть основная проблема. Не должно быть такого «Я огорчился, что никто не придумал, как это можно решить настолько красиво, насколько решил я». Если бы кто-то решил таким способом, я бы сразу отправил его в группу излишних оптимизаторов с непонятным кодом. Уж слишком это субъективно.
Собственно там несколько постепенно увеличивающихся ромбов. Соответственно точку старта и текущий размер в структуру, структуры в массив, упорядоченный по времени старта, выкидывать из массива по условию, если «волна» ушла за экран. Отрисовка — скорее всего просто отрисовка всех волн поверх друг друга если это не сильно влияет на быстродействие.
НЛО прилетело и опубликовало эту надпись здесь
Решению перфекционизма не хватает — в битве между ним и ленью победила лень. Ой, простите, прокрастинация )
НЛО прилетело и опубликовало эту надпись здесь
На какую позицию это тестовое задание?
На позицию разработчика.

Какие требования? Достаточный опыт для самостоятельной работы.
Язык не важен. Главное — какая база у человека и как он подходит к решению проблемы.

Эта задача тоже не просто так возникла.
> На позицию разработчика.

Разработчика чего?
Программного обеспечения для аппаратных систем (8
Небольшие проекты, разные платформы. От игр и 3d веб сайтов на мультитач-устройства, до embeded систем на микроконтроллеры.
Что ж. Слабо себе представляю 3d веб сайты для мультитач устройств, но для первой части задание действительно адекватное, пожалуй )
> От игр и 3d веб сайтов на мультитач-устройства, до embeded систем на микроконтроллеры.

«Вакансия: водитель.Требования: профессиональные навыки в управлении легковыми и грузовыми автомобилями, троллейбусами, трамваями, поездами метрополитена и фуникулёра, экскаваторами и бульдозерами, спецмашинами на гусеничном ходу, боевыми машинами пехоты и современными легкими/средними танками, находящимися на вооружении стран СНГ и НАТО. Навыки раллийного и экстремального вождения обязательны… „

далее тут
Смешно, конечно, но не про этот случай, к сожалению.

Если человек обладает достаточными знаниями и опытом, то сесть и изучить что-то с нуля ему не составит труда. Тем более, когда учить нужно лишь базовые вещи. В вашем смешном примере, если у человека нет водительских прав, то как с ним разговаривать дальше? Он не сможет быстро научиться управлять трактором или троллейбусом. Если же он опытный водитель, то освоить азы вождения бульдозера он сможет достаточно быстро.

Еще раз, я не требую знать всё. Я хочу, чтобы человек мог быстро и самостоятельно разобраться в программировании под разные задачи,
Слишком уж абстрактное «под разные задачи». А написание программ для AI? А программирование в сфере генетического моделирования? Для некоторых задач надо быть ну очень в теме предметной области. И, как ни крути, пример задания в топике — одна из таких более-менее специфичных задач, с которыми 95% разработчиков и не сталкивалось, да и не нужно было в работе. И это не настолько очевидно, чтобы въехать сразу и волшебным образом «уметь» их решать на ходу.

Я не спорю с тем, что, возможно, именно для вашей вакансии именно такой человек и нужен был — никаких претензий, но тогда и топик должен бы называться «Что можно узнать о кандидате по тестовому заданию на вакансию X с требованиями Y».
игр и 3d веб сайтов

Вот это, пожалуй, самое принципиальное и объясняющее, почему тестовое задание именно такое. Разработчики-то сильно разные бывают.
Нет принципиального значения как выглядит тестовое задание. Если вы не хотите специально проверить может ли человек, например, написать клиент для базы данных. Все равно какое задание, если вы оцениваете его бинарно: сделал или не сделал. Из каждой реализации можно сделать множество выводов.

А это задание максимально абстрактное. Оно не требует использования JavaScript, PHP, или наоборот C# и win api.
Не согласен, недостаточно абстрактное — тут специфика именно гейм-дева или чего-то вроде этого. Разработчик может быть крут в своем деле (веб/бизнес-решения/frontend/UI/etc), но голова прямо с ходу не станет работать в незнакомом направлении. И тут бинарная оценка ну никак не будет объективной.
Я и говорю, нельзя применять бинарную оценку.
Кстати, объявление написано с нарушением закона, в позиции, где указывается что начальник у соискателя будет младше 36 лет :)
Что бы Вы сказали о таком тестовом задании? Интересно, честно говоря.
Я когда-то сталкивался с подобным работодателем — мне дали задание в котором была фраза «сделать как на картинке справа», на уточняющие вопросы человек не отвечал, на задание дали 2 часа. За два часа я сделал именно так «как на картинке» + с соблюдением всех остальных условий. Через день мне ответили, что я сделал не то, что «надо было сделать» и даже не ответили, что именно ожидали.
Так и тут — задание сводится не к выполнению, а к угадыванию, чего хочет автор от кандидата.
Так и тут — задание сводится не к выполнению, а к угадыванию, чего хочет автор от кандидата.

Вы делаете странные выводы. Я нигде не писал, что кому-то отвечал, мол, вы сделали не то.

Я никому не отказывал только основываясь на том, что человек решил задачу необычно или не так, как я бы ее решил. Как я писал, у меня не было своего решения довольно долгое время. Я смотрел на код и делал выводы для себя. Большинство не прошли тупо потому, что не смогли сделать это задание. С остальными в разговоре, темы для которого выбирались основываясь на выводах из кода, были выяснены те или иные разногласия.

Я уверен, никто из выполнивших задание не ушел с мыслью, что «я сделал все правильно, а они сказали, что это не так как они хотели».
Если не секрет, что именно Вы сделали?
Хороший вопрос :)
Систему частиц. Частицы вылетали из одной точки в левой нижней части экрана, но с разной скоростью, с немного разной траекторией и разным цветом. Внутреннюю реализацию не сильно помню, было года 4 назад.
На OpenGL или на UIKit?
На OpenGL, там сверху была большая надпись «Exercise II — [OpenGL ES skills]», но там рядом логотип компании и имейлы для ответа, потому обрезал как было быстрее.
Понятно, спасибо за ответ! )
На требование сделать «как на картинке» очень хочется эту картинку и вывести. :)
Не понял про version number 1.25
>Каждый тик клетка принимает максимальное значение своих четырех соседей.
В условии нигде не сказано, что если быстрая волна перекрыла медленную волну, то медленная волна должна умереть.
Даю вам еще 15 минут, чтобы подумать.
*падает ниц в благодарность за предоставленное время*
у первой (красной) волны скорость 1, у второй (синей) скорость 2. Точками отмечены клетки, затронутые соответствующей волной на данном тике.

ваш алгоритм затрет второй волной первую, и на тиках нижнего ряда будут только синие точки. В то время как наблюдения реального мира предполагают, что волны не затирают друг друга, а суммируются и продолжают нормально существовать после расхождения (см. интерференция). Соответственно красная волна продолжит медленно плестись уже за фронтом синей волны.

_____________________
рассуждения неверны в случае, если у всех волн скорость одинакова. Однако сие условие тоже нигде не оговаривается
Энциклопедический пример. Интерференция. Еще нужно учесть преломление воды и скорость ветра.

Вы решаете какую-то совершенно другую задачу.

По условию, волна полностью перекрашивает квадратики в свой цвет. Даже рисуночек сделал. И флэшик приложил.

То есть, если волна с бОльшим цветом обгоняет и затирает волну с меньшим цветом, то последняя отправляется в рай для волн и никого больше не интересует. Так что в первоначальном условии ваш вопрос и контрпример не имеет смысла.
На вашем рисунке все волны с одной скоростью распространяются (и такая ситуация невозможна). И про уход волны в рай для волн ничего не сказано. К чему я собственно и прикапываюсь).

Т.е. ваш подход — он верен, если рассматривать задачу именно как клеточный автомат. Мой пример вроде бы указывает на то, что задача клеточного автомата не эквивалентна поставленной задаче распространения волн.
Сейчас автор выделит ещё одну группу кандидатов — «сильно умные тут нашлись, а не поняли как я задания ставлю».

мне в голову приходит лениво генерировать JS ромбовидную картинку на канве и тупо двигать её слева-направо стилями по таймеру. формально задачу решает, но мне кажется тут же начались бы упреки, что это не то что хотели увидеть. Что снова доказывает несостоятельность синтетических задач — в отличие от практических они не имеют смысла. Когда ясен смысл, то ясно и какой алгоритм оптимальнее. А когда смысл в том, чтобы угодить экзаменатору — то его нет.
«мне кажется», «если бы», «синтетические задачи»… вы что-то придумали себе в голове, сидя на удобном кресле, попивая пивко, и делаете выводы, характеризуете людей. так держать!
вы характеризуете людей по коду, сидя в удобном кресле и делая выводы, а я — по статьям, сидя в удобном кресле и делая выводы, и я не вижу почему одно — нормально, а другое — плохо.
И не очень понятно, зачем поле вообще считать — там есть довольно простое аналитическое решение
Интересной была одна особенность всех решений — все… абсолютно все смотрели на задачу, следуя буква к букве её описанию в начале поста: сетка, по ней пробегает волна…


Мне кажется, что это абсолютно естественно — предлагать решение в терминах предметной области. Представьте пожалуйста такую ситуацию: вы пришли работать, ну скажем, в банк и вам передали на поддержку код вашего предшественника. Вы обрадуетесь, обнаружив внутри вместо абстракций «клиент», «счет», «ежемесячная выплата» и т.д. нейросеть? При этом все работает супер )))
Использование языка предметной области при разработке дает шанс, что код можно будет развивать и поддерживать. Не гарантирует, конечно )) Ведь вы же сможете нового сотрудника обучить специфике вашей предметной области, не так ли?
В моей жизни был именно такой случай. Была задача находить в тексте слова из «чёрного списка». В коде был написан конечный автомат, работающий по набору правил из внешнего файла. Отдельно прилагался «компилятор», который по списку слов генерировал файл с набором правил для конечного автомата. Разработчик уволился. Исходники «компилятора» утеряны. Документации нет. Вдруг понадобилось добавить ещё и «белый список». За задачу брались разные программисты, от джуниора-энтузиаста до мощных сениоров. Никто так и не решил.

В итоге джуниор выпилил конечный автомат нафиг. Написал «наивное» решение. Ну то есть с использованием списка строк, find() и т.п. Все были счастливы.
Я даю гораздо более простую первую задачу на собеседовании, на 5 строк и двойной цикл.
50% не решает, так что на приведенной большой задаче я бы веру в человечество так быстро терять бы не стал
А не приведёте ли тут эту задачку?
Что-то вроде найти простые числа или числа Фибоначчи до N, определение подсмотреть можно.
Но решается задача не дома, а непосредственно во время собеседования.

Ну а в случае успешного решения — уже сложные задачи.
1. Я специально просил не обсуждать специфику тестовых заданий
2. Производительность человека во время интервью и дома может кардинально отличаться. Я, например, знаю, что, когда на меня кто-то пристально смотрит, я не могу ни о чем думать вообще. В этот момент я выгляжу полным дебилом, что не очень хорошо сказывается на прохождении задач на собеседованиях.
Статья хорошая. Но вот мне как работодателю всегда было все равно, как человек может решать алгоритмические задачи. Ведь по многих компаниях этого просто и не надо, а людей на собеседования все равно «мучают» университетским задачками. У нас, например, важно только опыт работы с нашей CMS (наше основное направление), знание и опыт применения различных паттернов, качественный код (да-да, понимаю, что «качественный» — понятие довольно относительно).
Если учитывать, что автор имеет отношение к программированию графики, то само задание достаточно толковое.

По просьбе автора целесообразность «заданий» обсуждать не буду, только задам следующие вопросы:

1) Вы написали, что вы даете это задание на позицию разработчика. Имеете ли вы в виду, что на позицию старшего разработчика и другие вы такое задание не даете?

2) Какой срок вы ставили перед кандидатами?
У нас все позиции разработчиков — позиции старших разработчиков. «Старшесть» я определяю просто — если на человека я могу положиться в решении задачи, не контролировать его по мелочам и не проверять каждый чих. Если ты уже 20 лет программируешь, но я не могу на тебя положиться — ты не старший.

Тестовое задание позволяет сразу же отсеять совсем ненужных людей, или подумать еще раз, вдруг человек вам все-таки пригодится на роли, которой у вас даже и не было.

Так как все заняты, срок я жестко не ограничивал. Обычно, люди что-то присылали сразу или делали на выходных.
Если прошла неделя, а человек так ничего и не прислал, я начила интересоваться что да как.
НЛО прилетело и опубликовало эту надпись здесь
Просто Ваша вера в человечество пока не пошатнулась =)

Я видел людей, претендующих на старших (с опытом под 20 лет), которые не могли ответить, чем отличается виртуальная от чисто виртуальной функции (C++, если что).
НЛО прилетело и опубликовало эту надпись здесь
Дело не только в ответе. Когда человеку объясняешь сам разницу и просишь придумать область применения — он не может ничего придумать.

Или человек не понимает даже самых общих принципов многопоточности?

Я провёл много собеседований, всякого насмотрелся. И никогда не судил по одному-двум вопросам, всегда оценивал кандидата «в целом». Если он схватывал новые вещи на лету (пусть даже раньше о них и не слышал), то это было большим плюсом. Если он говорил, что спец в X, а сам на примитивные вопросы по X не может ответить — это было минусом.
НЛО прилетело и опубликовало эту надпись здесь
Практические навыки это обычно пара ссылок на гитхаб или AppStore. Очень показательно. Можно оценить код и результат. Пусть даже проекты не завершённые.

Если ссылок нет, то испытательный срок покажет практические навыки. =)
Задание то простое. Достаточно найти в каждой ячейке последнюю дошедшую до нее волну… codepen.io/iseeyou911/pen/nzijd
Я, если честно, не сильно понял, чем ООП это плохо. Потратил пару часов, набросал программу на WPF + MVVM, с командами и всем прочими ООПэшными вещами. Исходник кинул на яндекс диск. У меня ООП головного мозга?
По сути вся логика сводится к тому, чтобы определить цвет ячейки в любой момент времени.
1. Для варианта с постоянной скоростью волн, достаточно найти ближайшую волну, которая «накрывает» ячейку. Но это для первых V столбцов, где V-скорость волн. Для остальных столбцов можно тупо брать значения предыдущих ячеек в этой же строке. То есть для ячейки Cell[I][J] можно взять цвет ячейки Cell[I][J-V]
2. Если у каждой волны своя скорость, то нужно искать последнюю добавленную волну, которая накрывает ячейку. Она необязательно самая близкая.
Время работы алгоритма, как в первом, так и во втором случае, будет примерно O(M*N*P), где P — количество активных волн. Ну, это в худшем случае. Если понапрягать мозг, то я думаю, можно найти решение и побыстрее.
Я не говорил, что ООП это плохо.
Но как и всегда, большим количеством хорошего можно покончить жизнь самоубийством.

Я вот уже близок к самоубийству через переполнения желудка черешней (8
По поводу черешни — Роспотребнадзор не одобряет.
У вас WPF + MVVM головного мозга.

P.S. Если что, я «свой». просто наши технологии очень специфичны.
Не понял сути Вашего комментария. А если бы на HTML+CSS+Javascript написал, было бы HTML+CSS+Javascript головного мозга? У нас 100500 вариантов, как решить задачу и чем пользоваться при этом. Если WPF решает задачу, почему нет?
Потому, что от алгоритмических задач ждут корректного решения, а не излишней структурности. Вы решаете бОльшую задачу, чем поставил автор, создаете интерфейс, применяете паттерны.
Мне показалось, что автор негативно отнесся к применению ООП в решении задачи. Я применил ООП и паттерны, решил задачу, и спросил, отчего ООП — это плохо. Автор ответил на мой вопрос. То есть MVVM и ООП я использовал именно для того, чтобы показать, что задача вполне себе спокойно решается и с ними. Сам я могу решить задачу и без ООП, и на Javascript, хоть на C++. Выбранный метод решения просто был в контексте вопроса.
Я вашу мотивацию понял, но одно но: я не вижу ничего спокойного в том, чтобы делать простые вещи сложными универсальными способами. То, что мы можем программировать на одной ленте и писать туда палочки и звездочки доказано уже давно. То что мы можем использовать MVVM, WPF и еще стотыщпятьсот других супер универсальных технологий, которые создавались для индустриальных нужд, в примерах, которые приемуществ этих технологий не только не используют и не показывают, но и делают из мухи слона (про антипаттерны в стиле вот этого, вы наверняка помните), — это тоже всем ясно.
Поэтому, на деле вы нам тут демонстрируете опровержение антипаттернов.
У меня сложилось впечатление, что вы судите мой код, хотя сами в него и не заглядывали. Ок, давайте говорить предметно. Во первых, утверждение, что WPF и MVVM создавались для индустриальных нужд — весьма спорное утверждение. Как минимум потому, что
1. MVVM это не технология, это патерн. Он может использоваться не только в WPF, а везде, где есть возможность двустороннего связывания данных. Я его использую, чтобы вручную не перерисовывать UI. Потому что так проще, и быстрее. Благодаря грамотному использованию этого паттерна, мне не нужно перерисовывать каждый раз все поле, обновляются только измененные ячейки. И чтобы этого достичь, от меня практически ничего не потребовалось. По моему, это упрощает решение, а не усложняет.
2. Вы говорите, что преимущества WPF не используются в данном примере. А какие основные преимущества WPF?
— Поддержка MVVM из коробки, что, как я уже писал, упрощает решение
— Аппаратный рендеринг, что ускоряет работу с графикой, по сравнению, например, с GDI или GDI+
— Декларативная разметка интерфейса. Что означает, что я не написал ни строчки кода, чтобы вывести меню, контролы и ячейки. Это тоже упрощает решение.
В моем приложении 7 классов. И 5 из них связаны с решением задачи. От остальных двух никуда не деться. Да, я мог бы те 5 классов сделать и в одном. Но был бы он в 5 раз больше, работал бы медленне, был бы сложен для понимания и изменения. И нарушил бы кучу ООП принципов. Вы думаете, это надо показывать работодателю? Я так не думаю.
Теперь про антипаттерны. Как известно, они представляют из себя плохое решение проблемы, которое в будущем, при развитии системы, может стать источником ещё больших проблем. Не смотря на то, что тестовое задание навряд ли будет развиваться в нечто большее (хотя у меня такое было), Вы должны со мной согласться, что применение антипаттернов в коде крайне нежелательно. Ещё, раз Вы «свой», то знаете, что в C# любая программа содержит, как минимум, хотя бы 1 класс. Поскольку в задаче нам нужно производить, как минимум, 3 действия (хранение состояния, отображение в UI и логику), то поместив всё это в один класс, мы получим классический антипаттерн GOD object.
Таким образом, я считаю, что
— применение ООП задачу упрощает и делает более гибкой к изменениям
— применение MVVM позволяет писать меньше кода и больше фокусироваться на решении задачи
— применение WPF позволяет ускорить время разработки и скорость работы программы
Да, я видел, что многие решают эту задачу на javascript. И, хотя я не видел тут решения с волнами разной скорости (кроме моего), весь этот javascript вполне себе работает. Но если взглянуть на код этих решений, то везде есть изъяны. Какие-то тянут с собой дополнительные скрипты. Некоторые даже не обернуты в анонимную функцию и представляют собой просто смесь глобальных переменных и функций. Представьте, что Вы нанимаете javascript программиста. Если задача будет решена, но архитектура совсем никакая, то вы доверите ему самому принимать решения при разработе вашего веб проекта?
В дополнение, помимо критики, я прошу Вас предложить своё решение задачи или ещё лучше реализацию.
Посмотрел я ваш код, и он мне не нравится. В данном треде я согласен с несколькими ораторами, но пожалуй наиболее всеобъемлюще и четко выразился aml в следующей своей цитате:

По умолчанию, если ничего не сказано, надо делать максимальное простое и понятное решение. Если оно без ООП простое и понятное, значит ок. Если без ООП получается запутанное, а с ООП простое, значит надо было использовать ООП.
Это не типичнейшая проблема заданий. Если в задании сказано «посчитать 2*2», не надо додумывать за автора условия и абстрагироваться, до x*y, до считывания примеров из файлов, до создания грамматик и т.д. Расширять можно бесконечно. Самое простое решение — print 2*2. Всё, что сверху — это overengineering.


1) Ваш код не является ни максимально простым, ни простым.
2) Он не понятен досконально человеку, который не знает WPF, а понятность кода входила в формулировка задания.
3) Ваш код содержит, извините за тавтологию, слишком много ненужного кода, который не имеет к решаемой задаче никакого прямого отношения и существует только потому, что он использует WPF (использование рефлексии, шаблоны контроллов, конвертер, команды)
4) При том, что вы пишите, что основная фишка WPF — это performance, ваш код содержит overhead, потому что оборачивает простую вещь в ненужные слои абстракции.
5) Ваш код не однообразен: хоть вы и бьете себя в грудь «как крут MVVM, он позволяет 1), 2), 3)», сами то вы не везде его используете и обращаетесь к контроллам напрямую. Видимо потому, что несмотря на вами же сказанное, чувствуете, что с дополнительными абстракциями уже начинает наступать перебор.

Представленный код, ИМХО, не может быть каноническим решением данной задачи на WPF, поскольку даже в рамках WPF можно решить задачу проще и быстрее. Такое решение допустимо и оно работает, но показательным я бы его не стал называть.

Теперь о том, как я сам бы решал обсуждаемую задачу:
Вся информация о волнах уже присутствует в матрице. Нам не нужно хранить волны в виде сущностей, а «следующий кадр» легко получить, используя сдвиг столбцов матрицы. Таким образом, мое решение — это делать так, как предложил сам автор.
Код он уже привел, поэтому писать его второй раз я не буду. Действительно, данная система задает клеточный автомат, работу которого можно оптимизировать. Мне такой подход, как человеку изучавшему computer science, ближе потому, что он:
1) минималистичен и решает непосредственно поставленную задачу
2) Оптимальнее подхода с поиском «ближайшей волны»

В качестве UI для такой задачи можно вообще использовать консоль. Если говорить про приложение с графическим интерфейсом, то лично я бы делал так: выделил бы область памяти с нашей матрицей, изменял бы данный bitmap и рендерил бы его за 1 операцию. Да, разумеется, я обратил внимание на то, что в вашей программе волны могут иметь различную скорость, что не подразумевалось в данной задаче, но это тоже решается без дополнительных классов.

мы получим классический антипаттерн GOD object.


Это не god object, а структурным/процедурным программированием вообще-то называется.

1. Вся логика отрисовки поля находится в одном классе, в 2х функциях. Согласен, что можно написать проще. Можно даже написать проще, используя ООП. Но говорить, что этот код сложный я бы не стал. Что профессиональный программист не разберется в 5ти класах, решающих задачу, которую он сам и придумал — тоже вопрос. Учитывая, что какие то вообще вычисления происходят только в одном методе. В общем, пункт этот спорный.
2. Автору было все равно, как реализуется задача. К тому же, MVVM отделяет логику от представления. То есть просматривать задачу должно быть проще, чем если бы я использовал тот же GDI, или консоль. На самом деле, код не будет досконально понятен человеку, который не знает C#. Так что этот пункт также надуманный. В крайнем случае можно обратиться к автору и спросить, поймет он что написано в моем коде или нет.
3. От WPF там только это:
— Разметка формы и приложения
— Классы страницы и приложения
— Конвертер.
Рефлексия используется, да. Косвенно. В одном аттрибуте, в одной строчке одного класса, в котором и логики то нет. Команды с WPF нет так сильно связаны. Это больше архитектурный приём.
Но, я согласен с Вами, что можно было бы и без этого обойтись. Но, если Вы будете выводить в консоль, то Вам придется писать код для консоли, верно? Или код для битмапа и его рендера? Просто, я сделал это красиво (цветные квадратики и все такое :)), а Вы можете сделать понятно. Вот и вся разница.
4. Я просто не понял, о чем речь. В моем коде просто при изменении цвета ячейки перерисовывается эта ячейка. Для этого я использую стандартный интерфейс. Потому не совсем понял, что именно Вы имеете ввиду.
5. Ну, я вообще в грудь себя не бью. Вся информация, что я даю, есть в википедии и МСДНе. И, я рад, что Вы заметили прямое обращение к контролам в коде формы, Вы верно подметили, я это сделал, чтобы было проще понять суть и не отвлекаться на ненужные вещи. Никаких дополнительных абстракций я не делал. Мало того, основная моя деятельность связана с вебом, и WPF я сам знаю постольку-поскольку.

Я ни разу не называл свой код каноническим. Я даже писал, что его можно улучшить. Всё, что я хотел показать — это допустимое решение. Рад, что мы с Вами в этом согласны.

Теперь по поводу Вашего решения. Я тоже использую матрицу. А волны я храню отдельно только ради скорости работы. Сдвиг столбцов матрицы отлично подходит, когда скорость у всех волн одинаковая и не превышает количество столбцов. Тут я с Вами абсолютно согласен.
По поводу клеточного автомата. Я просто не понял, как это решит задачу, если скорость у всех волн будет больше единицы и разная. Окей, пусть будет одинаковая. Равная 2. И проверять нужно уже не 4 клетки, а больше (на бумажке это выглядит как 12 клеток, но могу ошибаться). И чем больше скорость волны, тем больше клеток надо проверять. А теперь возьмем скорость волны 0,99 от ширины матрицы. А Сколько клеток нужно проверить? (я думаю, где то (2P+1)(2P+1)*0.5, где P — скорость волны) Какова сложность этого алгоритма? Что то около O(M*N*P*P). Минималистичнее? Да. Проще? Да. Оптимальнее? Не думаю. Ещё возьмем скорость волны 1,5 от ширины матрицы. Как этот вариант отработает в клеточном автомате? Я, право, немного сомневаюсь в корректности такого решения. Конечно, это можно проверить только на практике.

«Это не god object, а структурным/процедурным программированием вообще-то называется.» Да, это я зря написал :)

Как бы там ни было, не думайте, что я какой то ярый фанат этих паттернов и ООП, или чего то другого. Это все равно, что сказать, что я фанат гвоздей или молотка. Всё это лишь инструменты для постоения программы. Я хотел построить программу с использованием ООП. Я это и сделал. Я написал именно так, как если бы я был соискателем. И если работодатель скажет мне потом, что их программист не разобрался в 5 классах, или не понял суть MVVM, или ещё чт то вроде того — то я скажу, что пусть его увольняют и берут меня.

Ещё как лирическое отступление. Год назад я устраивался на работу. Java программистом. Я Java не знал вообще. Мне дали тестовое задание и неделю времени. Задание состояло в написании клиент-серверного приложения и синхронизации, когда один сервер и много клиентов. Интерфейс консольный. Я всё сделал в стиле ООП, разбил на классы, закрыл что нужно интерфейсами, использовал паттерны, SOLID и много чего ещё (у меня было достаточно времени). Знаете, что мне сказал программист, который это проверял (и он же мой будущий начальник)? Что ему понравилось, как я применил ООП в решении. И я думаю, что это было одним из решающих факторов, по которым меня приняли на работу.

Ещё один пример. Года 3 назад мне дали тестовое задание — реализовать калькулятор выражений. Пользователь вводит выражение в консоль — и получает результат. Можно было вводить числа, скобки и простые операции, типа +-*/. Но было два условия.
— Чтобы добавление нового функционала занимало минимум времени и сил программиста
— Чтобы можно было легко изменить логику работы любой операции. Сделать плюс минусом, к примеру.
Я также решил все с использованием ООП. А работодатель, поглядев результат, сказал, что не хватает IoC, логирования и учета культуры.

Резюмируя, хочу сказать, что в тестовом задании главное не просто решить задачу, а показать работодателю, что ты обладаешь какими то ещё способностями. Главное — не переусердствовать. И пусть наши прения закончятся на том, что мое решение — допустимо. Также допустимо, как и Ваши с выводом в консоль или битмап. И везде есть свои плюсы и минусы.
Спасибо за рассказ. Ну что здесь сказать: везде свои требования и свои представления о том, как нужно отбирать кандидатов на те или иные позиции. Что показывать в тестовых заданиях, решать ли суперзадачу или же сохранять минимализм, и так далее. Мы с коллегами тестовые задания давали только людям без опыта и только если они проваливались на интервью. не могли написать код, когда на них кто-то смотрит, итд. Другими словами, целью было проверить, может ли человек в потенциале программировать, когда ему никто дома не мешает, итд. Сам придерживаюсь мнения, что по решению супер задач в тестовых заданиях вообще ничего нельзя сказать, потому что они достаточно синтетические и на практике их с высокой вероятностью так решать не будут.
Что можно узнать о работотдалете по тестовому заданию? =)

Неужели никто не заметил что меняется лишь первая колонка?! Все остальные колонки просто сдвигаются направо. Там никаких конечных автоматов не нужно совершенно.

Таких не берут в гугл.
Обсуждается выше в комментариях. Автор топика говорит — излишняя оптимизация.
Это не я говорил.

И да, почему-то мало кто видит, что генерится лишь левый столбик, а все остальное перемещается вправо.
Но это не делает это решение единственно правильным.
Процесс решения начинается с поиска самого простого варианта. Поэтому большинство пишет класс Wave и перерисовывает квадратики каждой волной. При обдумывании этого решения и во время реализации у большинства возникнут идеи что и как упростить / оптимизировать. Даже если сам человек не придет к какому-то решению, которое вам кажется оптимальным, наводящим вопросом его можно подтолкнуть в нужную сторону и посмотреть как он пойдет дальше.

Нельзя лишь на основании того, что первое решение было сделано просто и наивно, говорить, что кого-то не берут в гугл.
Ахааха =)
Вот именно так в гугл и набирают. И не берут именно из-за косяков такого порядка. В алгоритме решения.
если скорость волны 2 ячейки за 1 тик таймера (где написано что нельзя?) — то меняется сразу две колонки за тик. Таких не берут в IBM
Поправьте меня, если ошибаюсь, но для постоянной V, гораздо проще просто взять массив (N + (M/2) + 1 ) x M рендерить его в окно N x M начиная со столбца (M/2) + 2. Каждый тик, копируя все столбцы кроме последнего на единичку правее. А при щелчке мышкой — заносить в первые (M/2) + 1 столбцов нужный треугольник. Так что-бы столбец 1 был полностью цвета волны.
Приложенный вами код я бы назвал говном и попросил переписать нормально. Одни только три переменные BitmapData вызывают у меня искреннее удивление. Очень долго думал, но так и не смог найти адекватных причин, для чего так делалось, кроме, как неумение пользоваться классом Object.

var bmp:BitmapData = new BitmapData(Width, Height, false, 0x000000);
var buffer:BitmapData = new BitmapData(Width, Height, false, 0x000000);
var display:BitmapData = new BitmapData(Width*Size, Height*Size, false);


Вот, более адекватный код со сдвигом картинки и расчётом только первого столбца.
import flash.geom.Point;
import flash.display.BitmapData;
import flash.display.Bitmap;

const START_POINT:Point = new Point(1, 0);
const CELL_SIZE:int = 10;
const START_COLOR:int = 0xFFFFFF;

var imageWidth:int = stage.stageWidth / CELL_SIZE;
var imageHeight:int = stage.stageHeight / CELL_SIZE;
 
var bitmapData:BitmapData = new BitmapData(imageWidth, imageHeight, false); 
var colors:Object = {};
var colorIndex:int;

addColor(START_COLOR);

var bitmap:Bitmap = new Bitmap(bitmapData);
bitmap.scaleX = bitmap.scaleY = CELL_SIZE;
addChild(bitmap);

stage.addEventListener(MouseEvent.CLICK, onStageClick);
stage.addEventListener(Event.ENTER_FRAME, onStageEnterFrame);

function addColor(color:int):void {
    colorIndex++;
    colors[color] = colorIndex;
}
 
function onStageClick(e:MouseEvent):void {
    var position:int = e.localY / CELL_SIZE;
    var color:int = Math.random() * 0xFFFFFF;
    addColor(color);
    bitmapData.setPixel(0, position, color);
}
 
function onStageEnterFrame(e:Event):void {
    bitmapData.lock();
    bitmapData.copyPixels(bitmapData, bitmapData.rect, START_POINT);
    for (var i:int = 0; i < imageHeight; i++) {
        var topPixel:int = (i == 0) ? START_COLOR : bitmapData.getPixel(1, i - 1);
        var centerPixel:int = bitmapData.getPixel(1, i);
        var bottomPixel:int = (i == imageHeight - 1) ? START_COLOR : bitmapData.getPixel(1, i + 1);
        var topPixelIndex = colors[topPixel];
        var centerPixelIndex = colors[centerPixel];
        var bottomPixelIndex = colors[bottomPixel];
        var pixelColor:int;
        if (topPixelIndex >= centerPixelIndex && topPixelIndex >= bottomPixelIndex) pixelColor = topPixel;
        else if (centerPixelIndex >= topPixelIndex && centerPixelIndex >= bottomPixelIndex) pixelColor = centerPixel;
        else pixelColor = bottomPixel;
        bitmapData.setPixel(0, i, pixelColor);
    }
    bitmapData.unlock();
}
        if (topPixelIndex >= centerPixelIndex && topPixelIndex >= bottomPixelIndex) pixelColor = topPixel;
        else if (centerPixelIndex >= topPixelIndex && centerPixelIndex >= bottomPixelIndex) pixelColor = centerPixel;
        else pixelColor = bottomPixel;

И эти люди рассуждают о говнокоде, лол. Боюсь представить, как вы будете искать максимум из неизвестного числа элементов.
В условиях текущей задачи буду решать так:
function getPixelColor(...arguments):int
{
    var maxIndex:int;
    var result:int;
    var length:int = arguments.length;
    for (var i:int = 0; i < length; i++)
    {
        var color:int = arguments[i];
        var colorIndex:int = colors[color];
        if (maxIndex < colorIndex)
        {
            maxIndex = colorIndex;
            rusult = color;
        }
    }
    return result;
}


У меня тоже вопрос. Надо ли писать функцию для неизвестного числа элементов, если в задаче конкретное их конкретное число — три?
Все равно не очень. У вас же уже известны индексы, зачем передавать цвета в поиск, если вас интересует максимум среди индексов?

В вашем первом варианте в худшем случае (если чудесным образом не вмешается компилятор) будет четыре сравнения для трех элементов. Достаточно очевидно, что для нахождения максимума из N элементов достаточно N-1 сравнений. Так что да, пока пишете то, что пишете — надо.
Во-первых, эта функция используется вместо вычисления индексов. То есть код выглядит вот-так.

var topPixel:int = (i == 0) ? START_COLOR : bitmapData.getPixel(1, i - 1);
var centerPixel:int = bitmapData.getPixel(1, i);
var bottomPixel:int = (i == imageHeight - 1) ? START_COLOR : bitmapData.getPixel(1, i + 1);
var pixelColor:int = getPixelColor(topPixel, centerPixel, bottomPixel);
bitmapData.setPixel(0, i, pixelColor);


Цвета передаются потому что мы ищем не максимум среди индексов, а цвет, который соответствует максимальному индексу. Если не передавать цвета в функцию, то мы найдём индекс, но, как узнать, какой цвет этому индексу соответствует?

Во-вторых, про N-1. Допустим, пойдём этим способом, находим индекс в два сравнения. Сравнили topPixelIndex c centerPixelIndex и записали максимум. Потом сравнили полученный максимум с bottomPixelIndex и узнали, какой индекс самый большой. А теперь возвращаемся к вопросу, который я уже задавал. Как теперь узнать, какой цвет соответствует этому индексу? Опять нужно будет делать проверку.

var maxIndex:int = Math.max(topPixelIndex, centerPixelIndex, bottomPixelIndex);
if (maxIndex == topPixelIndex) pixelColor = topPixel;
else if (maxIndex == centerPixelIndex) pixelColor = centerPixelIndex;
else pixelColor = bottomPixel;


С таким вариантом в худшем случае у вас будет также четыре сравнения, плюс, дополнительная переменная. Хотя, соглашусь, получившийся код выглядит аккуратнее.

Собственно, я сам отвечу на свой вопрос. Узнать индекс быстро мы можем, если будем записывать цвета по индексу в массив. Тогда не нужно будет сравнение с If. Получится вот это.
import flash.geom.Point;
import flash.display.BitmapData;
import flash.display.Bitmap;

const START_POINT:Point = new Point(1, 0);
const CELL_SIZE:int = 10;
const START_COLOR:int = 0xFFFFFF;

var imageWidth:int = stage.stageWidth / CELL_SIZE;
var imageHeight:int = stage.stageHeight / CELL_SIZE;
 
var bitmapData:BitmapData = new BitmapData(imageWidth, imageHeight, false, START_COLOR:int); 
var indexes:Object = {};
var colors:Array = [];
// Лучше использовать Vector вместо Array, но парсер кода Habrahabr из-за этого ломает всё подсветку синтаксиса.
// var colors:Vector.<int> = new Vector.<int>();
var colorIndex:int;

addColor(START_COLOR);

var bitmap:Bitmap = new Bitmap(bitmapData);
bitmap.scaleX = bitmap.scaleY = CELL_SIZE;
addChild(bitmap);

stage.addEventListener(MouseEvent.CLICK, onStageClick);
stage.addEventListener(Event.ENTER_FRAME, onStageEnterFrame);

function addColor(color:int):void {
    indexes[color] = colorIndex;
    colors[colorIndex] = color;
    colorIndex++;
}
 
function onStageClick(e:MouseEvent):void {
    var position:int = e.localY / CELL_SIZE;
    var color:int = Math.random() * 0xFFFFFF;
    addColor(color);
    bitmapData.setPixel(0, position, color);
}
 
function onStageEnterFrame(e:Event):void {
    bitmapData.lock();
    bitmapData.copyPixels(bitmapData, bitmapData.rect, START_POINT);
    for (var i:int = 0; i < imageHeight; i++) {
        var topPixel:int = (i == 0) ? START_COLOR : bitmapData.getPixel(1, i - 1);
        var centerPixel:int = bitmapData.getPixel(1, i);
        var bottomPixel:int = (i == imageHeight - 1) ? START_COLOR : bitmapData.getPixel(1, i + 1);
        var topPixelIndex = indexes[topPixel];
        var centerPixelIndex = indexes[centerPixel];
        var bottomPixelIndex = indexes[bottomPixel];
        var maxIndex:int = Math.max(topPixelIndex, centerPixelIndex, bottomPixelIndex);
        var pixelColor:int = colors[maxIndex];
        bitmapData.setPixel(0, i, pixelColor);
    }
    bitmapData.unlock();
}


А теперь поговорим об оптимизации и читаемости. Соглашусь, последний вариант читается проще. Но также, я считаю, что читаемость первого варианта тоже хороша. Там довольно простой код. А это главное. Код должен легко читаться.

Мой первый вариант выполняется быстрее всех остальных более, чем 20% и использует меньше памяти. Когда писал этот, код я учитывал это, зная, что обращение к элементу массива во Flash медленнее, чем две операции сравнения.

Изначально у нас три пикселя, и городить дополнительную функцию для N значений, при этом заведомо замедляя работу, когда можно просто сравнить три значения при вполне читаемом коде, я не вижу ни какого смысла.
Никита, приятно познакомиться.
Вы всегда начинаете знакомство с кидания говна в собеседника?
Мне тоже приятно. Не сразу додумался до решения, которые вы предложили. Знакомство с кидания говна начинаю не всегда, только тогда, когда у меня плохое настроение. К вам лично негативных эмоций не испытываю. По-другому моё сообщение можно прочитать так: «Я взял за основу ваш код и решил его немного улучшить. Посмотрите, пожалуйста.».
Вы искали программиста, а тестовая задача для алгоритмиста. Так чего же вы хотели?
Зачем мешать все в одну кучу или у вас вакансия «компьютерщик»?
Извините, вы считаете это хоть минимально сложной алгоритмической задачей?
Видимо, тут перемешались понятия программист и кодер.
Да это именно задача на алгоритм.
С тем же успехом можно предложить задачу на поиск расстановки N ферзей на шахматной доске N на N клеток.

Многие сразу же сообразили, что в алгоритме движения наложенных друг на друга волн слева направо можно сильно оптимизировать отрисовку. Но, как не печально, многие этим вырыли себе могилу, запутавшись в своём же собственном коде


Почему так бывает? Потому что хотят задачу на алгоритм решить на языке программирования.

Да конечно есть и математики-программисты итд итп, но сути не меняет.

Минусяторы гуглите «Алгоритмист» узнаете много нового.
А алгоритмист знает, как ловить клики и выводить картинку в реальном времени?
Ну будет вам. Может мы еще биологу поставим задачу отрисовки крутящейся спирали ДНК?
Но если в этой задаче выбирать между клеточным автоматом, скользящим окном, буфером событий в каждой строке и набором «волн», то на основании чего алгоритмист может сделать такой выбор? Откуда-то придётся брать набор доступных операций отрисовки, формат их данных и «сложность» каждой из них. Иначе просто нет данных для работы… Если решать в одиночку, придётся быть компьютерщиком.
Вот хорошо, что вы заговорили о выборе алгоритма в этом вся суть. Кто же если не алгоритмист выберет оптимальный алгоритм?
Если автор скажет решить эту задачу расстановкой детских кубиков на полу задача станет не для программиста, а для детсадика?
В интерфейсе детских кубиков команда «сдвинуть изображение на пиксель вправо» выполняется за один такт. Останется реализовать построение левого столбца на языке, понятном детям. По-моему, безнадёжно.
чувак, приславший с откровенными графическими косяками, которые он знает как исправить может стать офигенным продукт-менеджером. Потому что в условия изменяющихся требований, надо показывать минимально работающий прототип
Вообще то ваше решение не совсем правильное. Ваш пример закончится либо runtime error либо после 4,294,967,295 кликов, либо по out of memory раньше. В целом решение красивое, но можно лучше.
Это зависит от ЯП (реализация целого типа данных) и/или разрядности процессора, но однозначно когда-нибудь закончится с ошибкой.
Прочитал пост и вспомнил, что в свое время делал достаточно интересную игру логическую игру на двоих vk.cc/1GSff9
Правила: pastebin.com/XtVpswb7
403
Автор — эта задача в вашей постановке весьма проста, особенно хорошо это ясно после просмотра флешки.
Я поражен тем, что некоторые кандидаты ее вообще не смогли решить, а некоторые нагородили черт знает чего.

История была бы неполной, если бы я не приложил здесь канонически правильного решения.

Еще больше я поражен этим вашим безапелляционным заявлением — особенно режет слух слово каноническое.
На каком основании вы решили что это каноническое, т.е. самое оптимальное решение решение, которое можно принять за образец?
Вы действительно уверены что нельзя придумать для этой задачи алгоритма проще и эффективнее вашего?

На самом деле, изначально его не было. Лишь к концу второго десятка «проверенных работ» я стал задумываться, а как бы я решил эту задачу…

А это вообще «убило». Я не понимаю, как можно давать задание, не зная его решения!
Как быть если в постановке задачи есть ошибки, противоречия или она вообще не имеет решения — вы не боитесь опозорится перед кандидатом как работодатель в таком случае?
> Я не понимаю, как можно давать задание, не зная его решения!

Когда я учился в ВУЗе, при выполнении некоторых лабораторных меня посещала мысль, что ментор сам не пытался её выполнить. Мысль была достаточно бредовая, и я гнал её прочь.

Когда мне довелось самому подготовить/провести пару лаб, я обнаружил, насколько много времени моего и друзей-добровольцев съедает эта вот проверка выполнимости, корректности итд, и у меня начали закрадываться подозрения по поводу происходившего… ))
Хм, у нас в ВУЗе было нечто аналогичное пару раз. Есть лаба, в методичке прямым текстом написано, что именно надо в конеце получить. На опыте получается совсем другое. Повторяем. Опять другое. Исследуем теорию, проверяем, блаблабла, доказываем, что наш результат верен. Подгоняем его под то, что нужно в методичке, зная, что это не правильно. Защищаем.
Отличная методичка и препод, который ее писал! Без шуток. Потому что именно так, на вот таких вот нестыковках и защитах, и можно чему-то научиться. Это называется «взрослая жизнь».
Согласен, про самое простое решение не стоило писать.

Про отсутствие решения. Мне это было не важно. Задача — не проверить себя, а посмотреть, как с этим справятся люди. Человек не должен быть роботом, если есть вопросы — спрашивай, если есть ошибка в задании — говори.

Я этому научился еще на первом курсе, когда на экзамене мне задали задачу с подразумеваемым ответом да или нет. Я потратил на нее часов пять, пытаясь понять где я ошибаюсь, и в итоге, когда уже это окончательно надоело, я подошел к преподу и сказал, что мне кажется, что у этой задачи в такой формулировке решения нет и вот почему… Это был правильный ответ…
Волна всегда имеет одну и ту же форму (квадрированный ромб), только видна не вся. Самое элементарное — просто двигать слева направо эти ромбы. Это решение точно так же применимо, если милые школьникам квадратики заменить на пиксели, а фронт волны превратить в окружность (или что угодно другое). Если кроме сдвига следить за размером, то кликать можно в любую точку.
Меня всегда мучило подозрение, что самая кривая среда разработки нарисует окружность в сто раз эффективнее, чем самая оптимальная моя функция. Поэтому последнее, чем я бы занялся — это ручное перекрашивание пикселей.
НЛО прилетело и опубликовало эту надпись здесь
Я правильно понимаю, что программиста Вы себе не нашли?
P.S. Подозреваю, что с таким подходом и не найдёте никогда.
Мой вариант. Не прилизывал и на собеседование в таком виде бы не отослал :)

demo view: jsfiddle.net/LMQn2/35/embedded/result/
code view: jsfiddle.net/LMQn2/35/

Делал через изменение в первом столбце. Все остальные копируют предыдущий (сдвиг).

зы. После просмотра алгоритма в 3 раза меньшего (в топике), загрустил :)
иногда цвет новой волны повторяет цвет фона и новую волну не видно :)
Эту задачу можно спокойно решить за O(height * waves), зачем сюда вплетать ширину области прорисовки?

Кроме того, совсем не обязательно в модель (которая также включает бизнес-логику, согласно определению MVC) запихивать цвета. Чтобы волны правильно перекрывали друг-друга, достаточно хранить в массиве только индексы волн. Хороший программист должен описать модель так, чтобы её спокойно понял алгоритмист, а систему представления (view/controller) так, чтобы её спокойно понял кодер.

Вот вся модель в пару десяток строк на Python:
class CanvasModel:
    def __init__(self, width, height):
        self.width, self.height = width, height
        self.waves, self.current_wave = [], 0
        self.matrix = [x[:] for x in [[0] * width] * height]

    def add_wave(self, line):
        self.current_wave += 1
        self.waves.append([self.current_wave, line, 0])
        self.matrix[line][0] = self.current_wave

    def process_wave(self, wave):
        [id, x, y], changed = wave, False
        wave[2] += 1                              # move the wave feather right
        diag1 = [p for p in zip(range(x, -1, -1), range(y, -1, -1)) if p[1] < self.width]
        diag2 = [p for p in zip(range(x+1, self.height), range(y-1, -1, -1)) if p[1] < self.width]
        for row, col in diag1:                    # process the top diagonal
            if id < self.matrix[row][col]: break  # stop in case of colliding with another wave
            self.matrix[row][col] = id            # propagate the wave index through the diagonal
            changed = True
        for row, col in diag2:                    # process the bottom diagonal
            if id < self.matrix[row][col]: break
            self.matrix[row][col] = id
            changed = True
        return changed

    def propagate(self):
        self.waves = [wave for wave in self.waves if self.process_wave(wave)]


В итоге получается модель, которую можно отрисовать хоть индексированными цветами, хоть градиентами, хоть вообще не рисовать (например, для юнит-тестов). И самое главное, никаких зависимостей.

Ну и для примера код отрисовки для вышеприведённой модели на curses (только консоль, только хардкор!)
Код для Curses
import curses
import time
import threading

def main(screen):
    colors = ['BLACK', 'BLUE', 'CYAN', 'GREEN', 'MAGENTA', 'RED', 'WHITE', 'YELLOW']
    curses.mousemask(curses.BUTTON1_PRESSED)
    [curses.init_pair(i + 1, 0, getattr(curses, 'COLOR_' + color)) for i, color in enumerate(colors)]
    canvas = CanvasModel(80, screen.getmaxyx()[0] - 1)
    threadLock = threading.Lock()
    
    def update_time(screen):
        while True:
            canvas.propagate()
            screen.clear()
            threadLock.acquire()
            for line in canvas.matrix:
                for elem in line:
                    screen.addstr(" ", curses.color_pair(elem % len(colors) + 1))
                screen.addstr("\n")
            screen.refresh()
            threadLock.release()
            time.sleep(.02)
    
    clock = threading.Thread(target=update_time, args=(screen,))
    clock.daemon = True
    clock.start()
    
    while True:
        event = screen.getch()
        if event == curses.KEY_MOUSE:
            line = curses.getmouse()[2]
            if line < canvas.height:
                threadLock.acquire()
                canvas.add_wave(line)
                threadLock.release()
        else:
            break
    
    curses.endwin()

if __name__ == "__main__":
    curses.wrapper(main)
Красиво. Но, к сожалению, последующая отрисовка потребует пересчета цветов для всей матрицы — ведь алгоритм не оставил информации, какие ячейки изменились. Так что «вплетать ширину области прорисовки» (и добавить слагаемое O(width * height)) всё равно придётся. Или надо будет сообщать о каждом изменении ячейки, что уже не так красиво.
На экране есть сетка M на N из цветных квадратиков. Нужно реализовать на этой сетке следующий эффект — по клику слева направо со скоростью V пробегает волна, меняя цвет квадратиков на другой (единый для всей волны). Эффект должен работать при любых значениях M, N, V. Волна начинается всегда у левой стенки. Одновременно может идти несколько волн разного цвета.


Пробегает? С какой скоростью? Один пиксель за квант времени? Каков квант времени? Имеет ли пользователь возможность кликать между квантами времени, или регистрация кликов идёт по тем же квантам, что и передвижение волн?
Откуда из текста задания можно понять, что волна должна идти усечённым клином?
Откуда в задании следует, что для каждой следующей волны цвет должен отличаться от предыдущей (или от всех на данный момент видимых на сетке)?

В вашем задании полно неясностей. Стоило ли ждать чего-то иного от соискателей?
Автор ожидал, что соискатели сами уточнять спорные или опущенные моменты. Доля логики в этом имеется.
ИМХО с такими вопросами — соискатель уже не прошел. Провален тест на самостоятельность. :)
Ну, если вопросы задавать нельзя или не нужно, то решение задачи упрощается до следующей: при щелчке экран окрашивается в какой-то цвет, причём всё время в один и тот же.
… или тест на адекватность. :)
Автор хорошо описал сильно углубляющихся кандидатов в параграфе Я не ищу простых путей!. Довольно тяжело оценить адекватность подхода к решению неточно поставленной задачи.
Кстати, ещё вопрос: откуда следует, что волна должна идти из какой-то заданной по вертикали точки, это определяется по щелчку? Вопрос встаёт только в случае положительного ответа на вопрос про клин.

Богатый опыт показывает, что без уточняющих вопросов возникают большие проблемы при сдаче проекта заказчику, который хотел совсем другое, чем подумал программист что же хотел заказчик. Иногда время на уточнение пожеланий превышает время на исполнение задания, но всегда покрывает то время, которое нужно на доделку того, что не было детально оговорено.

Не вижу смысла так путать программиста на тестовом задании. Если есть желание понять, как он думает в том случае, когда задание сформулировано неточно, как домысливает за заказчика, задаёт или нет наводящие вопросы — это одно. А понять как он может выполнить досконально понятное техническое задание — совсем другое.
Спасибо за статью и задание. Всегда полезно лишний раз проверить свою квалификацию.
bitbucket.org/ssoldatenko/wavetesttask
Сделал на java + swing. MVC, но Controller не выделен в отдельный класс, вместо него onMouseCliecked() и onTimerTick()
Использовал массив, волну рисовал целиком (в невидимой левой части), сдвигал — System.arraycopy()
«заработало» через 1.5 часа. На приведение в порядок и заливку в онлайн еще чуть больше 2х часов.
Регулируется ресайзом окна, и параметрами коммандной строки.
Зарегистрируйтесь на Хабре , чтобы оставить комментарий

Публикации

Истории