JavaRush /Java блог /Архив info.javarush /Тестовое задание "Image Comparison"
Roman_kh
33 уровень
Харьков

Тестовое задание "Image Comparison"

Статья из группы Архив info.javarush

Привет всем, дорогие читатели и форумчане!

Отличная идея начать выставлять тестовые задания для тех, кто хочет себя попробовать перед собеседованием. Начал эту тему и я вспомнил, что у меня тоже есть пара задач.
Здесь я выставлю только условие задания, в комментариях можно обсуждать алгоритм решения. Задание, как и водится, будет на английском.
  • The output of the comparison should be a copy of one of the images image with differences outlined with red rectangles as shown below.
  • We need to see your own code. No third party libraries and borrowed code is allowed.
  • Target completion time is 2 hours, but you may choose to use up to 4 hours. Submissions sent after 4 hours will be disqualified. Note that in addition to quality, time is also factored into scoring the task. The closer you get to 2 hours the higher is the score.
  • Тестовое задание Тестовое задание Тестовое задание
    Nice to have
    • It should be possible to exclude certain parts of the image from comparison, for example a clock or dynamically generated number. They will be provided by the caller as a list of rectangles to exclude.
    • Provide some sort of UI either as a web page or GUI that allows the user to select the images and view differences as an overlay on either of the images.
    Expected Deliverables
    • Source code.
    • Binary version of the algorithm that runs and produces output of comparison. No build should be required.
    • Output image showing the result of comparison.
    Tips and Hints
    • Use javax.imageio.ImageIO to read/write images.
    • Consider java.awt.image.BufferedImage#createGraphics() to draw on in-memory images.


    От себя хочу добавить, что хорошим тоном будет еще написать JUnit тесты для всего этого добра. Для этого нужно будет использовать какую-то систему сборки проектов Ant/Maven/Gradle чтобы подтянуть либу для JUnit.

    Ставим "+" на статье, если была полезна. Решаем ее, прокачиваем свои скиллы. Она попадалась у меня в двух компаниях! См. также мои другие статьи:
    Тестовое задание: "Написать Интерпретатор на язык BrainFuck"
    Тестовое задание "Image Comparison" Java - быстрее, сильнее и выше! Зарплаты украинских программистов. История успеха спустя 1.5 года от начала обучения
    Технические вопросы на собеседовании.
    Как найти работу? Рассылка резюме
    Профессиональное выгорание. Как устоять?
    Английский для IT и для собеседования
    Паттерн Command своими словами.
    Паттерн Singleton своими словами.
    Как создать исполняемый jar в Intellij IDEA / how to create jar in IDEA
    Помогите, нужна мотивация!

    Подписывайтесь на мой блог Паттерны Проектирования пишите в нем статьи!">
    Комментарии (25)
    ЧТОБЫ ПОСМОТРЕТЬ ВСЕ КОММЕНТАРИИ ИЛИ ОСТАВИТЬ КОММЕНТАРИЙ,
    ПЕРЕЙДИТЕ В ПОЛНУЮ ВЕРСИЮ
    Artem_Novikov Уровень 40
    9 августа 2017
    2 часа? да у меня бы 2 недели заняло
    Javin Уровень 7
    11 февраля 2017
    Просьба к тем, кто решил тестовое задание разбить свои решения на этапы и сформулировать промежуточные задачи, которые привели бы и остальных к пониманию алгоритмов и их реализации. Просто выложить решение, конечно, — проще, но учитывая специфику сайта и взаимопомощь участников форума, хотелось бы не просто ознакомиться с решениями…
    Мои попытки разбить задание на этапы и прийти к решению оказались безуспешными. Задачу-то, что сам сформулировал решил, а дальше куда идти не понимаю.
    Joysi Уровень 41
    8 февраля 2017
    Может немного усложним задачу?
    Необходимо найти в изображении последовательности из трех цифр и вывести их:
    P.S. Понятно, что за 4 часа не получится уложиться, но решать возможно будет интересно.
    Joysi Уровень 41
    8 февраля 2017
    Интересная задачка, тоже решил поалгоритмичать :)
    Собственно кодирование «в лоб» заняло 1.5 часа(правда я до этого умел работать с изображениями и не тратил времени на эту часть). Далее не понравился выход:

    Хотелось следующего:


    Дополнительные штрихи с выделениями областей + «макияж» кода (вынес из функций все захардкоженные цифры/строки в блок констант, ввел начальную валидацию, сделал небольшую обработку ошибок, комментарии и JavaDoc описание функций) довели общее время до почти двух с половиной часов.

    UI не делал, сделал консольную утилиту, где в параметрах командной строки задаются имена 2х выходных файлов и выходного с выделенными областями. JUnit тоже не стал прикручивать (с ним добавился бы час-полтора, так как придется для тестов генерировать различные массивы с областями, создавать моки для анализа вывода в консоль и т.п.).

    Общая схема была такая:
    1. Валидация
    2. Ищем пиксели, отличные в 2х картинках (вынес в отдельный массив, в отличии Himeg так как при работе было удобно маркировать элемент массива a значениями трех категорий:
    a=0 — точки в двух изображениях не отличаются в рамках допущения
    a=-1 — точка отличается, но в данный момент не приписана никакой области
    a>0 — точка приписана области a (где a=1,2....) )
    3. Строим области
    4. Раздвигаем границы областей
    5. Схлопываем пересеченные области
    6. Рисуем рамки областей и сохраняем итоговый файл.
    Javin Уровень 7
    6 февраля 2017
    А не поможет ли решение этой более простой задачи в создании одного из алгоритмов для тестового задания от «Image Comparison»?

    Задание: Вписать три случайные клетки в решётке в один минимальный по размерам прямоугольник. Вывести на консоль координаты вершин одной из его диагонали.
    Примечание: Координаты клетки 1: (2; 4), клетки 2: (4; 5), клетки 3: (3; 1).

    P.S.
    Искренне радуюсь за Himegа и остальных, кто быстро и верно находит нужные алгоритмы и реализует их программно. Молодцы!
    Himeg Уровень 15
    5 февраля 2017
    Заняло более четырех часов, но, тем не менее, получилось.
    Некоторые комментарии:
    1. Вопреки тому, что я предположил в первом сообщении, массив соответствия можно не создавать.
    2. Разница в 10% между пикселями действительно реализуется просто.
    3. Обведение прямоугольником: при сравнении изображений создается список координат всех отличающихся пикселей. Рекурсивный метод находит координаты диагоналей всех прямоугольников, которыми нужно обводить отличающиеся области, и рисует их в файл. Если я хоть слово напишу дальше, то будет жёсткий спойлер))

    А, да, чуть не забыл про JUnit тесты))))))))))
    alexeyfrei Уровень 34
    4 февраля 2017
    мде… я справился за 4 часа и 8 минут :/ без всяких гуи и юнит тестов, правда. но это от того, что я еще понятия не имею про гуи и юнит тесты, так что на это у меня неделя бы ушла.
    с 10% отклонением — просто, а вот обведение области прямоугольником я даже не думал, что будут сложности, пока не попробовал реализовать.
    по итогу, загнал все отличающиеся пиксели в список и потом перебирал его, попутно создавая новый список в который уже помещались области и ними же сравнивал пиксели.
    Torin Уровень 27
    4 февраля 2017
    У меня просьба ко всем не выкладывать пока решение, а договориться и выкатить в один день всем вместе. Просто у меня не всегда есть 3-4 часа сосредоточенно кодинга
    JuriMik Уровень 26
    3 февраля 2017
    Делал такое. Правда время ограничено было двумя часами, я не уложился, поэтому с рисованием квадратиков не срослось и я просто подсвечивал область, где были отличия, красным.
    Fry Уровень 41
    3 февраля 2017
    оо, делал когдато такое. суть решения маркировать области где не совпадают пиксели (дистанция больше 10%) а потом уже по областях рисовать квадратики. Помню на решение потратил около 2- ух часов. Не оптимально было, но работает. Области искал рекурсивным обходом писклей от первого найденного. Кому интересно, могу дать решение.