How should I practice Backpropagate a Scalar Computation Graph?

Start by reading the full statement, solve the visible examples, then compare the pattern against related NVIDIA phone screen problems in FastPrep.

Is Backpropagate a Scalar Computation Graph associated with NVIDIA?

FastPrep tags this as a NVIDIA phone screen coding practice problem when the problem catalog has that company and stage context.

Backpropagate a Scalar Computation Graph

NVIDIA● MediumFULLTIMEPHONE SCREEN

Learn

Problem statement

Evaluate a scalar computation graph and return the first derivative of one selected output with respect to every independent input leaf.

The arrays operations, left, right and leafValues describe the same N nodes. A node's index is its position in these arrays. Nodes are listed in topological order:

LEAF: node i is an independent real input variable evaluated at leafValues[i]. Its left[i] and right[i] are both -1.
ADD: node i is value[left[i]] + value[right[i]].
MUL: node i is value[left[i]] * value[right[i]].

Every operand of an ADD or MUL node refers to an earlier node. Its leafValues[i] is 0 and is ignored. Two leaf nodes are independent variables even when their supplied values are equal.

Selected output and derivatives

Let z = value[target]. Return dz/dx for each LEAF node, ordered by increasing leaf-node index. Include every leaf, even one that does not affect target; its derivative is 0. The selected node may itself be a leaf or may occur before the final graph node.

Use the ordinary analytic sum, product and chain rules over real variables at the supplied integer evaluation points. The upstream derivative of z with respect to itself is 1. All returned derivatives are exact signed 64-bit integers.

A node can be used by several later nodes. Add the derivative contributions from all such uses. If left[i] == right[i], the two operands still contribute separately: for example, the derivative of x*x is 2*x.

What the interview report shared

The second phone round included a simple backpropagation calculation. The report does not specify the graph, requested derivative or whether the calculation was done by hand. Here, the practice task returns numeric derivatives for a supplied static graph.

Function

backpropagateScalarGraph(operations: String[], left: int[], right: int[], leafValues: int[], target: int) → long[]

Examples

Example 1

operations = ["LEAF","LEAF","ADD","MUL"]left = [-1,-1,0,2]right = [-1,-1,1,2]leafValues = [3,-2,0,0]target = 3return = [2,2]

The leaves are x = 3 and y = -2. Node 2 is x + y = 1, and node 3 is (x + y)^2. Both leaf derivatives equal 2 * (x + y) = 2; the repeated multiplication operand contributes twice.

Example 2

operations = ["LEAF","LEAF","MUL","ADD"]left = [-1,-1,0,2]right = [-1,-1,1,0]leafValues = [2,3,0,0]target = 3return = [4,2]

The selected output is x*y + x at x = 2, y = 3. Its derivatives are y + 1 = 4 and x = 2. Both paths from x contribute.

Example 3

operations = ["LEAF","LEAF","MUL","ADD","MUL"]left = [-1,-1,0,2,3]right = [-1,-1,1,1,1]leafValues = [5,7,0,0,0]target = 2return = [7,5]

Node 2 is x*y at x = 5, y = 7. The selected derivatives are y = 7 and x = 5. Nodes 3 and 4 are later computations, so they do not change the selected output.

Constraints

1 <= N <= 24; all four node arrays have length N.
Each operation is LEAF, ADD or MUL. There is at least one leaf.
A leaf has left[i] == right[i] == -1. Every other node has 0 <= left[i], right[i] < i and leafValues[i] == 0.
0 <= target < N. Repeated operand indices are allowed.
The absolute value of every supplied leaf and every evaluated graph node is at most 1000.
The absolute value of every node's derivative with respect to every leaf is at most 10^12.
The absolute value of the selected output's sensitivity with respect to every intermediate node is at most 10^12, treating that node's value as an independent intermediate in the chain rule.
Inputs satisfy these guarantees. Signed 64-bit arithmetic is sufficient for every value, derivative and intermediate accumulation.