Google || Graph
Anonymous User
16625

https://leetcode.com/discuss/interview-question/1220530/Google-Phone-Screen-or-Graph

Ques:
You have a graph, where each node is a bank with $X in the vault, and each edge between the banks represents the time it takes to travel between the banks. You're a bank robber and you start by robbing bank 0. Given time limit T, what is the maximum amount of money you can rob across all the banks if you must end at bank 0 because that's where your getaway car is.

I proposed Djikstra to minimize the travel time, but couldn't figure out how add the part to maximize the money robbed. Maybe there's some DP component too?

Edit: Graph is undirected, and you can revisit the same bank as part of your path to get back to 0, but you can't rob it more than once.

Can someone please suggest the approach to this question?

Comments (25)