Revenue Milestones in Java

Good day ladies and gentlemen. Today is Wednesday January 06, 2021. The claims of electoral fraud in the 2020 presidential elections in the USA continue to be brought up. One way or the other January 20 is about two weeks away. If the claims do not pan out then on that day we will have a new president be sworn in. We will be able to read news without political opinions.

Earlier today my wife fixed a delicious chicken dish with a white sauce with lemon and capers. She served it with rice, baked potatoes and beats. For desert we had chocolate ice cream followed by a triple espresso. That marked the middle of my day. In the afternoon I finished two additional 2-hour blocks.

After done with the workday I generated this post and am ready to call it a day. Will head upstairs to relax and call my son. He is the ones that provide most of the news for us. My wife and I will then watch an Amazon Prime or Netflix movie and around 08:00 PM will go to bed.

We are waiting for the COVID-19 vaccine to become available for our age group. I would assume and hope that most social restrictions would be lifted as soon as a percentage of people in the area we live in receive the vaccine.

Let’s get down to the main subject of this post.

I decided to tackle the Revenue Milestones problem from the coding practice portal of Facebook. The problem is in the search category. I did look for the problem in HackerRank or and LeetCode to no avail.

The reason I like to find the specific problem is due to the fact that HackerRank and LeetCode because solutions have to pass a large set of tests. At the Facebook site there might be a couple test samples and a couple unit tests. Most problems need a dozen or more test cases to make sure one capture the requirements in the implementation.

We keep track of the revenue Facebook makes every day, 
and we want to know on what days Facebook hits certain revenue milestones.

Given an array of the revenue on each day, 
and an array of milestones Facebook wants to reach, 
return an array containing the days on which Facebook reached every milestone.

Input:

revenues is a length-N array representing how much revenue FB made on each day (from day 1 to day N). 
milestones is a length-K array of total revenue milestones.

Output:

Return a length-K array where K_i is the day on which FB first had milestones[i] total revenue. 
If the milestone is never met, return -1.

Please take your time and read the requirements. Take a look at the test example. Based on them I initially figures that the values in the milestones would be in ascending order. That is not the case. Such values may appear in a random order. If you just sort the values your answer will not match the order of the expected results. You need to compensate for you sorting the revenue values.

int[] getMilestoneDays(int[] revenues, int[] milestones)

The signature for the function / method we need to implement is simple. The revenues array contains the revenues per day starting on the left and ending on the right. The milestones are not in any particular order. Our function should return an array associated with the milestones array. In other words, the first entry should be for the day in which the first milestone was reached, the second entry in the day the second milestone was met. The process continues through the entire array.

I like to develop software on my computers. That is how I and most software engineers tend to work. I will solve the problem using Java on a Windows 10 computer using the VSCode IDE. When I have a tentative candidate for release, I will copy the body of the function / method on my machine and paste it on the Facebook IDE. I will then run the unit tests.

I will have to develop a test scaffolding to check out my solution as I am developing it. The test code IS NOT PART OF THE SOLUTION.

10, 20, 30, 40, 50, 60, 70, 80, 90, 100
100, 200, 500
main <<<   revenues: [10, 20, 30, 40, 50, 60, 70, 80, 90, 100]
main <<< milestones: [100, 200, 500]
main <<< output: [4, 6, 10]
main <<< output: [4, 6, 10]

Explanation:

On days 4, 5, and 6, FB has total revenue of $100, $150, and $210 respectively. 
Day 6 is the first time that FB has >= $200 of total revenue.


10, 20, 30, 40, 50, 60, 70, 80, 90, 100
100, 200, 1000
main <<<   revenues: [10, 20, 30, 40, 50, 60, 70, 80, 90, 100]
main <<< milestones: [100, 200, 1000]
main <<< output: [4, 6, -1]
main <<< output: [4, 6, -1]


1, 2, 3, 4, 5, 6, 7, 8, 9, 10
100, 200, 500
main <<<   revenues: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
main <<< milestones: [100, 200, 500]
main <<< output: [-1, -1, -1]
main <<< output: [-1, -1, -1]


100, 200, 300, 400, 500
300, 800, 1000, 1400
main <<<   revenues: [100, 200, 300, 400, 500]
main <<< milestones: [300, 800, 1000, 1400]
main <<< output: [2, 4, 4, 5]
main <<< output: [2, 4, 4, 5]


700, 800, 600, 400, 600, 700
3100, 2200, 800, 2100, 1000
main <<<   revenues: [700, 800, 600, 400, 600, 700]
main <<< milestones: [3100, 2200, 800, 2100, 1000]
main <<< output: [5, 4, 2, 3, 2]
main <<< output: [5, 4, 2, 3, 2]

I believe this is the only test sample provided by Facebook. There are two unit tests and a couple samples I created to check out some conditions.

The first line contains the values for the daily revenues. The second line contains the milestone values. Our test code will have to read these two lines and will have to populate a couple arrays.

The arrays are displayed. They have the same names that are used by the signature for the function / method we have to develop.

It seems that we call two different implementations of the solution. They both appear to return the same results. Hopefully you will agree with both pieces of code. If not, please leave me a message bellow or send me an email message.

    /**
     * Test scaffolding
     * !!! NOT PART OF SOLUTION !!!
     * 
     * @throws IOException
     */
    public static void main(String[] args) throws IOException {
        
        // **** open buffered reader ****
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // **** read revenue ****
        int[] revenues = Arrays.stream(br.readLine().split(", ")).mapToInt(Integer::parseInt).toArray();
 
        // **** read milestones ****
        int[] milestones = Arrays.stream(br.readLine().split(", ")).mapToInt(Integer::parseInt).toArray();

        // **** close buffered reader ****
        br.close();

        // ???? ????
        System.out.println("main <<<   revenues: " + Arrays.toString(revenues));
        System.out.println("main <<< milestones: " + Arrays.toString(milestones));

        // **** compute and display results ****
        System.out.println("main <<< output: " + Arrays.toString(getMilestoneDays(revenues, milestones)));
        System.out.println("main <<< output: " + Arrays.toString(getMilestoneDays1(revenues, milestones)));
    }

The test scaffolding verifies our assumptions on the code. We open a buffered reader, read the values for the two arrays and close it. The values are displayed. They seem to match the input lines. So far things are going well. We then make a call to an implementation of the solution and display the returned values. The process repeats for a second implementation.

    /**
     * Given an array of the revenue on each day, 
     * and an array of milestones Facebook wants to reach, 
     * return an array containing the days on which Facebook reached every milestone.
     */
    static int[] getMilestoneDays(int[] revenues, int[] milestones) {

        // **** initialization ****
        int[] ans = Arrays.stream(new int[milestones.length]).map(i -> -1).toArray();

        int revenue = 0;

        PriorityQueue<String> pq = new PriorityQueue<String>(new Comparator<String>() {
            public int compare(String str1, String str2) {
                String s1 = str1.substring(0, str1.indexOf(","));
                String s2 = str2.substring(0, str2.indexOf(","));
                Integer v1 = Integer.parseInt(s1);
                Integer v2 = Integer.parseInt(s2);
                if (v1 > v2)
                    return 1;
                if (v1 == v2)
                    return 0;
                else
                    return -1; 
            }
        });

        for (int i = 0; i < milestones.length; i++) {
            String s = "" + milestones[i] + "," + i;
            pq.add(s);
        }

        // **** traverse revenue array O(n) ****
        for (int r = 0; r < revenues.length; r++) {

            // **** update revenue ****
            revenue += revenues[r];

            // **** update the ans array with milestones that have been reached O(m) ****
            while (!pq.isEmpty()) {

                // **** extract milestone and index ****
                String[] strs = pq.peek().split(",");
                int milestone = Integer.parseInt(strs[0]);
                int m = Integer.parseInt(strs[1]);
    
                // **** check if done ****
                if (revenue < milestone)
                    break;

                // **** ****
                ans[m] = (r + 1);
               
                // **** remove lowest value milestone ****
                pq.remove();
            }
        }

        // **** return answer **** 
        return ans;
    }

We start by performing some initialization. The ans[] array is created and filled in with -1 values. We create a priority queue to maintain a key : value pair associated with milestone : index pair. These are encoded in a string separated by a ‘,’. The bulk of the work is performed in the loop. We traverse the revenues from left to right. This is the order the data was provided. The revenue variable that holds the cumulative value is updated. We then enter a second loop in which we take the top element from our priority queue (heap) and extract the milestone : index values. We check if the revenue is less than the selected milestone. If so we exit the loop. Otherwise we update the answer array and remove the head of the priority queue. After we have processed all the revenue items we return the result array.

    /**
     * Given an array of the revenue on each day, 
     * and an array of milestones Facebook wants to reach, 
     * return an array containing the days on which Facebook reached every milestone.
     */
    static int[] getMilestoneDays1(int[] revenues, int[] milestones) {

        // **** initialization ****
        int sum     = 0;
        int[] ans   = Arrays.stream(new int[milestones.length]).map(i -> -1).toArray();

        HashMap<Integer, Integer> idx = new HashMap<>();
        for (int i = 0; i < milestones.length; i++)
            idx.put(milestones[i], i);

        Arrays.sort(milestones);

        // **** traverse all revenues O(n) ****
        for (int m = 0, d = 0; d < revenues.length; d++) {

            // **** update the sum with today's revenue ****
            sum += revenues[d];

            // **** start from the current smallest milestone O(m) ****
            while ((m < milestones.length) && (sum >= milestones[m])) {

                // **** set day for milestone ****
                ans[idx.get(milestones[m])] = d + 1;

                // **** increment milestone index ****
                m++;
            }
        }

        // **** return answer **** 
        return ans;
    }

In the second attempt we replace the priority queue with a hash map. It seems to me to be somewhat simpler to follow.

We perform the initialization step which includes sorting the milestones array. Note that the hash map associates the values with the original positions of the milestones.

The outer loop is used to traverse all the revenues associated with the days. We then update the sum of revenues up to the current day. This is similar to what we did in the previous approach.

The next loop is used to look for the milestones that have been met. With that information at hand we update the ans[] array and increment the milestone index.

When all is set and done we return the ans[] array.

Hope you enjoyed solving this problem as much as I did. The entire code for this project can be found in my GitHub repository.

If you have comments or questions regarding this, or any other post in this blog, or if you would like for me to help out with any phase in the SDLC (Software Development Life Cycle) of a project associated with a product or service, please do not hesitate and leave me a note below. If you prefer, send me a private e-mail message. I will reply as soon as possible.

Keep on reading and experimenting. It is the best way to learn, become proficient, refresh your knowledge and enhance your developer toolset.

One last thing, many thanks to all 5,476 subscribers to this blog!!!

Keep safe during the COVID-19 pandemic and help restart the world economy. I believe we can all see the light at the end of the tunnel.

Regards;

John

john.canessa@gmail.com