We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
- Prepare
- Data Structures
- Queues
- Truck Tour
- Discussions
Truck Tour
Truck Tour
Sort by
recency
|
354 Discussions
|
Please Login in order to post a comment
Insanely broken exercise. Terrible test cases where every test has 1000 or more elements making it impossible to learn anything from the failure and it does not actually expect you to do a tour of the circle. In fact, if you try to you will fail. All the successful solutions only go clockwise and don't try to reach all the petrol pumps, they just go to the end of the array. It's shocking that this made it into the 1-week prep course and implies the rest of the HackerRank exercise library is even worse.
Easy python solution-
def truckTour(petrolpumps): n = len(petrolpumps) current_petrol = 0 total_petrol = 0 start_index = 0
Python
This is one of the easiest hard problems maybe.
A naive solution would be to start a tour from each gas station in turn, and check if the tour is feasible. A feasible tour is one where the fuel in the tank never goes negative while travelling. This is an O(n^2) algorithm.
However, it is easy to see that if a tour starting from S1 and passing through S2, S3, ..., Sk is infeasible, so is a tour from any Sj between S1 and Sk. So you don't need to check those, and the algorithm becomes O(n).
I am not sure queues were needed either -- but that's a cute opportunity to learn from the editorial :)