• Skip to primary navigation
  • Skip to content
  • Skip to primary sidebar
  • Skip to secondary sidebar

GoHired

Interview Questions asked in Google, Microsoft, Amazon

Join WeekEnd Online Batch from 4-April-2020 on How to Crack Coding Interview in Just 10 Weeks : Fees just 20,000 INR

  • Home
  • Best Java Books
  • Algorithm
  • Internship
  • Certificates
  • About Us
  • Contact Us
  • Privacy Policy
  • Array
  • Stack
  • Queue
  • LinkedList
  • DP
  • Strings
  • Tree
  • Mathametical
  • Puzzles
  • Graph

N Petrol bunks or City arranged in circle. You have Fuel and distance between petrol bunks. Is it possible to find starting point so that we can travel all Petrol Bunks

July 11, 2014 by Dhaval Dave

Find the first circular tour that visits all petrol pumps

There are n petrol bunks arranged in circle. Each bunk is separated from the rest by a certain distance. You choose some mode of travel which needs 1litre of petrol to cover 1km distance. You can’t infinitely draw any amount of petrol from each bunk as each bunk has some limited petrol only. But you know that the sum of litres of petrol in all the bunks is equal to the distance to be covered. ie let P1, P2, … Pn be n bunks arranged circularly. d1 is distance between p1 and p2, d2 is distance between p2 and p3. dn is distance between pn and p1.Now find out the bunk from where the travel can be started such that your mode of travel never runs out of fuel.
At first Glance we can think its travelling salesman problem and hence only in O(n!) or O(2^n * n^2) is possible.
But several as here We have one more parameter say fuel or capacity along with distance we can reduce complexity with the help of it.With examples we can understand this.
Ex 1 :

Point  Fuel  Distance to next point
P1     5     8
P2     3     4
P3     12    7
P4     1     4
P5     7     5

Method 1 : Brute Force

Algo :
1) Start from first point
2) Try to traverse each petrol bunks in next direction.
if not possible. break;

int i,j,st,tr;
int dist[n];
int fuel[n];
num=n;

j=0; //to track index of city/Petrolbunk 

while(j){
  for(i=j;i<n;i++){
     if(fuel[i]-dist[i] < 0) { tr =0 ; break; 
     //we can't start from i th , start from next    
     //city  and make num of traversed city = 0. 
     
     else if (tr == 5){return 1;} // we traversed all cities return True;
     else (tr++);  //else move to next and number of traversed city incremented
  }//for
 j++;
}//whileover

– Here we started from location 0;
if we cant traverse all city, just increment j ( city index) start from next city.

This method takes O ( n ^2 ) as for all city we are trying to travel all cities.

Method 2 : O(n) Time method.

first lets understand method
Start from P1. and store last = last+=fuel-distance Array
before starting last=0;

Point  last = last + fuel-distance (before refueling)
P1     -3 ( 0 + 5 - 8 )
P2     -4 ( -3 + 3 - 4 )
P3      1 ( -4 + 12 - 7)
P4     -2 ( 1 + 1 - 4 )
P5      0 ( -2 + 7 - 5 )

Now as at last we can reach with 0 value.
We can travel this cities with “X” location/city/petrol.
X will be next station of smallest last value. ie : P3 here.
(start from p3, You have 12 lit fuel next station P4 at 7 distance remaining fuel at P4 is 5, from there take 1 unit of fuel now you have 6. next station P5 at distance 4 , remaining fuel at P5 is 2, get 7 units fuel from P5 and go to P1… You can complete cycle.)
Ex. 2 :  Do it your self.

Point Fuel Distance to next point
 P1 3 3
 P2 4 10
 P3 6 2
 P4 3 4
 P5 7 6
 P6 11 9

Thanks to Dhaval for suggesting this Article

Code :

float [] fuel = { 3,4,6,3,7,11 };
float [] dist = { 3,10,2,4,6,9 };
int n = 6;

int FindMinimumPosition()
{
    float last = 1;
    int position = 0;
    float minimumFuel = 1;
    int minimumPosition = 0;

    while (position < n)
    {
        last += fuel[position];
        last -= dist[position];
        position++; // could be n which is past array bounds
        if (last < minimumFuel) {
            minimumFuel = last;
            minimumPosition = position % n; //in case of last station
        }
    }

    return minimumPosition
}

This takes O(n) time complexity + O(n) Space complexity to store “last[n]”
Working Code : http://ideone.com/KVAFfg
If you want to share such question , solution  or your experience of any company, Please do share at admin@gohired.in , As sharing is caring

-IF YOU LIKE OUR EFFORT, PLEASE LIKE AND SHARE OUR FB-PAGE AND SITE

Similar Articles

Filed Under: Amazon Interview Question, Array, Flipkart Interview Questions, Hacker Earth Questions, Interview Questions, Microsoft Interview Questions, problem Tagged With: Array

Reader Interactions

Primary Sidebar

Join WeekEnd Online/Offline Batch from 4-April-2020 on How to Crack Coding Interview in Just 10 Weeks : Fees just 20,000 INR

Join WeekEnd Online/Offline Batch from 4-April-2020

WhatsApp us

Secondary Sidebar

Custom Search

  • How I cracked AMAZON
  • LeetCode
  • Adobe
  • Amazon
  • Facebook
  • Microsoft
  • Hacker Earth
  • CSE Interview

Top Rated Questions

write a c program that given a set a of n numbers and another number x determines whether or not there exist two elements in s whose sum is exactly x

Subset Sum Problem Dynamic programming

Reversal of LinkedList

Implement LRU Cache

Add Sub Multiply very large number stored as string

Binary Tree in Java

Edit Distance ( Dynamic Programming )

Find two non repeating elements in an array of repeating elements

SAP Off Campus Hiring_ March 2015 Computer Skills

Stock Buy Sell to Maximize Profit

Diagonal Traversal of Binary Tree

Serialise Deserialise N-ary Tree

Maximum sum contiguous subarray of an Array

Python String and numbers

In Given LinkedList Divide LL in N Sub parts and delete first K nodes of each part

There are N nuts and N bolts, u have to find all the pairs of nuts and bolts in minimum no. of iteration

Search element in a matrix with all rows and columns in sorted order

Check Binary Tree is Binary Search Tree or not

Get K Max and Delete K Max in stream of incoming integers

HackeEarth Flipkart’s Drone

Binary Tree in Java

TicTacToe Game As Asked in Flipkart

Puzzle : 100 doors in a row Visit and Toggle the door. What state the door will be after nth pass ?

Find shortest distances between every pair of vertices ( Dynamic Programming Floyd Warshall Algorithm)

C Program for TAIL command of UNIX

FizzBuzz Solution C C++

Generate next palindrome number

N teams are participating. each team plays twice with all other teams. Some of them will go to the semi final. Find Minimum and Maximum number of matches that a team has to win to qualify for finals ?

Maximum of all subarrays of size k

Find next greater number with same set of digits

Copyright © 2025 · Genesis Framework · WordPress · Log in