Find minimum buckets required to hold all the elements in an array


  • 2
    D

    I was asked this question in Microsoft

    You are given an array of integers and bucket capacity k(sum of the elements in the bucket should not exceed k), return minimum buckets required to hold all the elements in the array. You are required to return list of buckets not number of buckets.

    Example.
    Arr = [7,3,5,4,1] and bucket size is 9.
    return --> [ [7,1],[5,4],[3]]. if multiple answer is possible with same number of buckets then return any of them.

    Followup Question ---> in case of multiple answer return buckets such that maximum difference between sum of elements in the buckets should be minimum.

    so for above example return [ [7],[5,1],[4,3] ],
    1st bucket sum = 7
    2nd bucket sum = 6
    3rd bucket sum = 7

    maximum difference between bucket =1 (which is minimum).


  • 1

    For the first part, a greedy approach seems about right. I simply try to pack in as much as I can into every bucket. However I make sure that I try to add at least one small number for every big number I add. This makes sure I don't waste buckets by only adding maximally or minimally.

    vector<vector<int>> guessBuckets(vector<int> &arr, int maxCap) {
      vector<vector<int>> ans;
    
      sort(arr.begin(), arr.end());
    
      int i = 0, j = arr.size()-1, sum = 0;
      vector<int> temp;
    
      while(i <= j) {
    
        while(i <= j) {
          // try to add bigger number
          if(sum + arr[j] <= maxCap) {
            temp.push_back(arr[j]);
            sum += arr[j--];
          }
    
          // try to add smaller number
          if(i <= j && sum + arr[i] <= maxCap) {
            temp.push_back(arr[i]);
            sum += arr[i++];
          } else
            break; // can't add anymore
        }
    
        ans.push_back(temp);
    
        temp.clear();
        sum = 0;
      }
    
      return ans;
    }
    

    For arr[] = [7, 3, 5, 4, 1], it returns answer as [[7, 1], [5, 3], [4]].

    Dunno about the followup question. Maybe we can do something with the mean of the array. For example, for the aforementioned case:

    • The sum of the array is 20.
    • If each bucket could hold a max sum of 9, then we need about ceil(20/9) == 3 buckets in an ideal world. (Incidentally this is also the correct answer. NOTE: This is not guaranteed to be true every time.)
    • So the mean sum inside each bucket should be around floor(20/3) to ceil(20/3) == 6 to 7. If you look at the optimal answer [[7], [5,1], [4,3]], one can see very well that each bucket has a sum in the mean range.

    Perhaps that is the secret: Running a greedy algorithm with a maximum sum up to the mean and not the maximum capacity. However I don't see how it ensures the total minimum number of buckets.

    Honestly, determining a global optimal bucket configuration sounds like a NP problem. Will sit on it, I guess.


  • 0
    A
    public static void listBuckets(int[] in, int bucketsize) {
    		Arrays.sort(in);
    		List<List<Integer>> finalL = new ArrayList<List<Integer>>();
    		int sum = 0;
    		int i = 0, j = in.length - 1;
    		List<Integer> inL = new ArrayList<Integer>();
    		while (i < j) {
    			while (sum + in[j] <= bucketsize) {
    				inL.add(in[j]);
    				sum += in[j--];
    			}
    			
    			while(sum+in[i] <= bucketsize) {
    				inL.add(in[i]);
    				sum += in[i++];
    			}
    			
    			finalL.add(inL);
    			inL = new ArrayList<>();
    			sum = 0;
    		}
    		
    		if(i == j && in[i] < bucketsize) {
    			inL.add(in[i]);
    			finalL.add(inL);
    		}
    
    		for (List<Integer> l : finalL) {
    			for (int p : l) {
    				System.out.print(p + " ");
    			}
    			System.out.println();
    		}
    	}

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.