intuit OA 2025 dec 17

'''

given you a tree with 1 as root node ,with parent info
when a command sent by ith node
that command travels through that node to its child node
via ordered dfs manner
that means if you have x children in dfs you will try to process them in ordered manner
given you a list of queries
in each query you will be given commandNode , xdistanceTimeNode
so if you pass a command from given commandNode , which node will get that in x distance time
if it is not possible return -1

============================================================================================================================================

say you are given a tree

like
 1 2 3 4 5 6 7 8 9
-1 1 1 1 3 5 3 5 7//parentInfo

so the tree would look like

                1

      2         3          4

            5       7

          6   8       9

lets have adjList
and sort all the children in each node
as question demands
now if you do the dfs and log it in an array the dfsArray would look like

1 2 3 5 6 8 7 9 4

lets assume the query you got is 3,2
so command sent from 3 and what is the second node it recieves it
check the dfs array it says 5

but you need to be careful you should not enter into other substrees
how can you do that if you know the subtree population then you can easily do this

you know how to get the population of subtree easily
that's it with the help of ordered dfs you will know wether the query exceeded boundary to send -1
or you have a valid node which recieves the command as ith in the line from commandNode

'''
from collections import defaultdict
class Solution:

    def dfs(self,adjList,node,subtreepopulation,dfsarr):
        for child in adjList[node]:
            dfsarr.append(child)
            self.dfs(adjList,child,subtreepopulation,dfsarr)
        for child in adjList[node]:
            subtreepopulation[node] += subtreepopulation[child]

        return



    def ithNodeToRecieveCommand(self,parent,queries):
        n = len(parent)
        adjList = defaultdict(lambda:[])
        for i in range(1,n):
            adjList[parent[i]].append(i+1)
        for k,arr in adjList.items():
            arr.sort()
        subtreepopulation = [1 for i in range(n+1)]
        dfsarr =[1]
        self.dfs(adjList,1,subtreepopulation,dfsarr)
        # print(dfsarr)
        indmapp = defaultdict(lambda:-1)
        for i in range(n):
            indmapp[dfsarr[i]] = i
        ans = []
        # print(indmapp)

        for q in queries:
            if subtreepopulation[q[0]]<q[1]:
                ans.append(-1)
            else:
                ans.append(dfsarr[indmapp[q[0]]+(q[1]-1)])
        return ans


def main():
    solution = Solution()

    # Test cases: (parent_array, queries, expected_result, description)
    test_cases = [
        (
            [-1, 1, 1, 1, 3, 5, 3, 5, 7],
            [[3, 2]],
            [5],
            "Example from problem - command from node 3, 2nd node receives it"
        ),
        (
            [-1, 1, 1, 1, 3, 5, 3, 5, 7],
            [[1, 1], [1, 5], [3, 1]],
            [1, 6, 3],
            "Multiple queries from root and subtree"
        ),

    ]

    print("Running test cases...\n")
    passed = 0
    failed = 0

    for i, (parent, queries, expected, description) in enumerate(test_cases, 1):
        try:
            result = solution.ithNodeToRecieveCommand(parent, queries)
            status = "✓ PASS" if result == expected else "✗ FAIL"

            if result == expected:
                passed += 1
            else:
                failed += 1

            print(f"Test {i}: {status}")
            print(f"  Parent: {parent}")
            print(f"  Queries: {queries}")
            print(f"  Description: {description}")
            print(f"  Expected: {expected}")
            print(f"  Got:      {result}")
        except Exception as e:
            failed += 1
            print(f"Test {i}: ✗ ERROR")
            print(f"  Parent: {parent}")
            print(f"  Queries: {queries}")
            print(f"  Description: {description}")
            print(f"  Error: {e}")
        print()

    print(f"Results: {passed} passed, {failed} failed out of {len(test_cases)} tests")


if __name__ == "__main__":
    main()