Amazon Online Assessment (OA) - Find The Highest Profit

An e-commerce company imports a type of fitness band from China and sell them in US for a higher price for a profit. The company has multiple suppliers for the product, each with their own inventory. The suppliers raise the price of their product when inventory gets small due to scarcity. More specifically, the profit the e-commerce company makes for each product sold is equal to the number of products left from 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 = [4, 6] order = 4

Output: 19
Explanation:

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

  • getting 1 item from the first supplier for 6
  • getting 1 item from the first supplier for 5
  • getting 1 item from the first supplier for 4
  • getting 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

  • getting 1 item for a profit of 10 from the first supplier
  • getting 1 item for a profit of 10 from the second supplier
  • getting 1 item for a profit of 9 from the first supplier
  • getting 1 item for a profit of 9 from the second supplier
  • getting 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

1
-
from typing import List
1
+
from itertools import accumulate
2
+
from typing import Counter, List
3
+
def seq_sum(start: int, stop: int) -> int:
4
+
    return (start + stop - 1) * (stop - start) // 2
5
+
2
6
def find_profit(inventory: List[int], order: int) -> int:
3
-
    # WRITE YOUR BRILLIANT CODE HERE
7
+
    # (stock, suppliers count) in stock desc
4
-
    return 0
8
+
    count = sorted(Counter(inventory).items(), reverse=True)
9
+
    suppliers = 0
10
+
    profit = 0
11
+
    left = order
12
+
    for i, (stock, extra) in enumerate(count):
13
+
        next_stock = count[i + 1][0] if i < len(count) - 1 else 0
14
+
        suppliers += extra
15
+
        supply = suppliers * (stock - next_stock)
16
+
        full, part = divmod(min(left, supply), suppliers)
17
+
        profit += suppliers * seq_sum(stock - full + 1, stock + 1) \
18
+
            + part * (stock - full)
19
+
        left -= supply
20
+
        if left <= 0:
21
+
            break
22
+
    return profit
23
+
5
24
if __name__ == '__main__':
6
25
    inventory = [int(x) for x in input().split()]
7
26
    order = int(input())
8
27
    res = find_profit(inventory, order)
9
28
    print(res)