Microsoft OA Problem

Result
Ongoing
Posted
13 Sept 2025
315 reads

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)

  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]

        1[0]           2 [1]          3 [0]
    

    The answer in this case would be [0, -1, 1, -1]
    For node 0: 0 -> 2
    For node 1: 1 -> 0 > 2
    For node 2: 2
    For node 3: 3 -> 0 > 2

Know someone preparing? Send it to them:WhatsAppLinkedInX

Interviewed at Microsoft recently?

Write up your rounds while you still remember the questions. It helps the next person more than you would think.

Share your experience
Discussion 0

Questions for the author, or how your own interview compared.

Join the discussion

Sign in with Google to comment or ask the author a question.

No comments yet

Be the first to share your thoughts and start the discussion!