Last active 1 day ago

loupe.md Raw

Code Question Amazon manages a network of warehouses connected as a weighted tree with network_nodes nodes labeled from 1 to network_nodes. Each edge (u, v) has a positive integer weight network_weight, representing the transfer time between u and v. The distance between two nodes is the sum of weights along their unique path. Given an integer batch_time, compute for every warehouse c the number of ordered pairs of other warehouses (a, b) such that: a ≠ b, a ≠ c, b ≠ c The distances from node a to node b and from node a to node c are divisible by batch_time. Note: The path between node a and b is not required to pass through c. Only the distances from a to c and a to b must be divisible by batch_time. Return an array where each element represents the number of valid ordered pairs for that warehouse. Additional Notes In an ordered pair, (a, b) and (b, a) are treated as different pairs. The warehouse network is a tree (undirected, connected graph with no cycles, no self-loops, and no multiple edges). Both warehouse labels (nodes) and transfer times (weights) are positive integers. Example network_nodes = 4 network_from = [1, 1, 2] network_to = [2, 3, 4] network_weight = [2, 5, 3] batch_time = 5 Explanation: For warehouse 1, valid pairs: (3, 4) and (4, 3) For warehouse 2, no valid pairs For warehouse 3, valid pairs: (1, 4) and (4, 1) For warehouse 4, valid pairs: (1, 3) and (3, 1) Output: [2, 0, 2, 2] Function Description Complete the function countPackagePairs: Parameters: int network_nodes: number of warehouses int network_from[network_nodes - 1]: one endpoint of each edge int network_to[network_nodes - 1]: other endpoint of each edge int network_weight[network_nodes - 1]: weight (distance) of each edge int batch_time: fixed duration Constraints 2 ≤ network_nodes ≤ 1000 1 ≤ network_from[i], network_to[i] ≤ n 1 ≤ network_weight[i] ≤ 10^6 1 ≤ batch_time ≤ 1000 Input Format for Custom Testing First line: two integers network_nodes and network_nodes - 1 Next n-1 lines: network_from[i] network_to[i] network_weight[i] Last line: batch_time Sample Case 0 Input: 4 3 1 2 2 2 3 2 3 4 2 2 Output: 6 6 6 6 Explanation: Each warehouse can connect to every other warehouse → all pairs valid. Sample Case 1 Input: 2 1 1 2 5 2 Output: 0 0 Explanation: Distance not divisible by batch_time Also not enough nodes to form (a, b, c)