Microsoft Interview Experience: Round 1
Summary
I had my first technical interview round with Microsoft, where I was presented with a challenging graph problem involving balancing stones across nodes to maintain a specific difference constraint with neighbors. I successfully devised a solution using BFS and a priority queue.
Full Experience
I received a direct call from a Microsoft recruiter, who informed me that my profile had been shortlisted for an interview and asked about my availability. My two technical interviews were scheduled for October 28, 2025. In the first round, the interviewer asked me a graph problem: 'We have a connected graph, and every node has some number of stones. We need to balance the graph by adding stones so that every adjacent node in the graph does not have a difference of stones more than one.' I approached this question using a Breadth-First Search (BFS). The key insight was to start the BFS from nodes that had the highest number of stones, and I also utilized a priority queue (max heap) to always process the node with the highest number of stones in each iteration. This greedy approach allowed me to add the minimum necessary stones to neighbors if they had fewer stones than needed. The interviewer was very supportive and provided hints when I needed them. This round lasted one hour, but DSA questions consume time so quickly that it didn't feel like a full hour.
Interview Questions (1)
Given a connected graph where each node possesses a certain number of stones, the objective is to balance the graph. This balance is achieved by adding stones such that the absolute difference in the number of stones between any two adjacent nodes is not more than one.