ZSCALER Coding Question – Solved

Question

Track Command Position

A network contains n nodes, where node 1 is the root node. The network structure is represented as a tree, with each node (except the root) having exactly one parent specified by the array par, where par[i] represents the parent of node i (1-based indexing).

Commands propagate through the network as follows: A node sends the command to its direct child nodes in ascending order of their indices. Each child node propagates the command to its subtree using the same process. The propagation stops when all nodes in the subtree have received the command.

Given q queries, each query (startNode[i], index[i]) asks for the index-th node in the sequence of command propagation starting from node startNode[i]. Return the index-th node or -1 if fewer than index[i] nodes receive the command. Each query is processed independently.

Example:
n = 9  
par = [-1, 1, 1, 1, 3, 5, 3, 5, 7]  
q = 4  
query = [[1, 5], [7, 2], [9, 2], [3, 6]]

If node 1 sends a command, the nodes receive it in the following order: [1, 2, 3, 5, 6, 8, 7, 9, 4].  
If node 3 sends a command, the nodes receive it in the following order: [3, 5, 6, 8, 7, 9].  
If node 7 sends a command, the nodes receive it in the following order: [7, 9].  
If node 9 sends a command, the nodes receive it in the following order: [9].

So, on processing the queries:  
1. query[0] = [1, 5]: If node 1 sends a command, the 5th node receiving it would be 6.  
2. query[1] = [7, 2]: If node 7 sends a command, the 2nd node receiving it would be 9.  
3. query[2] = [9, 2]: If node 9 sends a command, there's no 2nd node to receive it.  
4. query[3] = [3, 6]: If node 3 sends a command, the 6th node receiving it would be 9.

Hence, the array returned = [6, 9, -1, 9].

Function Description:  
Complete the function getAnswersToQueries in the editor with the following parameters:  
int par[n]: Each par[i] represents the parent of the i-th node.  
int query[q][2]: Each query[i] consists of [startNode[i], index[i]].

Returns:  
int[q]: an array of integers of size q representing answers to the queries.

TreasuresBase Expert · Accepted Answer

from collections import defaultdict
from functools import lru_cache
from sys import setrecursionlimit
setrecursionlimit(10 ** 6)
def getAnswersToQueries(par, query):
    h = defaultdict(list)
    n = len(par)
    for index in range(n):
        val = index+1
        h[par[index]].append(val)
    
    inorder_index = []
    final_check = (}
    
    @lru_cache(None)
    def childs(root, pt):
        inorder_index.append(root)
        result = 1
        for j in h[root]:
            result += childs(j, root)
        final_check[root] = result
        return result
    childs(1,-1)
    index_mapping = (}
    for index, val in enumerate(inorder_index):
        index_mapping[val] = index
    # print(inorder_index)
    # print(index_mapping)
    answer = []
    for node, command in query:
        depth = final_check[node]
        if depth < command:
            answer.append(-1)
        else:
            get_index = index_mapping[node]
            answer.append(inorder_index[get_index+command-1])
    return answer

ZSCALER Coding Question – Solved

Image of the Question

All Testcases Passed ✔

Solution

🔒 Please login to view the solution

Explanation

Related Questions