Round 1
Questions:
Question
One of the products comes in n sizes as indicated in the array size. The category manager recognizes that some of the sizes are repetitive and do not provide a good user experience. To make the best use of inventory, the product should be available in distinct sizes. The size of the ith product, size[i], can be increased by one unit for an amount in the cost array, cost[i].
Given the arrays size and cost for the product, find the minimal total cost in order to make all the sizes distinct.
Example 1:
Given n = 4, size = [2, 3, 3, 2] and cost = [2, 4, 5, 1].
It costs 7 units to make the prices distinct.
We can also adjust size[1] to 5, which costs cost[1] * (5-size[1]) = 8, and size[3] to 4, which costs cost[3] * (4-size[3]) = 2. Therefore, the total cost is 8 + 2 = 10.
However, 7 is the minimum cost required to make all sizes distinct.
Function Description:
Complete the function getMinimalCost in the editor below.
int size[n]: the sizes of the product
int cost[n]: the cost to change each size
Returns long: the minimal total cost to make all sizes distinct
Constraints
• 1 <= n <= 2*10^5
• 1 <= size[i] <= 10^9
• 1 <= cost[i] <= 10^4
Example 2: given size = [3,7,9,7,8] and cost = [5,2,5,7,5] output is 6.
Increase the second value in size from 7 to 10 at a cost of 3*2 = 6.
Example 3: given size = [3,3,4,5] and cost = [5,2,2,1] output is 5.
Solve in optimal way in java for large inputs as per given constraints.
Candidate's Approach
No approach provided.
Interviewer's Feedback
No feedback provided.
Round 2
Questions:
Question
We have different types of products. You are given an array products of size n, where products[i] represents the number of items of product type i (where i ranges from 0 to n-1). These products need to be packed into batches for shipping.
The batch packing must adhere to the following conditions:
- No two items in the same batch can be of the same product type, meaning all items in a batch must be of distinct types.
- The number of items packed in the current batch must be strictly greater than the number packed in the previous batch.
Additionally, note that each item can be packed only once, and it is not required to pack every item.
Determine the maximum number of batches that can be prepared for shipment.
Note: The product types are numbered from 0 to n-1. Thus, the number of items of product type i (0 <= i <= n-1) is given by products[i].
Example: products = [2, 3, 1, 4, 2]
An optimal way to prepare the batches is: - The first batch contains 1 item of product type 4. The remaining items = [2, 3, 1, 4, 1]
- The second batch contains 2 items of product types: 0 and 1. The remaining items = [1, 2, 1, 4, 1].
- The third batch contains 3 items of product types: 0, 1, and 3. The remaining items = [0, 1, 1, 3, 1].
- The fourth batch contains 4 items of product types: 1, 2, 3, and 4. The remaining items = [0, 0, 2, 0].
Even though 2 items remain, a batch requires 5 items of different product types. Therefore, only 4 batches can be prepared, which is the maximum possible.
Hence, the answer is 4.
Function Description:
Complete the function maximizeGroups in the editor below.
int products(n): the number of items of each product type.
Constraints:
1 <= n <= 10^5
0 <= products[i] <= 10^9
Example 2: given products = [1, 2, 7]. output is 3.
Last time you mentioned / solved using binary search but only 11/15 test cases passed.
Candidate's Approach
No approach provided.
Interviewer's Feedback
No feedback provided.