DoorDash Coding Interview: Best Route Through a Score Tree

The interviewer opens

Hi, and thanks for joining. Welcome to your interview for the software engineer role at DoorDash. We'll work through one coding problem together, so please think out loud as you go. If you need to step out or take a break, you can pause any time with the Pause button at the top right.

The problem is about finding the highest-scoring route through a tree of values, which is a bit like picking the most rewarding path through a network of stops. It's in the Problem tab on the right, so please read it through and ask me anything before you start.

The problem

Given a binary tree of integers, find the path with the largest total.

• values: the tree in level order, LeetCode style. values[0] is the root, children are listed only for non-null nodes, and null marks a missing child.

A path is a sequence of nodes where each adjacent pair is parent and child, and no node repeats. It has at least one node and need not pass through the root. Return the largest sum of node values over all paths.

Example: values = [-10, 9, 20, null, null, 15, 7] → 42 (path 15 → 20 → 7)

Sizes: 1 ≤ number of nodes ≤ 10^4; the tree may be as deep as it has nodes.