User Roman_kh
Roman_kh
33 уровень
Харьков

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

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

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

Отличная идея начать выставлять тестовые задания для тех, кто хочет себя попробовать перед собеседованием. Начал эту тему и я вспомнил, что у меня тоже есть пара задач.
Здесь я выставлю только условие задания, в комментариях можно обсуждать алгоритм решения. Задание, как и водится, будет на английском.
  • 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
    Помогите, нужна мотивация!

    Подписывайтесь на мой блог Паттерны Проектирования пишите в нем статьи!">
    Комментарии (29)
    ЧТОБЫ ПОСМОТРЕТЬ ВСЕ КОММЕНТАРИИ ИЛИ СДЕЛАТЬ КОММЕНТАРИЙ,
    ПЕРЕЙДИТЕ В ПОЛНУЮ ВЕРСИЮ
    Gnoemes Уровень 8, Ижевск
    10 августа 2017
    Ура!
    Смог реализовать, правда на это ушло около 10 часов (пока даже не джуниор).
    Больше всего времени потратил на рекурсивный алгоритм расширения областей (около 5-6 часов).
    Остальное же время ушло создание более менее не убого GUI и ввод/вывод. Оставлю ссылку на репозиторий, а результат вот:
    Artem_Novikov Уровень 40, Харьков, Украина
    9 августа 2017
    2 часа? да у меня бы 2 недели заняло
    FutureSenior Уровень 6
    3 августа 2017
    друзья!
    Помогите, не понимаю как это сделать… Может кто-то объяснить? В лс, если никто не хочет видеть.
    Javin Уровень 7, Stockholm, Швеция
    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. Рисуем рамки областей и сохраняем итоговый файл.
    FarRenGate Уровень 26, Амстердам, Беларусь
    8 февраля 2017
    Добил-таки задание, ушло явно больше 4 часов, но вроде работает как положено. Хорошая задачка, решал с интересом. Поиск различных пикселей занял совсем немного усилий, вот над квадратиками чуть мозги не вскипели
    Javin Уровень 7, Stockholm, Швеция
    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% отклонением — просто, а вот обведение области прямоугольником я даже не думал, что будут сложности, пока не попробовал реализовать.
    по итогу, загнал все отличающиеся пиксели в список и потом перебирал его, попутно создавая новый список в который уже помещались области и ними же сравнивал пиксели.