Cut Wood / Facebook Interview

Question

This question was asked through the Facebook interview and the suggested solution is solving via binary search.

I have put the binary search solution but it still looks too complicated.

Question:

Given an int array wood representing the length of n pieces of wood and an int k. It is required to cut these pieces of wood such that more or equal to k pieces of the same length len are cut. What is the longest len you can get?

Input: wood = [5, 9, 7], k = 3 Output: 5 Explanation: 5 -> 5 9 -> 5 + 4 7 -> 5 + 2

Input: wood = [5, 9, 7], k = 4 Output: 4 Explanation: 5 -> 4 + 1 9 -> 4 * 2 + 1 7 -> 4 + 3

package AmazonOthers.src;

import java.util.Arrays;

public class CutWood {


    public static void main(String[] args) {
        int[] array1 = {5,9,7};
        int k = 3;
        System.out.println( woodCut(array1,k) ) ;

        int[] array2 = {124,232,456};
        Arrays.sort(array2);
        int k2 = 7;
        System.out.println( woodCut(array2,k2) ) ;

        int[] array3 = {3,6,7,11};
        Arrays.sort(array3);
        int k3 = 8;
        System.out.println( woodCut(array3,k3) ) ;

    }

    private static int woodCut(int[] array1,int k) {

        int l = 0;
        int h = Integer.MAX_VALUE;

        while(l<h){
            int mid = l + (h-l)/2;
            if(isValid(array1, mid, k)){
                l = mid +1;
            }else{
                h=mid-1;
            }
        }
        return h;

    }

    private static boolean isValid(int[] array1, int mid, int k) {

        int count = 0;
        for(int val: array1){
            count+=val/mid;
        }
        return count>=k;
    }


}

Answer 1

Overall I think you have about the simplest you could hope for. The only thing I'd do is set your bounds better. You know that you can do min(array)/ceil(k/len(array)) and you know you at most you can do max(array)/floor(k/len(array)).

I was going to suggest going for extra credit with a more sophisticated algorithm, but I don't think you can beat what the binary search approach. At worst you're going to be 32 or 64 * O(n). Given the simplicity of the algorithm I think that will likely beat sorting and all the alternatives I can think of either explicitly or implicitly do a sort which would be O(n log n).

Answer 2

I have added a getMaxValue() method to limit the search?

Could you please evaluate the solution if is it meets the limiting the search ?

Thanks.

package main.algorithms;

public class CutWood {

    public boolean isValid(int[] wood, int cutLength, int k){
        int count = 0;
        for(int w: wood){
            count += w / cutLength;
        }
        return count >= k;
    }

    public int cutWood(int[] wood, int k){
        // corner cases:
        if(wood.length == 0 || k == 0) return 0;
        int left = 1;
        int right = getMaxValue(wood);
        int res = 0;

        if(!isValid(wood, left, k)) return 0;

        while(left < right){
            int mid = left + (right - left)/2;
            boolean valid = isValid(wood, mid, k);
            if(valid){
                left = mid + 1;
                res = mid;
            }
            else
                right = mid;
        }
        return res;
    }

    private int getMaxValue(int[] wood) {
        int max = 0;
        for(int i : wood){
            if (i> max){
                max  = i;
            }
        }
        return max;
    }

}