Tallest Billboard

HardDynamic Programming1d dp

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

You are building a billboard that rests on two steel supports, one on each side, and the two supports must have **equal** height. You have a collection of rods; a support is made by welding together some rods (lengths add up). Each rod may go into the left support, the right support, or be left unused. Return the largest possible height of the billboard, i.e. the largest common height the two supports can reach. If no positive equal height is possible, return 0.

Examples

Input: rods = [1,2,3,6]
Output: 6
Supports {1,2,3} and {6}, both height 6.
Input: rods = [1,2,3,4,5,6]
Output: 10
Supports {2,3,5} and {4,6}, both height 10.
Input: rods = [1,2]
Output: 0
No split gives two equal positive heights.

Constraints

  • 1 <= rods.length <= 20
  • 1 <= rods[i] <= 1000
  • sum(rods) <= 5000

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More 1d dp problems