dimagithahahab/yadro-containers

Тестовое задание на позицию «Инженер-стажёр по разработке ПО для систем хранения данных на Go»

Алгоритм

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

1. Посчитаем количество шаров каждого цвета.
2. Определим вместимость каждого контейнера.
3. Отсортируем списки количеств шаров каждого цвета и вместимостей контейнеров по возрастанию.
4. Сравним отсортированные списки. Например, если самый маленький контейнер может вместить 2 шара, то должен существовать самый редкий цвет, в который окрашены только 2 шара, и наоборот.

Запуск

1. git clone https://github.com/DimaGitHahahab/yadro-containers
2. Перейти в корень проекта
3. go run ./cmd/main.go

Почему алгоритм всегда работает

Если соответствие найдено, то покажем, что действительно можно разложить шары по соответствующим контейнерам только с помощью swap-операций.

Представим, что все шары лежат в одном большом массиве, но вместо цвета шара в качестве значения используется номер контейнера, которому соответствует этот шар. Тогда наша задача сводится к сортировке этого массива только swap-операциями. Например, подойдет модифицированный selection sort: если элемент уже находится в подмассиве (диапазоне индексов) относящемуся к своему контейнеру, то пропустим его, это относится как к элементу рассматриваемому во внешнем цикле, так и во внутреннем:

for (i = 0; i < n - 1; i++) {
    for (j = i + 1; j < n; j++) {
        if (i in range(container(a[i])) or j in range(container(a[j])))
            continue;
        if (a[i] > a[j]) {
            swap(a[j], a[i]);
        }
    }
}

На самом деле, чтобы ответить на вопрос задачи, не нужно реализовывать шаги из доказательства (класть элементы в большой массив, сортировать и т.д.). По условию нужно уметь отвечать на вопрос "возможно ли отсортировать", а не сортировать.