Frontend School

Ad Segment Optimization

DSA
easy

Ad Segment Optimization

Easy
Dynamic Programming
Knapsack

Overview

Inmobi's ad platform helps advertisers reach their desired audience efficiently. A key challenge is optimizing campaign budgets to achieve specific reach goals. This problem simulates a simplified scenario where you need to determine the most cost-effective way to target a precise number of users for an ad campaign by selecting various audience segments.

What you need to do / Task

Given a list of available audience segments, where each segment has a certain users count and an associated cost, and a targetUsers count, your task is to find the minimum total cost to reach exactly targetUsers. You can select any segment type multiple times. If it's not possible to reach the targetUsers exactly, you should indicate this.

Input & output

Input:

  • segments: An array of objects, where each object represents an audience segment with two properties: users (number) and cost (number).
  • targetUsers: A number representing the exact total number of users you need to reach.

Output:

  • Return a number representing the minimum total cost to reach targetUsers. If targetUsers cannot be reached exactly, return -1.

Clarifications

  • Can segments be used multiple times? Yes, you can select the same segment type multiple times to contribute to the total targetUsers. For example, if targetUsers = 20 and you have a segment {users: 10, cost: 2}, you can select this segment twice for a total of 20 users and cost 4.
  • What if targetUsers is 0? If targetUsers is 0, the minimum cost is 0, as no segments need to be selected.
  • What if segments is empty? If segments is empty and targetUsers is greater than 0, it's impossible to reach the target, so return -1. If targetUsers is 0, return 0.

Examples

1

Example 1

Input:

segments = [{users: 10, cost: 2}, {users: 20, cost: 3}], targetUsers = 30

Output:

5

Note:

To reach 30 users, you can select the segment with 10 users (cost 2) and the segment with 20 users (cost 3). Total cost = 2 + 3 = 5.

2

Example 2

Input:

segments = [{users: 5, cost: 1}, {users: 10, cost: 4}], targetUsers = 12

Output:

-1

Note:

It's impossible to reach exactly 12 users using combinations of segments with 5 and 10 users.

3

Example 3

Input:

segments = [{users: 3, cost: 5}, {users: 5, cost: 8}], targetUsers = 0

Output:

0

Note:

To reach 0 users, no segments are needed, so the cost is 0.

4

Example 4

Input:

segments = [{users: 7, cost: 10}], targetUsers = 21

Output:

30

Note:

To reach 21 users, you can select the segment with 7 users (cost 10) three times. Total cost = 10 * 3 = 30.

Constraints

Constraints & assumptions

  • 1 <= segments.length <= 200
  • 1 <= segments[i].users <= 5000
  • 1 <= segments[i].cost <= 1000
  • 0 <= targetUsers <= 5000
  • All users and cost values are positive integers.

Out of scope

  • Optimizations for extremely large targetUsers or segments.length beyond the specified constraints.
  • Handling negative users or cost values.
  • Input validation beyond basic type checks.

What interviewers evaluate

  • Correctness of the dynamic programming approach and state definition.
  • Efficiency of the algorithm in terms of time and space complexity.
  • Proper handling of edge cases, such as targetUsers = 0 or when the target is unreachable.
  • Clarity, readability, and structure of the implemented code.

Loading editor...