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.
Discussion
Loading comments…