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

Truck Tour

  • driftwood + 1 comment

    C++ USERS

    This problem can be completed in O(N) (linear) time complexity using std::queue<type>; if you've not utilized queue when solving the problem, you've not been successful (mind the category that the problem is in...)

    HINTS:

    • - You require only the standard constructor class of std::queue<type>

    • - O(N) is possible; you must only iterate through the queue<type> once

    • - Mind the size of input variables; set type accordingly

    • - queue<type>'s type must make use of std::pair<type,type>

    • GrahamS + 1 comment

      I used a <vector> rather than a <queue>, and then just wrapped the index around to make it a circular queue. Still a "queue-based solution" but a bit more efficient than repeatedly pushing and popping elements.

      struct Pump {
    int fuel;
    int distanceToNext;
    Pump(int f,int d) : fuel(f), distanceToNext(d) {}
};

bool getTruckin (vector<Pump>& pumps, int startPump) {
    int fuelInTank = 0;
    int currentPump = startPump;
    
    while (true) {
        fuelInTank += pumps[currentPump].fuel; // Fill her up
        
        if (fuelInTank < pumps[currentPump].distanceToNext) {
            // Not enough fuel to reach next pump
            return false; 
        } else {
            int nextPump = (currentPump + 1) % pumps.size();
            if (nextPump == startPump) {
                return true; // Completed loop
            } else {
                fuelInTank -= pumps[currentPump].distanceToNext;
                currentPump = nextPump; // Keep on truckin
            }
        }
    }
}
      • jyotsanamall12 + 0 comments

        hey i used queues too...but i am getting a wrong answer for test cases in which n= 100000. where is this code going wrong. please help!

        void queue :: circle()
{
    node *now= front;
    int Pleft= 0, c= 0, index= 0;
    node *temp= now, *ptr= now;
    while(temp->next != now)
    {
        
        Pleft+= temp->petrol;
        //cout<<"pleft: "<<Pleft<<" distance: "<<temp->dist<<endl;
        if(Pleft < temp->dist)
        {
            temp= ptr->next;
            now= temp;
            ptr= temp;
            Pleft= 0;
            c= 0;
        }
        else
        {
            c++;
            if(c == 1)
            {
                ptr= temp;
                index= temp->petrol;
            }   
            Pleft-= temp->dist;
           // cout<<"in else pleft: "<<Pleft<<endl;
            temp= temp->next;
        }
    }
    int flag= 0;
    while(front->next != front)
    {
        if(index == front->petrol)
        {
            cout<<flag<<endl;
            break;
        }
        flag++;
        front= front->next;
    }
}