Microsoft·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

May 2026

Summary

Microsoft SWE interview with a graph problem that looks manageable until you realize the solution needs two separate algorithms chained together. Not a bad experience, just a lot to hold in your head at once.

Questions Asked (1)

Given an undirected weighted connected graph with n nodes, define a 'restricted path' as one that goes from node 1 to node n where each step moves to a node strictly closer to node n (by shortest distance). Count the number of such restricted paths modulo 10^9 + 7.

Algorithms & Data Structures

Author's notes

I knew Dijkstra immediately but blanked on what to do after.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

First, compute the shortest distance from node n to all other nodes using Dijkstra's algorithm. Then, sort nodes by distance from n in ascending order and use dynamic programming to count the number of restricted paths from node 1 to each node, where transitions are only allowed from a node to its neighbors that are strictly closer to n. Finally, output the count for node n modulo 10^9+7.

Pro tip: Clarify that the graph is undirected and weighted, and that 'strictly closer' means the shortest distance to n decreases at each step. Mention that the DP must process nodes in increasing order of distance from n to ensure correct dependencies.

1. Compute shortest distances from node n

Run Dijkstra's algorithm from node n to find the shortest distance d[v] from every node v to n. This defines the 'closer' relation.

2. Sort nodes by distance from n

Create a list of nodes sorted in ascending order of d[v]. This order ensures that when processing a node, all nodes closer to n have already been processed.

3. Initialize DP array

Set dp[1] = 1 (one way to start at node 1) and dp[v] = 0 for all other nodes. dp[v] will store the number of restricted paths from 1 to v.

4. Process nodes in sorted order and update DP

For each node u in sorted order, for each neighbor v of u, if d[v] < d[u], then add dp[u] to dp[v] modulo 10^9+7. This counts paths that move strictly closer to n.

5. Return dp[n] modulo 10^9+7

After processing all nodes, dp[n] contains the total number of restricted paths from 1 to n. Output it modulo 10^9+7.

Key Points to Mention

Dijkstra's algorithm for computing shortest distances from node n.
Dynamic programming with topological order based on distance from n.
Modulo arithmetic to handle large counts (10^9+7).
Strict inequality condition: only move to nodes with smaller distance to n.
Graph is undirected and weighted, so edges are bidirectional.
Time complexity: O((n + m) log n) for Dijkstra plus O(n + m) for DP, where m is number of edges.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.