FastPrepMinimum-Sum Tree Fill with Unit Steps
Problems/Minimum-Sum Tree Fill with Unit Steps

Minimum-Sum Tree Fill with Unit Steps

Visa logoVisa● MediumFULLTIMEOA
QuestionFunctionExamplesConstraints

Problem statement

Source note: In a Visa online assessment with two problems in 90 minutes, both were tree questions wrapped in an application story that the report does not give. This one gave a tree where only some nodes have a known value; the rest must be filled in so that neighbouring nodes always differ by exactly one, with the total of all values as small as possible.

The report gives no input format, value range, examples or limits, and does not say what to return when no filling exists or whether values may be negative. Practice choices here: the tree is an undirected edge list, -1 marks an empty node, at least one value is known, every value must be a non-negative integer, the answer is the smallest total as a 64-bit integer or -1 when no filling exists, and the limits and examples are ours.

The judged task matches the report at about 70%.

A tree has n nodes numbered 0 to n - 1, connected by the undirected edges in edges. Some nodes already have a value: if values[i] is not -1, node i must keep exactly that value. A value of -1 means node i is empty and must be filled.

Fill every empty node with a non-negative integer so that the two ends of every edge differ by exactly 1. Among all valid fillings, find the smallest possible sum of all n values (known and filled).

Return that smallest sum, or -1 if no valid filling exists. The sum can exceed the 32-bit integer range.

Function

minimumFilledSum(n: int, edges: int[][], values: int[]) → long

Examples

Example 1

n = 6edges = [[0,1],[1,2],[1,3],[3,4],[3,5]]values = [-1,-1,5,-1,2,-1]return = 19
  • Node 2 is known to be 5 and node 4 is known to be 2. They are three edges apart (2 - 1 - 3 - 4) and differ by 3, so the path between them must step down by one each time: node 1 is 4 and node 3 is 3.
  • Node 0 is next to node 1 (value 4), so it is 3 or 5; the smaller choice 3 is best.
  • Node 5 is next to node 3 (value 3), so it is 2 or 4; choose 2.
  • The total is 3 + 4 + 5 + 3 + 2 + 2 = 19.

Example 2

n = 3edges = [[0,1],[1,2]]values = [0,-1,3]return = -1

Nodes 0 and 2 are two edges apart, so their values can differ by at most 2. They differ by 3, so no filling works and the answer is -1.

Example 3

n = 5edges = [[0,1],[0,2],[0,3],[0,4]]values = [-1,1,-1,-1,-1]return = 4
  • Node 1 is 1, so the center node 0 is 0 or 2. Choose 0.
  • Each other leaf is next to the center, so it must be 1: the value -1 is not allowed because filled values cannot be negative.
  • The total is 0 + 1 + 1 + 1 + 1 = 4.

Constraints

  • 1 <= n <= 5000
  • edges.length == n - 1, each edge is [u, v] with 0 <= u, v < n and u != v, and the edges form a tree.
  • values.length == n
  • Each values[i] is -1 or satisfies 0 <= values[i] <= 10^9.
  • At least one values[i] is not -1.

More Visa problems

  • Count Prime Values in SubtreesOA · Seen Nov 2026
  • House RobberPHONE SCREEN · Seen Nov 2026
  • House Robber IIIPHONE SCREEN · Seen Nov 2026
All Visa interview questionsSee Visa hiring insights
Saved
class Solution {
    public long minimumFilledSum(int n, int[][] edges, int[] values) {
        // Write your code here.
    }
}
Checking account…