Skip to content

Latest commit

 

History

History
133 lines (73 loc) · 10.3 KB

perfect-rectangle.md

File metadata and controls

133 lines (73 loc) · 10.3 KB
Raw

Perfect Rectangle

Задача

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

Задача на LeetCode.

Вопросы

На собеседовании важно задавать уточняющие вопросы, чтобы полностью понять условия задачи.

  1. Уточнение входных данных:

  • Каков формат входных данных? Например, массив координат углов прямоугольников представлен в каком формате (двумерный массив, список пар координат и т.д.)?

    Каждый прямоугольник представлен массивом 4 чисел, пары соседних чисел соответствуют координатам (x, y) левого нижнего и верхнего правого углов.

  • Какие типы значений могут принимать координаты углов прямоугольников? Целые числа, числа с плавающей точкой или что-то еще?

    Целые числа -1e5 до 1e5

  • Нужно ли валидировать входные данные?

    Нет. Считаем, что валидацией занимается другая функция.

  1. Условия слияния прямоугольников:

  • Как располагаются прямоугольники относительно осей координат?

    Всегда параллельно.

  • Какие условия должны быть выполнены для того, чтобы два прямоугольника можно было сложить мозаикой? Например, они должны быть обязательно смежными или могут перекрываться частично?

    Должны быть смежными. Пересечения или, напротив, пустоты запрещены.

  1. Ожидаемый результат:

  • Желаемый формат вывода решения задачи. Например, нужно ли вернуть координаты углов результирующего прямоугольника или просто булево значение, указывающее, возможно ли сложить прямоугольники мозаикой?

    Просто булево значение. Вернуть True если можно, в противном случае False .

  1. Алгоритмический подход:

  • Существуют ли какие-либо оптимизационные требования к решению задачи? Какие объемы входных данных?

    Количество прямоугольников от 1 до 2 * 1e4 .

Время спросить про примеры, а лучше предложить свои.

Примеры

True . Прямоугольники складываются в мозаику.

False . Прямоугольники не складываются в мозаику, так как есть пустота между прямоугольниками.

False . Прямоугольники не складываются в мозаику, так как есть наложение прямоугольников.

Решение методом перебора (brute-force)

Метод перебора в данной задаче подразумевает проверку всех возможных комбинаций прямоугольников:

  • Два вложенных цикла, проверяем каждый прямоугольник со всеми остальными;
    • Проверяем на пересечения, если есть — проверяем следующую пару;
    • Проверяем на пустоты, если есть — проверяем следующую пару;
    • Если добрались сюда, то нет ни пересечений ни пустот — возвращаем True;
  • В противном случае, возвращаем False.

Сложность данного решения O(N^2) , надо перебрать ~1e8 элементов. Допустимо ли данная сложность? Важно задать этот вопрос. Может нам надо выполнить эту программу один раз и выкинуть, и зачем тогда писать оптимальное решение. Ответ: Хотим запускать для серии запросов ( ~1e3 ) и общее время тогда превысит разумные границы, желательно написать решение за линию.

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

Первый подход

Что если считать площадь?

  • Бежим по всем прямоугольникам;
    • Складываем площади;
    • Подновляем максимальный и минимальный x, y — углы «большого» прямоугольника, в который вписывается мозаика;
  • Проверяем, что площадь описывающего прямоугольника равна сумме площадей.

Это будет работать для примеров выше. Это ловушка! 😅

На этом месте хороший интервьюер может намекнуть «вы уверены, что это будет работать всегда?». Важно ловить такие намеки.

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

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

Нужно искать другое условие, необходимое и достаточное.

Второй подход

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

Соответствия противоположных углов друг другу, кроме ровно 4.

Другой вариант — представить себе, что соседние прямоугольники раскрашены в два цвета в шахматном порядке.

Тогда можно сказать, что каждому углу одного цвета должен соответствовать угол другого цвета.

Алгоритм:

  • Заводим хеш-мап со счетчиками;
  • Бежим по всем прямоугольникам:
    • Для каждого угла с противоположной стороны, прибавляем и отнимаем единицу соответственно (считаем противоположные углы);
    • Обновляем максимальный и минимальный x, y — углы «большого» прямоугольника, в который вписывается мозаика;
  • Проверяем счетчики для каждой точки:
    • Возвращаем True если все счётчики равны 0 (углы, которым нашлась пара и они друг друга уравновесили), кроме ровно 4 точек (для которых не нашлось пар, это должно быть внешние углы прямоугольников с краю) и координаты этих 4 точек совпадают с углами «большого» прямоугольника;
    • Иначе возвращаем False;

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

Сложность данного решения O(N) , где N — количество прямоугольников, так как мы проверяем каждый прямоугольник один раз. Аналогично по памяти. Потребуется хранить счетчики в количестве пропорциональном количеству прямоугольников.

P. S. Обсудить можно в телеграм-чате любознательных программистов. Welcome! 🤗

Подписывайтесь на мой твитер или канал в телеграме, чтобы узнавать о новых разборах задач.