Find the highest amount of money a shopkeeper can make through a certain number of sales

Question

I did a coding problem for a job interview recently where I got the right results, but my code wasn't fast enough and they didn't tell me why.

Imagine there's a greedy shopkeeper who has a bunch of items and a certain quantity of each item. He sells each item at a price equal to its remaining quantity and he wants to make as much money as possible through a certain number of sales. I think the number of items, the quantity of each item, and the number of sales could each be up to 10⁵? Any solution in Java had to run in less than 4 seconds.

The example given was 5 items with quantities 10, 10, 8, 9, and 1. Through 6 sales, the most money he could make would be 10+10+9+9+9+8=55.

To clarify, it works as follows:

After the first sale, take one of the quantity of 10 items for a price of 10. Since there are 9 of that item left, the price is now 9 and the remaining items are:

9, 10, 8, 9, 1 with a revenue of 10 after the first sale

continuing in this fashion, each time taking the priciest item available

9, 9, 8, 9, 1 with a revenue of 20 after 2 sales
8, 9, 8, 9, 1 with a revenue of 29 after 3 sales
8, 8, 8, 9, 1 with a revenue of 38 after 4 sales
8, 8, 8, 9, 1 with a revenue of 47 after 5 sales
7, 8, 8, 9, 1 with a revenue of 55 after 6 sales

The main way I tried was by getting the maximum quantity every time and adding this for the selected number of sales. But for thousands of items, this was too slow. Something like:

public static long getMaximumAmount(List<Integer> arr, int m) {
    long revenue = 0;
    int max = 0;
    while (m>0) {
        max = Collections.max(arr);
        revenue += max;
        arr.set(arr.indexOf(max),max-1);
        m--;
    }
    return revenue;
}

Then I tried sorting the quantities every time and taking the top element that way, but this was also too slow.

Then I tried sorting them once and starting with the top element and comparing with adjacent elements each time to get the max that way, but that was also too slow. EDIT: I think I was close here. You could sort it once, remove the top element, then loop through the remaining elements to find where to re-insert the element minus 1 to keep it sorted.

And finally I tried not sorting it and starting with the first element and comparing with adjacent elements each time to get the higher quantity, but that didn't always get the right results despite being faster.

Answer 1

Here is a solution using a TreeMap. It works as follows.

• compute a frequency count of all the items.
• then, get the last item (most expensive) from the map
• add to revenue.
• adjust that item's frequency down by 1 since to reduce number of that items availability at that price.
• if (it is 1, remove it) from the map.
• now increment the frequency of item-1 or create a new entry if it doesn't exist.
• continue until m == 0

Additional logic is included to throw an exception if the inventory exceeds the desired sales. One could also just return what was computed with available items. It depends on what is required.

public static long getMaximumAmount(List<Integer> arr, int m) {
    TreeMap<Integer, Integer> inventory = arr.stream()
            .collect(Collectors.toMap(a -> a, b -> 1, Integer::sum,
                    () -> new TreeMap<>()));
    long revenue = 0;
    while (m > 0) {
        if (inventory.isEmpty()) {
                  throw new RuntimeException("Insufficient items to meet sales");
        }
        Entry<Integer,Integer> e = inventory.lastEntry();
       
        int item = e.getKey();
        int remaining =e.getValue();
        revenue += item;
        if (e.getValue() == 1) {    // remove it as
            inventory.remove(item); // no more remaining
        } else {
            inventory.put(item, remaining-1); // update
        }
        // create new entry or increment existing
        // don't update if item will be <= 0
        if (item > 1) {
           inventory.compute(item-1, (k,v)->v == null ? 1 : v+1);
        }
        m--;
    }
    return revenue;
}

This seems to work for a large range of values and sales in sub second times.