Microsoft Technical Interview Experience – Graph BFS Priority Queue

Following a shortlist by the recruiter, two technical interviews were scheduled for October 28, 2025. The first round lasted one hour and focused on a graph algorithm challenge with a supportive inter

Following a shortlist by the recruiter, two technical interviews were scheduled for October 28, 2025. The first round lasted one hour and focused on a graph algorithm challenge with a supportive interviewer who provided hints when necessary.

Problem Statement Given a connected graph where each node holds a specific number of stones, the task was to balance the graph by adding stones. The constraint was to ensure that the difference in stone counts between any two adjacent nodes did not exceed one.

Solution Approach The problem was solved using a Breadth-First Search (BFS) combined with a greedy strategy. The key was to utilize a Priority Queue (max heap) to manage the traversal. By initializing the process with nodes containing the highest number of stones and always prioritizing the node with the current maximum count, the algorithm could greedily add the minimum number of necessary stones to neighbors that had fewer than the required amount.