Round 1
Questions: Given n routers placed on a Cartesian plane and provided with a source and destination vertex, the task was to determine whether it was possible to reach the destination. Only adjacent vertices could be explored, and a vertex was considered adjacent if it had the minimum distance from the current vertex while remaining within a given threshold. Additionally, once a vertex was visited, the previously visited node became inactive (i.e., could no longer be used). The goal was to determine if a path existed from the source to the destination under these constraints.
Candidate's Approach
The initial approach involved a brute-force search using a queue. The algorithm identified adjacent vertices by selecting those with the minimum distance first since multiple adjacent vertices could have the same minimum distance weight. Due to time constraints, an optimization was suggested using a priority queue to efficiently retrieve the adjacent vertex with the minimum weight.
The interviewer suggested further optimizing the solution by precomputing a priority queue for each vertex at the start, allowing faster access to the optimal adjacent nodes. However, the interview was rushed, and there was no opportunity to discuss the time complexity or further refinements.
Interviewer's Feedback
No feedback provided.