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.
Quick Answer: 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
Solution
from typing import List
import heapq
def min_cost_make_distinct(size: List[int], cost: List[int]) -> int:
n = len(size)
if n == 0:
return 0
pairs = sorted(zip(size, cost)) # (s, c)
maxheap = [] # stores (-cost, start_size)
i = 0
pos = pairs[0][0]
total_cost = 0
while i < n or maxheap:
# If heap is empty, jump to next available start size
if not maxheap and i < n and pos < pairs[i][0]:
pos = pairs[i][0]
# Add all items that can start at or before 'pos'
while i < n and pairs[i][0] <= pos:
s, c = pairs[i]
heapq.heappush(maxheap, (-c, s))
i += 1
# Assign current position to the item with the highest cost
if maxheap:
negc, s0 = heapq.heappop(maxheap)
c0 = -negc
total_cost += c0 * (pos - s0)
pos += 1
return total_cost
Explanation
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).
Hints
- Sort items by their initial size.
- Sweep positions from left to right; at each integer position, at most one item can be assigned.
- Maintain a max-heap (priority queue) of costs for items whose size is <= current position.
- Greedily assign the current position to the item with the highest per-unit cost to avoid paying that cost in future increments.