Home » Interview coding problems/challenges

# Highway billboard

**Highway billboard**: Here, we are going to learn to find maximum profits with some constraints. This can be featured in any interview coding rounds.

Submitted by Radib Kar, on February 04, 2020

**Description:**

This is a standard dynamic programing problem of finding maximum profits with some constraints. This can be featured in any interview coding rounds.

**Problem statement:**

Consider a highway of **M** miles. The task is to place billboards on the highway such that revenue is maximized. The possible sites for billboards are given by number * x_{1} < x_{2} < ... < x_{(n-1)} < x_{n}* specifying positions in miles measured from one end of the road. If we place a billboard at position

*, we receive a revenue of*

**x**_{i}*. The constraint is that no two billboards can be placed*

**r**_{i}> 0**within t miles or less than it**.

Input: M=15, n=5 x[n]= {6,8,12,14,15} revenue[n] = {3,6,5,3,5} t = 5 Output: 11

**Explanation with example**

So, we have to maximize the revenue by placing the billboards where the gap between any two billboard is ** t**.

Here,

The corresponding distances of the billboards with respect to the origin are,

x[5]= {6,8,12,14,15}

We can augment the origin, so the augmented array becomes: (no need to augment if origin revenue exists)

x[6]= {0,6,8,12,14,15} t=5

The graphical interpretation of the billboards is like following:

**Figure 1: Billboards**

The augmented revenue array:

revenue[6] = {0,3,6,5,3,5}

Now, the brute force approach can be to check all the possible combination of billboards and updating the maximum revenue accumulated from each possible combinations.

Few of such possible combinations can be:

So, maximum revenue that can be collected is **11**.

For any billboard ** b_{i}** we have three choices

- Don't pick
*b*_{i} - Start from
*b*_{i} - Pick
and other billboards accordingly*b*_{i}

Say,

M(i)=maximum revenue upto first i billboards

So,

M(0)=0 if b_{i}is not picked, M(i)=M(i-1) if billboard placement starts from b_{i}M(i)=r[i] If we place b_{i}then need to pace b_{j}where d[i]>d[j]-t such that revenue maximizesSo,

**Problem Solution approach**

We convert the above recursion to dynamic programing as there will many overlapping sub problems solving the recursion. (Try to generate the recursion tree yourself)

1) Construct DP[n] for n billboards // considering billboard placing starts from it 2) Fill the array with base value which is r[i] 3) for i=1 to n-1 // recursion case 1 and 2 // either not picking ith billboard or starting // from ith billboard which ever is maximum dp[i] = max(dp[i-1],dp[i]); // recursion case 3 // picking ith billboard for j=0 to i-1 if(a[j]< a[i]-k)//feasible placing dp[i]= max(dp[i],dp[j]+r[i]); end for end for Result is dp[n-1]

**C++ implementation:**

#include <bits/stdc++.h> using namespace std; int max(int x, int y) { return (x > y) ? x : y; } int billboard(vector<int> a, vector<int> r, int n, int k) { int dp[n]; for (int i = 0; i < n; i++) dp[i] = r[i]; //base value dp[0] = r[0]; for (int i = 1; i < n; i++) { //first two recursion case int mxn = max(dp[i - 1], dp[i]); //picking ith billboard, third recursion case for (int j = 0; j < i; j++) { if (a[j] < a[i] - k) mxn = max(mxn, dp[j] + r[i]); } dp[i] = mxn; } return dp[n - 1]; } int main() { int n, k, item, m; cout << "Enter highway length:\n"; cin >> m; cout << "Enter number of billboards\n"; cin >> n; cout << "Enter minimum distance between any two billboards\n"; cin >> k; vector<int> a; vector<int> r; cout << "Enter billboard distances one by one from origin\n"; for (int i = 0; i < n; i++) { cin >> item; a.push_back(item); } cout << "Enter revenues for the respective billboards\n"; for (int i = 0; i < n; i++) { cin >> item; r.push_back(item); } if (a[0] == 0) { a.insert(a.begin(), 0); r.insert(r.begin(), 0); n = n + 1; } cout << "Maximum revenue that can be collected is: " << billboard(a, r, n, k) << endl; return 0; }

**Output**

RUN 1: Enter highway length: 20 Enter number of billboards 5 Enter minimum distance between any two billboards 5 Enter billboard distances one by one from origin 3 7 12 13 14 Enter revenues for the respective billboards 15 10 1 6 2 Maximum revenue that can be collected is: 21 RUN 2: Enter highway length: 15 Enter number of billboards 5 Enter minimum distance between any two billboards 5 Enter billboard distances one by one from origin 6 8 12 14 15 Enter revenues for the respective billboards 3 6 5 3 5 Maximum revenue that can be collected is: 11

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions

**Ad:**
Are you a blogger? Join our Blogging forum.