Quick Overview

This question evaluates algorithmic problem-solving and data-processing competencies, focusing on numeric optimization for making array elements distinct with minimal cost and on traversal and aggregation over a social graph to rank movies by friend and friends-of-friends frequency.

Minimize cost & recommend movies

Company: Amazon

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

##### Question Given arrays size[] and cost[] where size[i] is the size of the i-th product and cost[i] is the cost to increase size[i] by one unit, compute the minimal total cost required to increment elements so that all sizes become distinct. Implement recommendMovies(userName) that returns a list of movie titles ordered by how frequently they were watched by the user’s friends and friends-of-friends, using Helper.getFriends and Helper.getMoviesWatched.

Overview: This question evaluates algorithmic problem-solving and data-processing competencies, focusing on numeric optimization for making array elements distinct with minimal cost and on traversal and aggregation over a social graph to rank movies by friend and friends-of-friends frequency.

You are given two arrays size and cost of equal length n. size[i] is the initial size of the i-th product, and cost[i] is the cost to increase size[i] by one unit. In one operation you may increase size[i] by 1, paying cost[i]. You cannot decrease any value. Compute the minimal total cost required to transform the array so that all final sizes are pairwise distinct integers.

Constraints

  • 1 <= n <= 200000
  • 0 <= size[i] <= 10^9
  • 1 <= cost[i] <= 10^9
  • Only increments are allowed
  • Output may exceed 32-bit; use 64-bit integer arithmetic

Hints

  1. Sort items by their initial size.
  2. Sweep positions from left to right; at each integer position, at most one item can be assigned.
  3. Maintain a max-heap (priority queue) of costs for items whose size is <= current position.
  4. Greedily assign the current position to the item with the highest per-unit cost to avoid paying that cost in future increments.

Min Cost to Make Sizes Distinct

mediumAmazonSoftware EngineerGreedy

You are given two arrays size and cost of equal length n. size[i] is the initial size of the i-th product, and cost[i] is the cost to increase size[i] by one unit. In one operation you may increase size[i] by 1, paying cost[i]. You cannot decrease any value. Compute the minimal total cost required to transform the array so that all final sizes are pairwise distinct integers.

Examples

Example 1
Input
size = [1,1,1], cost = [1,2,3]
Output
4
Notes
Assign final sizes [1,2,3]. Costs: 3*(1-1)=0, 2*(2-1)=2, 1*(3-1)=2; total = 4.
Example 2
Input
size = [2,2,1], cost = [100,1,1]
Output
1
Notes
Assign final sizes [1,2,3] by keeping expensive item at 2 and pushing a cheap item to 3. Total cost = 1.

Constraints

  • •1 <= n <= 200000
  • •0 <= size[i] <= 10^9
  • •1 <= cost[i] <= 10^9
  • •Only increments are allowed
  • •Output may exceed 32-bit; use 64-bit integer arithmetic

Comments (0)

No comments yet. Be the first to comment!

Submit your answer

Approved first answer today earns 30 XP
Bold⌘BItalic⌘IInline code⌘`Bullet listTab to nest (○ ■)Numbered listTab to nest (a. i.)QuoteCode block
Formatting help
Sample input
{"cost":[1,2,3],"size":[1,1,1]}
Language
Case 1
Input
{
  "cost": [
    1,
    2,
    3
  ],
  "size": [
    1,
    1,
    1
  ]
}
Expected
4
Case 2
Input
{
  "cost": [
    10,
    10,
    10
  ],
  "size": [
    0,
    2,
    5
  ]
}
Expected
0

Browse More Questions

Show the approach

Approach

Sort items by initial size s. Sweep integer positions pos from the smallest s upward. At each pos, consider all items with s <= pos as available and push them into a max-heap keyed by per-unit cost c. Assign the current position to the item with the highest c to avoid paying that cost in future increments, adding c * (pos - s) to the total. If no items are available, jump pos to the next start size. This greedy strategy is optimal by an exchange argument: if a cheaper item is chosen earlier than a more expensive one, swapping their assignments reduces or preserves cost.

Time complexity:
O(n log n)
Space complexity:
O(n)