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.

Loading coding console...

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)