Microsoft OA Problem
- Result
- Ongoing
- Posted
- 13 Sept 2025
Summary
I encountered a challenging tree-based algorithmic problem during the Microsoft Online Assessment.
How it went
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.
Questions asked (1)
- 01
Max Value of Connected Subgraph Including Node
Data Structures & Algorithms · Hard
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