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.
  1. Prepare
  2. Data Structures
  3. Queues
  4. Truck Tour
  5. Discussions

Truck Tour

Sort by

recency

|

366 Discussions

|

  • hideki_ryuga_pe1
     + 0 comments

    Save the previous circle you already calculated, in a way you can speed it up via memoization. After each pump you can add that pump's total cost to the cost of the pumps before it. Using this strategy you will never have to recalclate the beginning of the loop.

    There's probably other ways to optimize it, but I got lazy after memoizing the beginning part of the loop. This way you never have to worry about trying to loop back your array around.

  • yogesh_bl_mysore
     + 0 comments

    Im getting an error with this:int fuel = 0; int miles = 0; int index = 0; for (int i = 0; i < petrolpumps.size(); i++) { fuel += petrolpumps.get(i).get(0); miles += petrolpumps.get(i).get(1); if (fuel < miles) { fuel = 0; miles = 0; index = i + 1; } } return index; However if I change the inequality to this "if (fuel - miles < 0)" ,it is passing all the test cases. They are both supposed to be the same according to linear inequalities. This is math defying. Please help.

  • jakubsliwice
     + 0 comments
    def truckTour(petrolpumps):
    ln = len(petrolpumps)
    
    petrolpumps = [x - y for x, y in petrolpumps]
    
    for i in range(ln):
        sm = 0
        for j in range(ln):
            sm += petrolpumps[(i + j) % ln]
            if sm < 0:
                break
        else:
            return i
    return -1

  • al_bayona
     + 0 comments

    The problem is misleading, as it does not crearly states that there will always be a solution. You are led to believe to check if you go the full circle. You usually are taught to think of all scenarios, including no solution. So this was a very vague problem description. Finally, I was able to do it by using a prefix list in O(n) time, by using tabulation to optimize checking all the posible circles. 

    def truckTour(petrolpumps):
    _prefix = [ x[0] - x[1] for x in petrolpumps]
    _min = [0] * len(_prefix)
    _min2 = [0] * len(_prefix)

    print(_prefix)

    for i in range(1, len(_prefix)):
        _prefix[i] += _prefix[i-1]

    for i in range(len(_prefix)):
        if i == 0:
            _min[-(i+1)] = _prefix[-(i+1)]
            _min2[i] = _prefix[i]
        else:
            _min[-(i+1)] = min(_min[-i], _prefix[-(i+1)])
            _min2[i] = min(_min2[i-1], _prefix[i])

    # print(_prefix)
    # print(_min)
    # print(_min2)



    if _min[0] > 0:
        return 0

    for i, n in enumerate(_prefix):
        if i > 0:
            if _min[i] - _prefix[i-1] > 0 and _min2[i] + _prefix[-1] - _prefix[i-1] > 0:
                print(i)
                return i

  • manceraaxel
     + 0 comments
    def truckTour(petrol_pumps):
    start_index = 0
    total_liters = 0
    total_distance = 0

    for i in range(len(petrol_pumps)):
        liters, distance = petrol_pumps[i]
        total_liters += liters
        total_distance += distance
        # Arriving to next petrol pump

        if total_liters - total_distance < 0:
            # Initialize start index before restarting in start index
            start_index = i + 1
            total_liters = 0
            total_distance = 0
    
    return start_index