I was given this problem at Texas Instruments this morning after implementing three other algorithms like Radix sorting, Spiral Matrix II, and a farming DFS challenge. I had 8 minutes left to bang this one out, so after I decrypted the weird wording, I started working up a solution around Djikstra's algorithm. Then the interviewer told me that time was up and asked if I had any last words.
What the hell? This would take a while to digest plan and code.
Dijkstra on the expanded graph would probably work, but it would probably take 15+ minutes for some of the best competitive programmers in the world. For normal people, that’s an 1hr+ problem.
4 problems in an hour?
Yes sire. A bit less since the interviewer started out talking about what they do.
The difficulty of questions could mean that they are more picky, but the difficulty of getting an offer is relative to the applicant pool and what yield they want from it. Unless enough other people are doing better and taking that offer... don’t be discouraged.
Your mistake was leaving only 8 minutes for this problem. Radix sort, spiral matrix, farm dfs should all have been solved in 20 minutes.
Input data are trivial. No need to implement anything. Answer is 30. Took me less than 5mn
Fail