2
\$\begingroup\$

Suppose there is a circle. There are n petrol pumps on that circle. You are given two sets of data.

  1. The amount of petrol that petrol pump will give.
  2. Distance from that petrol pump to the next petrol pump.

Calculate the first point from where a truck will be able to complete the circle (The truck will stop at each petrol pump and it has infinite capacity). Expected time complexity is O(n). Assume for 1 litre petrol, the truck can go 1 unit of distance.

For example, let there be 4 petrol pumps with amount of petrol and distance to next petrol pump value pairs as {4, 6}, {6, 5}, {7, 3} and {4, 5}. The first point from where truck can make a circular tour is 2nd petrol pump. Output should be “start = 1″ (index of 2nd petrol pump).

Looking for code-review, best-practices and optimizations.

public final class PetrolPumpCircularTour {
    
    private PetrolPumpCircularTour() {};

    public static int startingStations(List<PetrolPumpData> gasStations) {
        
        if (gasStations.size() == 0) {
            throw new IllegalArgumentException("There should be atleast a single gas stats");
        }
        
        int front = 0;
        int rear = 0; // is actually 0, after a circle. but 1 is just a game we play for circular queue.
        
        int statationsCovered = 0;
        int gasSavedSoFar = 0;
        
        while (statationsCovered < gasStations.size()) {
            int currentPetrol = gasStations.get(rear).getLitres() + gasSavedSoFar;
            int currentDistance = gasStations.get(rear).getDistance();
            gasSavedSoFar = currentPetrol - currentDistance;
            statationsCovered = statationsCovered + 1;
            
            if (gasSavedSoFar < 0) {
                rear = (rear + 1) % gasStations.size();
                front =  (front + 1) % gasStations.size();
                gasSavedSoFar = 0;
                statationsCovered = 0;
                if (rear == 0) {
                    return -1;
                }
            } else {
                rear = (rear + 1) % gasStations.size();
            }
        }
            
        return front;
    }
}


public class PetrolPumpCircularTourTest {
    
    @Test
    public void test1( ) {
        List<PetrolPumpData> list1 = new ArrayList<PetrolPumpData>();
        list1.add(new PetrolPumpData(4, 6));
        list1.add(new PetrolPumpData(6, 5));
        list1.add(new PetrolPumpData(7, 3));
        list1.add(new PetrolPumpData(4, 5));
        
        assertEquals(1, PetrolPumpCircularTour.startingStations(list1));
    }
    
    @Test
    public void test2() {
        List<PetrolPumpData> list2 = new ArrayList<PetrolPumpData>();
        list2.add(new PetrolPumpData(40, 6));
        list2.add(new PetrolPumpData(6, 5));
        list2.add(new PetrolPumpData(7, 3));
        list2.add(new PetrolPumpData(4, 5));
        
        assertEquals(0, PetrolPumpCircularTour.startingStations(list2));
    }
    
    @Test
    public void test3() {
        List<PetrolPumpData> list3 = new ArrayList<PetrolPumpData>();
        list3.add(new PetrolPumpData(4, 6));
        list3.add(new PetrolPumpData(3, 5));
        list3.add(new PetrolPumpData(70, 3));
        list3.add(new PetrolPumpData(4, 5));
        
        assertEquals(2, PetrolPumpCircularTour.startingStations(list3));
    }
    
    @Test
    public void test4( ) {
        List<PetrolPumpData> list4 = new ArrayList<PetrolPumpData>();
        list4.add(new PetrolPumpData(4, 6));
        list4.add(new PetrolPumpData(3, 5));
        list4.add(new PetrolPumpData(2, 3));
        list4.add(new PetrolPumpData(40, 5));
        
        assertEquals(3, PetrolPumpCircularTour.startingStations(list4));
    }
}
\$\endgroup\$

2 Answers 2

1
\$\begingroup\$

Can you prove the algorithm works? It really looks suspicious. Besides, running it against a

{4,6}, {6,5}, {1,3}, {7,3}, {4,5}

test case returns 2. (Hint: the correct algorithm is much simpler).

\$\endgroup\$
1
\$\begingroup\$

At first look, this seems to be an exercise in using the remainder/modulus operator

We have a circular list of details that we need to evaluate the list starting at different points along it.

We can evaluate a list as a circular list by using the remainder % operator like this

for(int index = 0; index < allStations.length; index++){
    int currentStation = allStations[(index + startingPoint) % allStations.length];
// do something with the current station
}

Note: I am using an array for the list rather than a List for ease.

The solution should be a moving window along the circular list. For each starting point (0 => allStations.length), check if this is a valid route. If it is, return the starting point. A route is valid, if the cumulative fuel balance is not negative.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.