Microsoft
More Experiences
Microsoft OA Problem
September 13, 2025 • 4 reads
Summary
I encountered a challenging tree-based algorithmic problem during the Microsoft Online Assessment.
Full Experience
I recently participated in the Microsoft Online Assessment and was presented with the following algorithmic challenge. The problem involved traversing a tree and calculating a specific value for connected subgraphs, starting from each node.
Interview Questions (1)
Q1
Max Value of Connected Subgraph Including Node
Data Structures & AlgorithmsHard
A tree with N nodes and N−1 edges. Each node has a value: either 0 or 1. The tree is connected and acyclic (i.e., a valid tree).
Output:
For each node, compute the maximum value of any connected subgraph (subtree) that includes that node.
Definition of Value:
For a subgraph (connected set of nodes), the value is: Value = Number of 1’s − Number of 0’s
Constraints:
1 <= N <= 1e5
Example:
0 [0]The answer in this case would be [0, -1, 1, -1]1[0] 2 [1] 3 [0]
For node 0: 0 -> 2
For node 1: 1 -> 0 > 2
For node 2: 2
For node 3: 3 -> 0 > 2