Microsoft Interview Question
Software Engineer / Developers1 Assume that the gas tank in our mode of transport has unlimited capacity.
2 Initially, the gas tank in our mode of transport is empty.
3 start from the city where (d_i - P_i) is maximum
4 Fill gas at every station
You do not know how much petrol is there in each tank to compute your formula....
Start from any arbitrary node and go in one direction. say left... then keep going by refueling the tank at each gas bunk.. If your car runs out of gas... then start from the next gas station but store the gas station in a global queue or sthg too...keep doing this unless you either come back to the original station in which case you found the solution or u run out of gas after the gas station which is already present in the global queue. If that happens, then start your solution in the other direction. and i think all this should be done using recursion and backtracking...
Solution 1:
1) First, we have to start from a station where p_i >= d_i. Find all such i's, put them in a list L.
2) For each station i in L, check if a series of conditions are satisfied: (p_i-d_i) + p_i+1 >= d_i+1, (p_i-d_i)+(p_i+1 - d_i+1) + p_i+2 >= d_i+2, ..., until it circles back to i. The first i satisfies these conditions is the station we are looking for.
3) the running time is about O(n^2)
Solution 2:
1) Find the station i with the largest gap between the fuel and distance, i.e., (p_i - d_i) is the minimum.
2) go through the circle on the reverse direction, i.e., i -> i-1 -> i-2, ..., sum up all (p_i - d_i) along the road, until the sum becomes positive, let's the sum is S >= 0. Suppose the path length is L.
3) now the above path can be viewed as a new station i', with (p_i' - d_i') = S. The problem is reduced to a smaller problem with n - L + 1 nodes
4) The running time is roughly O(nlogn)
I did not get your 2nd solution. Your first solution also looks complicated. There is a simpler O(n^2) solution:
1. Find difference between petrol and distance (i.e. p_i - d_i) of all stations
2. For each positive number as starting bunk, sum the differences of n stations.
2.a. If at any point the sum becomes less than zero, start over with the next positive number
2.b. If the sum becomes zero when the last difference is added, we got the starting stations
Step 2 has complexity O(n^2)
hey...can be done n O(n) time..using circular link list
1.find the diff betwn p and d for each bunk...O(n)
2.start from any bunk..curr=start->next...sum=start->diff
if(sum<0)then start=curr;curr=curr->next;sum=start->diff;
else sum+=curr->diff...curr=curr->next;
3.cout<<start->d<<start->p..
Can be done in O(n).
1)construct 2n size array which hold the bunks start from anywhere twice, for example, bi,b(i+1).....b(i+n-1);bi,b(i+1).....b(i+n-1)
2)Now construct another 2n size array R to hold R[k]=R[k-1]+petrolatbunk[k]-distance[k-1,k]
3)Finally, you will find R[i]=R[i+n], then that is it.
#include<iostream>
#define MAX 10
using namespace std;
void optimize(int n, int p[], int d[]){
int start=0, end, sumdis=0, sumpetrol=0;
int clockstart=0;
bool firstTry=true;
int travel=start;
while(clockstart!=start || firstTry==true){
//cout<<travel<<" ";
sumdis+=d[travel];
sumpetrol+=p[travel];
//to check if there is sufficient petrol to travel further
if(sumpetrol<sumdis){
if(firstTry==true)firstTry=false;
if(travel < n-1)
start=travel+1;
else
start=0;
travel=start;sumdis=0;sumpetrol=0;//clockstart=start;firstTry=true;
cout<<endl;
continue;
}
// to implement circular nature in array
if(travel < n-1)
travel=travel+1;
else
travel=0;
if(travel==start){
cout<<"Success";
cout<<"\n"<<"Start->"<<start+1<<" End-->"<<travel;
return;
}
}
cout<<"\n"<<"failure";
}
int main(){
int n, p[MAX],d[MAX];
cout<<"Input NO. of Petrol Pumps-->";
cin>>n;
cout<<endl<<"Enter Petrol -->";
for(int i=0;i<n;i++)
cin>>p[i];
cout<<endl<<"Enter Distance -->";
for(int i=0;i<n;i++)
cin>>d[i];
optimize(n,p,d);
system("PAUSE");
return 0;
}
list<int> findStartPoints(int* petrols , int* distances, int noOfPumps)
{
print("petrols are : \t", petrols, noOfPumps);
print("distances are : \t",distances,noOfPumps);
list<int> validStartPoints;
// find the complete paths validity
// i.e. before reaching any station j the sum of petrols till that point should be more than or equal to the distance covered till that
// let x be the start point p[x] + p[x+1] ... + p[j-1] >= d[x] + d[x+1] + ..... d[j-1]
// where x < j <= (x-1) such that if x > noOfPumps then x resets to 1
for( int pumpId = 0 ; pumpId < noOfPumps ; pumpId++ )
{
cout << "checking for start point : " << pumpId << endl;
int pv = 0 ;
int distance = 0;
int i;
cout << "The last pump would be : " << (pumpId + noOfPumps - 1) % noOfPumps << endl ;
for( i = pumpId ; i != (pumpId + noOfPumps - 1) % noOfPumps ; i = (i + 1) % noOfPumps )
{
pv += petrols[i];
distance += distances[i];
cout << "from " << i << " to " << (i + 1) % noOfPumps << " petrol = " << pv << " and distance = " << distance << endl;
if( pv < distance )
break;
}
if( i == ( (pumpId + noOfPumps - 1) % noOfPumps ) )
{
cout << "So this is a valid start point.\n" ;
validStartPoints.push_back(pumpId);
}
else
cout << "This is not a valid start point \n";
}
return validStartPoints;
}
Hi
Actual answer for this question is no need to do the calculation,
the condition is it is a circular linked list,
Do the following steps.
1. Group the nodes while huge fuel available, medium fuel available, less fuel is available, and finally no fuel is available,
I think hardly it will take 4 to 5 groups.
2. start from heavy fuel available nodes, and traverse towards the next medium or less fuel valuable states,
3. suppose medium fuel group is behind heavy fuel group start from medium fuel nodes,
4. suppose less fuel is behind the heavy fuel and medium fuel is ahead of the heavy fuel do the mind calculation is the fuel in less fuel group sufficient to travel and reach the heavy fuel grip, if not start from the heavy fuel group.
5. like this you have to decide and finally travel to no fuel group or very less fuel group. this is the logic behind this puzzle.
Further use the below logic
1.
struct node {
struct node *next;
int liter_petrol;
int distance;
};
find the node()
{
int petrolarray[numberofnodes];
int distancearray[numberofnodes];
struct node * traverse = node1_ptr;
int i = 0;
while ( traverse->next != node1_ptr) {
petrolarray[i] = liter_petrol;
distancearray[i] = distance;
i++;
}
for ( i = 0; i < numberofnodes; i++) {
printf ("node = %d\t volumeofpetrol = %d\t distance = %d\n",
i, petrolarray[i], distancearray[i] );
}
printf ("Now decide where to start based on the output\n");
}
Further use the below logic
1.
struct node {
struct node *next;
int liter_petrol;
int distance;
};
find the node()
{
int petrolarray[numberofnodes];
int distancearray[numberofnodes];
struct node * traverse = node1_ptr;
int i = 0;
while ( traverse->next != node1_ptr) {
petrolarray[i] =traverse-> liter_petrol;
distancearray[i] =traverse-> distance;
traverse = traverse->next;
i++;
}
for ( i = 0; i < numberofnodes; i++) {
printf ("node = %d\t volumeofpetrol = %d\t distance = %d\n",
i, petrolarray[i], distancearray[i] );
}
printf ("Now decide where to start based on the output\n");
}
Check this algo and reply back if you face any issues.
- marutikutre June 07, 2013public class AlgoPetrolDistance{
public static void main(String[] args){
Random random = new Random();
List myPetrolPumpsList = new ArrayList<PetrolPump>();
for(int i = 0; i < 6; i++){
myPetrolPumpsList.add(new PetrolPump(random.nextInt(20), random.nextInt(20)));
}
System.out.println("list " + myPetrolPumpsList);
//For finding out first possible route to all destinations in circle with given conditions
int startPoint = solution_1(myPetrolPumpsList);
if(startPoint == -1){
System.out.println("There is no possible startPoint to visit all Petrol pumps/destinations");
}else{
System.out.println("startPoint to reach all nodes is " + (startPoint + 1));
}
//For findint out whether its possible to reach all points starting from each node
for(int i = 0; i < 6; i++){
int result = possibleStartPointsToCoverDistance(myPetrolPumpsList, i);
if(result ==-1){
System.out.println("There is no possible route from " + i);
}else{
System.out.println(" There is possiblity to cover all Points if user starts from " + i);
}
}
}
static int solution_1(List<PetrolPump> myPetrolPumpsList){
int start = 0;
int petrolsum = 0;
int distancesum = 0;
int index = 0;
int nodesVisited = 0;
int totalNodesVisited = 0;
int size = myPetrolPumpsList.size();
//max no of iterations are limited to 2n if all nodes are visited before 2*n iterations then it will break.
while(nodesVisited != size && totalNodesVisited != 2 * size)
{
petrolsum += myPetrolPumpsList.get(index).mMaxPetrolLimit;
distancesum += myPetrolPumpsList.get(index).mDistanceToNextPump;
totalNodesVisited++;
nodesVisited++;
//Total of petrol is not enough to cover the distance then start from next node
if(petrolsum < distancesum)
{
petrolsum = 0;
nodesVisited = 0;
distancesum = 0;
start = index + 1;
}
System.out.println(" Nodes visited " + nodesVisited);
index = (index + 1) % size;
}
//To return if all nodes are not reachable
if(nodesVisited != size){
return -1;
}
// Return starting point
return start;
}
static int possibleStartPointsToCoverDistance(List<PetrolPump> myPetrolPumpsList, int startNode){
int petrolsum = 0;
int distancesum = 0;
int index = startNode;
int nodesVisited = 0;
int totalNodesVisited = 0;
int size = myPetrolPumpsList.size();
//max no of iterations are limited to 2n if all nodes are visited before 2*n iterations then it will break.
while(nodesVisited != size && totalNodesVisited != size)
{
petrolsum += myPetrolPumpsList.get(index).mMaxPetrolLimit;
distancesum += myPetrolPumpsList.get(index).mDistanceToNextPump;
totalNodesVisited++;
nodesVisited++;
//Total of petrol is not enough to cover the distance to next point then return -1 to indicates its not possible
if(petrolsum < distancesum)
{
return -1;
}
index = (index + 1) % size;
}
//To return if all nodes are not reachable
if(nodesVisited != size){
return -1;
}
// Return starting point
return startNode;
}
}
POJO to keep information about each petrol pump(amount of petrol can be filled at this pump and distance to next pump)
public class PetrolPump{
int mMaxPetrolLimit;
int mDistanceToNextPump;
/**
* @param maxPetrolLimit
* @param distanceToNextPump
*/
public PetrolPump(int maxPetrolLimit, int distanceToNextPump){
super();
mMaxPetrolLimit = maxPetrolLimit;
mDistanceToNextPump = distanceToNextPump;
}
/**
* @return the maxPetrolLimit
*/
public int getMaxPetrolLimit(){
return mMaxPetrolLimit;
}
/**
* @param maxPetrolLimit the maxPetrolLimit to set
*/
public void setMaxPetrolLimit(final int maxPetrolLimit){
mMaxPetrolLimit = maxPetrolLimit;
}
/**
* @return the distanceToNextPump
*/
public int getDistanceToNextPump(){
return mDistanceToNextPump;
}
/**
* @param distanceToNextPump the distanceToNextPump to set
*/
public void setDistanceToNextPump(final int distanceToNextPump){
mDistanceToNextPump = distanceToNextPump;
}
/*
* (non-Javadoc)
*
* @see java.lang.Object#toString()
*/
@Override
public String toString(){
return "[" + mMaxPetrolLimit + " " + mDistanceToNextPump + "]";
}
}