Parte da empresa Microsoft
Empresa engajada
Pergunta de entrevista da empresa LinkedIn
Implement a function to compute the maximum sum of any downward path in a tree represented by a parent array and node values.
Resposta da entrevista
Sigiloso
8 de set. de 2025
I designed a DFS-based recursive solution to traverse the tree, maintaining a global maximum path sum. Built an adjacency list to represent the tree. Used recursion to compute the max downward path sum from each node. Updated a global maximum at every node. Achieved O(n) time complexity. The solution passed all test cases.