Problem 2

Amazon Web Services (AWS) has several data centers which have multiple processors that perform computations. In one such data center, these processors are placed in a sequence with their IDs denoted by 1, 2, ..., n. Each processor consumes a certain amount of power to boot up, denoted by bootingPower[i]. After booting, a processor uses processingPower[i] of power to run the processes. For maximum utilization, the data center wishes to group these processors into clusters. Clusters can only be formed of processors located adjacent to each other. For example, processors 2, 3, 4, 5 can form a cluster, but 1, 3, 4 cannot.

The net power consumption of a cluster of k processors (i, i+1, ..., i+k−1) is defined as:

net_power = \
    max(bootingPower[i, i+1, ..., i+k-1]) + (sum of processingPower[i to i+k-1]) * k

That is, net power consumption = maximum booting power among the k processors + (sum of processing power of processors) * k.

A cluster of processors is said to be sustainable if its net power consumption does not exceed a given threshold value powerMax.

Given the booting power consumption and the processing power consumption of n processors denoted by bootingPower and processingPower respectively, and the threshold value powerMax, find the maximum possible number of processors which can be grouped together to form a sustainable cluster. If no such clusters can be formed, return 0.

Example

processingPower = [2, 1, 3, 4, 5]
bootingPower = [3, 6, 1, 3, 4]
powerMax = 25

If k = 2, any adjacent pair can be chosen. The highest usage is the pair [4,5] with net power consumption 4 + (4 + 5) * 2 = 22. Next, try k = 3. Group the first 3 processors together as:

Maximum Power = 25
Cluster of 3 processors
Maximum booting power = 6
Sum of processing power = 6
Net Power Consumption = 6 + 6 * 3 = 24

Here,

Maximum booting power = max(3, 6, 1) = 6
Sum of processing powers = 2 + 1 + 3 = 6
Thus, net power consumption = 6 + 6 * 3 = 24 ≤ powerMax

Thus, we can group k = 3 processors to form a sustainable cluster. Note that the minimum power consumption to form a cluster of k = 4 processors is 46, by forming a cluster of the first 4 processors. Since this cost is greater than the threshold, we cannot form a cluster with 4 processors. The maximum possible cluster size is 3.

Function Description

Complete the function findMaximumSustainableClusterSize in the editor below.

Parameters

int processingPower[n]: the power consumption of each processor in running the processes
int bootingPower[n]: the power consumption of each processor in bootup
long_int powerMax: the threshold power consumption

Returns

int: the maximum cluster size which is sustainable, if no cluster exists, return 0.

Constraints

1 ≤ n ≤ 10^5
1 ≤ powerMax ≤ 10^14

Note: It is not mandatory for all clusters of size k to be sustainable. Even one such cluster is sufficient.

Solution

This problem can be approached as a sliding window problem given the constraint:

Clusters can only be formed of processors located adjacent to each other.

Therefore, starting at index zero, the window is adjusted such that a sustainable cluster is formed when the following criteria is met:

net power consumption = maximum booting power + (sum of processing power) * k

where net power consumption ≤ max power (powerMax). The maximum cluster size is then the largest sustainable cluster.

This approach is suboptimal, since it uses a double-nested loop. That is, the time complexity is O(n^2).

Instead, this problem can be solved in linear time (O(n)) using a monotonic queue (or monotone priority queue), a variant of a priority queue in which the priorities of extracted items are required to form a monotonic sequence (i.e., for all n ∈ N a_n+1 ≥ a_n for monotonically increasing and a_n+1 ≤ a_n for monotonically decreasing).

Using a monotonically decreasing queue, the processor with the maximum booting power for the current cluster under consideration is maintained at the front of the queue. For each processor i, we remove any elements from the queue with a smaller booting power in order to maintain the monotonically decreasing property. If the window for the cluster of processors changes (e.g., when the start index is increased by one because the net power of the current cluster exceeds the max power), the processor at the front of the queue is removed.

If a monotonically decreasing queue is not used, the maximum booting power would need to be calculated for each window, thus necessitating the double-nested loop of the naive solution, which scales with n.

NOTE: While there is a nested loop in this solution as well, the total number of operations across all iterations of the inner loop is bounded by O(n). This is known as amortized analysis - even though there's a nested loop, the total work done by that inner loop across all iterations of the outer loop is linear.

package main

// Complete the 'findMaximumSustainableClusterSize' function below.
//
// The function is expected to return an INTEGER.
// The function accepts the following parameters:
//  1. INTEGER_ARRAY processingPower
//  2. INTEGER_ARRAY bootingPower
//  3. LONG_INTEGER powerMax

import (
	"github.com/gammazero/deque"
)

// findMaximumSustainableClusterSizeNaive finds maximum sustainable cluster
// size using a sliding window.
func findMaximumSustainableClusterSizeNaive(
	processingPower []int32, bootingPower []int32, powerMax int64) int32 {
	// This problem can be approached as a sliding window problem given the
	// constraint:
	//
	//   >Clusters can only be formed of processors located adjacent to each
	//    other.
	//
	// Therefore, starting at index zero, the window is adjusted such that the
	// maximum cluster is formed when the following criteria is met:
	//
	//   net power consumption = maximum booting power + (sum of processing power) * k
	//
	// where net power consumption ≤ max power.
	maxClusterSize := 0
	numProcessors := len(processingPower)
	// Calculate the largest sustainable cluster starting with processor i
	for i := 0; i < numProcessors; i++ {
		clusterSize := 1
		sumProcessingPower := int64(processingPower[i])
		maxBootingPower := int64(bootingPower[i])

		// Calculate the inital net power consumption
		power := maxBootingPower + sumProcessingPower*int64(clusterSize)
		if power <= powerMax && clusterSize > maxClusterSize {
			maxClusterSize = clusterSize
		}

		// Attempt to add processor j to the cluster.
		for j := i + 1; j < numProcessors; j++ {
			// Recalculate maximum booting power
			if int64(bootingPower[j]) > maxBootingPower {
				maxBootingPower = int64(bootingPower[j])
			}
			// Recalculate sum of processing power
			sumProcessingPower += int64(processingPower[j])
			clusterSize++
			power = maxBootingPower + sumProcessingPower*int64(clusterSize)
			// If the cluster is sustainable (net power consumption does not exceed
			// powerMax) and is greater than the current maximum cluster size, update
			// maxClusterSize
			if power <= powerMax && clusterSize > maxClusterSize {
				maxClusterSize = clusterSize
			}
		}
	}
	return int32(maxClusterSize)
}

// findMaximumSustainableClusterSizeOptimal finds maximum sustainable cluster
// size using a monotonic queue.
func findMaximumSustainableClusterSizeOptimal(
	processingPower []int32, bootingPower []int32, powerMax int64) int32 {
	// A monotonic queue (or monotone priority queue) is maintained with the
	// maximum booting power of the current group of processors.
	//
	// The monotonic queue is implemented using a deque in order to efficiently
	// add and remove items at either end with O(1) performance.
	//
	// Pointers to the start and end of the sliding window are maintained in
	// order to preserve the following criteria:
	//
	//   net power consumption = maximum booting power + (sum of processing power) * k
	//
	// where net power consumption ≤ max power.
	//
	// NOTE: In order to preserve the bounds of the sliding window, the deque
	// holds the indices of bootingPower, not its values.
	var mq deque.Deque[int]
	maxClusterSize, clusterSize, start, end := 0, 0, 0, 0
	var sumProcessingPower int32 = 0
	for end < len(processingPower) {
		// Remove elements from the back of the queue until the queue is empty or
		// the element at the back of the queue is greater than the current
		// element, then append the current element to the back of the queue.
		for mq.Len() > 0 && bootingPower[mq.Back()] < bootingPower[end] {
			mq.PopBack()
		}
		mq.PushBack(end)
		maxBootingPower := bootingPower[mq.Front()]
		sumProcessingPower += processingPower[end]
		power := maxBootingPower + sumProcessingPower*int32(clusterSize)
		clusterSize++
		if int64(power) <= powerMax {
			end++
		} else {
			sumProcessingPower -= processingPower[start]
			clusterSize--
			start++
			end++
		}
		if clusterSize > maxClusterSize {
			maxClusterSize = clusterSize
		}
		// Preserve the bounds of the sliding window by checking that the element
		// at the front of the queue is still within the window. If not, remove it.
		if start > mq.Front() {
			mq.PopFront()
		}
	}
	return int32(maxClusterSize)
}

Source

Solution

grind.rip