BCG Senior+ Forward Deploy Engineer Interview Experience — An Unweighted Graph Turned Weighted

A friend referred me for a Senior Forward Deploy Engineer role. The interviewer was very nice. The first 30 minutes were a deep dive into my projects, with many questions related to AI.

The last 30 minutes were a live coding problem: find the shortest path in an unweighted graph represented by an adjacency matrix. Given the adjacency matrix of a connected, undirected graph with no loops or multiple edges, I had to find the shortest distance, measured by the fewest edges, between two specified vertices.

The matrix was an n x n array of booleans. matrix[i][j] == true meant that there was an edge between vertex i and vertex j. The two target vertices were zero-indexed and within the bounds of the matrix.

For example:

matrix = [
  [false, false, true],
  [false, false, true],
  [true,  true,  false]
]
vertex1 = 0
vertex2 = 1

The result was 2, following the path 0 -> 2 -> 1.

At the time, I did not even understand what the values in the matrix represented. I clearly had not practiced enough problems. The original problem only required BFS. The interviewer then changed it to a weighted graph, which made it more complicated and called for a heuristic approach such as A* Search or Greedy Search.