1
\$\begingroup\$

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;
    }


}
\$\endgroup\$
2
\$\begingroup\$

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).

| improve this answer | |
\$\endgroup\$
0
\$\begingroup\$

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;
    }

}
| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.