Problem Statement:
You are working on an Amazon Data Center you are required to reduce the amount of main memory cosumption by the processes.
Given list of processes where each value representing memory consuption by the process and given one variable m representing number of processes to be removed. We need to delete m number of processes from the list in contiguous manner and return minimum amount of main memory used by all the proccesses running after deleting contiguous segment of processes.
Example - processes = {10,4,8,13,20}, m = 2;
output = 22 [removing 13 and 20 as its consuming large memory]
Constraints:
1<N<1000000000 //size of the array
1<m<100000 //contigous segment of the array.
1<process[i]<1000000000
Try to figure out the approach before heading to the solution it will help you to develop problem solving skills.
Approach:
It is simply solved using Fixed Size Sliding Window Approach
Steps:
1. First, calculate the total sum of the whole array. It is required to get the final answer because we have to remove the maximum contiguous block from the array.
2. Now, use the fixed-size sliding window logic to find the maximum contiguous subarray sum of size `m`.
3. For the final answer, just take the difference between the total sum and the maximum contiguous subarray sum.
Code:
public class Amazon{
public static void main(String[] args) {
int [] arr={5, 3, 9, 7, 4, 1, 8};
int n=arr.length;
int m=3; //windows size
int totalsum=0;
for(int i:arr) totalsum+=i;
int i=0;
int j=0;
int sum=0;
int maxSumSubarray=0;
while(j<n){
sum+=arr[j];
if(j-i+1<m) j++;
else if(j-i+1==m){
maxSumSubarray=Math.max(maxSumSubarray,sum);
sum-=arr[i];
i++;
j++;
}
}
System.out.println(totalsum-maxSumSubarray);
}
}
Google OA Problem Based on Hashing:
If you have any doubt feel free to ask in comments😊
Well explained
ReplyDelete