FastPrepMaximum Highway Billboard Revenue
Problems/Maximum Highway Billboard Revenue

Maximum Highway Billboard Revenue

Expedia logoExpedia● MediumNEW GRADONSITE INTERVIEW

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: The report's example and its rule that billboards must be more than X apart are kept. We chose how to handle unordered input, the limits, and that placing a billboard is optional. Our version is about 98% the same as the reported question.

Candidate billboard i is at positions[i] on a highway from 0 through roadLength, and earns revenue[i]. Select any subset of candidates to maximize total revenue.

Every pair of selected billboards must be more than gap units apart. A distance exactly equal to gap is not allowed. Positions are distinct but may be supplied in any order. Return the greatest total revenue; selecting none earns 0.

Function

maximumBillboardRevenue(roadLength: int, positions: int[], revenue: int[], gap: int) → int

Examples

Example 1

roadLength = 20positions = [2,8,9,10,15]revenue = [20,50,10,30,5]gap = 5return = 75

Choose sites 2,8,15 for revenue 20+50+5=75. Consecutive distances 6 and 7 both exceed 5.

Example 2

roadLength = 10positions = [1,6]revenue = [4,7]gap = 5return = 7

Distance 5 is forbidden, so choose only the higher-revenue site.

Constraints

  • 1 <= roadLength <= 1000000.
  • 0 <= positions.length, revenue.length <= 2000.
  • 0 <= positions[i], revenue[i], gap <= 1000000.
  • positions and revenue have equal lengths.
  • All candidate positions are distinct and at most roadLength.

More Expedia Onsite Interview questions

  • Scramble StringONSITE INTERVIEW · Seen Sep 2026
  • Smallest Sufficient TeamONSITE INTERVIEW · Seen Sep 2026
  • Check Anagram Pairs Index by IndexONSITE INTERVIEW · Seen Oct 2025
  • Fresh Oranges Left After Rotting StopsONSITE INTERVIEW · Seen Oct 2025
  • Longest Increasing SubsequenceONSITE INTERVIEW · Seen Oct 2025
  • Lowest Common Ancestor with Repeated and Missing ValuesONSITE INTERVIEW · Seen Oct 2025
  • Shortest Substring with Exactly K OnesONSITE INTERVIEW · Seen Oct 2025
  • Middle Element of a Linked ListONSITE INTERVIEW · Seen Nov 2024
  • Minimum in a Rotated Sorted ArrayONSITE INTERVIEW · Seen Sep 2024
  • Mirror Image Binary TreesONSITE INTERVIEW · Seen Sep 2024

Similar questions at other companies

  • Maximum Total Length of Non-Overlapping IntervalsBloomberg LP · ONSITE INTERVIEWBloomberg LP interview questions
  • Russian Doll EnvelopesGoogle · ONSITE INTERVIEWGoogle interview questions
  • Russian Doll EnvelopesInMobi · ONSITE INTERVIEWInMobi interview questions
  • Fill a Time Window with SongsMicrosoft · OAMicrosoft interview questions
  • Maximum Taxi EarningsWells Fargo · OAWells Fargo interview questions
  • Weighted Jobs from an Encoded Test CaseJP Morgan Chase · OAJP Morgan Chase interview questions
  • Maximum Profit in Job SchedulingAmazon · PHONE SCREEN
  • Maximum Event Value with an Attendance LimitSnowflake · PHONE SCREENSnowflake interview questions
  • 3Sum SmallerSalesforce · ONSITE INTERVIEWSalesforce interview questions
  • Maintain a Consistent-Hashing RingCohesity · ONSITE INTERVIEW

Interview reports that mention this question

  • Expedia New Grad SDE Earlier Loops: 5 Experiences (Part 2 of 3)

Expedia interview experiences

  • Expedia Intern Final Round in 2021: 28 Experiences (Part 4 of 6)
  • Expedia Intern Finals Before 2020: 14 Experiences (Part 6 of 6)
  • Expedia Intern Final Round in 2020: 24 Experiences (Part 5 of 6)
  • Expedia Intern Final Round in 2022: 15 Experiences (Part 3 of 6)
  • Expedia Intern Final Round in 2023: 17 Experiences (Part 2 of 6)
All Expedia interview questionsSee Expedia hiring insights
Saved
class Solution {
    public int maximumBillboardRevenue(int roadLength, int[] positions, int[] revenue, int gap) {
        // Write your code here.
    }

}
Checking account…