Round 1
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] / 2^x), e.g. floor(3/2^1) = 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
Constraints:
- 1 <= n <= 10^5
- 0 <= m <= 10^9
- 1 <= price[i] <= 10^9
-
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 salesVelocity
- int stockLevel
- Implement the constructor
Product(String productid, int salesVelocity, int stockLevel)
- Create a class called
InventoryClearance
. - Create a method called
identifyClearanceItems(List<Product> products)
that returns a list of strings representing the product IDs that are eligible for clearance.
Constraints:
- 1 <= n <= 10^5
- 0 <= salesVelocity <= 10^5
- 0 <= stockLevel <= 10^5
- Create a class called
Candidate's Approach
-
For the Items Purchase question, the approach involves using a greedy algorithm combined with a max heap. The steps are as follows:
- Heapify the price array.
- Continuously pop the largest price, apply the discount using the coupons, and push the discounted price back into the heap.
- Stop when either the number of coupons (m) becomes 0 or the price array is empty.
- Finally, return the sum of the remaining prices in the array.
The time complexity is O(m * log(n)) and space complexity is O(n).
-
For the Java specific question, the implementation involves creating the
Product
class with the specified properties and constructor, and theInventoryClearance
class with the method to identify clearance items based on the given criteria.
Interviewer's Feedback
No feedback provided.