Лучшие решения для задач Microsoft на собеседовании. Разделите массив на N подмножеств со сбалансированной суммой.

Описание:

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

Пример:

вход {1, 2, 3, 4, 5} n = 3

вывод [[5], [1,4], [2,3]];

Решение:

Обычно эта задача выглядит как типичная проблема с разделами https://en.wikipedia.org/wiki/Partition_problem

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

Есть много подходов к решению этой проблемы, оптимизированных для особых случаев. В случае, если мы ничего особенного не знаем о входных данных и требованиях, поэтому, на мой взгляд, лучшим решением будет использовать самый простой и базовый подход - жадный алгоритм. Https://en.wikipedia.org/wiki/Greedy_algorithm

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

Код C ++:

vector<vector<int>> part(const vector<int> & v, int n) {
    int v_size = v.size();
    // in this vector we will keep sums of the partitions
    vector<int> sums(n, 0);
    
    // in this priority queue we will keep values of the priorities
    // it is just numbers from 0 to numbers of partitions. 
    // We will use these numbers as indexes  
    // to access sums and to definition priorities of the partitions
    // in other words the sums tied with the partitions by 
    // these priority values.
    
    // Pay attention that the sums we keep in the external 
    // vector described above, 
    // so we need to declare a special comparator
    // for the queue in order to sort the queue by the 
    // priority values.
    auto compare = [&sums](int a, int b) { 
        return sums[a] >= sums[b]; 
    };
    priority_queue<int, std::vector<int>, 
                   decltype(compare)> pq(compare);
    // here we will keep values of the partitions
    vector<vector<int>> result(n, vector<int>());
    // generate numbers of the priority values.
    for (int i = 0; i < n; i++) {
        pq.push(i);
    }
    // The input array is sorted ascending so we will process 
    // it from the back to the front.
    for (int i = v_size - 1; i >= 0; --i) {
        // take the highest priority from the queue
        int c = pq.top(); pq.pop();
        // put the max value from the input array to the partition 
        // with the highest priority, 
        // that is partition with the lowest sum.
        result[c].push_back(v[i]);
        // increase the lowest sum to max value from 
        // the input array.    
        sums[c] += v[i];
        // push back the priority value. After this call the queue 
        // will be resorted corresponding to 
        // new value of the sums array.
        pq.push(c);
    }
    return result;
}

Репозиторий с полной версией проекта вы можете найти здесь: https://github.com/jolly-fellow/microsoft/tree/master/partition_array_into_n_subsets_with_balanced_sum

Вернуться к оглавлению.

Лучшие решения для задач Microsoft на собеседовании. Разделите массив на N подмножеств со сбалансированной суммой.