Today, I had my first onsite interview round, where I was given a graph traversal problem involving restricted movement based on a given condition.

Problem Overview:
• There are n nodes and e connections.
. Each edges have [u,v,l] which means u connect to v and required minimum health l.
• Each connection has a constraint value, and you can traverse it only if your current health meets or exceeds this value.
• The goal is to determine the minimum health required to reach destination node from starting node.

My Initial Approach:

I used BFS with a priority queue, exploring all possible paths while tracking the minimum health needed along the way. If a connection required a higher health than my current one, I would update it accordingly. Upon reaching the destination, I would return the minimum health required.

Time Complexity: (E+V)LogV

Interviewer’s Feedback:

The interviewer pointed out potential inefficiencies in my approach, though I wasn’t fully convinced initially. They then guided me toward an alternative solution using Binary Search.

Optimized Approach (Using Binary Search):
1. Define the Search Range: Between the lowest and highest possible healths.
2. Binary Search on health:
• For a given mid health, check if it’s possible to reach the destination using only connections that allow traversal within this limit.
• This check is done using graph traversal (BFS/DFS).
3. Adjust Search Space: Update the range based on whether reaching the destination was possible.

Time Complexity: (E+V)LogS, where S is the maximum constraint value.

Outcome:

Unfortunately, I couldn’t complete my implementation within the 45-minute timeframe, and I might receive a “No Hire” or “Lean Hire” decision.

Reflection:

I’m still unsure why my initial approach wouldn’t work efficiently, especially since S (the constraint range) was mentioned to be large. My approach seemed better in terms of complexity, yet the interviewer preferred the binary search method.

Would love to hear your thoughts—do you think my initial approach had fundamental flaws, or was it just a matter of choosing a different technique?