Company: AT&T
Difficulty: medium
In a machine learning project, there are n computational units, each with its unique computational capacity, represented by an array called storage . Partition computational units into machine learning models with minimal replacements. Given: An array storage of n computational units An integer k representing the desired number of models The objective is to: Partition the array into k subarrays Each subarray must form a valid permutation (containing integers 1 to m in any order, where m is the length) In order to complete a permutation, any computational unit can be replaced with another that has any capacity. Find the minimum number of replacements needed ( minOp ) Return the lexicographically smallest array of model capacities ( modelCap ) Example n = 6 k = 2 storage = [2, 3, 1, 5, 6, 2] One optimal partition is [[2], [3, 1, 5, 6, 2]]: [2] can be converted to [1] in one operation [3, 1, 5, 6, 2] can be converted to [3, 1, 5, 4, 2] in one operation This requires minOp = 2 replacements