Clarification for problem 22.16 Fair Bonuses


#1

The problem statement does not specifically states what value to assign to neighbors with same productivity
(and does not disallow neighbor repetitions either). In the spirit of the problem, it makes sense to assign the same value. If there are neighbor developers with same productivity, then neither the priority queue based solution nor the last presented solution gives correct values.
The following was my approach:

static int[] fairBonus(int[] arr){
    if (arr == null || arr.length == 0) return arr;
    int[] ret = new int[arr.length];
    for(int i = 0; i < arr.length; ++i){
        ret[i] = 1;
    }
    for(int i = 1; i < arr.length; ++i){
        if (arr[i-1] < arr[i]) ret[i] = ret[i-1]+1;
        else if (arr[i-1] == arr[i]) ret[i] = ret[i-1];
    }
    for(int i = arr.length-2; i >= 0; --i){
        int val = ret[i];
        if (arr[i] > arr[i+1]) val = ret[i+1]+1;
        else if (arr[i] == arr[i+1]) val = ret[i+1];
        ret[i] = Math.max(ret[i], val);
    }
    return ret;
}

#2

Thanks for the feedback, the problem statement only defines the situation if two neighbors have different productivities. However, in the inverse, it means they need to have the same bonus otherwise the constraint will be invalid from either one side or the other. As a result, the algorithms we presented actually could handle the cases if there are duplicates.

You may try to check the codes on our Github site and try to run some test cases on that. Feel free to leave your questions if you have any after the testing.


#3

I also think the algorithms on the book are not correct. For an input of <100,300,500,400,600,900,700,700,200,100,1000,1000,800,800,600> the out put should be
<1,2,3,1,2,4,3,3,2,1,3,3,2,2,1> but the book algorithm will produce <1,2,3,1,2,3,1,3,2,1,2,2,1,2,1>