Katkat
Back

Solve scheduling and tree path problems

SnowflakeSoftware Engineer · Technical Screen
HardSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to optimize path calculations in a tree by combining depth-first traversal with a greedy or dynamic programming approach to select paths that satisfy specific constraints.

Problem: Constrained Subtree Path Weight

You are given a binary tree where each node contains an integer value. A path is defined as a sequence of nodes connecting any two nodes in the tree (the path does not necessarily pass through the root).

Your task is to find a path that contains at most K nodes, such that the sum of the node values on the path is maximized.

Function Signature

class Node:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

def max_path_sum_with_limit(root: Node, K: int) -> int:

Constraints

  • The tree contains between 1 and 10,000 nodes.
  • Node values can be negative, positive, or zero.
  • 1 <= K <= number of nodes.

Examples

Example 1: Input: root = [1, -2, 3], K = 2 Output: 3 Explanation: The path [3] is the maximum weight path with at most 2 nodes.

Example 2: Input: root = [10, 2, 5, 1, 1], K = 3 Output: 17 Explanation: The path [2, 10, 5] is invalid because it contains 3 nodes but exceeds K if K was smaller; here, the path [5, 10, 2] is weight 17.

Edge Cases

  • Trees with a single node.
  • Trees where all node values are negative (the result should be the maximum single node value).
  • Very deep, degenerate trees (linked-list style).

Hints

Hint 1

A path in a tree can be represented as two downward paths starting from a common ancestor (the 'peak' of the path).

Hint 2

Consider using recursion to return the set of all possible path sums and their respective lengths starting from the current node downwards.

Hint 3

For each node, you can treat it as the highest point of a path and attempt to combine the best paths from the left and right subtrees that satisfy the length constraint.

Follow-up questions

  • How would you optimize the solution if K is very small, such as K=2 or K=3?
  • If node values were non-negative, how would your strategy change?
  • How would you modify the algorithm if the tree were a generic N-ary tree instead of a binary tree?