Uber Coding Interview: Team Party Fun Planner

The interviewer opens

Hi, and thanks for joining. Welcome to your interview for the software engineer role at Uber. We'll work through one coding problem together, and I'd like you to think out loud as you go. If you need to step out or take a break, the Pause button at the top right of your screen will stop things at any time.

The problem is about planning team parties over a company org chart, and it's up in the Problem tab now. Please read it through, take your time, and ask me anything that's unclear before you start.

The problem

Each manager wants the most fun a party drawn only from their own team could have.

• fun: list of non-negative ints; fun[i] is employee i's fun score.
• managers: list of ints; managers[i] is employee i's direct manager, or -1 for the CEO. The chart is a tree.

Employee i's team is i plus everyone reporting to i directly or indirectly. Return a list best where best[i] is the maximum total fun of a set drawn from i's team in which no employee appears with their direct manager.

Example: fun = [3, 2, 5, 4], managers = [-1, 0, 0, 1] → [9, 4, 5, 4]

1 ≤ n ≤ 10^5; the chart may be a chain of depth n.