Amazon Online Assessment (OA) - Find The Highest Profit

An e-commerce company imports a type of fitness band from China and sells them in the US for a higher price. The company sources the product from multiple suppliers, each with their own inventory. The suppliers raise the price of their product when inventory decreases due to scarcity. More specifically, the profit that the e-commerce company makes on each product sold is equal to the number of products left with the supplier.

Given a list of integers representing the number of products each supplier has and an integer representing the number of products sold, find the maximum profit the company can make.

Examples

Example 1:

Input:

inventories = [6, 4] order = 4

Output: 19

Explanation:

There are two suppliers, with inventory of 4 and 6 respectively. A total of 4 items are ordered. We can make maximum profit by

• selling 1 item from the first supplier for 6
• selling 1 item from the first supplier for 5
• selling 1 item from the first supplier for 4, which brings down the inventory of the first supplier to 3
• selling 1 item from the second supplier for 4

The maximum profit is 6 + 5 + 4 + 4 = 19.

Example 2:

Input:

inventories = [10, 10]

order = 5

Output: 46

Explanation:

The maximum profit we can generate is by

• selling 1 item for a profit of 10 from the first supplier
• selling 1 item for a profit of 10 from the second supplier
• selling 1 item for a profit of 9 from the first supplier
• selling 1 item for a profit of 9 from the second supplier
• selling 1 item for a profit of 8 from the first or second supplier

The maximum profit is 10 + 10 + 9 + 9 + 8 = 46.

Try it yourself

Solution

The higher the stock, the higher profit we get, so it's always better to buy from a supplier with the highest stock. After each purchase, the supplier's stock would drop by 1, and we repeat this process until we have fulfilled all orders.

Let's visualize with a table, where content of each cell denotes the order we buy each product, and - indicates products that we don't need since we have enough already:

inventories = [3, 6, 6], order = 14

Initially, supplier 2 and 3 have the highest stock (6), so we purchase products from them until all 3 suppliers have 3 products left. At this point, we have 5 more orders, so we purchase 6 products (2 from each supplier) with profit 3 and 2, and finally 2 products with profit 1.

To always purchase from a supplier with highest stock, we need to remember the stock of each supplier. Repeatedly removing the largest value while inserting new values, sounds like a good fit for priority queues / heaps, and so we have a solution:

1from heapq import heapify, heappop, heappush
2from typing import List
3
4def find_profit(inventory: List[int], order: int) -> int:
5    # python has min heap, negate to reverse order
6    stocks = [-stock for stock in inventory]
7    heapify(stocks)
8    profit = 0
9    for _ in range(order):
10        stock = -heappop(stocks)
11        profit += stock
12        heappush(stocks, -(stock - 1))
13    return profit
14
15if __name__ == '__main__':
16    inventory = [int(x) for x in input().split()]
17    order = int(input())
18    res = find_profit(inventory, order)
19    print(res)
20

1import java.util.Arrays;
2import java.util.List;
3import java.util.PriorityQueue;
4import java.util.Scanner;
5import java.util.stream.Collectors;
6
7class Solution {
8    public static int findProfit(List<Integer> inventory, int order) {
9        // negate to reverse order; PriorityQueue does not have a constructor
10        // that takes both a collection and a comparator
11        PriorityQueue<Integer> stocks = new PriorityQueue<>(
12                inventory.stream().map(i -> -i).collect(Collectors.toList()));
13        int profit = 0;
14        for (; order > 0; order--) {
15            int stock = -stocks.poll();
16            profit += stock;
17            stocks.offer(-(stock - 1));
18        }
19        return profit;
20    }
21
22    public static List<String> splitWords(String s) {
23        return s.isEmpty() ? List.of() : Arrays.asList(s.split(" "));
24    }
25
26    public static void main(String[] args) {
27        Scanner scanner = new Scanner(System.in);
28        List<Integer> inventory = splitWords(scanner.nextLine()).stream().map(Integer::parseInt).collect(Collectors.toList());
29        int order = Integer.parseInt(scanner.nextLine());
30        scanner.close();
31        int res = findProfit(inventory, order);
32        System.out.println(res);
33    }
34}
35

Optimization

That's a good first approach, but there is still plenty of room for improvement.

Consider if supplies and order are large:

inventories = [50000], order = 50000

In this case, we are essentially removing 50000, inserting 49999, removing 49999, inserting 49998, and so on. We are in fact removing and inserting items from/into the priority queue order times. Note that order is not the size but the value of an input, which means the runtime is actually exponential to the input size (see pseudo-polynomial)!

If we look more closely, we'll see that our profit in this case is 50000 + 49999 + ... + 1, the sum of an arithmetic sequence, which has a closed form formula:

sum(a, a + 1, ..., b - 2, b - 1) = (a + b - 1) * (b - a) / 2

In another direction, consider if there are many suppliers with the same number of products:

inventories = [10, 10, 10, 10, 10], order = 50

Since we always pick from the suppliers with highest stock, if there are multiple suppliers with the same (but all highest) number of products, we will only move on to a lower number if we bought from all of them. So rather than processing one at a time, we could group suppliers with the same number of products and process each group at a time.

Let's visualize with a profit table of the example in the first solution:

The first solution essentially calculates 6 + 6 + 5 + 5 + 4 + 4 + 3 + 3 + 3 + 2 + 2 + 2 + 1 + 1, while we instead want to compute 2 * (6 + 5 + 4) + 3 * (3 + 2) + 2 * (1).

To do this, we first group suppliers by stock (1 supplier has 3 products, and 2 suppliers have 6 products), then sort by stock descending:

stocks = [(stock=6, count=2), (stock=3, count=1)]

By looking at the first 2 pairs, we can find out how many products the 2 suppliers can provide us before other suppliers can compete:

supply = (6 - 3) * 2 = 6

Since we need 14 products, we will take all 6 of them, and the profit gained is:

profit += 2 * sum(4, ..., 6)

Now there are 3 suppliers with the highest stock (2 from before and 1 joining the competition). Following the same logic, they can offer:

supply = (3 - 0) * 3 = 9

However we only need 8 more, so we take

full = floor(8 / 3) = 2 products from each of the 3 suppliers (at stock 3 and 2), and an extra of

part = 8 mod 3 = 2 products (at stock 1).

So we gain a profit of:

profit += 3 * sum(2, ..., 3) + 2 * (1)

Thus we have the optimized solution:

1from typing import Counter, List
2
3def seq_sum(start: int, stop: int) -> int:
4    '''Returns sum of arithmetic sequence from start to stop (exclusive).
5    '''
6    return (start + stop - 1) * (stop - start) // 2
7
8def find_profit(inventory: List[int], order: int) -> int:
9    # (stock, suppliers count) in stock desc
10    stocks = sorted(Counter(inventory).items(), reverse=True)
11    # number of suppliers with highest stock
12    suppliers = 0
13    # total profit
14    profit = 0
15    # for each supplier group with same stock
16    for i, (stock, extra) in enumerate(stocks):
17        # while we still have unfullfilled orders
18        if order <= 0:
19            break
20        # stock of next supplier group
21        next_stock = stocks[i + 1][0] if i < len(stocks) - 1 else 0
22        # suppliers = suppliers from before + new suppliers
23        suppliers += extra
24        # number of products that current suppliers have best prices of
25        # before other suppliers can compete
26        supply = suppliers * (stock - next_stock)
27        # (full rows of products to purchase, extras in last row)
28        full, part = divmod(min(order, supply), suppliers)
29        # profit gained from full rows and last row
30        profit += suppliers * seq_sum(stock - full + 1, stock + 1) \
31            + part * (stock - full)
32        order -= supply
33    return profit
34
35if __name__ == '__main__':
36    inventory = [int(x) for x in input().split()]
37    order = int(input())
38    res = find_profit(inventory, order)
39    print(res)
40

1import java.util.Arrays;
2import java.util.Comparator;
3import java.util.HashMap;
4import java.util.List;
5import java.util.Scanner;
6import java.util.Map.Entry;
7import java.util.stream.Collectors;
8
9class Solution {
10    // returns sum of arithmetic sequence from start to stop (exclusive).
11    private static int seqSum(int start, int stop) {
12        return (start + stop - 1) * (stop - start) / 2;
13    }
14
15    public static int findProfit(List<Integer> inventory, int order) {
16        HashMap<Integer, Integer> counter = new HashMap<>();
17        for (int item : inventory)
18            counter.merge(item, 1, Integer::sum);
19        // (stock, suppliers count) in stock desc
20        List<Entry<Integer, Integer>> stocks = counter.entrySet().stream()
21                .sorted(Comparator.comparingInt(Entry<Integer, Integer>::getKey).reversed())
22                .collect(Collectors.toList());
23        // number of suppliers with highest stock
24        int suppliers = 0;
25        // total profit
26        int profit = 0;
27        // for each supplier group with same stock,
28        // while we still have unfullfilled orders
29        for (int i = 0; i < stocks.size() && order > 0; i++) {
30            int stock = stocks.get(i).getKey();
31            // stock of next supplier group
32            int nextStock = i < stocks.size() - 1 ? stocks.get(i + 1).getKey() : 0;
33            // suppliers = suppliers from before + new suppliers
34            suppliers += stocks.get(i).getValue();
35            // number of products that current suppliers have best prices of
36            // before other suppliers can compete
37            int supply = suppliers * (stock - nextStock);
38            // full rows of products to purchase
39            int full = Math.min(order, supply) / suppliers;
40            // extras in last row
41            int part = Math.min(order, supply) % suppliers;
42            // profit gained from full rows and last row
43            profit += suppliers * seqSum(stock - full + 1, stock + 1) + part * (stock - full);
44            order -= supply;
45        }
46        return profit;
47    }
48
49    public static List<String> splitWords(String s) {
50        return s.isEmpty() ? List.of() : Arrays.asList(s.split(" "));
51    }
52
53    public static void main(String[] args) {
54        Scanner scanner = new Scanner(System.in);
55        List<Integer> inventory = splitWords(scanner.nextLine()).stream().map(Integer::parseInt).collect(Collectors.toList());
56        int order = Integer.parseInt(scanner.nextLine());
57        scanner.close();
58        int res = findProfit(inventory, order);
59        System.out.println(res);
60    }
61}
62