The question asks if a trip can be made successfully, but it leaves out the definition of successfully. In an interview, I would ask the following questions (heck, I want the following questions answered by anyone before I even continue on this problems):
- Would the idea be to complete a circuit and keep the cost below 1 unit per distance?
- Can there be negative costs (so we can earn money)?
- How big can the number of stations be?
The last two questions can be easily deduced from the online judge if one has patients. But the first question is essential to this problem.
Does anyone have insight?
- I do not understand your question actually. You may misunderstand the
cost[i]is the cost of gas, not money. From
station i+1, you can fuel the car with
gas[i]unit of gas, then it will cost
cost[i]unit of gas to
- costs is always positive.
- You can solve the problem as sufficient as you can. For example, if you implement in a
O(N^2)solution, you get time limit exceed, you might think about a better solution. I think when you having interview, the best solution may come out iteratively. If interviewee tell you the test case scale, it maybe a cheat to come up the best solution.