Round 1
Questions: Madam C.J. Walker is historically renowned for becoming the first African-American businesswoman in America. One of her business plans involving the sale of cosmetics and perfumes for women is a modification of the standard 0-1 knapsack problem.
Walker's business plan begins with an array of n items. She wants to buy products and resell them for profit. The cost of buying the item is cost, and it earns her a profit of 21. She has a total of x amount of money.
Find the maximum profit that can be generated for the given amount of money. As the answer can be rather large, report the answer as maxProfit % (10 ^ 9 + 7) where % denotes modulo operator.
Example
Suppose there n = 5 items with costs cost = [10, 20, 14, 40, 50], and the initial amount of money that Walker has is x = 70
Some possible combination of items Walker can buy are:
- She can buy items 0, 1, and 2 for a cost of 44 and obtain a profit of 2 ^ 0 + 2 ^ 1 + 2 ^ 2 = 7
- She can buy items 0 and 4 for a cost of 60 and obtain a profit of 2 ^ 0 + 2 ^ 4 = 17
- She can buy items 1 and 4 for a cost of 70 and obtain a profit of 2 ^ 1 + 2 ^ 4 = 18
- She can buy items 2 and 4 for a cost of 64 and obtain a profit of 2 ^ 2 + 2 ^ 4 = 20
Out of all the possible combinations, the maximum profit obtained is by buying items 2 and 4 for a cost of 64 to obtain a profit of 20.
returns- max Profit: an integer denoting the maximum profit that can be obtained % (10^9+7)
Constraints 1<=n<=10^5 1<= cost[i]<=10^5 0<=x<= 10^9
Test Cases:
-
TC 0:
- cost size is 3, cost = [3, 4, 1], x = 8
- Output: 7
-
TC 1:
- cost size is 5, cost = [19, 78, 27, 18, 20], x = 25
- Output: 16
Function:
int maxProfit(vector<int>& cost, int x) { // code }
Candidate's Approach
I used a modified 0-1 knapsack approach to solve the problem. However, only a few test cases passed.
Interviewer's Feedback
No feedback provided.