How should I practice Key Sum Management?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Rubrik online assessment problems in FastPrep.

Is Key Sum Management associated with Rubrik?

FastPrep tags this as a Rubrik coding interview or online assessment practice problem when the problem catalog has that company context.

Problem · Tree

Key Sum Management

Learn this problem

● HardRubrikINTERNOA

Problem statement

Key 1 is the root of an initial tree with n keys. Every key starts with value 0, and a key's level is its distance from the root.

The first n - 1 rows of operations contain the two endpoints of the initial tree edges. The remaining q rows are operations:

Ro p v: add a new key v as a child of p. Its value starts at 0, and v is the current node count plus one.
Re level z: for every key u currently at that exact level, let x be u's value immediately before this operation. Assign x + z to u and every key currently in u's subtree.

How the tree changes

1. Initial tree

Initial keys grouped by tree level
Level	Left subtree	Middle	Right subtree
0	Key 1 · value `X1`
1	Key 2 · `X2`	—	Key 3 · `X3`
2	Key 4 · `X4`, Key 5 · `X5`	—	Key 6 · `X6`, Key 7 · `X7`
3	Key 8 · `X8` under key `4`	—	—

2. Rotation

Ro 1 9 adds key 9 as a new child of key 1. Its value starts at 0; every existing edge and value stays unchanged.

Tree after adding key 9
Level	Left subtree	New middle key	Right subtree
0	Key 1 · value `X1`
1	Key 2 · `X2`	Key 9 · `0`	Key 3 · `X3`
2	Keys 4, 5 · unchanged	—	Keys 6, 7 · unchanged
3	Key 8 · unchanged	—	—

3. Rekey

Re 1 4 starts at every level-1 key. Each selected key's previous value plus 4 is copied through its whole subtree.

Values after rekeying level 1
Level	Key 2 subtree	Key 9 subtree	Key 3 subtree
0	Key 1 stays `X1`
1	Key 2 · `X2 + 4`	Key 9 · `4`	Key 3 · `X3 + 4`
2	Keys 4, 5 · `X2 + 4`	—	Keys 6, 7 · `X3 + 4`
3	Key 8 · `X2 + 4`	—	—

Return the sum of all key values after all operations.

Function

keySumManagement(operations: String[][], n: int, q: int) → long

Examples

Example 1

operations = [["1", "2"], ["2", "4"], ["1", "3"], ["4", "5"], ["Re", "1", "10"], ["Ro", "4", "6"], ["Re", "2", "4"], ["Re", "3", "4"]]n = 5q = 4return = 70

The final values of keys 1 through 6 are [0, 10, 10, 14, 18, 18], whose sum is 70.

Example 2

operations = [["2", "1"], ["3", "1"], ["4", "2"], ["5", "1"], ["Ro", "4", "6"], ["Re", "2", "91277"], ["Re", "1", "50944"], ["Ro", "1", "7"], ["Re", "1", "17666"]]n = 5q = 5return = 360716

After the final Rekey operation, keys 2 through 6 each have value 68610, key 7 has value 17666, and key 1 remains 0. Their sum is 360716.

Constraints

1 ≤ n, q ≤ 10^5

1 ≤ z ≤ 10^5, where z is the number added in the Rekey query.

All other inputs satisfy the constraints and problem requirements.

In the Rotation query, the new key v always equals the current number of nodes in the tree + 1.