2 Hackerrank questions
- Items Purchase
n items where the price of the ith item is price[i]. A frequent customer has m discount coupons. If x discount coupons are used on the ith item, its price is reduced to the integer floor(price(i] / 2x), e.g. floor(3/21) = floor(1.5) = 1.
Find the minimum amount needed to purchase all the items of the shop using at most m coupons.
Example Consider n = 2, price = [2, 4], m = 2. The optimum solution: • Purchase item 1 for 2. • Use 2 coupons on item 2, so the discounted price is 4/2^2 = 4 / 4 = 1. The amount required = 2 + 1 = 3.
Function Description Complete the function findMinimumPrice in the editor below. findMinimumPrice has the following parameters: int price[n]: the original prices of the items int m: the number of discount coupons
1<= n <= 10^5
0<= m <= 10^9
1<= price[i] <= 10^9
Sol: Passes all Test cases. TC: O(m* log(n)), SC: O(n)
Use greedy approach + maxHeap. Heapify the Price arr. Pop the largest, apply the discount, push back. Don't push if price[i] becomes 0.
Do this till
1. m becomes 0
2. price becomes empty.
Return the sum of price arr afterwards.
- Java specific question. Create and implement Product class.
Implement the classes shown.
• Create a class called Product that implements the /Product interface.
• This class should have the following properties:
• String productid • int sales Velocity • int stockLevel
• Implement the constructor Product(String productid, int salesVelocity, int stockLevel)
• Create a class called InventoryClearance.
• Create a method called identifyClearance/tems(List products) that • returns a list of strings representing the product IDs that are eligible for clearance
Function Description Complete the classes Product and InventoryClearance in the editor below. Constraints
• 1 ≤n≤ 105
• 0 ≤ salesVelocity ≤ 105
• 0 ≤ stockLevel ≤ 105